algebraic-graphs 0.0.1 → 0.0.2
raw patch · 19 files changed
+239/−222 lines, 19 filesPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
API changes (from Hackage documentation)
- Algebra.Graph.Fold: box :: (Graph g, Vertex g ~ (u, v)) => Fold u -> Fold v -> g
+ Algebra.Graph.Fold: box :: (Graph g, Vertex g ~ (a, b)) => Fold a -> Fold b -> g
Files
- README.md +1/−1
- algebraic-graphs.cabal +22/−11
- src/Algebra/Graph.hs +13/−12
- src/Algebra/Graph/AdjacencyMap.hs +2/−2
- src/Algebra/Graph/AdjacencyMap/Internal.hs +42/−42
- src/Algebra/Graph/Class.hs +1/−1
- src/Algebra/Graph/Fold.hs +14/−13
- src/Algebra/Graph/HigherKinded/Class.hs +9/−10
- src/Algebra/Graph/IntAdjacencyMap.hs +4/−4
- src/Algebra/Graph/IntAdjacencyMap/Internal.hs +42/−42
- src/Algebra/Graph/Relation.hs +1/−1
- src/Algebra/Graph/Relation/Internal.hs +51/−51
- src/Algebra/Graph/Relation/Preorder.hs +1/−2
- src/Algebra/Graph/Relation/Symmetric.hs +1/−1
- src/Algebra/Graph/Relation/Transitive.hs +1/−1
- test/Algebra/Graph/Test/AdjacencyMap.hs +2/−2
- test/Algebra/Graph/Test/Fold.hs +15/−12
- test/Algebra/Graph/Test/Graph.hs +15/−12
- test/Algebra/Graph/Test/IntAdjacencyMap.hs +2/−2
README.md view
@@ -1,6 +1,6 @@ # Algebraic graphs -[](https://travis-ci.org/snowleopard/alga) [](https://ci.appveyor.com/project/snowleopard/alga)+[](https://hackage.haskell.org/package/algebraic-graphs) [](https://travis-ci.org/snowleopard/alga) [](https://ci.appveyor.com/project/snowleopard/alga) A library for algebraic construction and manipulation of graphs in Haskell. See [this paper](https://github.com/snowleopard/alga-paper) for the motivation behind the library, the underlying
algebraic-graphs.cabal view
@@ -1,5 +1,5 @@ name: algebraic-graphs-version: 0.0.1+version: 0.0.2 synopsis: A library for algebraic graph construction and transformation license: MIT license-file: LICENSE@@ -11,23 +11,34 @@ build-type: Simple cabal-version: >=1.10 tested-with: GHC==8.0.2+stability: experimental description:- A library for algebraic construction and manipulation of graphs in Haskell. See+ __Alga__ is a library for algebraic construction and manipulation of graphs in Haskell. See <https://github.com/snowleopard/alga-paper this paper> for the motivation behind the library, the underlying theory and implementation details. .- The top-level module "Algebra.Graph" defines the core data type 'Algebra.Graph.Graph'- which is a deep embedding of four graph construction primitives 'Algebra.Graph.empty',- 'Algebra.Graph.vertex', 'Algebra.Graph.overlay' and 'Algebra.Graph.connect'. More- conventional graph representations can be found in "Algebra.Graph.AdjacencyMap" and- "Algebra.Graph.Relation".+ The top-level module+ <http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph.html Algebra.Graph>+ defines the core data type+ <http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph.html#t:Graph Graph>.+ which is a deep embedding of four graph construction primitives /empty/,+ /vertex/, /overlay/ and /connect/. More conventional graph representations can be found+ <http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-AdjacencyMap.html Algebra.Graph.AdjacencyMap>+ and+ <http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-Relation.html Algebra.Graph.Relation>. .- The type classes defined in "Algebra.Graph.Class" and "Algebra.Graph.HigherKinded.Class"+ The type classes defined in+ <http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-Class.html Algebra.Graph.Class>+ and+ <http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-HigherKinded-Class.html Algebra.Graph.HigherKinded.Class> can be used for polymorphic graph construction and manipulation. Also see- "Algebra.Graph.Fold" that defines the Boehm-Berarducci encoding of algebraic graphs and- provides additional flexibility for polymorphic graph manipulation.+ <http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-Fold.html Algebra.Graph.Fold>+ that defines the Boehm-Berarducci encoding of algebraic graphs and provides additional+ flexibility for polymorphic graph manipulation. .- This is an experimental library and the API will be unstable until version 1.0.0.+ This is an experimental library and the API will be unstable until version 1.0.0. Please+ consider contributing to the on-going discussions on the library API at+ https://github.com/snowleopard/alga/issues. extra-doc-files: README.md
src/Algebra/Graph.hs view
@@ -67,7 +67,7 @@ > 1 + 2 * 3 == Overlay (Vertex 1) (Connect (Vertex 2) (Vertex 3)) > 1 * (2 + 3) == Connect (Vertex 1) (Overlay (Vertex 2) (Vertex 3)) -The 'Eq' instance is currently implemented using the 'AdjacencyMap' as the+The 'Eq' instance is currently implemented using the 'AM.AdjacencyMap' as the /canonical graph representation/ and satisfies all axioms of algebraic graphs: * 'overlay' is commutative and associative:@@ -409,6 +409,7 @@ -- size ('overlay' x y) == size x + size y -- size ('connect' x y) == size x + size y -- size x >= 1+-- size x >= 'vertexCount' x -- @ size :: Graph a -> Int size = foldg 1 (const 1) (+) (+)@@ -616,12 +617,12 @@ -- lengths of the given lists. -- -- @--- torus xs [] == 'empty'--- torus [] ys == 'empty'--- torus [x] [y] == 'edge' (x, y) (x, y)--- torus xs ys == 'box' ('circuit' xs) ('circuit' ys)--- torus [1..2] "ab" == 'edges' [ ((1,\'a\'),(1,\'b\')), ((1,\'a\'),(2,\'a\')), ((1,\'b\'),(1,\'a\')), ((1,\'b\'),(2,\'b\'))--- , ((2,\'a\'),(1,\'a\')), ((2,\'a\'),(2,\'b\')), ((2,\'b\'),(1,\'b\')), ((2,\'b\'),(2,\'a\')) ]+-- torus xs [] == 'empty'+-- torus [] ys == 'empty'+-- torus [x] [y] == 'edge' (x, y) (x, y)+-- torus xs ys == 'box' ('circuit' xs) ('circuit' ys)+-- torus [1,2] "ab" == 'edges' [ ((1,\'a\'),(1,\'b\')), ((1,\'a\'),(2,\'a\')), ((1,\'b\'),(1,\'a\')), ((1,\'b\'),(2,\'b\'))+-- , ((2,\'a\'),(1,\'a\')), ((2,\'a\'),(2,\'b\')), ((2,\'b\'),(1,\'b\')), ((2,\'b\'),(2,\'a\')) ] -- @ torus :: [a] -> [b] -> Graph (a, b) torus = H.torus@@ -692,7 +693,7 @@ | intact sx || intact ty = C.connect x y | otherwise = (C.connect sx sy, C.connect tx ty, C.connect sx sty `C.overlay` C.connect stx ty) --- | The function @replaceVertex x y@ replaces vertex @x@ with vertex @y@ in a+-- | The function @'replaceVertex' x y@ replaces vertex @x@ with vertex @y@ in a -- given 'Graph'. If @y@ already exists, @x@ and @y@ will be merged. -- Complexity: /O(s)/ time, memory and size. --@@ -758,15 +759,15 @@ induce :: (a -> Bool) -> Graph a -> Graph a induce = H.induce --- | Simplify a given graph. Semantically, this is the identity function, but--- it simplifies a given polymorphic graph expression according to the laws of--- the algebra. The function does not compute the simplest possible expression,+-- | Simplify a graph expression. Semantically, this is the identity function,+-- but it simplifies a given expression according to the laws of the algebra.+-- The function does not compute the simplest possible expression, -- but uses heuristics to obtain useful simplifications in reasonable time. -- Complexity: the function performs /O(s)/ graph comparisons. It is guaranteed -- that the size of the result does not exceed the size of the given expression. -- -- @--- simplify x == x+-- simplify == id -- 'size' (simplify x) <= 'size' x -- simplify 'empty' '===' 'empty' -- simplify 1 '===' 1
src/Algebra/Graph/AdjacencyMap.hs view
@@ -295,7 +295,7 @@ forest :: Ord a => Forest a -> AdjacencyMap a forest = C.forest --- | The function @replaceVertex x y@ replaces vertex @x@ with vertex @y@ in a+-- | The function @'replaceVertex' x y@ replaces vertex @x@ with vertex @y@ in a -- given 'AdjacencyMap'. If @y@ already exists, @x@ and @y@ will be merged. -- Complexity: /O((n + m) * log(n))/ time. --@@ -325,7 +325,7 @@ -- the following holds: -- -- @--- map ('getVertex' h) ('Data.Graph.vertices' $ 'getGraph' h) == Set.toAscList ('vertexSet' g)+-- map ('getVertex' h) ('Data.Graph.vertices' $ 'getGraph' h) == Set.'Set.toAscList' ('vertexSet' g) -- map (\\(x, y) -> ('getVertex' h x, 'getVertex' h y)) ('Data.Graph.edges' $ 'getGraph' h) == 'edgeList' g -- @ data GraphKL a = GraphKL {
src/Algebra/Graph/AdjacencyMap/Internal.hs view
@@ -134,9 +134,9 @@ -- consistent ('vertex' x) == True -- consistent ('overlay' x y) == True -- consistent ('connect' x y) == True--- consistent ('AdjacencyMap.edge' x y) == True+-- consistent ('Algebra.Graph.AdjacencyMap.edge' x y) == True -- consistent ('edges' xs) == True--- consistent ('AdjacencyMap.graph' xs ys) == True+-- consistent ('Algebra.Graph.AdjacencyMap.graph' xs ys) == True -- consistent ('fromAdjacencyList' xs) == True -- @ consistent :: Ord a => AdjacencyMap a -> Bool@@ -147,10 +147,10 @@ -- Complexity: /O(1)/ time and memory. -- -- @--- 'AdjacencyMap.isEmpty' empty == True--- 'AdjacencyMap.hasVertex' x empty == False--- 'AdjacencyMap.vertexCount' empty == 0--- 'AdjacencyMap.edgeCount' empty == 0+-- 'Algebra.Graph.AdjacencyMap.isEmpty' empty == True+-- 'Algebra.Graph.AdjacencyMap.hasVertex' x empty == False+-- 'Algebra.Graph.AdjacencyMap.vertexCount' empty == 0+-- 'Algebra.Graph.AdjacencyMap.edgeCount' empty == 0 -- @ empty :: AdjacencyMap a empty = AdjacencyMap $ Map.empty@@ -159,11 +159,11 @@ -- Complexity: /O(1)/ time and memory. -- -- @--- 'AdjacencyMap.isEmpty' (vertex x) == False--- 'AdjacencyMap.hasVertex' x (vertex x) == True--- 'AdjacencyMap.hasVertex' 1 (vertex 2) == False--- 'AdjacencyMap.vertexCount' (vertex x) == 1--- 'AdjacencyMap.edgeCount' (vertex x) == 0+-- 'Algebra.Graph.AdjacencyMap.isEmpty' (vertex x) == False+-- 'Algebra.Graph.AdjacencyMap.hasVertex' x (vertex x) == True+-- 'Algebra.Graph.AdjacencyMap.hasVertex' 1 (vertex 2) == False+-- 'Algebra.Graph.AdjacencyMap.vertexCount' (vertex x) == 1+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (vertex x) == 0 -- @ vertex :: a -> AdjacencyMap a vertex x = AdjacencyMap $ Map.singleton x Set.empty@@ -173,14 +173,14 @@ -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory. -- -- @--- 'AdjacencyMap.isEmpty' (overlay x y) == 'AdjacencyMap.isEmpty' x && 'AdjacencyMap.isEmpty' y--- 'AdjacencyMap.hasVertex' z (overlay x y) == 'AdjacencyMap.hasVertex' z x || 'AdjacencyMap.hasVertex' z y--- 'AdjacencyMap.vertexCount' (overlay x y) >= 'AdjacencyMap.vertexCount' x--- 'AdjacencyMap.vertexCount' (overlay x y) <= 'AdjacencyMap.vertexCount' x + 'AdjacencyMap.vertexCount' y--- 'AdjacencyMap.edgeCount' (overlay x y) >= 'AdjacencyMap.edgeCount' x--- 'AdjacencyMap.edgeCount' (overlay x y) <= 'AdjacencyMap.edgeCount' x + 'AdjacencyMap.edgeCount' y--- 'AdjacencyMap.vertexCount' (overlay 1 2) == 2--- 'AdjacencyMap.edgeCount' (overlay 1 2) == 0+-- 'Algebra.Graph.AdjacencyMap.isEmpty' (overlay x y) == 'Algebra.Graph.AdjacencyMap.isEmpty' x && 'Algebra.Graph.AdjacencyMap.isEmpty' y+-- 'Algebra.Graph.AdjacencyMap.hasVertex' z (overlay x y) == 'Algebra.Graph.AdjacencyMap.hasVertex' z x || 'Algebra.Graph.AdjacencyMap.hasVertex' z y+-- 'Algebra.Graph.AdjacencyMap.vertexCount' (overlay x y) >= 'Algebra.Graph.AdjacencyMap.vertexCount' x+-- 'Algebra.Graph.AdjacencyMap.vertexCount' (overlay x y) <= 'Algebra.Graph.AdjacencyMap.vertexCount' x + 'Algebra.Graph.AdjacencyMap.vertexCount' y+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (overlay x y) >= 'Algebra.Graph.AdjacencyMap.edgeCount' x+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (overlay x y) <= 'Algebra.Graph.AdjacencyMap.edgeCount' x + 'Algebra.Graph.AdjacencyMap.edgeCount' y+-- 'Algebra.Graph.AdjacencyMap.vertexCount' (overlay 1 2) == 2+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (overlay 1 2) == 0 -- @ overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a overlay x y = AdjacencyMap $ Map.unionWith Set.union (adjacencyMap x) (adjacencyMap y)@@ -192,16 +192,16 @@ -- of vertices of the arguments: /m = O(m1 + m2 + n1 * n2)/. -- -- @--- 'AdjacencyMap.isEmpty' (connect x y) == 'AdjacencyMap.isEmpty' x && 'AdjacencyMap.isEmpty' y--- 'AdjacencyMap.hasVertex' z (connect x y) == 'AdjacencyMap.hasVertex' z x || 'AdjacencyMap.hasVertex' z y--- 'AdjacencyMap.vertexCount' (connect x y) >= 'AdjacencyMap.vertexCount' x--- 'AdjacencyMap.vertexCount' (connect x y) <= 'AdjacencyMap.vertexCount' x + 'AdjacencyMap.vertexCount' y--- 'AdjacencyMap.edgeCount' (connect x y) >= 'AdjacencyMap.edgeCount' x--- 'AdjacencyMap.edgeCount' (connect x y) >= 'AdjacencyMap.edgeCount' y--- 'AdjacencyMap.edgeCount' (connect x y) >= 'AdjacencyMap.vertexCount' x * 'AdjacencyMap.vertexCount' y--- 'AdjacencyMap.edgeCount' (connect x y) <= 'AdjacencyMap.vertexCount' x * 'AdjacencyMap.vertexCount' y + 'AdjacencyMap.edgeCount' x + 'AdjacencyMap.edgeCount' y--- 'AdjacencyMap.vertexCount' (connect 1 2) == 2--- 'AdjacencyMap.edgeCount' (connect 1 2) == 1+-- 'Algebra.Graph.AdjacencyMap.isEmpty' (connect x y) == 'Algebra.Graph.AdjacencyMap.isEmpty' x && 'Algebra.Graph.AdjacencyMap.isEmpty' y+-- 'Algebra.Graph.AdjacencyMap.hasVertex' z (connect x y) == 'Algebra.Graph.AdjacencyMap.hasVertex' z x || 'Algebra.Graph.AdjacencyMap.hasVertex' z y+-- 'Algebra.Graph.AdjacencyMap.vertexCount' (connect x y) >= 'Algebra.Graph.AdjacencyMap.vertexCount' x+-- 'Algebra.Graph.AdjacencyMap.vertexCount' (connect x y) <= 'Algebra.Graph.AdjacencyMap.vertexCount' x + 'Algebra.Graph.AdjacencyMap.vertexCount' y+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (connect x y) >= 'Algebra.Graph.AdjacencyMap.edgeCount' x+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (connect x y) >= 'Algebra.Graph.AdjacencyMap.edgeCount' y+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (connect x y) >= 'Algebra.Graph.AdjacencyMap.vertexCount' x * 'Algebra.Graph.AdjacencyMap.vertexCount' y+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (connect x y) <= 'Algebra.Graph.AdjacencyMap.vertexCount' x * 'Algebra.Graph.AdjacencyMap.vertexCount' y + 'Algebra.Graph.AdjacencyMap.edgeCount' x + 'Algebra.Graph.AdjacencyMap.edgeCount' y+-- 'Algebra.Graph.AdjacencyMap.vertexCount' (connect 1 2) == 2+-- 'Algebra.Graph.AdjacencyMap.edgeCount' (connect 1 2) == 1 -- @ connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a connect x y = AdjacencyMap $ Map.unionsWith Set.union [ adjacencyMap x, adjacencyMap y,@@ -214,9 +214,9 @@ -- @ -- vertices [] == 'empty' -- vertices [x] == 'vertex' x--- 'AdjacencyMap.hasVertex' x . vertices == 'elem' x--- 'AdjacencyMap.vertexCount' . vertices == 'length' . 'Data.List.nub'--- 'AdjacencyMap.vertexSet' . vertices == Set.'Set.fromList'+-- 'Algebra.Graph.AdjacencyMap.hasVertex' x . vertices == 'elem' x+-- 'Algebra.Graph.AdjacencyMap.vertexCount' . vertices == 'length' . 'Data.List.nub'+-- 'Algebra.Graph.AdjacencyMap.vertexSet' . vertices == Set.'Set.fromList' -- @ vertices :: Ord a => [a] -> AdjacencyMap a vertices = AdjacencyMap . Map.fromList . map (\x -> (x, Set.empty))@@ -226,8 +226,8 @@ -- -- @ -- edges [] == 'empty'--- edges [(x, y)] == 'AdjacencyMap.edge' x y--- 'AdjacencyMap.edgeCount' . edges == 'length' . 'Data.List.nub'+-- edges [(x, y)] == 'Algebra.Graph.AdjacencyMap.edge' x y+-- 'Algebra.Graph.AdjacencyMap.edgeCount' . edges == 'length' . 'Data.List.nub' -- 'edgeList' . edges == 'Data.List.nub' . 'Data.List.sort' -- @ edges :: Ord a => [(a, a)] -> AdjacencyMap a@@ -239,7 +239,7 @@ -- @ -- fromAdjacencyList [] == 'empty' -- fromAdjacencyList [(x, [])] == 'vertex' x--- fromAdjacencyList [(x, [y])] == 'AdjacencyMap.edge' x y+-- fromAdjacencyList [(x, [y])] == 'Algebra.Graph.AdjacencyMap.edge' x y -- fromAdjacencyList . 'adjacencyList' == id -- 'overlay' (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys) -- @@@ -256,8 +256,8 @@ -- @ -- edgeList 'empty' == [] -- edgeList ('vertex' x) == []--- edgeList ('AdjacencyMap.edge' x y) == [(x,y)]--- edgeList ('AdjacencyMap.star' 2 [3,1]) == [(2,1), (2,3)]+-- edgeList ('Algebra.Graph.AdjacencyMap.edge' x y) == [(x,y)]+-- edgeList ('Algebra.Graph.AdjacencyMap.star' 2 [3,1]) == [(2,1), (2,3)] -- edgeList . 'edges' == 'Data.List.nub' . 'Data.List.sort' -- @ edgeList :: AdjacencyMap a -> [(a, a)]@@ -269,8 +269,8 @@ -- @ -- adjacencyList 'empty' == [] -- adjacencyList ('vertex' x) == [(x, [])]--- adjacencyList ('AdjacencyMap.edge' 1 2) == [(1, [2]), (2, [])]--- adjacencyList ('AdjacencyMap.star' 2 [1,3]) == [(1, []), (2, [1,3]), (3, [])]+-- adjacencyList ('Algebra.Graph.AdjacencyMap.edge' 1 2) == [(1, [2]), (2, [])]+-- adjacencyList ('Algebra.Graph.AdjacencyMap.star' 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] -- 'fromAdjacencyList' . adjacencyList == id -- @ adjacencyList :: AdjacencyMap a -> [(a, [a])]@@ -290,7 +290,7 @@ -- Complexity: /O(log(n))/ time. -- -- @--- removeEdge x y ('AdjacencyMap.edge' x y) == 'vertices' [x, y]+-- removeEdge x y ('Algebra.Graph.AdjacencyMap.edge' x y) == 'vertices' [x, y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . 'removeVertex' x == 'removeVertex' x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2@@ -307,7 +307,7 @@ -- @ -- gmap f 'empty' == 'empty' -- gmap f ('vertex' x) == 'vertex' (f x)--- gmap f ('AdjacencyMap.edge' x y) == 'AdjacencyMap.edge' (f x) (f y)+-- gmap f ('Algebra.Graph.AdjacencyMap.edge' x y) == 'Algebra.Graph.AdjacencyMap.edge' (f x) (f y) -- gmap id == id -- gmap f . gmap g == gmap (f . g) -- @@@ -324,7 +324,7 @@ -- induce (const False) x == 'empty' -- induce (/= x) == 'removeVertex' x -- induce p . induce q == induce (\\x -> p x && q x)--- 'AdjacencyMap.isSubgraphOf' (induce p x) x == True+-- 'Algebra.Graph.AdjacencyMap.isSubgraphOf' (induce p x) x == True -- @ induce :: Ord a => (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a induce p = AdjacencyMap . Map.map (Set.filter p) . Map.filterWithKey (\k _ -> p k) . adjacencyMap
src/Algebra/Graph/Class.hs view
@@ -289,7 +289,7 @@ -- isSubgraphOf x y = 'overlay' x y == y -- @ -- The complexity therefore depends on the complexity of equality testing of--- a particular graph instance.+-- the specific graph instance. -- -- @ -- isSubgraphOf 'empty' x == True
src/Algebra/Graph/Fold.hs view
@@ -373,6 +373,7 @@ -- size ('overlay' x y) == size x + size y -- size ('connect' x y) == size x + size y -- size x >= 1+-- size x >= 'vertexCount' x -- @ size :: Fold a -> Int size = foldg 1 (const 1) (+) (+)@@ -538,12 +539,12 @@ -- lengths of the given lists. -- -- @--- torus xs [] == 'empty'--- torus [] ys == 'empty'--- torus [x] [y] == 'edge' (x, y) (x, y)--- torus xs ys == 'box' ('circuit' xs) ('circuit' ys)--- torus [1..2] "ab" == 'edges' [ ((1,\'a\'),(1,\'b\')), ((1,\'a\'),(2,\'a\')), ((1,\'b\'),(1,\'a\')), ((1,\'b\'),(2,\'b\'))--- , ((2,\'a\'),(1,\'a\')), ((2,\'a\'),(2,\'b\')), ((2,\'b\'),(1,\'b\')), ((2,\'b\'),(2,\'a\')) ]+-- torus xs [] == 'empty'+-- torus [] ys == 'empty'+-- torus [x] [y] == 'edge' (x, y) (x, y)+-- torus xs ys == 'box' ('circuit' xs) ('circuit' ys)+-- torus [1,2] "ab" == 'edges' [ ((1,\'a\'),(1,\'b\')), ((1,\'a\'),(2,\'a\')), ((1,\'b\'),(1,\'a\')), ((1,\'b\'),(2,\'b\'))+-- , ((2,\'a\'),(1,\'a\')), ((2,\'a\'),(2,\'b\')), ((2,\'b\'),(1,\'b\')), ((2,\'b\'),(2,\'a\')) ] -- @ torus :: (C.Graph g, C.Vertex g ~ (a, b)) => [a] -> [b] -> g torus xs ys = C.circuit xs `box` C.circuit ys@@ -590,8 +591,8 @@ removeEdge :: (Eq (C.Vertex g), C.Graph g) => C.Vertex g -> C.Vertex g -> Fold (C.Vertex g) -> g removeEdge s t g = piece st where (_, _, st) = smash s t g --- | The function @replaceVertex x y@ replaces vertex @x@ with vertex @y@ in a--- given 'Graph'. If @y@ already exists, @x@ and @y@ will be merged.+-- | The function @'replaceVertex' x y@ replaces vertex @x@ with vertex @y@ in a+-- given graph expression. If @y@ already exists, @x@ and @y@ will be merged. -- Complexity: /O(s)/ time, memory and size. -- -- @@@ -685,16 +686,16 @@ induce :: C.Graph g => (C.Vertex g -> Bool) -> Fold (C.Vertex g) -> g induce p g = bind g $ \v -> if p v then C.vertex v else C.empty --- | Simplify a given graph. Semantically, this is the identity function, but--- it simplifies a given polymorphic graph expression according to the laws of--- the algebra. The function does not compute the simplest possible expression,+-- | Simplify a graph expression. Semantically, this is the identity function,+-- but it simplifies a given polymorphic graph expression according to the laws+-- of the algebra. The function does not compute the simplest possible expression, -- but uses heuristics to obtain useful simplifications in reasonable time. -- Complexity: the function performs /O(s)/ graph comparisons. It is guaranteed -- that the size of the result does not exceed the size of the given expression. -- Below the operator @~>@ denotes the /is simplified to/ relation. -- -- @--- simplify x == x+-- simplify == id -- 'size' (simplify x) <= 'size' x -- simplify 'empty' ~> 'empty' -- simplify 1 ~> 1@@ -735,7 +736,7 @@ -- box x ('vertex' ()) ~~ x -- box x 'empty' ~~ 'empty' -- @-box :: (C.Graph g, C.Vertex g ~ (u, v)) => Fold u -> Fold v -> g+box :: (C.Graph g, C.Vertex g ~ (a, b)) => Fold a -> Fold b -> g box x y = C.overlays $ xs ++ ys where xs = map (\b -> gmap (,b) x) $ toList y
src/Algebra/Graph/HigherKinded/Class.hs view
@@ -14,8 +14,7 @@ -- basic polymorphic graph construction primitives. Functions that cannot be -- implemented fully polymorphically and require the use of an intermediate data -- type are not included. For example, to compute the size of a 'Graph'--- expression you will need to use a concrete data type, such as "Algebra.Graph"--- or "Algebra.Graph.Fold".+-- expression you will need to use a concrete data type, such as "Algebra.Graph". -- -- See "Algebra.Graph.Class" for alternative definitions where the core type -- class is not higher-kinded and permits more instances.@@ -264,7 +263,7 @@ -- isSubgraphOf x y = 'overlay' x y == y -- @ -- The complexity therefore depends on the complexity of equality testing of--- a particular graph instance.+-- the specific graph instance. -- -- @ -- isSubgraphOf 'empty' x == True@@ -443,12 +442,12 @@ -- lengths of the given lists. -- -- @--- torus xs [] == 'empty'--- torus [] ys == 'empty'--- torus [x] [y] == 'edge' (x, y) (x, y)--- torus xs ys == 'box' ('circuit' xs) ('circuit' ys)--- torus [1..2] "ab" == 'edges' [ ((1,\'a\'),(1,\'b\')), ((1,\'a\'),(2,\'a\')), ((1,\'b\'),(1,\'a\')), ((1,\'b\'),(2,\'b\'))--- , ((2,\'a\'),(1,\'a\')), ((2,\'a\'),(2,\'b\')), ((2,\'b\'),(1,\'b\')), ((2,\'b\'),(2,\'a\')) ]+-- torus xs [] == 'empty'+-- torus [] ys == 'empty'+-- torus [x] [y] == 'edge' (x, y) (x, y)+-- torus xs ys == 'box' ('circuit' xs) ('circuit' ys)+-- torus [1,2] "ab" == 'edges' [ ((1,\'a\'),(1,\'b\')), ((1,\'a\'),(2,\'a\')), ((1,\'b\'),(1,\'a\')), ((1,\'b\'),(2,\'b\'))+-- , ((2,\'a\'),(1,\'a\')), ((2,\'a\'),(2,\'b\')), ((2,\'b\'),(1,\'b\')), ((2,\'b\'),(2,\'a\')) ] -- @ torus :: Graph g => [a] -> [b] -> g (a, b) torus xs ys = circuit xs `box` circuit ys@@ -497,7 +496,7 @@ removeVertex :: (Eq a, Graph g) => a -> g a -> g a removeVertex v = induce (/= v) --- | The function @replaceVertex x y@ replaces vertex @x@ with vertex @y@ in a+-- | The function @'replaceVertex' x y@ replaces vertex @x@ with vertex @y@ in a -- given 'Graph'. If @y@ already exists, @x@ and @y@ will be merged. -- Complexity: /O(s)/ time, memory and size. --
src/Algebra/Graph/IntAdjacencyMap.hs view
@@ -11,8 +11,8 @@ -- motivation behind the library, the underlying theory, and implementation details. -- -- This module defines the 'IntAdjacencyMap' data type, as well as associated--- operations and algorithms. 'AdjaceIntAdjacencyMapncyMap' is an instance of--- the 'C.Graph' type class, which can be used for polymorphic graph construction+-- operations and algorithms. 'IntAdjacencyMap' is an instance of the 'C.Graph'+-- type class, which can be used for polymorphic graph construction -- and manipulation. See "Algebra.Graph.AdjacencyMap" for graphs with -- non-@Int@ vertices. -----------------------------------------------------------------------------@@ -297,7 +297,7 @@ forest :: Forest Int -> IntAdjacencyMap forest = C.forest --- | The function @replaceVertex x y@ replaces vertex @x@ with vertex @y@ in a+-- | The function @'replaceVertex' x y@ replaces vertex @x@ with vertex @y@ in a -- given 'IntAdjacencyMap'. If @y@ already exists, @x@ and @y@ will be merged. -- Complexity: /O((n + m) * log(n))/ time. --@@ -327,7 +327,7 @@ -- the following holds: -- -- @--- map ('getVertex' h) ('Data.Graph.vertices' $ 'getGraph' h) == IntSet.toAscList ('vertexSet' g)+-- map ('getVertex' h) ('Data.Graph.vertices' $ 'getGraph' h) == IntSet.'IntSet.toAscList' ('vertexSet' g) -- map (\\(x, y) -> ('getVertex' h x, 'getVertex' h y)) ('Data.Graph.edges' $ 'getGraph' h) == 'edgeList' g -- @ data GraphKL = GraphKL {
src/Algebra/Graph/IntAdjacencyMap/Internal.hs view
@@ -134,9 +134,9 @@ -- consistent ('vertex' x) == True -- consistent ('overlay' x y) == True -- consistent ('connect' x y) == True--- consistent ('IntAdjacencyMap.edge' x y) == True+-- consistent ('Algebra.Graph.IntAdjacencyMap.edge' x y) == True -- consistent ('edges' xs) == True--- consistent ('IntAdjacencyMap.graph' xs ys) == True+-- consistent ('Algebra.Graph.IntAdjacencyMap.graph' xs ys) == True -- consistent ('fromAdjacencyList' xs) == True -- @ consistent :: IntAdjacencyMap -> Bool@@ -147,10 +147,10 @@ -- Complexity: /O(1)/ time and memory. -- -- @--- 'IntAdjacencyMap.isEmpty' empty == True--- 'IntAdjacencyMap.hasVertex' x empty == False--- 'IntAdjacencyMap.vertexCount' empty == 0--- 'IntAdjacencyMap.edgeCount' empty == 0+-- 'Algebra.Graph.IntAdjacencyMap.isEmpty' empty == True+-- 'Algebra.Graph.IntAdjacencyMap.hasVertex' x empty == False+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' empty == 0+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' empty == 0 -- @ empty :: IntAdjacencyMap empty = IntAdjacencyMap $ IntMap.empty@@ -159,11 +159,11 @@ -- Complexity: /O(1)/ time and memory. -- -- @--- 'IntAdjacencyMap.isEmpty' (vertex x) == False--- 'IntAdjacencyMap.hasVertex' x (vertex x) == True--- 'IntAdjacencyMap.hasVertex' 1 (vertex 2) == False--- 'IntAdjacencyMap.vertexCount' (vertex x) == 1--- 'IntAdjacencyMap.edgeCount' (vertex x) == 0+-- 'Algebra.Graph.IntAdjacencyMap.isEmpty' (vertex x) == False+-- 'Algebra.Graph.IntAdjacencyMap.hasVertex' x (vertex x) == True+-- 'Algebra.Graph.IntAdjacencyMap.hasVertex' 1 (vertex 2) == False+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' (vertex x) == 1+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (vertex x) == 0 -- @ vertex :: Int -> IntAdjacencyMap vertex x = IntAdjacencyMap $ IntMap.singleton x IntSet.empty@@ -173,14 +173,14 @@ -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory. -- -- @--- 'IntAdjacencyMap.isEmpty' (overlay x y) == 'IntAdjacencyMap.isEmpty' x && 'IntAdjacencyMap.isEmpty' y--- 'IntAdjacencyMap.hasVertex' z (overlay x y) == 'IntAdjacencyMap.hasVertex' z x || 'IntAdjacencyMap.hasVertex' z y--- 'IntAdjacencyMap.vertexCount' (overlay x y) >= 'IntAdjacencyMap.vertexCount' x--- 'IntAdjacencyMap.vertexCount' (overlay x y) <= 'IntAdjacencyMap.vertexCount' x + 'IntAdjacencyMap.vertexCount' y--- 'IntAdjacencyMap.edgeCount' (overlay x y) >= 'IntAdjacencyMap.edgeCount' x--- 'IntAdjacencyMap.edgeCount' (overlay x y) <= 'IntAdjacencyMap.edgeCount' x + 'IntAdjacencyMap.edgeCount' y--- 'IntAdjacencyMap.vertexCount' (overlay 1 2) == 2--- 'IntAdjacencyMap.edgeCount' (overlay 1 2) == 0+-- 'Algebra.Graph.IntAdjacencyMap.isEmpty' (overlay x y) == 'Algebra.Graph.IntAdjacencyMap.isEmpty' x && 'Algebra.Graph.IntAdjacencyMap.isEmpty' y+-- 'Algebra.Graph.IntAdjacencyMap.hasVertex' z (overlay x y) == 'Algebra.Graph.IntAdjacencyMap.hasVertex' z x || 'Algebra.Graph.IntAdjacencyMap.hasVertex' z y+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' (overlay x y) >= 'Algebra.Graph.IntAdjacencyMap.vertexCount' x+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' (overlay x y) <= 'Algebra.Graph.IntAdjacencyMap.vertexCount' x + 'Algebra.Graph.IntAdjacencyMap.vertexCount' y+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (overlay x y) >= 'Algebra.Graph.IntAdjacencyMap.edgeCount' x+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (overlay x y) <= 'Algebra.Graph.IntAdjacencyMap.edgeCount' x + 'Algebra.Graph.IntAdjacencyMap.edgeCount' y+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' (overlay 1 2) == 2+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (overlay 1 2) == 0 -- @ overlay :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap overlay x y = IntAdjacencyMap $ IntMap.unionWith IntSet.union (adjacencyMap x) (adjacencyMap y)@@ -192,16 +192,16 @@ -- of vertices of the arguments: /m = O(m1 + m2 + n1 * n2)/. -- -- @--- 'IntAdjacencyMap.isEmpty' (connect x y) == 'IntAdjacencyMap.isEmpty' x && 'IntAdjacencyMap.isEmpty' y--- 'IntAdjacencyMap.hasVertex' z (connect x y) == 'IntAdjacencyMap.hasVertex' z x || 'IntAdjacencyMap.hasVertex' z y--- 'IntAdjacencyMap.vertexCount' (connect x y) >= 'IntAdjacencyMap.vertexCount' x--- 'IntAdjacencyMap.vertexCount' (connect x y) <= 'IntAdjacencyMap.vertexCount' x + 'IntAdjacencyMap.vertexCount' y--- 'IntAdjacencyMap.edgeCount' (connect x y) >= 'IntAdjacencyMap.edgeCount' x--- 'IntAdjacencyMap.edgeCount' (connect x y) >= 'IntAdjacencyMap.edgeCount' y--- 'IntAdjacencyMap.edgeCount' (connect x y) >= 'IntAdjacencyMap.vertexCount' x * 'IntAdjacencyMap.vertexCount' y--- 'IntAdjacencyMap.edgeCount' (connect x y) <= 'IntAdjacencyMap.vertexCount' x * 'IntAdjacencyMap.vertexCount' y + 'IntAdjacencyMap.edgeCount' x + 'IntAdjacencyMap.edgeCount' y--- 'IntAdjacencyMap.vertexCount' (connect 1 2) == 2--- 'IntAdjacencyMap.edgeCount' (connect 1 2) == 1+-- 'Algebra.Graph.IntAdjacencyMap.isEmpty' (connect x y) == 'Algebra.Graph.IntAdjacencyMap.isEmpty' x && 'Algebra.Graph.IntAdjacencyMap.isEmpty' y+-- 'Algebra.Graph.IntAdjacencyMap.hasVertex' z (connect x y) == 'Algebra.Graph.IntAdjacencyMap.hasVertex' z x || 'Algebra.Graph.IntAdjacencyMap.hasVertex' z y+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' (connect x y) >= 'Algebra.Graph.IntAdjacencyMap.vertexCount' x+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' (connect x y) <= 'Algebra.Graph.IntAdjacencyMap.vertexCount' x + 'Algebra.Graph.IntAdjacencyMap.vertexCount' y+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (connect x y) >= 'Algebra.Graph.IntAdjacencyMap.edgeCount' x+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (connect x y) >= 'Algebra.Graph.IntAdjacencyMap.edgeCount' y+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (connect x y) >= 'Algebra.Graph.IntAdjacencyMap.vertexCount' x * 'Algebra.Graph.IntAdjacencyMap.vertexCount' y+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (connect x y) <= 'Algebra.Graph.IntAdjacencyMap.vertexCount' x * 'Algebra.Graph.IntAdjacencyMap.vertexCount' y + 'Algebra.Graph.IntAdjacencyMap.edgeCount' x + 'Algebra.Graph.IntAdjacencyMap.edgeCount' y+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' (connect 1 2) == 2+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' (connect 1 2) == 1 -- @ connect :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap connect x y = IntAdjacencyMap $ IntMap.unionsWith IntSet.union [ adjacencyMap x, adjacencyMap y,@@ -214,9 +214,9 @@ -- @ -- vertices [] == 'empty' -- vertices [x] == 'vertex' x--- 'IntAdjacencyMap.hasVertex' x . vertices == 'elem' x--- 'IntAdjacencyMap.vertexCount' . vertices == 'length' . 'Data.List.nub'--- 'IntAdjacencyMap.vertexIntSet' . vertices == IntSet.'IntSet.fromList'+-- 'Algebra.Graph.IntAdjacencyMap.hasVertex' x . vertices == 'elem' x+-- 'Algebra.Graph.IntAdjacencyMap.vertexCount' . vertices == 'length' . 'Data.List.nub'+-- 'Algebra.Graph.IntAdjacencyMap.vertexSet' . vertices == IntSet.'IntSet.fromList' -- @ vertices :: [Int] -> IntAdjacencyMap vertices = IntAdjacencyMap . IntMap.fromList . map (\x -> (x, IntSet.empty))@@ -226,8 +226,8 @@ -- -- @ -- edges [] == 'empty'--- edges [(x, y)] == 'IntAdjacencyMap.edge' x y--- 'IntAdjacencyMap.edgeCount' . edges == 'length' . 'Data.List.nub'+-- edges [(x, y)] == 'Algebra.Graph.IntAdjacencyMap.edge' x y+-- 'Algebra.Graph.IntAdjacencyMap.edgeCount' . edges == 'length' . 'Data.List.nub' -- 'edgeList' . edges == 'Data.List.nub' . 'Data.List.sort' -- @ edges :: [(Int, Int)] -> IntAdjacencyMap@@ -239,7 +239,7 @@ -- @ -- fromAdjacencyList [] == 'empty' -- fromAdjacencyList [(x, [])] == 'vertex' x--- fromAdjacencyList [(x, [y])] == 'IntAdjacencyMap.edge' x y+-- fromAdjacencyList [(x, [y])] == 'Algebra.Graph.IntAdjacencyMap.edge' x y -- fromAdjacencyList . 'adjacencyList' == id -- 'overlay' (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys) -- @@@ -256,8 +256,8 @@ -- @ -- edgeList 'empty' == [] -- edgeList ('vertex' x) == []--- edgeList ('IntAdjacencyMap.edge' x y) == [(x,y)]--- edgeList ('IntAdjacencyMap.star' 2 [3,1]) == [(2,1), (2,3)]+-- edgeList ('Algebra.Graph.IntAdjacencyMap.edge' x y) == [(x,y)]+-- edgeList ('Algebra.Graph.IntAdjacencyMap.star' 2 [3,1]) == [(2,1), (2,3)] -- edgeList . 'edges' == 'Data.List.nub' . 'Data.List.sort' -- @ edgeList :: IntAdjacencyMap -> [(Int, Int)]@@ -269,8 +269,8 @@ -- @ -- adjacencyList 'empty' == [] -- adjacencyList ('vertex' x) == [(x, [])]--- adjacencyList ('IntAdjacencyMap.edge' 1 2) == [(1, [2]), (2, [])]--- adjacencyList ('IntAdjacencyMap.star' 2 [1,3]) == [(1, []), (2, [1,3]), (3, [])]+-- adjacencyList ('Algebra.Graph.IntAdjacencyMap.edge' 1 2) == [(1, [2]), (2, [])]+-- adjacencyList ('Algebra.Graph.IntAdjacencyMap.star' 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] -- 'fromAdjacencyList' . adjacencyList == id -- @ adjacencyList :: IntAdjacencyMap -> [(Int, [Int])]@@ -290,7 +290,7 @@ -- Complexity: /O(log(n))/ time. -- -- @--- removeEdge x y ('IntAdjacencyMap.edge' x y) == 'vertices' [x, y]+-- removeEdge x y ('Algebra.Graph.IntAdjacencyMap.edge' x y) == 'vertices' [x, y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . 'removeVertex' x == 'removeVertex' x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2@@ -307,7 +307,7 @@ -- @ -- gmap f 'empty' == 'empty' -- gmap f ('vertex' x) == 'vertex' (f x)--- gmap f ('IntAdjacencyMap.edge' x y) == 'IntAdjacencyMap.edge' (f x) (f y)+-- gmap f ('Algebra.Graph.IntAdjacencyMap.edge' x y) == 'Algebra.Graph.IntAdjacencyMap.edge' (f x) (f y) -- gmap id == id -- gmap f . gmap g == gmap (f . g) -- @@@ -324,7 +324,7 @@ -- induce (const False) x == 'empty' -- induce (/= x) == 'removeVertex' x -- induce p . induce q == induce (\\x -> p x && q x)--- 'IntAdjacencyMap.isSubgraphOf' (induce p x) x == True+-- 'Algebra.Graph.IntAdjacencyMap.isSubgraphOf' (induce p x) x == True -- @ induce :: (Int -> Bool) -> IntAdjacencyMap -> IntAdjacencyMap induce p = IntAdjacencyMap . IntMap.map (IntSet.filter p) . IntMap.filterWithKey (\k _ -> p k) . adjacencyMap
src/Algebra/Graph/Relation.hs view
@@ -285,7 +285,7 @@ forest :: Ord a => Tree.Forest a -> Relation a forest = C.forest --- | The function @replaceVertex x y@ replaces vertex @x@ with vertex @y@ in a+-- | The function @'replaceVertex' x y@ replaces vertex @x@ with vertex @y@ in a -- given 'AdjacencyMap'. If @y@ already exists, @x@ and @y@ will be merged. -- Complexity: /O((n + m) * log(n))/ time. --
src/Algebra/Graph/Relation/Internal.hs view
@@ -152,9 +152,9 @@ -- consistent ('vertex' x) == True -- consistent ('overlay' x y) == True -- consistent ('connect' x y) == True--- consistent ('Relatation.edge' x y) == True+-- consistent ('Algebra.Graph.Relation.edge' x y) == True -- consistent ('edges' xs) == True--- consistent ('Relatation.graph' xs ys) == True+-- consistent ('Algebra.Graph.Relation.graph' xs ys) == True -- consistent ('fromAdjacencyList' xs) == True -- @ consistent :: Ord a => Relation a -> Bool@@ -165,10 +165,10 @@ -- Complexity: /O(1)/ time and memory. -- -- @--- 'Relation.isEmpty' empty == True--- 'Relation.hasVertex' x empty == False--- 'Relation.vertexCount' empty == 0--- 'Relation.edgeCount' empty == 0+-- 'Algebra.Graph.Relation.isEmpty' empty == True+-- 'Algebra.Graph.Relation.hasVertex' x empty == False+-- 'Algebra.Graph.Relation.vertexCount' empty == 0+-- 'Algebra.Graph.Relation.edgeCount' empty == 0 -- @ empty :: Relation a empty = Relation Set.empty Set.empty@@ -177,11 +177,11 @@ -- Complexity: /O(1)/ time and memory. -- -- @--- 'Relation.isEmpty' (vertex x) == False--- 'Relation.hasVertex' x (vertex x) == True--- 'Relation.hasVertex' 1 (vertex 2) == False--- 'Relation.vertexCount' (vertex x) == 1--- 'Relation.edgeCount' (vertex x) == 0+-- 'Algebra.Graph.Relation.isEmpty' (vertex x) == False+-- 'Algebra.Graph.Relation.hasVertex' x (vertex x) == True+-- 'Algebra.Graph.Relation.hasVertex' 1 (vertex 2) == False+-- 'Algebra.Graph.Relation.vertexCount' (vertex x) == 1+-- 'Algebra.Graph.Relation.edgeCount' (vertex x) == 0 -- @ vertex :: a -> Relation a vertex x = Relation (Set.singleton x) Set.empty@@ -191,14 +191,14 @@ -- Complexity: /O((n + m) * log(n))/ time and /O(n + m)/ memory. -- -- @--- 'Relation.isEmpty' (overlay x y) == 'Relation.isEmpty' x && 'Relation.isEmpty' y--- 'Relation.hasVertex' z (overlay x y) == 'Relation.hasVertex' z x || 'Relation.hasVertex' z y--- 'Relation.vertexCount' (overlay x y) >= 'Relation.vertexCount' x--- 'Relation.vertexCount' (overlay x y) <= 'Relation.vertexCount' x + 'Relation.vertexCount' y--- 'Relation.edgeCount' (overlay x y) >= 'Relation.edgeCount' x--- 'Relation.edgeCount' (overlay x y) <= 'Relation.edgeCount' x + 'Relation.edgeCount' y--- 'Relation.vertexCount' (overlay 1 2) == 2--- 'Relation.edgeCount' (overlay 1 2) == 0+-- 'Algebra.Graph.Relation.isEmpty' (overlay x y) == 'Algebra.Graph.Relation.isEmpty' x && 'Algebra.Graph.Relation.isEmpty' y+-- 'Algebra.Graph.Relation.hasVertex' z (overlay x y) == 'Algebra.Graph.Relation.hasVertex' z x || 'Algebra.Graph.Relation.hasVertex' z y+-- 'Algebra.Graph.Relation.vertexCount' (overlay x y) >= 'Algebra.Graph.Relation.vertexCount' x+-- 'Algebra.Graph.Relation.vertexCount' (overlay x y) <= 'Algebra.Graph.Relation.vertexCount' x + 'Algebra.Graph.Relation.vertexCount' y+-- 'Algebra.Graph.Relation.edgeCount' (overlay x y) >= 'Algebra.Graph.Relation.edgeCount' x+-- 'Algebra.Graph.Relation.edgeCount' (overlay x y) <= 'Algebra.Graph.Relation.edgeCount' x + 'Algebra.Graph.Relation.edgeCount' y+-- 'Algebra.Graph.Relation.vertexCount' (overlay 1 2) == 2+-- 'Algebra.Graph.Relation.edgeCount' (overlay 1 2) == 0 -- @ overlay :: Ord a => Relation a -> Relation a -> Relation a overlay x y = Relation (domain x `union` domain y) (relation x `union` relation y)@@ -210,16 +210,16 @@ -- of vertices of the arguments: /m = O(m1 + m2 + n1 * n2)/. -- -- @--- 'Relation.isEmpty' (connect x y) == 'Relation.isEmpty' x && 'Relation.isEmpty' y--- 'Relation.hasVertex' z (connect x y) == 'Relation.hasVertex' z x || 'Relation.hasVertex' z y--- 'Relation.vertexCount' (connect x y) >= 'Relation.vertexCount' x--- 'Relation.vertexCount' (connect x y) <= 'Relation.vertexCount' x + 'Relation.vertexCount' y--- 'Relation.edgeCount' (connect x y) >= 'Relation.edgeCount' x--- 'Relation.edgeCount' (connect x y) >= 'Relation.edgeCount' y--- 'Relation.edgeCount' (connect x y) >= 'Relation.vertexCount' x * 'Relation.vertexCount' y--- 'Relation.edgeCount' (connect x y) <= 'Relation.vertexCount' x * 'Relation.vertexCount' y + 'Relation.edgeCount' x + 'Relation.edgeCount' y--- 'Relation.vertexCount' (connect 1 2) == 2--- 'Relation.edgeCount' (connect 1 2) == 1+-- 'Algebra.Graph.Relation.isEmpty' (connect x y) == 'Algebra.Graph.Relation.isEmpty' x && 'Algebra.Graph.Relation.isEmpty' y+-- 'Algebra.Graph.Relation.hasVertex' z (connect x y) == 'Algebra.Graph.Relation.hasVertex' z x || 'Algebra.Graph.Relation.hasVertex' z y+-- 'Algebra.Graph.Relation.vertexCount' (connect x y) >= 'Algebra.Graph.Relation.vertexCount' x+-- 'Algebra.Graph.Relation.vertexCount' (connect x y) <= 'Algebra.Graph.Relation.vertexCount' x + 'Algebra.Graph.Relation.vertexCount' y+-- 'Algebra.Graph.Relation.edgeCount' (connect x y) >= 'Algebra.Graph.Relation.edgeCount' x+-- 'Algebra.Graph.Relation.edgeCount' (connect x y) >= 'Algebra.Graph.Relation.edgeCount' y+-- 'Algebra.Graph.Relation.edgeCount' (connect x y) >= 'Algebra.Graph.Relation.vertexCount' x * 'Algebra.Graph.Relation.vertexCount' y+-- 'Algebra.Graph.Relation.edgeCount' (connect x y) <= 'Algebra.Graph.Relation.vertexCount' x * 'Algebra.Graph.Relation.vertexCount' y + 'Algebra.Graph.Relation.edgeCount' x + 'Algebra.Graph.Relation.edgeCount' y+-- 'Algebra.Graph.Relation.vertexCount' (connect 1 2) == 2+-- 'Algebra.Graph.Relation.edgeCount' (connect 1 2) == 1 -- @ connect :: Ord a => Relation a -> Relation a -> Relation a connect x y = Relation (domain x `union` domain y) (relation x `union` relation y@@ -235,9 +235,9 @@ -- @ -- vertices [] == 'empty' -- vertices [x] == 'vertex' x--- 'Relation.hasVertex' x . vertices == 'elem' x--- 'Relation.vertexCount' . vertices == 'length' . 'Data.List.nub'--- 'Relation.vertexSet' . vertices == Set.'Set.fromList'+-- 'Algebra.Graph.Relation.hasVertex' x . vertices == 'elem' x+-- 'Algebra.Graph.Relation.vertexCount' . vertices == 'length' . 'Data.List.nub'+-- 'Algebra.Graph.Relation.vertexSet' . vertices == Set.'Set.fromList' -- @ vertices :: Ord a => [a] -> Relation a vertices xs = Relation (Set.fromList xs) Set.empty@@ -247,8 +247,8 @@ -- -- @ -- edges [] == 'empty'--- edges [(x,y)] == 'Relation.edge' x y--- 'Relation.edgeCount' . edges == 'length' . 'Data.List.nub'+-- edges [(x,y)] == 'Algebra.Graph.Relation.edge' x y+-- 'Algebra.Graph.Relation.edgeCount' . edges == 'length' . 'Data.List.nub' -- @ edges :: Ord a => [(a, a)] -> Relation a edges es = Relation (Set.fromList $ uncurry (++) $ unzip es) (Set.fromList es)@@ -259,7 +259,7 @@ -- @ -- fromAdjacencyList [] == 'empty' -- fromAdjacencyList [(x, [])] == 'vertex' x--- fromAdjacencyList [(x, [y])] == 'Relation.edge' x y+-- fromAdjacencyList [(x, [y])] == 'Algebra.Graph.Relation.edge' x y -- 'overlay' (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys) -- @ fromAdjacencyList :: Ord a => [(a, [a])] -> Relation a@@ -274,8 +274,8 @@ -- @ -- edgeList 'empty' == [] -- edgeList ('vertex' x) == []--- edgeList ('Relation.edge' x y) == [(x,y)]--- edgeList ('Relation.star' 2 [1,3]) == [(2,1), (2,3)]+-- edgeList ('Algebra.Graph.Relation.edge' x y) == [(x,y)]+-- edgeList ('Algebra.Graph.Relation.star' 2 [1,3]) == [(2,1), (2,3)] -- edgeList . 'edges' == 'Data.List.nub' . 'Data.List.sort' -- @ edgeList :: Ord a => Relation a -> [(a, a)]@@ -289,8 +289,8 @@ -- @ -- preset x 'empty' == Set.empty -- preset x ('vertex' x) == Set.empty--- preset 1 ('Relatation.edge' 1 2) == Set.empty--- preset y ('Relatation.edge' x y) == Set.fromList [x]+-- preset 1 ('Algebra.Graph.Relation.edge' 1 2) == Set.empty+-- preset y ('Algebra.Graph.Relation.edge' x y) == Set.fromList [x] -- @ preset :: Ord a => a -> Relation a -> Set a preset x = Set.mapMonotonic fst . Set.filter ((== x) . snd) . relation@@ -303,8 +303,8 @@ -- @ -- postset x 'empty' == Set.empty -- postset x ('vertex' x) == Set.empty--- postset x ('Relatation.edge' x y) == Set.fromList [y]--- postset 2 ('Relatation.edge' 1 2) == Set.empty+-- postset x ('Algebra.Graph.Relation.edge' x y) == Set.fromList [y]+-- postset 2 ('Algebra.Graph.Relation.edge' 1 2) == Set.empty -- @ postset :: Ord a => a -> Relation a -> Set a postset x = Set.mapMonotonic snd . Set.filter ((== x) . fst) . relation@@ -342,7 +342,7 @@ -- @ -- gmap f 'empty' == 'empty' -- gmap f ('vertex' x) == 'vertex' (f x)--- gmap f ('Relation.edge' x y) == 'Relation.edge' (f x) (f y)+-- gmap f ('Algebra.Graph.Relation.edge' x y) == 'Algebra.Graph.Relation.edge' (f x) (f y) -- gmap id == id -- gmap f . gmap g == gmap (f . g) -- @@@ -359,7 +359,7 @@ -- induce (const False) x == 'empty' -- induce (/= x) == 'removeVertex' x -- induce p . induce q == induce (\\x -> p x && q x)--- 'Relation.isSubgraphOf' (induce p x) x == True+-- 'Algebra.Graph.Relation.isSubgraphOf' (induce p x) x == True -- @ induce :: Ord a => (a -> Bool) -> Relation a -> Relation a induce p (Relation d r) = Relation (Set.filter p d) (Set.filter pp r)@@ -371,7 +371,7 @@ -- -- @ -- reflexiveClosure 'empty' == 'empty'--- reflexiveClosure ('vertex' x) == 'Relatation.edge' x x+-- reflexiveClosure ('vertex' x) == 'Algebra.Graph.Relation.edge' x x -- @ reflexiveClosure :: Ord a => Relation a -> Relation a reflexiveClosure (Relation d r) =@@ -383,7 +383,7 @@ -- @ -- symmetricClosure 'empty' == 'empty' -- symmetricClosure ('vertex' x) == 'vertex' x--- symmetricClosure ('Relatation.edge' x y) == 'Relatation.edges' [(x, y), (y, x)]+-- symmetricClosure ('Algebra.Graph.Relation.edge' x y) == 'Algebra.Graph.Relation.edges' [(x, y), (y, x)] -- @ symmetricClosure :: Ord a => Relation a -> Relation a symmetricClosure (Relation d r) = Relation d $ r `union` (Set.map swap r)@@ -394,7 +394,7 @@ -- @ -- transitiveClosure 'empty' == 'empty' -- transitiveClosure ('vertex' x) == 'vertex' x--- transitiveClosure ('Relatation.path' $ 'Data.List.nub' xs) == 'Relatation.clique' ('Data.List.nub' xs)+-- transitiveClosure ('Algebra.Graph.Relation.path' $ 'Data.List.nub' xs) == 'Algebra.Graph.Relation.clique' ('Data.List.nub' xs) -- @ transitiveClosure :: Ord a => Relation a -> Relation a transitiveClosure old@(Relation d r)@@ -408,8 +408,8 @@ -- -- @ -- preorderClosure 'empty' == 'empty'--- preorderClosure ('vertex' x) == 'Relatation.edge' x x--- preorderClosure ('Relatation.path' $ 'Data.List.nub' xs) == 'reflexiveClosure' ('Relatation.clique' $ 'Data.List.nub' xs)+-- preorderClosure ('vertex' x) == 'Algebra.Graph.Relation.edge' x x+-- preorderClosure ('Algebra.Graph.Relation.path' $ 'Data.List.nub' xs) == 'reflexiveClosure' ('Algebra.Graph.Relation.clique' $ 'Data.List.nub' xs) -- @ preorderClosure :: Ord a => Relation a -> Relation a preorderClosure = reflexiveClosure . transitiveClosure@@ -421,7 +421,7 @@ @'C.vertex' x == 'C.vertex' x * 'C.vertex' x@ -The 'Show' instance produces transitively closed expressions:+The 'Show' instance produces reflexively closed expressions: @show (1 :: ReflexiveRelation Int) == "edge 1 1" show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"@@@ -453,7 +453,7 @@ @'C.connect' x y == 'C.connect' y x@ -The 'Show' instance produces transitively closed expressions:+The 'Show' instance produces symmetrically closed expressions: @show (1 :: SymmetricRelation Int) == "vertex 1" show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"@@@ -528,7 +528,7 @@ @'C.path' xs == 'C.clique' xs@ -The 'Show' instance produces transitively closed expressions:+The 'Show' instance produces reflexively and transitively closed expressions: @show (1 :: PreorderRelation Int) == "edge 1 1" show (1 * 2 :: PreorderRelation Int) == "edges [(1,1),(1,2),(2,2)]"
src/Algebra/Graph/Relation/Preorder.hs view
@@ -16,7 +16,7 @@ import Algebra.Graph.Relation.Internal --- | Construct a reflexive relation from a 'Relation'.+-- | Construct a preorder relation from a 'Relation'. -- Complexity: /O(1)/ time. fromRelation :: Relation a -> PreorderRelation a fromRelation = PreorderRelation@@ -25,4 +25,3 @@ -- Complexity: /O(n * m * log(m))/ time. toRelation :: Ord a => PreorderRelation a -> Relation a toRelation = preorderClosure . fromPreorder-
src/Algebra/Graph/Relation/Symmetric.hs view
@@ -21,7 +21,7 @@ import qualified Data.Set as Set --- | Construct a reflexive relation from a 'Relation'.+-- | Construct a symmetric relation from a 'Relation'. -- Complexity: /O(1)/ time. fromRelation :: Relation a -> SymmetricRelation a fromRelation = SymmetricRelation
src/Algebra/Graph/Relation/Transitive.hs view
@@ -16,7 +16,7 @@ import Algebra.Graph.Relation.Internal --- | Construct a reflexive relation from a 'Relation'.+-- | Construct a transitive relation from a 'Relation'. -- Complexity: /O(1)/ time. fromRelation :: Relation a -> TransitiveRelation a fromRelation = TransitiveRelation
test/Algebra/Graph/Test/AdjacencyMap.hs view
@@ -354,8 +354,8 @@ test "adjacencyList (edge 1 2) == [(1, [2]), (2, [])]" $ adjacencyList (edge 1 (2 :: Int)) == [(1, [2]), (2, [])] - test "adjacencyList (star 2 [1,3]) == [(1, []), (2, [1,3]), (3, [])]" $- adjacencyList (star 2 [1,3::Int]) == [(1, []), (2, [1,3]), (3, [])]+ test "adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]" $+ adjacencyList (star 2 [3,1::Int]) == [(1, []), (2, [1,3]), (3, [])] putStrLn "\n============ vertexSet ============" test "vertexSet empty == Set.empty" $
test/Algebra/Graph/Test/Fold.hs view
@@ -298,6 +298,9 @@ test "size x >= 1" $ \(x :: F) -> size x >= 1 + test "size x >= vertexCount x" $ \(x :: F) ->+ size x >= vertexCount x+ putStrLn "\n============ hasVertex ============" test "hasVertex x empty == False" $ \(x :: Int) -> hasVertex x empty == False@@ -483,21 +486,21 @@ , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ] putStrLn "\n============ torus ============"- test "torus xs [] == empty" $ \xs ->- torus xs [] == (empty :: Fold (Int, Int))+ test "torus xs [] == empty" $ \xs ->+ torus xs [] == (empty :: Fold (Int, Int)) - test "torus [] ys == empty" $ \ys ->- torus [] ys == (empty :: Fold (Int, Int))+ test "torus [] ys == empty" $ \ys ->+ torus [] ys == (empty :: Fold (Int, Int)) - test "torus [x] [y] == edge (x, y) (x, y)" $ \(x :: Int) (y :: Int) ->- torus [x] [y] == (edge (x, y) (x, y) :: Fold (Int, Int))+ test "torus [x] [y] == edge (x, y) (x, y)" $ \(x :: Int) (y :: Int) ->+ torus [x] [y] == (edge (x, y) (x, y) :: Fold (Int, Int)) - test "torus xs ys == box (circuit xs) (circuit ys)" $ \(xs :: [Int]) (ys :: [Int]) ->- torus xs ys == (box (circuit xs) (circuit ys) :: Fold (Int, Int))+ test "torus xs ys == box (circuit xs) (circuit ys)" $ \(xs :: [Int]) (ys :: [Int]) ->+ torus xs ys == (box (circuit xs) (circuit ys) :: Fold (Int, Int)) - test ("torus [1..2] \"ab\" == <correct result>") $- (torus [1..2] "ab" :: Fold (Int, Char)) == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b'))- , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ]+ test ("torus [1,2] \"ab\" == <correct result>") $+ (torus [1,2] "ab" :: Fold (Int, Char)) == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b'))+ , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ] putStrLn "\n============ deBruijn ============" test "deBruijn k [] == empty" $ \k ->@@ -640,7 +643,7 @@ isSubgraphOf (induce p x) x == True putStrLn "\n============ simplify ============"- test "simplify x == x" $ \(x :: F) ->+ test "simplify == id" $ \(x :: F) -> simplify x == x test "size (simplify x) <= size x" $ \(x :: F) ->
test/Algebra/Graph/Test/Graph.hs view
@@ -296,6 +296,9 @@ test "size x >= 1" $ \(x :: G) -> size x >= 1 + test "size x >= vertexCount x" $ \(x :: G) ->+ size x >= vertexCount x+ putStrLn "\n============ hasVertex ============" test "hasVertex x empty == False" $ \(x :: Int) -> hasVertex x empty == False@@ -481,21 +484,21 @@ , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3 :: Int,'b')) ] putStrLn "\n============ torus ============"- test "torus xs [] == empty" $ \xs ->- torus xs [] == (empty :: Graph (Int, Int))+ test "torus xs [] == empty" $ \xs ->+ torus xs [] == (empty :: Graph (Int, Int)) - test "torus [] ys == empty" $ \ys ->- torus [] ys == (empty :: Graph (Int, Int))+ test "torus [] ys == empty" $ \ys ->+ torus [] ys == (empty :: Graph (Int, Int)) - test "torus [x] [y] == edge (x, y) (x, y)" $ \(x :: Int) (y :: Int) ->- torus [x] [y] == edge (x, y) (x, y)+ test "torus [x] [y] == edge (x, y) (x, y)" $ \(x :: Int) (y :: Int) ->+ torus [x] [y] == edge (x, y) (x, y) - test "torus xs ys == box (circuit xs) (circuit ys)" $ \(xs :: [Int]) (ys :: [Int]) ->- torus xs ys == box (circuit xs) (circuit ys)+ test "torus xs ys == box (circuit xs) (circuit ys)" $ \(xs :: [Int]) (ys :: [Int]) ->+ torus xs ys == box (circuit xs) (circuit ys) - test ("torus [1..2] \"ab\" == <correct result>") $- torus [1..2] "ab" == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b'))- , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2 :: Int,'a')) ]+ test ("torus [1,2] \"ab\" == <correct result>") $+ torus [1,2] "ab" == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b'))+ , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2 :: Int,'a')) ] putStrLn "\n============ deBruijn ============" test "deBruijn k [] == empty" $ \k ->@@ -638,7 +641,7 @@ isSubgraphOf (induce p x) x == True putStrLn "\n============ simplify ============"- test "simplify x == x" $ \(x :: G) ->+ test "simplify == id" $ \(x :: G) -> simplify x == x test "size (simplify x) <= size x" $ \(x :: G) ->
test/Algebra/Graph/Test/IntAdjacencyMap.hs view
@@ -351,8 +351,8 @@ test "adjacencyList (edge 1 2) == [(1, [2]), (2, [])]" $ adjacencyList (edge 1 2) == [(1, [2]), (2, [])] - test "adjacencyList (star 2 [1,3]) == [(1, []), (2, [1,3]), (3, [])]" $- adjacencyList (star 2 [1,3]) == [(1, []), (2, [1,3]), (3, [])]+ test "adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]" $+ adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] putStrLn "\n============ vertexSet ============" test "vertexSet empty == IntSet.empty" $