algebraic-edge-graphs 0.1.0 → 0.1.1

raw patch · 12 files changed

+259/−246 lines, 12 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• CHANGELOG.md +6/−0
• algebraic-edge-graphs.cabal +3/−2
• src/EdgeGraph.hs +67/−61
• src/EdgeGraph/AdjacencyMap.hs +13/−13
• src/EdgeGraph/AdjacencyMap/Internal.hs +23/−23
• src/EdgeGraph/Class.hs +12/−12
• src/EdgeGraph/Fold.hs +46/−46
• src/EdgeGraph/HigherKinded/Class.hs +32/−32
• src/EdgeGraph/Incidence.hs +8/−8
• src/EdgeGraph/Incidence/Internal.hs +19/−19
• src/EdgeGraph/IntAdjacencyMap.hs +10/−10
• src/EdgeGraph/IntAdjacencyMap/Internal.hs +20/−20

@@ -1,5 +1,11 @@ # Changelog +## 0.1.1 — 2026-04-24++* Added reference to the theory in [this paper](https://jackliellcock.com/papers/edge_graphs/paper.pdf).+* Fixed broken Haddock links throughout the documentation.+* Tightened whitespace and alignment of formula blocks in module documentation for consistent rendering on Hackage.+ ## 0.1.0 — 2026-03-10  * Initial release.

@@ -1,6 +1,6 @@ cabal-version: 2.4 name:          algebraic-edge-graphs-version:       0.1.0+version:       0.1.1 synopsis:      A library for algebraic edge-graph construction and transformation license:       MIT license-file:  LICENSE@@ -17,7 +17,8 @@              , GHC ==9.12.1 description:   A library for algebraic construction and manipulation of edge-indexed graphs-  in Haskell. Based on the theory of algebraic edge graphs.+  in Haskell. Based on the theory of algebraic edge graphs, as described in+  <https://jackliellcock.com/papers/edge_graphs/paper.pdf this paper>.   .   The top-level module "EdgeGraph" defines the core data type   'EdgeGraph.EdgeGraph' which is a deep embedding of six graph construction

@@ -15,9 +15,13 @@ -- 'EdgeGraph' is an instance of the type class defined in "EdgeGraph.Class", -- which can be used for polymorphic edge graph construction and manipulation. ----- The 'Eq' instance is implemented using the 'I.Incidence' as the /canonical+-- The 'Eq' instance is implemented using the 'EdgeGraph.Incidence.Incidence' as the /canonical -- graph representation/ and satisfies all axioms of algebraic edge graphs. --+-- See <https://jackliellcock.com/papers/edge_graphs/paper.pdf this paper> for+-- the motivation behind the library and the underlying theory of algebraic+-- edge graphs.+-- ----------------------------------------------------------------------------- module EdgeGraph (     -- * Algebraic data type for edge graphs@@ -63,7 +67,7 @@  {-| The 'EdgeGraph' datatype is a deep embedding of the core edge graph construction primitives 'EdgeGraph.empty', 'EdgeGraph.edge', 'overlay', 'into', 'pits' and 'tips'.-The 'Eq' instance is implemented using the 'I.Incidence' as the /canonical+The 'Eq' instance is implemented using the 'EdgeGraph.Incidence.Incidence' as the /canonical graph representation/ and satisfies all axioms of algebraic edge graphs. In equations we use the infix operators '(EdgeGraph.Class.+++)' for 'overlay', '(EdgeGraph.Class.>+>)' for 'into', '(EdgeGraph.Class.<+>)' for 'pits', and '(EdgeGraph.Class.>+<)' for 'tips'.@@ -71,10 +75,10 @@     * 'overlay' is commutative, associative, and idempotent with 'EdgeGraph.empty' as       the identity: -        >         x +++ y == y +++ x+        > x +++ y         == y +++ x         > x +++ (y +++ z) == (x +++ y) +++ z-        >         x +++ x == x-        >     x +++ empty == x+        > x +++ x         == x+        > x +++ empty     == x      * 'EdgeGraph.empty' is the identity for 'into', 'pits', and 'tips'. 'pits' and       'tips' are commutative.@@ -99,7 +103,7 @@     * Absorption and saturation for each connect operator (shown for 'into'):          > x >+> y +++ x +++ y == x >+> y-        > x >+> x == (x >+> x) >+> x+        > x >+> x             == (x >+> x) >+> x  When specifying the time and memory complexity of graph algorithms, /s/ will denote the /size/ of the corresponding 'EdgeGraph' expression.@@ -108,12 +112,14 @@ 'Foldable' type class, as the latter does not count 'Empty' leaves of the expression: -@'length' 'EdgeGraph.empty'                == 0-'size'   'EdgeGraph.empty'                 == 1-'length' ('EdgeGraph.edge' x)              == 1-'size'   ('EdgeGraph.edge' x)              == 1+@+'length' 'EdgeGraph.empty'             == 0+'size'   'EdgeGraph.empty'             == 1+'length' ('EdgeGraph.edge' x)          == 1+'size'   ('EdgeGraph.edge' x)          == 1 'length' ('EdgeGraph.empty' 'EdgeGraph.Class.+++' 'EdgeGraph.empty') == 0-'size'   ('EdgeGraph.empty' 'EdgeGraph.Class.+++' 'EdgeGraph.empty') == 2@+'size'   ('EdgeGraph.empty' 'EdgeGraph.Class.+++' 'EdgeGraph.empty') == 2+@  The 'size' of any graph is positive, and the difference @('size' g - 'length' g)@ corresponds to the number of occurrences of 'EdgeGraph.empty' in an expression @g@.@@ -260,9 +266,9 @@ -- of the given list, and /S/ is the sum of sizes of the graphs in the list. -- -- @--- overlays []          == 'EdgeGraph.empty'--- overlays [x]         == x--- overlays [x,y]       == 'overlay' x y+-- overlays []        == 'EdgeGraph.empty'+-- overlays [x]       == x+-- overlays [x,y]     == 'overlay' x y -- 'isEmpty' . overlays == 'all' 'isEmpty' -- @ overlays :: [EdgeGraph a] -> EdgeGraph a@@ -273,9 +279,9 @@ -- of the given list, and /S/ is the sum of sizes of the graphs in the list. -- -- @--- intos []          == 'EdgeGraph.empty'--- intos [x]         == x--- intos [x,y]       == 'into' x y+-- intos []        == 'EdgeGraph.empty'+-- intos [x]       == x+-- intos [x,y]     == 'into' x y -- 'isEmpty' . intos == 'all' 'isEmpty' -- @ intos :: [EdgeGraph a] -> EdgeGraph a@@ -289,11 +295,11 @@ -- complexity of 'size' is /O(s)/, since all functions have cost /O(1)/. -- -- @--- foldg 'EdgeGraph.empty' 'EdgeGraph.edge' 'overlay' 'into' 'pits' 'tips' == id--- foldg []    (\\x -> [x])  (++)  (++) (++) (++)      == 'Data.Foldable.toList'--- foldg 0     (const 1)     (+)   (+)  (+)  (+)       == 'Data.Foldable.length'--- foldg 1     (const 1)     (+)   (+)  (+)  (+)       == 'size'--- foldg True  (const False) (&&)  (&&) (&&) (&&)      == 'isEmpty'+-- foldg 'EdgeGraph.empty' 'EdgeGraph.edge'          'overlay' 'into' 'pits' 'tips' == id+-- foldg []    (\\x -> [x])   (++)    (++) (++) (++) == 'Data.Foldable.toList'+-- foldg 0     (const 1)     (+)     (+)  (+)  (+)  == 'Data.Foldable.length'+-- foldg 1     (const 1)     (+)     (+)  (+)  (+)  == 'size'+-- foldg True  (const False) (&&)    (&&) (&&) (&&) == 'isEmpty' -- @ foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> (b -> b -> b) -> (b -> b -> b) -> EdgeGraph a -> b foldg e v o c p t = go@@ -311,9 +317,9 @@ -- the canonical incidence representation. -- -- @--- isSubgraphOf 'EdgeGraph.empty'    x               == True+-- isSubgraphOf 'EdgeGraph.empty'    x             == True -- isSubgraphOf ('EdgeGraph.edge' x) 'EdgeGraph.empty'         == False--- isSubgraphOf x          ('overlay' x y) == True+-- isSubgraphOf x        ('overlay' x y) == True -- @ isSubgraphOf :: Ord a => EdgeGraph a -> EdgeGraph a -> Bool isSubgraphOf x y = I.isSubgraphOf (C.toEdgeGraph x) (C.toEdgeGraph y)@@ -323,9 +329,9 @@ -- Complexity: /O(s)/ time. -- -- @---                               x === x                               == True---                               x === 'overlay' x 'EdgeGraph.empty'             == False---                   'overlay' x y === 'overlay' x y                   == True+-- x === x                                                 == True+-- x === 'overlay' x 'EdgeGraph.empty'                                   == False+-- 'overlay' x y === 'overlay' x y                             == True -- 'overlay' ('EdgeGraph.edge' 1) ('EdgeGraph.edge' 2) === 'overlay' ('EdgeGraph.edge' 2) ('EdgeGraph.edge' 1) == False -- @ (===) :: Eq a => EdgeGraph a -> EdgeGraph a -> Bool@@ -343,9 +349,9 @@ -- Complexity: /O(s)/ time. -- -- @--- isEmpty 'EdgeGraph.empty'                     == True--- isEmpty ('overlay' 'EdgeGraph.empty' 'EdgeGraph.empty') == True--- isEmpty ('EdgeGraph.edge' x)                  == False+-- isEmpty 'EdgeGraph.empty'                   == True+-- isEmpty ('overlay' 'EdgeGraph.empty' 'EdgeGraph.empty')   == True+-- isEmpty ('EdgeGraph.edge' x)                == False -- isEmpty ('removeEdge' x $ 'EdgeGraph.edge' x) == True -- @ isEmpty :: EdgeGraph a -> Bool@@ -362,7 +368,7 @@ -- size ('into' x y)    == size x + size y -- size ('pits' x y)    == size x + size y -- size ('tips' x y)    == size x + size y--- size x               >= 1+-- size x             >= 1 -- @ size :: EdgeGraph a -> Int size = foldg 1 (const 1) (+) (+) (+) (+)@@ -384,7 +390,7 @@ -- @ -- edgeCount 'EdgeGraph.empty'    == 0 -- edgeCount ('EdgeGraph.edge' x) == 1--- edgeCount            == 'length' . 'edgeList'+-- edgeCount          == 'length' . 'edgeList' -- @ edgeCount :: Ord a => EdgeGraph a -> Int edgeCount = I.edgeCount . C.toEdgeGraph@@ -404,9 +410,9 @@ -- Complexity: /O(s * log(n))/ time and /O(n)/ memory. -- -- @--- edgeSet 'EdgeGraph.empty'   == Set.'Set.empty'--- edgeSet . 'EdgeGraph.edge'  == Set.'Set.singleton'--- edgeSet . 'edges' == Set.'Set.fromList'+-- edgeSet 'EdgeGraph.empty'   == 'Data.Set.empty'+-- edgeSet . 'EdgeGraph.edge'  == 'Data.Set.singleton'+-- edgeSet . 'edges' == 'Data.Set.fromList' -- @ edgeSet :: Ord a => EdgeGraph a -> Set.Set a edgeSet = foldr Set.insert Set.empty@@ -416,9 +422,9 @@ -- Complexity: /O(s * log(n))/ time and /O(n)/ memory. -- -- @--- edgeIntSet 'EdgeGraph.empty'   == IntSet.'IntSet.empty'--- edgeIntSet . 'EdgeGraph.edge'  == IntSet.'IntSet.singleton'--- edgeIntSet . 'edges' == IntSet.'IntSet.fromList'+-- edgeIntSet 'EdgeGraph.empty'   == 'Data.IntSet.empty'+-- edgeIntSet . 'EdgeGraph.edge'  == 'Data.IntSet.singleton'+-- edgeIntSet . 'edges' == 'Data.IntSet.fromList' -- @ edgeIntSet :: EdgeGraph Int -> IntSet.IntSet edgeIntSet = foldr IntSet.insert IntSet.empty@@ -438,7 +444,7 @@ -- -- @ -- nodeList 'EdgeGraph.empty'    == []--- nodeList ('EdgeGraph.edge' x) == ['I.Node' (Set.'Set.singleton' x) (Set.'Set.singleton' x)]+-- nodeList ('EdgeGraph.edge' x) == ['EdgeGraph.Incidence.Node' ('Data.Set.singleton' x) ('Data.Set.singleton' x)] -- @ nodeList :: Ord a => EdgeGraph a -> [I.Node a] nodeList = I.nodeList . C.toEdgeGraph@@ -447,7 +453,7 @@ -- Complexity: /O(s + n * log(n))/ time and /O(n)/ memory. -- -- @--- nodeSet 'EdgeGraph.empty' == Set.'Set.empty'+-- nodeSet 'EdgeGraph.empty' == 'Data.Set.empty' -- @ nodeSet :: Ord a => EdgeGraph a -> Set.Set (I.Node a) nodeSet = I.nodeSet . C.toEdgeGraph@@ -584,7 +590,7 @@ -- Complexity: /O(s)/ time, memory and size. -- -- @--- removeEdge x ('EdgeGraph.edge' x)     == 'EdgeGraph.empty'+-- removeEdge x ('EdgeGraph.edge' x)       == 'EdgeGraph.empty' -- removeEdge x . removeEdge x == removeEdge x -- @ removeEdge :: Eq a => a -> EdgeGraph a -> EdgeGraph a@@ -596,9 +602,9 @@ -- Complexity: /O(s)/ time, memory and size. -- -- @--- replaceEdge x x            == id+-- replaceEdge x x          == id -- replaceEdge x y ('EdgeGraph.edge' x) == 'EdgeGraph.edge' y--- replaceEdge x y            == 'mergeEdges' (== x) y+-- replaceEdge x y          == 'mergeEdges' (== x) y -- @ replaceEdge :: Eq a => a -> a -> EdgeGraph a -> EdgeGraph a replaceEdge u v = fmap $ \w -> if w == u then v else w@@ -609,7 +615,7 @@ -- -- @ -- mergeEdges (const False) x == id--- mergeEdges (== x) y        == 'replaceEdge' x y+-- mergeEdges (== x)        y == 'replaceEdge' x y -- @ mergeEdges :: Eq a => (a -> Bool) -> a -> EdgeGraph a -> EdgeGraph a mergeEdges p v = fmap $ \w -> if p w then v else w@@ -632,8 +638,8 @@ -- Complexity: /O(s)/ time, memory and size. -- -- @--- transpose 'EdgeGraph.empty'     == 'EdgeGraph.empty'--- transpose ('EdgeGraph.edge' x)  == 'EdgeGraph.edge' x+-- transpose 'EdgeGraph.empty'       == 'EdgeGraph.empty'+-- transpose ('EdgeGraph.edge' x)    == 'EdgeGraph.edge' x -- transpose . transpose == id -- @ transpose :: EdgeGraph a -> EdgeGraph a@@ -645,10 +651,10 @@ -- /O(1)/ to be evaluated. -- -- @--- induce (const True)  x        == x--- induce (const False) x        == 'EdgeGraph.empty'--- induce (/= x)                 == 'removeEdge' x--- induce p . induce q           == induce (\\x -> p x && q x)+-- induce (const True)  x      == x+-- induce (const False) x      == 'EdgeGraph.empty'+-- induce (/= x)               == 'removeEdge' x+-- induce p . induce q         == induce (\\x -> p x && q x) -- 'isSubgraphOf' (induce p x) x == True -- @ induce :: (a -> Bool) -> EdgeGraph a -> EdgeGraph a@@ -662,10 +668,10 @@ -- that the size of the result does not exceed the size of the given expression. -- -- @--- simplify x                         ==    x--- 'size' (simplify x)                <=    'size' x--- simplify 'EdgeGraph.empty'                   '===' 'EdgeGraph.empty'--- simplify ('EdgeGraph.edge' 1)                '===' 'EdgeGraph.edge' 1+-- simplify x                   ==    x+-- 'size' (simplify x)            <=    'size' x+-- simplify 'EdgeGraph.empty'               '===' 'EdgeGraph.empty'+-- simplify ('EdgeGraph.edge' 1)            '===' 'EdgeGraph.edge' 1 -- simplify ('EdgeGraph.edge' 1 'EdgeGraph.Class.+++' 'EdgeGraph.edge' 1) '===' 'EdgeGraph.edge' 1 -- @ simplify :: Ord a => EdgeGraph a -> EdgeGraph a@@ -684,7 +690,7 @@ -- -- @ -- box ('path' [0,1]) ('path' "ab") == 'edges' [ ((0,\'a\'),(0,\'b\')), ((0,\'a\'),(1,\'a\'))---                                             , ((0,\'b\'),(1,\'b\')), ((1,\'a\'),(1,\'b\')) ]+--                                       , ((0,\'b\'),(1,\'b\')), ((1,\'a\'),(1,\'b\')) ] -- @ -- Up to an isomorphism between the resulting edge types, this operation -- is /commutative/, /associative/, /distributes/ over 'overlay', has singleton@@ -692,8 +698,8 @@ -- stands for the equality up to an isomorphism, e.g. @(x, ()) ~~ x@. -- -- @--- box x y               ~~ box y x--- box x (box y z)       ~~ box (box x y) z+-- box x y             ~~ box y x+-- box x (box y z)     ~~ box (box x y) z -- box x ('overlay' y z) == 'overlay' (box x y) (box x z) -- box x ('EdgeGraph.edge' ())     ~~ x -- box x 'EdgeGraph.empty'         ~~ 'EdgeGraph.empty'@@ -701,13 +707,13 @@ box :: EdgeGraph a -> EdgeGraph b -> EdgeGraph (a, b) box = H.box --- | Convert an 'EdgeGraph' to the Boehm-Berarducci encoding ('F.Fold').+-- | Convert an 'EdgeGraph' to the Boehm-Berarducci encoding ('EdgeGraph.Fold.Fold'). -- This is useful for applying folds defined in "EdgeGraph.Fold",--- such as 'F.shortestPaths', 'F.reachable', and 'F.isAcyclic'.+-- such as 'EdgeGraph.Fold.shortestPaths', 'EdgeGraph.Fold.reachable', and 'EdgeGraph.Fold.isAcyclic'. -- -- @--- toFold 'EdgeGraph.empty'    == F.'F.empty'--- toFold ('EdgeGraph.edge' x) == F.'F.edge' x+-- toFold 'EdgeGraph.empty'    == 'EdgeGraph.Fold.empty'+-- toFold ('EdgeGraph.edge' x) == 'EdgeGraph.Fold.edge' x -- @ toFold :: EdgeGraph a -> F.Fold a toFold = foldg F.empty F.edge F.overlay F.into F.pits F.tips

@@ -122,9 +122,9 @@ -- i.e. the edges that the given edge flows into. -- -- @--- postset x 'EdgeGraph.AdjacencyMap.empty'                        == Set.'Set.empty'--- postset x ('EdgeGraph.AdjacencyMap.edge' x)                     == Set.'Set.empty'--- postset 1 ('into' ('EdgeGraph.AdjacencyMap.edge' 1) ('EdgeGraph.AdjacencyMap.edge' 2)) == Set.'Set.singleton' 2+-- postset x 'EdgeGraph.AdjacencyMap.empty'                    == 'Data.Set.empty'+-- postset x ('EdgeGraph.AdjacencyMap.edge' x)                 == 'Data.Set.empty'+-- postset 1 ('into' ('EdgeGraph.AdjacencyMap.edge' 1) ('EdgeGraph.AdjacencyMap.edge' 2)) == 'Data.Set.singleton' 2 -- @ postset :: Ord a => a -> AdjacencyMap a -> Set a postset a (AdjacencyMap m) = maybe Set.empty succs (Map.lookup a m)@@ -134,9 +134,9 @@ -- i.e. the edges that flow into the given edge. -- -- @--- preset x 'EdgeGraph.AdjacencyMap.empty'                        == Set.'Set.empty'--- preset x ('EdgeGraph.AdjacencyMap.edge' x)                     == Set.'Set.empty'--- preset 2 ('into' ('EdgeGraph.AdjacencyMap.edge' 1) ('EdgeGraph.AdjacencyMap.edge' 2)) == Set.'Set.singleton' 1+-- preset x 'EdgeGraph.AdjacencyMap.empty'                    == 'Data.Set.empty'+-- preset x ('EdgeGraph.AdjacencyMap.edge' x)                 == 'Data.Set.empty'+-- preset 2 ('into' ('EdgeGraph.AdjacencyMap.edge' 1) ('EdgeGraph.AdjacencyMap.edge' 2)) == 'Data.Set.singleton' 1 -- @ preset :: Ord a => a -> AdjacencyMap a -> Set a preset a (AdjacencyMap m) = maybe Set.empty preds (Map.lookup a m)@@ -153,8 +153,8 @@ -- directed flow from each edge to its successors. -- -- @--- 'dfsForest' 'EdgeGraph.AdjacencyMap.empty'                         == []--- 'dfsForest' ('EdgeGraph.AdjacencyMap.edge' x)                      == [Node x []]+-- 'dfsForest' 'EdgeGraph.AdjacencyMap.empty'                       == []+-- 'dfsForest' ('EdgeGraph.AdjacencyMap.edge' x)                    == [Node x []] -- 'isSubgraphOf' ('forest' $ 'dfsForest' x) x == True -- 'dfsForest' . 'forest' . 'dfsForest'        == 'dfsForest' -- @@@ -182,9 +182,9 @@ -- and no edge appears after one of its successors. -- -- @--- 'isTopSort' [] 'EdgeGraph.AdjacencyMap.empty'     == True+-- 'isTopSort' []  'EdgeGraph.AdjacencyMap.empty'    == True -- 'isTopSort' [x] ('EdgeGraph.AdjacencyMap.edge' x) == True--- 'isTopSort' [] ('EdgeGraph.AdjacencyMap.edge' x)  == False+-- 'isTopSort' []  ('EdgeGraph.AdjacencyMap.edge' x) == False -- @ isTopSort :: Ord a => [a] -> AdjacencyMap a -> Bool isTopSort xs m = go Set.empty xs@@ -198,9 +198,9 @@ -- Edges that form directed cycles are grouped into the same component. -- -- @--- 'scc' 'EdgeGraph.AdjacencyMap.empty'                          == 'EdgeGraph.AdjacencyMap.empty'--- 'scc' ('EdgeGraph.AdjacencyMap.edge' x)                       == 'EdgeGraph.AdjacencyMap.edge' (Set.'Set.singleton' x)--- 'scc' ('circuit' (1:xs))               == 'EdgeGraph.AdjacencyMap.edge' (Set.'Set.fromList' (1:xs))+-- 'scc' 'EdgeGraph.AdjacencyMap.empty'                        == 'EdgeGraph.AdjacencyMap.empty'+-- 'scc' ('EdgeGraph.AdjacencyMap.edge' x)                     == 'EdgeGraph.AdjacencyMap.edge' ('Data.Set.singleton' x)+-- 'scc' ('circuit' (1:xs))             == 'EdgeGraph.AdjacencyMap.edge' ('Data.Set.fromList' (1:xs)) -- 'edgeCount' ('scc' x) >= 'edgeCount' x == False -- @ scc :: Ord a => AdjacencyMap a -> AdjacencyMap (Set a)

@@ -59,11 +59,11 @@  -- | The t'AdjacencyMap' data type represents an edge-indexed graph as a map -- from each edge to its t'Adjacency' information. This is an equivalent--- representation to 'I.Incidence' (the canonical flow representation for+-- representation to 'EdgeGraph.Incidence.Internal.Incidence' (the canonical flow representation for -- algebraic edge graphs), but indexed by edge for efficient lookups. -- -- The 'Eq' instance is derived from the underlying 'Map' and is correct--- because the representation is canonical (one-to-one with 'I.Incidence').+-- because the representation is canonical (one-to-one with 'EdgeGraph.Incidence.Internal.Incidence'). newtype AdjacencyMap a = AdjacencyMap   { adjacencyMap :: Map a (Adjacency a)   } deriving Eq@@ -80,14 +80,14 @@   pits    = pits   tips    = tips --- | Convert an t'AdjacencyMap' to its equivalent 'I.Incidence' representation.+-- | Convert an t'AdjacencyMap' to its equivalent 'EdgeGraph.Incidence.Internal.Incidence' representation. -- -- For each edge, reconstruct its source node (pitNode) and sink node (tipNode), -- then collect all unique nodes into a set. -- -- @--- 'toIncidence' 'EdgeGraph.AdjacencyMap.Internal.empty'    == 'I.empty'--- 'toIncidence' ('EdgeGraph.AdjacencyMap.Internal.edge' x) == 'I.edge' x+-- 'toIncidence' 'EdgeGraph.AdjacencyMap.Internal.empty'    == 'EdgeGraph.Incidence.Internal.empty'+-- 'toIncidence' ('EdgeGraph.AdjacencyMap.Internal.edge' x) == 'EdgeGraph.Incidence.Internal.edge' x -- @ toIncidence :: Ord a => AdjacencyMap a -> I.Incidence a toIncidence (AdjacencyMap m)@@ -100,14 +100,14 @@       , I.Node (joins adj) (succs adj)   -- sink node       ] --- | Convert an 'I.Incidence' to an t'AdjacencyMap'.+-- | Convert an 'EdgeGraph.Incidence.Internal.Incidence' to an t'AdjacencyMap'. -- -- Scans all nodes once to build edge-to-source and edge-to-sink maps, -- then constructs the t'Adjacency' record for each edge. -- -- @--- 'fromIncidence' 'I.empty'    == 'EdgeGraph.AdjacencyMap.Internal.empty'--- 'fromIncidence' ('I.edge' x) == 'EdgeGraph.AdjacencyMap.Internal.edge' x+-- 'fromIncidence' 'EdgeGraph.Incidence.Internal.empty'    == 'EdgeGraph.AdjacencyMap.Internal.empty'+-- 'fromIncidence' ('EdgeGraph.Incidence.Internal.edge' x) == 'EdgeGraph.AdjacencyMap.Internal.edge' x -- @ fromIncidence :: Ord a => I.Incidence a -> AdjacencyMap a fromIncidence (I.Incidence ns)@@ -216,12 +216,12 @@ -- representations by merging nodes that share edges. -- -- @--- 'isEmpty' ('overlay' x y)   == 'isEmpty' x && 'isEmpty' y--- 'overlay' 'EdgeGraph.AdjacencyMap.Internal.empty' x         == x--- 'overlay' x 'EdgeGraph.AdjacencyMap.Internal.empty'         == x--- 'overlay' x y               == 'overlay' y x--- 'overlay' x ('overlay' y z) == 'overlay' ('overlay' x y) z--- 'overlay' x x               == x+-- 'isEmpty' ('overlay' x y)       == 'isEmpty' x && 'isEmpty' y+-- 'overlay' 'EdgeGraph.AdjacencyMap.Internal.empty' x             == x+-- 'overlay' x     'EdgeGraph.AdjacencyMap.Internal.empty'         == x+-- 'overlay' x     y             == 'overlay' y x+-- 'overlay' x     ('overlay' y z) == 'overlay' ('overlay' x y) z+-- 'overlay' x     x             == x -- @ overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a overlay x y = fromIncidence $ I.overlay (toIncidence x) (toIncidence y)@@ -312,7 +312,7 @@ -- -- @ -- adjacencyList 'EdgeGraph.AdjacencyMap.Internal.empty'    == []--- adjacencyList ('EdgeGraph.AdjacencyMap.Internal.edge' x) == [(x, Adjacency (Set.'Data.Set.singleton' x) (Set.'Data.Set.singleton' x) Set.'Data.Set.empty' Set.'Data.Set.empty')]+-- adjacencyList ('EdgeGraph.AdjacencyMap.Internal.edge' x) == [(x, Adjacency ('Data.Set.singleton' x) ('Data.Set.singleton' x) 'Data.Set.empty' 'Data.Set.empty')] -- @ adjacencyList :: AdjacencyMap a -> [(a, Adjacency a)] adjacencyList (AdjacencyMap m) = Map.toAscList m@@ -358,9 +358,9 @@ -- Complexity: /O((|forks| + |preds|) * log n)/ time. -- -- @--- detachPit x ('EdgeGraph.AdjacencyMap.Internal.edge' x)                      == 'EdgeGraph.AdjacencyMap.Internal.edge' x--- detachPit 2 ('into' ('EdgeGraph.AdjacencyMap.Internal.edge' 1) ('EdgeGraph.AdjacencyMap.Internal.edge' 2))  == 'edges' [1, 2]--- detachPit 1 ('pits' ('EdgeGraph.AdjacencyMap.Internal.edge' 1) ('EdgeGraph.AdjacencyMap.Internal.edge' 2))  == 'edges' [1, 2]+-- detachPit x ('EdgeGraph.AdjacencyMap.Internal.edge' x)                 == 'EdgeGraph.AdjacencyMap.Internal.edge' x+-- detachPit 2 ('into' ('EdgeGraph.AdjacencyMap.Internal.edge' 1) ('EdgeGraph.AdjacencyMap.Internal.edge' 2)) == 'edges' [1, 2]+-- detachPit 1 ('pits' ('EdgeGraph.AdjacencyMap.Internal.edge' 1) ('EdgeGraph.AdjacencyMap.Internal.edge' 2)) == 'edges' [1, 2] -- @ detachPit :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a detachPit a (AdjacencyMap m) = case Map.lookup a m of@@ -383,9 +383,9 @@ -- Complexity: /O((|joins| + |succs|) * log n)/ time. -- -- @--- detachTip x ('EdgeGraph.AdjacencyMap.Internal.edge' x)                      == 'EdgeGraph.AdjacencyMap.Internal.edge' x--- detachTip 1 ('into' ('EdgeGraph.AdjacencyMap.Internal.edge' 1) ('EdgeGraph.AdjacencyMap.Internal.edge' 2))  == 'edges' [1, 2]--- detachTip 1 ('tips' ('EdgeGraph.AdjacencyMap.Internal.edge' 1) ('EdgeGraph.AdjacencyMap.Internal.edge' 2))  == 'edges' [1, 2]+-- detachTip x ('EdgeGraph.AdjacencyMap.Internal.edge' x)                 == 'EdgeGraph.AdjacencyMap.Internal.edge' x+-- detachTip 1 ('into' ('EdgeGraph.AdjacencyMap.Internal.edge' 1) ('EdgeGraph.AdjacencyMap.Internal.edge' 2)) == 'edges' [1, 2]+-- detachTip 1 ('tips' ('EdgeGraph.AdjacencyMap.Internal.edge' 1) ('EdgeGraph.AdjacencyMap.Internal.edge' 2)) == 'edges' [1, 2] -- @ detachTip :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a detachTip a (AdjacencyMap m) = case Map.lookup a m of@@ -408,8 +408,8 @@ -- @ -- gmap f 'EdgeGraph.AdjacencyMap.Internal.empty'    == 'EdgeGraph.AdjacencyMap.Internal.empty' -- gmap f ('EdgeGraph.AdjacencyMap.Internal.edge' x) == 'EdgeGraph.AdjacencyMap.Internal.edge' (f x)--- gmap id           == id--- gmap f . gmap g   == gmap (f . g)+-- gmap id         == id+-- gmap f . gmap g == gmap (f . g) -- @ gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap b gmap f = fromIncidence . I.gmap f . toIncidence

@@ -49,10 +49,10 @@     * 'overlay' is commutative, associative, and idempotent with 'EdgeGraph.Class.empty' as       the identity: -        >         x +++ y == y +++ x+        > x +++ y         == y +++ x         > x +++ (y +++ z) == (x +++ y) +++ z-        >         x +++ x == x-        >     x +++ empty == x+        > x +++ x         == x+        > x +++ empty     == x      * 'EdgeGraph.Class.empty' is the identity for 'into', 'pits', and 'tips': @@ -105,7 +105,7 @@     * Absorption and saturation for each connect operator (shown for 'into'):          > x >+> y +++ x +++ y == x >+> y-        > x >+> x == (x >+> x) >+> x+        > x >+> x             == (x >+> x) >+> x  When specifying the time and memory complexity of graph algorithms, /n/ will denote the number of edges in the graph, /m/ will denote the number of@@ -249,9 +249,9 @@ -- a particular graph instance. -- -- @--- isSubgraphOf 'EdgeGraph.Class.empty'    x               == True+-- isSubgraphOf 'EdgeGraph.Class.empty'    x             == True -- isSubgraphOf ('edge' x) 'EdgeGraph.Class.empty'         == False--- isSubgraphOf x          ('overlay' x y) == True+-- isSubgraphOf x        ('overlay' x y) == True -- @ isSubgraphOf :: (EdgeGraph g, Eq g) => g -> g -> Bool isSubgraphOf x y = overlay x y == y@@ -337,12 +337,12 @@ -- lengths of the given lists. -- -- @--- node []  []    == 'EdgeGraph.Class.empty'--- node [x] []    == 'edge' x--- node []  [y]   == 'edge' y--- node [x] [y]   == 'into' ('edge' x) ('edge' y)--- node [x] [y,z] == 'into' ('edge' x) ('tips' ('edge' y) ('edge' z))--- node [x,y] [z] == 'into' ('pits' ('edge' x) ('edge' y)) ('edge' z)+-- node []    []    == 'EdgeGraph.Class.empty'+-- node [x]   []    == 'edge' x+-- node []    [y]   == 'edge' y+-- node [x]   [y]   == 'into' ('edge' x) ('edge' y)+-- node [x]   [y,z] == 'into' ('edge' x) ('tips' ('edge' y) ('edge' z))+-- node [x,y] [z]   == 'into' ('pits' ('edge' x) ('edge' y)) ('edge' z) -- @ node :: EdgeGraph g => [Edge g] -> [Edge g] -> g node xs ys = pitss (map edge xs) `into` tipss (map edge ys)

@@ -71,12 +71,12 @@  The 'Show' instance is defined using basic graph construction primitives: -@show ('EdgeGraph.Fold.empty'                            :: Fold Int) == "empty"-show ('edge' 1                           :: Fold Int) == "edge 1"-show ('overlay' ('edge' 1) ('edge' 2)    :: Fold Int) == "edges [1,2]"-show ('into' ('edge' 1) ('edge' 2)       :: Fold Int) == "into (edge 1) (edge 2)"@+@show ('EdgeGraph.Fold.empty'                     :: Fold Int) == "empty"+show ('edge' 1                    :: Fold Int) == "edge 1"+show ('overlay' ('edge' 1) ('edge' 2) :: Fold Int) == "edges [1,2]"+show ('into' ('edge' 1) ('edge' 2)    :: Fold Int) == "into (edge 1) (edge 2)"@ -The 'Eq' instance is currently implemented using the 'I.Incidence' as the+The 'Eq' instance is currently implemented using the 'EdgeGraph.Incidence.Incidence' as the /canonical graph representation/ and satisfies all axioms of algebraic edge graphs. In equations we use the infix operators '(EdgeGraph.Class.+++)' for 'overlay', '(EdgeGraph.Class.>+>)' for 'into', '(EdgeGraph.Class.<+>)' for 'pits', and '(EdgeGraph.Class.>+<)' for 'tips'.@@ -110,17 +110,17 @@ 'Foldable' type class, as the latter does not count 'EdgeGraph.Fold.empty' leaves of the expression: -@'length' 'EdgeGraph.Fold.empty'              == 0-'size'   'EdgeGraph.Fold.empty'               == 1-'length' ('edge' x)            == 1-'size'   ('edge' x)            == 1+@'length' 'EdgeGraph.Fold.empty'             == 0+'size'   'EdgeGraph.Fold.empty'             == 1+'length' ('edge' x)          == 1+'size'   ('edge' x)          == 1 'length' ('EdgeGraph.Fold.empty' +++ 'EdgeGraph.Fold.empty') == 0 'size'   ('EdgeGraph.Fold.empty' +++ 'EdgeGraph.Fold.empty') == 2@  The 'size' of any graph is positive, and the difference @('size' g - 'length' g)@ corresponds to the number of occurrences of 'EdgeGraph.Fold.empty' in an expression @g@. -Converting a t'Fold' to the corresponding 'I.Incidence' takes /O(s + m * log(m))/+Converting a t'Fold' to the corresponding 'EdgeGraph.Incidence.Incidence' takes /O(s + m * log(m))/ time and /O(s + m)/ memory. This is also the complexity of the graph equality test, because it is currently implemented by converting graph expressions to canonical representations based on incidences.@@ -280,10 +280,10 @@ -- @ -- foldg 'EdgeGraph.Fold.empty' 'edge' 'overlay' 'into' 'pits' 'tips'        == id -- foldg 'EdgeGraph.Fold.empty' 'edge' 'overlay' (flip 'into') 'tips' 'pits' == 'transpose'--- foldg [] return (++) (++) (++) (++)                        == 'Data.Foldable.toList'--- foldg 0 (const 1) (+) (+) (+) (+)                          == 'Data.Foldable.length'--- foldg 1 (const 1) (+) (+) (+) (+)                          == 'size'--- foldg True (const False) (&&) (&&) (&&) (&&)               == 'isEmpty'+-- foldg [] return (++) (++) (++) (++)            == 'Data.Foldable.toList'+-- foldg 0 (const 1) (+) (+) (+) (+)              == 'Data.Foldable.length'+-- foldg 1 (const 1) (+) (+) (+) (+)              == 'size'+-- foldg True (const False) (&&) (&&) (&&) (&&)   == 'isEmpty' -- @ foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> (b -> b -> b) -> (b -> b -> b) -> Fold a -> b foldg e v o i p t g = runFold g e v o i p t@@ -292,9 +292,9 @@ -- Complexity: /O(s)/ time. -- -- @--- isEmpty 'EdgeGraph.Fold.empty'                     == True--- isEmpty ('overlay' 'EdgeGraph.Fold.empty' 'EdgeGraph.Fold.empty') == True--- isEmpty ('edge' x)                  == False+-- isEmpty 'EdgeGraph.Fold.empty'                   == True+-- isEmpty ('overlay' 'EdgeGraph.Fold.empty' 'EdgeGraph.Fold.empty')   == True+-- isEmpty ('edge' x)                == False -- isEmpty ('removeEdge' x $ 'edge' x) == True -- @ isEmpty :: Fold a -> Bool@@ -309,7 +309,7 @@ -- size ('edge' x)      == 1 -- size ('overlay' x y) == size x + size y -- size ('into' x y)    == size x + size y--- size x               >= 1+-- size x             >= 1 -- @ size :: Fold a -> Int size = foldg 1 (const 1) (+) (+) (+) (+)@@ -331,7 +331,7 @@ -- @ -- edgeCount 'EdgeGraph.Fold.empty'    == 0 -- edgeCount ('edge' x) == 1--- edgeCount            == 'length' . 'edgeList'+-- edgeCount          == 'length' . 'edgeList' -- @ edgeCount :: Ord a => Fold a -> Int edgeCount = I.edgeCount . toIncidence@@ -350,8 +350,8 @@ -- Complexity: /O(s * log(n))/ time and /O(n)/ memory. -- -- @--- edgeSet 'EdgeGraph.Fold.empty'  == Set.'Set.empty'--- edgeSet . 'edge' == Set.'Set.singleton'+-- edgeSet 'EdgeGraph.Fold.empty'  == 'Data.Set.empty'+-- edgeSet . 'edge' == 'Data.Set.singleton' -- @ edgeSet :: Ord a => Fold a -> Set.Set a edgeSet = I.edgeSet . toIncidence@@ -361,8 +361,8 @@ -- Complexity: /O(s * log(n))/ time and /O(n)/ memory. -- -- @--- edgeIntSet 'EdgeGraph.Fold.empty'  == IntSet.'IntSet.empty'--- edgeIntSet . 'edge' == IntSet.'IntSet.singleton'+-- edgeIntSet 'EdgeGraph.Fold.empty'  == 'Data.IntSet.empty'+-- edgeIntSet . 'edge' == 'Data.IntSet.singleton' -- @ edgeIntSet :: Fold Int -> IntSet.IntSet edgeIntSet = I.edgeIntSet . toIncidence@@ -390,7 +390,7 @@ -- Complexity: /O(s * log(m))/ time and /O(m)/ memory. -- -- @--- nodeSet 'EdgeGraph.Fold.empty' == Set.'Set.empty'+-- nodeSet 'EdgeGraph.Fold.empty' == 'Data.Set.empty' -- @ nodeSet :: Ord a => Fold a -> Set.Set (I.Node a) nodeSet = I.nodeSet . toIncidence@@ -449,7 +449,7 @@ -- Complexity: /O(s)/ time, memory and size. -- -- @--- removeEdge x ('edge' x)     == 'EdgeGraph.Fold.empty'+-- removeEdge x ('edge' x)       == 'EdgeGraph.Fold.empty' -- removeEdge x . removeEdge x == removeEdge x -- @ removeEdge :: (Eq (C.Edge g), C.EdgeGraph g) => C.Edge g -> Fold (C.Edge g) -> g@@ -460,9 +460,9 @@ -- Complexity: /O(s)/ time, memory and size. -- -- @--- replaceEdge x x            == id+-- replaceEdge x x          == id -- replaceEdge x y ('edge' x) == 'edge' y--- replaceEdge x y            == 'mergeEdges' (== x) y+-- replaceEdge x y          == 'mergeEdges' (== x) y -- @ replaceEdge :: (Eq (C.Edge g), C.EdgeGraph g) => C.Edge g -> C.Edge g -> Fold (C.Edge g) -> g replaceEdge u v = gmap $ \w -> if w == u then v else w@@ -473,7 +473,7 @@ -- -- @ -- mergeEdges (const False) x == id--- mergeEdges (== x) y        == 'replaceEdge' x y+-- mergeEdges (== x)        y == 'replaceEdge' x y -- @ mergeEdges :: C.EdgeGraph g => (C.Edge g -> Bool) -> C.Edge g -> Fold (C.Edge g) -> g mergeEdges p v = gmap $ \u -> if p u then v else u@@ -495,8 +495,8 @@ -- Complexity: /O(s)/ time, memory and size. -- -- @--- transpose 'EdgeGraph.Fold.empty'     == 'EdgeGraph.Fold.empty'--- transpose ('edge' x)  == 'edge' x+-- transpose 'EdgeGraph.Fold.empty'       == 'EdgeGraph.Fold.empty'+-- transpose ('edge' x)    == 'edge' x -- transpose . transpose == id -- @ transpose :: C.EdgeGraph g => Fold (C.Edge g) -> g@@ -508,8 +508,8 @@ -- @ -- gmap f 'EdgeGraph.Fold.empty'    == 'EdgeGraph.Fold.empty' -- gmap f ('edge' x) == 'edge' (f x)--- gmap id           == id--- gmap f . gmap g   == gmap (f . g)+-- gmap id         == id+-- gmap f . gmap g == gmap (f . g) -- @ gmap :: C.EdgeGraph g => (a -> C.Edge g) -> Fold a -> g gmap f = foldg C.empty (C.edge . f) C.overlay C.into C.pits C.tips@@ -524,7 +524,7 @@ -- bind ('edges' xs) f    == 'overlays' ('map' f xs) -- bind x (const 'EdgeGraph.Fold.empty') == 'EdgeGraph.Fold.empty' -- bind x 'edge'          == x--- bind (bind x f) g      == bind x (\\y -> bind (f y) g)+-- bind (bind x f) g    == bind x (\\y -> bind (f y) g) -- @ bind :: C.EdgeGraph g => Fold a -> (a -> g) -> g bind g f = foldg C.empty f C.overlay C.into C.pits C.tips g@@ -551,10 +551,10 @@ -- that the size of the result does not exceed the size of the given expression. -- -- @--- simplify x                     == x--- 'size' (simplify x)            <= 'size' x--- simplify 'EdgeGraph.Fold.empty'               ~> 'EdgeGraph.Fold.empty'--- simplify ('edge' 1)            ~> 'edge' 1+-- simplify x                 == x+-- 'size' (simplify x)          <= 'size' x+-- simplify 'EdgeGraph.Fold.empty'             ~> 'EdgeGraph.Fold.empty'+-- simplify ('edge' 1)          ~> 'edge' 1 -- simplify ('edge' 1 + 'edge' 1) ~> 'edge' 1 -- @ simplify :: (Eq g, C.EdgeGraph g) => Fold (C.Edge g) -> g@@ -574,7 +574,7 @@ -- -- @ -- box ('EdgeGraph.Class.path' [0,1]) ('EdgeGraph.Class.path' "ab") == 'edges' [ ((0,\'a\'),(0,\'b\')), ((0,\'a\'),(1,\'a\'))---                                          , ((0,\'b\'),(1,\'b\')), ((1,\'a\'),(1,\'b\')) ]+--                                       , ((0,\'b\'),(1,\'b\')), ((1,\'a\'),(1,\'b\')) ] -- @ -- Up to an isomorphism between the resulting edge types, this operation -- is /commutative/, /associative/, /distributes/ over 'overlay', has singleton@@ -582,8 +582,8 @@ -- stands for the equality up to an isomorphism, e.g. @(x, ()) ~~ x@. -- -- @--- box x y               ~~ box y x--- box x (box y z)       ~~ box (box x y) z+-- box x y             ~~ box y x+-- box x (box y z)     ~~ box (box x y) z -- box x ('overlay' y z) == 'overlay' (box x y) (box x z) -- box x ('edge' ())     ~~ x -- box x 'EdgeGraph.Fold.empty'         ~~ 'EdgeGraph.Fold.empty'@@ -606,9 +606,9 @@ -- | Compute shortest paths between edge endpoints using a weight function. -- -- @--- shortestPaths id    g -- use edge labels as weights--- shortestPaths (const 1) g -- unit-weight shortest paths (hop count)--- shortestPaths id 'EdgeGraph.Fold.empty' == Map.'Map.empty'+-- shortestPaths id 'EdgeGraph.Fold.empty' == 'Data.Map.Strict.empty'+-- shortestPaths (const 1) g               -- unit-weight shortest paths (hop count)+-- shortestPaths id        g               -- use edge labels as weights -- @ shortestPaths :: (Ord a, Num w, Ord w)               => (a -> w) -> Fold a -> Map.Map (End a, End a) w@@ -639,7 +639,7 @@ -- | Compute reachability between edge endpoints. -- -- @--- reachable 'EdgeGraph.Fold.empty'  == Map.'Map.empty'+-- reachable 'EdgeGraph.Fold.empty' == 'Data.Map.Strict.empty' -- @ reachable :: Ord a => Fold a -> Map.Map (End a, End a) Bool reachable = semiringPaths (||) (&&) True (const True)@@ -656,8 +656,8 @@ -- | Check if the graph is acyclic. -- -- @--- isAcyclic 'EdgeGraph.Fold.empty'                        == True--- isAcyclic ('edge' 1)                     == True+-- isAcyclic 'EdgeGraph.Fold.empty'                    == True+-- isAcyclic ('edge' 1)                 == True -- isAcyclic ('into' ('edge' 1) ('edge' 1)) == False -- @ isAcyclic :: Ord a => Fold a -> Bool

@@ -74,10 +74,10 @@     * 'overlay' is commutative, associative, and idempotent with 'EdgeGraph.HigherKinded.Class.empty' as       the identity: -        >         x +++ y == y +++ x+        > x +++ y         == y +++ x         > x +++ (y +++ z) == (x +++ y) +++ z-        >         x +++ x == x-        >     x +++ empty == x+        > x +++ x         == x+        > x +++ empty     == x      * 'EdgeGraph.HigherKinded.Class.empty' is the identity for 'into', 'pits', and 'tips': @@ -130,7 +130,7 @@     * Absorption and saturation for each connect operator (shown for 'into'):          > x >+> y +++ x +++ y == x >+> y-        > x >+> x == (x >+> x) >+> x+        > x >+> x             == (x >+> x) >+> x  When specifying the time and memory complexity of graph algorithms, /n/ will denote the number of edges in the graph, /m/ will denote the number of@@ -206,9 +206,9 @@ -- a particular graph instance. -- -- @--- isSubgraphOf 'EdgeGraph.HigherKinded.Class.empty'    x               == True+-- isSubgraphOf 'EdgeGraph.HigherKinded.Class.empty'    x             == True -- isSubgraphOf ('edge' x) 'EdgeGraph.HigherKinded.Class.empty'         == False--- isSubgraphOf x          ('overlay' x y) == True+-- isSubgraphOf x        ('overlay' x y) == True -- @ isSubgraphOf :: (EdgeGraph g, Eq (g a)) => g a -> g a -> Bool isSubgraphOf x y = overlay x y == y@@ -217,9 +217,9 @@ -- Complexity: /O(s)/ time. -- -- @--- isEmpty 'EdgeGraph.HigherKinded.Class.empty'                     == True--- isEmpty ('overlay' 'EdgeGraph.HigherKinded.Class.empty' 'EdgeGraph.HigherKinded.Class.empty') == True--- isEmpty ('edge' x)                  == False+-- isEmpty 'EdgeGraph.HigherKinded.Class.empty'                   == True+-- isEmpty ('overlay' 'EdgeGraph.HigherKinded.Class.empty' 'EdgeGraph.HigherKinded.Class.empty')   == True+-- isEmpty ('edge' x)                == False -- isEmpty ('removeEdge' x $ 'edge' x) == True -- @ isEmpty :: EdgeGraph g => g a -> Bool@@ -242,7 +242,7 @@ -- @ -- edgeCount 'EdgeGraph.HigherKinded.Class.empty'    == 0 -- edgeCount ('edge' x) == 1--- edgeCount            == 'length' . 'edgeList'+-- edgeCount          == 'length' . 'edgeList' -- @ edgeCount :: (Ord a, EdgeGraph g) => g a -> Int edgeCount = length . edgeList@@ -261,8 +261,8 @@ -- Complexity: /O(s * log(n))/ time and /O(n)/ memory. -- -- @--- edgeSet 'EdgeGraph.HigherKinded.Class.empty'  == Set.'Set.empty'--- edgeSet . 'edge' == Set.'Set.singleton'+-- edgeSet 'EdgeGraph.HigherKinded.Class.empty'  == 'Data.Set.empty'+-- edgeSet . 'edge' == 'Data.Set.singleton' -- @ edgeSet :: (Ord a, EdgeGraph g) => g a -> Set.Set a edgeSet = foldr Set.insert Set.empty@@ -272,8 +272,8 @@ -- Complexity: /O(s * log(n))/ time and /O(n)/ memory. -- -- @--- edgeIntSet 'EdgeGraph.HigherKinded.Class.empty'  == IntSet.'IntSet.empty'--- edgeIntSet . 'edge' == IntSet.'IntSet.singleton'+-- edgeIntSet 'EdgeGraph.HigherKinded.Class.empty'  == 'Data.IntSet.empty'+-- edgeIntSet . 'edge' == 'Data.IntSet.singleton' -- @ edgeIntSet :: EdgeGraph g => g Int -> IntSet.IntSet edgeIntSet = foldr IntSet.insert IntSet.empty@@ -359,12 +359,12 @@ -- lengths of the given lists. -- -- @--- node []  []    == 'EdgeGraph.HigherKinded.Class.empty'--- node [x] []    == 'edge' x--- node []  [y]   == 'edge' y--- node [x] [y]   == 'into' ('edge' x) ('edge' y)--- node [x] [y,z] == 'into' ('edge' x) ('tips' ('edge' y) ('edge' z))--- node [x,y] [z] == 'into' ('pits' ('edge' x) ('edge' y)) ('edge' z)+-- node []    []    == 'EdgeGraph.HigherKinded.Class.empty'+-- node [x]   []    == 'edge' x+-- node []    [y]   == 'edge' y+-- node [x]   [y]   == 'into' ('edge' x) ('edge' y)+-- node [x]   [y,z] == 'into' ('edge' x) ('tips' ('edge' y) ('edge' z))+-- node [x,y] [z]   == 'into' ('pits' ('edge' x) ('edge' y)) ('edge' z) -- @ node :: EdgeGraph g => [a] -> [a] -> g a node xs ys = pitss (map edge xs) `into` tipss (map edge ys)@@ -386,9 +386,9 @@ -- lengths of the given lists. -- -- @--- mesh xs     []   == 'EdgeGraph.HigherKinded.Class.empty'--- mesh []     ys   == 'EdgeGraph.HigherKinded.Class.empty'--- mesh [x]    [y]  == 'edge' (x, y)+-- mesh xs  []  == 'EdgeGraph.HigherKinded.Class.empty'+-- mesh []  ys  == 'EdgeGraph.HigherKinded.Class.empty'+-- mesh [x] [y] == 'edge' (x, y) -- @ mesh :: EdgeGraph g => [a] -> [b] -> g (a, b) mesh xs ys = path xs `box` path ys@@ -398,8 +398,8 @@ -- lengths of the given lists. -- -- @--- torus xs     []   == 'EdgeGraph.HigherKinded.Class.empty'--- torus []     ys   == 'EdgeGraph.HigherKinded.Class.empty'+-- torus xs [] == 'EdgeGraph.HigherKinded.Class.empty'+-- torus [] ys == 'EdgeGraph.HigherKinded.Class.empty' -- @ torus :: EdgeGraph g => [a] -> [b] -> g (a, b) torus xs ys = circuit xs `box` circuit ys@@ -423,7 +423,7 @@ -- Complexity: /O(s)/ time, memory and size. -- -- @--- removeEdge x ('edge' x)     == 'EdgeGraph.HigherKinded.Class.empty'+-- removeEdge x ('edge' x)       == 'EdgeGraph.HigherKinded.Class.empty' -- removeEdge x . removeEdge x == removeEdge x -- @ removeEdge :: (Eq a, EdgeGraph g) => a -> g a -> g a@@ -434,9 +434,9 @@ -- Complexity: /O(s)/ time, memory and size. -- -- @--- replaceEdge x x            == id+-- replaceEdge x x          == id -- replaceEdge x y ('edge' x) == 'edge' y--- replaceEdge x y            == 'mergeEdges' (== x) y+-- replaceEdge x y          == 'mergeEdges' (== x) y -- @ replaceEdge :: (Eq a, EdgeGraph g) => a -> a -> g a -> g a replaceEdge u v = fmap $ \w -> if w == u then v else w@@ -447,7 +447,7 @@ -- -- @ -- mergeEdges (const False) x == id--- mergeEdges (== x) y        == 'replaceEdge' x y+-- mergeEdges (== x)        y == 'replaceEdge' x y -- @ mergeEdges :: (Eq a, EdgeGraph g) => (a -> Bool) -> a -> g a -> g a mergeEdges p v = fmap $ \w -> if p w then v else w@@ -485,7 +485,7 @@ -- -- @ -- box ('path' [0,1]) ('path' "ab") == 'edges' [ ((0,\'a\'),(0,\'b\')), ((0,\'a\'),(1,\'a\'))---                                          , ((0,\'b\'),(1,\'b\')), ((1,\'a\'),(1,\'b\')) ]+--                                       , ((0,\'b\'),(1,\'b\')), ((1,\'a\'),(1,\'b\')) ] -- @ -- Up to an isomorphism between the resulting edge types, this operation -- is /commutative/, /associative/, /distributes/ over 'overlay', has singleton@@ -493,8 +493,8 @@ -- stands for the equality up to an isomorphism, e.g. @(x, ()) ~~ x@. -- -- @--- box x y               ~~ box y x--- box x (box y z)       ~~ box (box x y) z+-- box x y             ~~ box y x+-- box x (box y z)     ~~ box (box x y) z -- box x ('overlay' y z) == 'overlay' (box x y) (box x z) -- box x ('edge' ())     ~~ x -- box x 'EdgeGraph.HigherKinded.Class.empty'         ~~ 'EdgeGraph.HigherKinded.Class.empty'

@@ -48,9 +48,9 @@ -- Complexity: /O(n^2 * m)/ time. -- -- @--- isSubgraphOf 'EdgeGraph.Incidence.empty' x          == True--- isSubgraphOf ('edge' x) 'EdgeGraph.Incidence.empty' == False--- isSubgraphOf x ('overlay' x y)  == True+-- isSubgraphOf 'EdgeGraph.Incidence.empty' x         == True+-- isSubgraphOf ('edge' x) 'EdgeGraph.Incidence.empty'  == False+-- isSubgraphOf x ('overlay' x y) == True -- @ isSubgraphOf :: Ord a => Incidence a -> Incidence a -> Bool isSubgraphOf x y = overlay x y == y@@ -163,9 +163,9 @@ -- Complexity: /O(n * m * log(m))/ time. -- -- @--- replaceEdge x x            == id+-- replaceEdge x x          == id -- replaceEdge x y ('edge' x) == 'edge' y--- replaceEdge x y            == 'mergeEdges' (== x) y+-- replaceEdge x y          == 'mergeEdges' (== x) y -- @ replaceEdge :: Ord a => a -> a -> Incidence a -> Incidence a replaceEdge u v = gmap (\w -> if w == u then v else w)@@ -176,7 +176,7 @@ -- -- @ -- mergeEdges (const False) x == id--- mergeEdges (== x) y        == 'replaceEdge' x y+-- mergeEdges (== x)        y == 'replaceEdge' x y -- @ mergeEdges :: Ord a => (a -> Bool) -> a -> Incidence a -> Incidence a mergeEdges p v = gmap (\u -> if p u then v else u)@@ -186,8 +186,8 @@ -- Complexity: /O(n * m)/ time. -- -- @--- edgeIntSet 'EdgeGraph.Incidence.empty'    == IntSet.'IntSet.empty'--- edgeIntSet ('edge' x) == IntSet.'IntSet.singleton' x+-- edgeIntSet 'EdgeGraph.Incidence.empty'    == 'Data.IntSet.empty'+-- edgeIntSet ('edge' x) == 'Data.IntSet.singleton' x -- @ edgeIntSet :: Incidence Int -> IntSet.IntSet edgeIntSet = IntSet.fromAscList . edgeList

@@ -219,12 +219,12 @@ -- Complexity: /O(n^2 * m)/ time. -- -- @--- 'isEmpty' ('overlay' x y)   == 'isEmpty' x && 'isEmpty' y--- 'overlay' 'EdgeGraph.Incidence.Internal.empty' x         == x--- 'overlay' x 'EdgeGraph.Incidence.Internal.empty'         == x--- 'overlay' x y               == 'overlay' y x--- 'overlay' x ('overlay' y z) == 'overlay' ('overlay' x y) z--- 'overlay' x x               == x+-- 'isEmpty' ('overlay' x y)       == 'isEmpty' x && 'isEmpty' y+-- 'overlay' 'EdgeGraph.Incidence.Internal.empty' x             == x+-- 'overlay' x     'EdgeGraph.Incidence.Internal.empty'         == x+-- 'overlay' x     y             == 'overlay' y x+-- 'overlay' x     ('overlay' y z) == 'overlay' ('overlay' x y) z+-- 'overlay' x     x             == x -- @ overlay :: Ord a => Incidence a -> Incidence a -> Incidence a overlay (Incidence xs) (Incidence ys) =@@ -245,9 +245,9 @@ -- Complexity: /O((n + |E_l| * |E_r|)^2 * m)/ time. -- -- @--- 'isEmpty' ('into' x y)       == 'isEmpty' x && 'isEmpty' y--- 'into' 'EdgeGraph.Incidence.Internal.empty' x             == x--- 'into' x 'EdgeGraph.Incidence.Internal.empty'             == x+-- 'isEmpty' ('into' x y)     == 'isEmpty' x && 'isEmpty' y+-- 'into' 'EdgeGraph.Incidence.Internal.empty' x           == x+-- 'into' x 'EdgeGraph.Incidence.Internal.empty'           == x -- 'into' ('edge' x) ('edge' y) /= 'overlay' ('edge' x) ('edge' y) -- @ into :: Ord a => Incidence a -> Incidence a -> Incidence a@@ -308,8 +308,8 @@ -- Complexity: /O(L^2 * log(L))/ time and /O(L)/ memory. -- -- @--- edges []    == 'EdgeGraph.Incidence.Internal.empty'--- edges [x]   == 'edge' x+-- edges []  == 'EdgeGraph.Incidence.Internal.empty'+-- edges [x] == 'edge' x -- @ edges :: Ord a => [a] -> Incidence a edges = foldr overlay empty . map edge@@ -393,9 +393,9 @@ -- Complexity: /O(n * log(n))/ time. -- -- @--- detachPit x ('edge' x)                      == 'edge' x--- detachPit 2 ('into' ('edge' 1) ('edge' 2))  == 'edges' [1, 2]--- detachPit 1 ('pits' ('edge' 1) ('edge' 2))  == 'edges' [1, 2]+-- detachPit x ('edge' x)                 == 'edge' x+-- detachPit 2 ('into' ('edge' 1) ('edge' 2)) == 'edges' [1, 2]+-- detachPit 1 ('pits' ('edge' 1) ('edge' 2)) == 'edges' [1, 2] -- @ detachPit :: Ord a => a -> Incidence a -> Incidence a detachPit a r@(Incidence ns)@@ -419,9 +419,9 @@ -- Complexity: /O(n * log(n))/ time. -- -- @--- detachTip x ('edge' x)                      == 'edge' x--- detachTip 1 ('into' ('edge' 1) ('edge' 2))  == 'edges' [1, 2]--- detachTip 1 ('tips' ('edge' 1) ('edge' 2))  == 'edges' [1, 2]+-- detachTip x ('edge' x)                 == 'edge' x+-- detachTip 1 ('into' ('edge' 1) ('edge' 2)) == 'edges' [1, 2]+-- detachTip 1 ('tips' ('edge' 1) ('edge' 2)) == 'edges' [1, 2] -- @ detachTip :: Ord a => a -> Incidence a -> Incidence a detachTip a r@(Incidence ns)@@ -446,8 +446,8 @@ -- @ -- gmap f 'EdgeGraph.Incidence.Internal.empty'    == 'EdgeGraph.Incidence.Internal.empty' -- gmap f ('edge' x) == 'edge' (f x)--- gmap id           == id--- gmap f . gmap g   == gmap (f . g)+-- gmap id         == id+-- gmap f . gmap g == gmap (f . g) -- @ gmap :: (Ord a, Ord b) => (a -> b) -> Incidence a -> Incidence b gmap f (Incidence ns) = Incidence $ normalize $ map mapNode $ Set.toList ns

@@ -114,9 +114,9 @@ -- i.e. the edges that the given edge flows into. -- -- @--- postset x 'EdgeGraph.IntAdjacencyMap.empty'                        == Set.'Set.empty'--- postset x ('EdgeGraph.IntAdjacencyMap.edge' x)                     == Set.'Set.empty'--- postset 1 ('into' ('EdgeGraph.IntAdjacencyMap.edge' 1) ('EdgeGraph.IntAdjacencyMap.edge' 2)) == Set.'Set.singleton' 2+-- postset x 'EdgeGraph.IntAdjacencyMap.empty'                    == 'Data.Set.empty'+-- postset x ('EdgeGraph.IntAdjacencyMap.edge' x)                 == 'Data.Set.empty'+-- postset 1 ('into' ('EdgeGraph.IntAdjacencyMap.edge' 1) ('EdgeGraph.IntAdjacencyMap.edge' 2)) == 'Data.Set.singleton' 2 -- @ postset :: Int -> IntAdjacencyMap -> Set Int postset a (IntAdjacencyMap m) = maybe Set.empty succs (Map.lookup a m)@@ -126,9 +126,9 @@ -- i.e. the edges that flow into the given edge. -- -- @--- preset x 'EdgeGraph.IntAdjacencyMap.empty'                        == Set.'Set.empty'--- preset x ('EdgeGraph.IntAdjacencyMap.edge' x)                     == Set.'Set.empty'--- preset 2 ('into' ('EdgeGraph.IntAdjacencyMap.edge' 1) ('EdgeGraph.IntAdjacencyMap.edge' 2)) == Set.'Set.singleton' 1+-- preset x 'EdgeGraph.IntAdjacencyMap.empty'                    == 'Data.Set.empty'+-- preset x ('EdgeGraph.IntAdjacencyMap.edge' x)                 == 'Data.Set.empty'+-- preset 2 ('into' ('EdgeGraph.IntAdjacencyMap.edge' 1) ('EdgeGraph.IntAdjacencyMap.edge' 2)) == 'Data.Set.singleton' 1 -- @ preset :: Int -> IntAdjacencyMap -> Set Int preset a (IntAdjacencyMap m) = maybe Set.empty preds (Map.lookup a m)@@ -144,8 +144,8 @@ -- directed flow from each edge to its successors. -- -- @--- 'dfsForest' 'EdgeGraph.IntAdjacencyMap.empty'                         == []--- 'dfsForest' ('EdgeGraph.IntAdjacencyMap.edge' x)                      == [Node x []]+-- 'dfsForest' 'EdgeGraph.IntAdjacencyMap.empty'                       == []+-- 'dfsForest' ('EdgeGraph.IntAdjacencyMap.edge' x)                    == [Node x []] -- 'isSubgraphOf' ('forest' $ 'dfsForest' x) x == True -- 'dfsForest' . 'forest' . 'dfsForest'        == 'dfsForest' -- @@@ -173,9 +173,9 @@ -- and no edge appears after one of its successors. -- -- @--- 'isTopSort' [] 'EdgeGraph.IntAdjacencyMap.empty'     == True+-- 'isTopSort' []  'EdgeGraph.IntAdjacencyMap.empty'    == True -- 'isTopSort' [x] ('EdgeGraph.IntAdjacencyMap.edge' x) == True--- 'isTopSort' [] ('EdgeGraph.IntAdjacencyMap.edge' x)  == False+-- 'isTopSort' []  ('EdgeGraph.IntAdjacencyMap.edge' x) == False -- @ isTopSort :: [Int] -> IntAdjacencyMap -> Bool isTopSort xs m = go Set.empty xs

@@ -65,14 +65,14 @@   pits    = pits   tips    = tips --- | Convert an t'IntAdjacencyMap' to its equivalent 'I.Incidence' representation.+-- | Convert an t'IntAdjacencyMap' to its equivalent 'EdgeGraph.Incidence.Internal.Incidence' representation. -- -- For each edge, reconstruct its source node (pitNode) and sink node (tipNode), -- then collect all unique nodes into a set. -- -- @--- 'toIncidence' 'EdgeGraph.IntAdjacencyMap.Internal.empty'    == 'I.empty'--- 'toIncidence' ('EdgeGraph.IntAdjacencyMap.Internal.edge' x) == 'I.edge' x+-- 'toIncidence' 'EdgeGraph.IntAdjacencyMap.Internal.empty'    == 'EdgeGraph.Incidence.Internal.empty'+-- 'toIncidence' ('EdgeGraph.IntAdjacencyMap.Internal.edge' x) == 'EdgeGraph.Incidence.Internal.edge' x -- @ toIncidence :: IntAdjacencyMap -> I.Incidence Int toIncidence (IntAdjacencyMap m)@@ -85,14 +85,14 @@       , I.Node (joins adj) (succs adj)       ] --- | Convert an 'I.Incidence' to an t'IntAdjacencyMap'.+-- | Convert an 'EdgeGraph.Incidence.Internal.Incidence' to an t'IntAdjacencyMap'. -- -- Scans all nodes once to build edge-to-source and edge-to-sink maps, -- then constructs the t'Adjacency' record for each edge. -- -- @--- 'fromIncidence' 'I.empty'    == 'EdgeGraph.IntAdjacencyMap.Internal.empty'--- 'fromIncidence' ('I.edge' x) == 'EdgeGraph.IntAdjacencyMap.Internal.edge' x+-- 'fromIncidence' 'EdgeGraph.Incidence.Internal.empty'    == 'EdgeGraph.IntAdjacencyMap.Internal.empty'+-- 'fromIncidence' ('EdgeGraph.Incidence.Internal.edge' x) == 'EdgeGraph.IntAdjacencyMap.Internal.edge' x -- @ fromIncidence :: I.Incidence Int -> IntAdjacencyMap fromIncidence (I.Incidence ns)@@ -205,12 +205,12 @@ -- representations by merging nodes that share edges. -- -- @--- 'isEmpty' ('overlay' x y)   == 'isEmpty' x && 'isEmpty' y--- 'overlay' 'EdgeGraph.IntAdjacencyMap.Internal.empty' x         == x--- 'overlay' x 'EdgeGraph.IntAdjacencyMap.Internal.empty'         == x--- 'overlay' x y               == 'overlay' y x--- 'overlay' x ('overlay' y z) == 'overlay' ('overlay' x y) z--- 'overlay' x x               == x+-- 'isEmpty' ('overlay' x y)       == 'isEmpty' x && 'isEmpty' y+-- 'overlay' 'EdgeGraph.IntAdjacencyMap.Internal.empty' x             == x+-- 'overlay' x     'EdgeGraph.IntAdjacencyMap.Internal.empty'         == x+-- 'overlay' x     y             == 'overlay' y x+-- 'overlay' x     ('overlay' y z) == 'overlay' ('overlay' x y) z+-- 'overlay' x     x             == x -- @ overlay :: IntAdjacencyMap -> IntAdjacencyMap -> IntAdjacencyMap overlay x y = fromIncidence $ I.overlay (toIncidence x) (toIncidence y)@@ -346,9 +346,9 @@ -- Complexity: /O((|forks| + |preds|) * log n)/ time. -- -- @--- detachPit x ('EdgeGraph.IntAdjacencyMap.Internal.edge' x)                      == 'EdgeGraph.IntAdjacencyMap.Internal.edge' x--- detachPit 2 ('into' ('EdgeGraph.IntAdjacencyMap.Internal.edge' 1) ('EdgeGraph.IntAdjacencyMap.Internal.edge' 2))  == 'edges' [1, 2]--- detachPit 1 ('pits' ('EdgeGraph.IntAdjacencyMap.Internal.edge' 1) ('EdgeGraph.IntAdjacencyMap.Internal.edge' 2))  == 'edges' [1, 2]+-- detachPit x ('EdgeGraph.IntAdjacencyMap.Internal.edge' x)                 == 'EdgeGraph.IntAdjacencyMap.Internal.edge' x+-- detachPit 2 ('into' ('EdgeGraph.IntAdjacencyMap.Internal.edge' 1) ('EdgeGraph.IntAdjacencyMap.Internal.edge' 2)) == 'edges' [1, 2]+-- detachPit 1 ('pits' ('EdgeGraph.IntAdjacencyMap.Internal.edge' 1) ('EdgeGraph.IntAdjacencyMap.Internal.edge' 2)) == 'edges' [1, 2] -- @ detachPit :: Int -> IntAdjacencyMap -> IntAdjacencyMap detachPit a (IntAdjacencyMap m) = case Map.lookup a m of@@ -371,9 +371,9 @@ -- Complexity: /O((|joins| + |succs|) * log n)/ time. -- -- @--- detachTip x ('EdgeGraph.IntAdjacencyMap.Internal.edge' x)                      == 'EdgeGraph.IntAdjacencyMap.Internal.edge' x--- detachTip 1 ('into' ('EdgeGraph.IntAdjacencyMap.Internal.edge' 1) ('EdgeGraph.IntAdjacencyMap.Internal.edge' 2))  == 'edges' [1, 2]--- detachTip 1 ('tips' ('EdgeGraph.IntAdjacencyMap.Internal.edge' 1) ('EdgeGraph.IntAdjacencyMap.Internal.edge' 2))  == 'edges' [1, 2]+-- detachTip x ('EdgeGraph.IntAdjacencyMap.Internal.edge' x)                 == 'EdgeGraph.IntAdjacencyMap.Internal.edge' x+-- detachTip 1 ('into' ('EdgeGraph.IntAdjacencyMap.Internal.edge' 1) ('EdgeGraph.IntAdjacencyMap.Internal.edge' 2)) == 'edges' [1, 2]+-- detachTip 1 ('tips' ('EdgeGraph.IntAdjacencyMap.Internal.edge' 1) ('EdgeGraph.IntAdjacencyMap.Internal.edge' 2)) == 'edges' [1, 2] -- @ detachTip :: Int -> IntAdjacencyMap -> IntAdjacencyMap detachTip a (IntAdjacencyMap m) = case Map.lookup a m of@@ -396,8 +396,8 @@ -- @ -- gmap f 'EdgeGraph.IntAdjacencyMap.Internal.empty'    == 'EdgeGraph.IntAdjacencyMap.Internal.empty' -- gmap f ('EdgeGraph.IntAdjacencyMap.Internal.edge' x) == 'EdgeGraph.IntAdjacencyMap.Internal.edge' (f x)--- gmap id           == id--- gmap f . gmap g   == gmap (f . g)+-- gmap id         == id+-- gmap f . gmap g == gmap (f . g) -- @ gmap :: (Int -> Int) -> IntAdjacencyMap -> IntAdjacencyMap gmap f = fromIncidence . I.gmap f . toIncidence