h$I.      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                                                                                                                                                                                                                                                   (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?mX3algebraic-graphsThe  data type represents a graph by a map of vertices to their adjacency sets. We define a ; instance as a convenient notation for working with graphs: 0 ==  0 1 + 2 ==  ( 1) ( 2) 1 * 2 ==  ( 1) ( 2) 1 + 2 * 3 ==  ( 1) ( ( 2) ( 3)) 1 * (2 + 3) ==  ( 1) ( ( 2) ( 3)) Note: the 7 instance does not satisfy several "customary laws" of , which dictate that  0 and  1; should act as additive and multiplicative identities, and 0 as additive inverse. Nevertheless, overloading ,  and  is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ? instance is defined using basic graph construction primitives: show (empty :: AdjacencyMap Int) == "empty" show (1 :: AdjacencyMap Int) == "vertex 1" show (1 + 2 :: AdjacencyMap Int) == "vertices [1,2]" show (1 * 2 :: AdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"The 3 instance satisfies all axioms of algebraic graphs: is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z is associative and has  as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * zThe following useful theorems can be proved from the above set of axioms. has # as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of : -x * y + x + y == x * y x * x * x == x * xWhen specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges in the graph, respectively.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:  1 <  2  3 <  1 2  1 <  1 1  1 1 <  1 2  1 2 <  1 1 +  2 2  1 2 <  1 3*Note that the resulting order refines the  ! relation and is compatible with  and  operations:   x y ==> x <= y # <= x x <= x + y x + y <= x * yalgebraic-graphsThe  adjacency map of a graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory.  adjacencyMap  == Map. adjacencyMap ( x) == Map. x Set. adjacencyMap ( 1 1) == Map. 1 (Set. 1) adjacencyMap ( 1 2) == Map. [(1,Set. 2), (2,Set.)] algebraic-graphsConstruct the  empty graph.   empty == True  x empty == False  empty == 0  empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex.   (vertex x) == False  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0 algebraic-graphsConstruct the graph comprising  a single edge. edge x y ==  ( x) ( y)  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 algebraic-graphsOverlay two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O((n + m) * log(n)) time and O(n + m) memory.   (overlay x y) ==   x &&   y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphsConnect two graphs. This is an associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).   (connect x y) ==   x &&   y  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) <=  x *  y +  x +  y  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x vertices ==   . map   x . vertices ==  x  . vertices ==  .   . vertices == Set. algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] ==  edges [(x,y)] ==  x y edges ==   .  ( )  . edges ==  .   . edges ==  .   algebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==      . overlays ==    algebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==      . connects ==    algebraic-graphsThe  ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf . x == True isSubgraphOf ( x) / == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True isSubgraphOf x y ==> x <= y algebraic-graphs(Check if a graph is empty. Complexity: O(1) time. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty (" x $  x) == True isEmpty (# x y $  x y) == False algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ($ y) == (x == y) hasVertex x . " x ==   False algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y . # x y ==  ' False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (3 x) == 1 vertexCount ==  . ) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(n) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  ==  .   algebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList  == [] edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList .   ==  .   edgeList . & ==   .  !" . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexSet  == Set. vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet  == Set. edgeSet ( x) == Set. edgeSet ( x y) == Set. (x,y) edgeSet .   == Set. algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and memory. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (0 1 2) == [(1, [2]), (2, [])] adjacencyList (, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]  . adjacencyList == id algebraic-graphsThe preset of an element x is the set of its direct predecessors. Complexity:  O(n * log(n)) time and O(n) memory.  preSet x  == Set. preSet x ( x) == Set. preSet 1 ( 1 2) == Set. preSet y ( x y) == Set. [x] algebraic-graphsThe postset of a vertex is the set of its direct successors. Complexity:  O(log(n)) time and O(1) memory.  postSet x  == Set. postSet x ( x) == Set. postSet x ( x y) == Set. [y] postSet 2 ( 1 2) == Set. algebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] ==  path [x] ==  x path [x,y] ==  x y path .   == & . path algebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==   [(x,y), (y,x)] circuit .   == & . circuit algebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] ==  " [(x,y), (x,z), (y,z)] clique (xs   ys) == " (clique xs) (clique ys) clique .   == & . clique algebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] ==   [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] ==  x star x [y] ==  x y star x [y,z] ==   [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity:  O(L * log(n)) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==   .  (  ) stars .  == id $ (stars xs) (stars ys) == stars (xs   ys) algebraic-graphsConstruct a graph from a list of adjacency sets; a variation of . Complexity: O((n + m) * log(n)) time and O(n + m) memory. 9fromAdjacencySets [] ==  fromAdjacencySets [(x, Set.)] ==  x fromAdjacencySets [(x, Set. y)] ==  x y fromAdjacencySets .  (  Set.) ==   (fromAdjacencySets xs) (fromAdjacencySets ys) == fromAdjacencySets (xs   ys) algebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. forest [] == ? forest [x] ==   x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==   [(1,2), (1,3), (4,5)] forest ==   .    "algebraic-graphs1Remove a vertex from a given graph. Complexity:  O(n*log(n)) time. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x #algebraic-graphs0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y ( x y) ==  [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . " x == " x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 $algebraic-graphs The function $ x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y == % (== x) y %algebraic-graphsMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))8 time, assuming that the predicate takes constant time. mergeVertices ( 7 False) x == id mergeVertices (== x) y == $ x y mergeVertices  & 1 (0 * 2) == 1 * 1 mergeVertices   1 (3 + 4 * 5) == 4 * 1 &algebraic-graphs&Transpose a given graph. Complexity:  O(m * log(n)) time, O(n + m) memory.  transpose  ==  transpose ( x) ==  x transpose ( x y) == ! y x transpose . transpose == id  . transpose ==   .  !" .  'algebraic-graphsTransform a graph by applying a function to each of its vertices. This is similar to Functor's  , but can be used with non-fully-parametric . Complexity: O((n + m) * log(n)) time. gmap f  ==  gmap f ( x) ==  (f x) gmap f ( x y) ==  (f x) (f y) gmap   ==  # gmap f . gmap g == gmap (f . g) (algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(n + m)7 time, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x ==  induce (/= x) == "< x induce p . induce q == induce (\x -> p x && q x)   (induce p x) x == True )algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are  . Complexity: O(n + m) time.  induceJust (  #) ==  induceJust ( (  x)  ) ==  x induceJust . '  ' ==   induceJust . ' (\x -> if p x then   x else  ) == ( p *algebraic-graphsLeft-to-right relational composition of graphs: vertices x and z< are connected in the resulting graph if there is a vertex y , such that x is connected to y in the first graph, and y is connected to z in the second graph. There are no isolated vertices in the result. This operation is associative, has  and single- graphs as annihilating zeroes, and distributes over . Complexity: O(n * m * log(n)) time and O(n + m) memory. compose  x ==  compose x  ==  compose ( x) y ==  compose x ( y) ==  compose x (compose y z) == compose (compose x y) z compose x ( y z) == & (compose x y) (compose x z) compose ( x y) z == & (compose x z) (compose y z) compose ( x y) ( y z) ==  x z compose ( [1..5]) ( [1..5]) ==   [(1,3), (2,4), (3,5)] compose ( [1..5]) ( [1..5]) ==  [1,3,5,2,4] +algebraic-graphs Compute the Cartesian product of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. box ( [0,1]) ( "ab") ==   [ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((0,'b'), (1,'b')) , ((1,'a'), (1,'b')) ] Up to isomorphism between the resulting vertex types, this operation is  commutative,  associative,  distributes over , has singleton graphs as  identities and  as the annihilating zero. Below ~~1 stands for 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 z) ==  (box x y) (box x z) box x ( ()) ~~ x box x  ~~  & (box x y) == box (& x) (& y)  (box x y) ==  x *  y  (box x y) <=  x *  y +  x *  y ,algebraic-graphs Compute the  reflexive and transitive closure of a graph. Complexity: O(n * m * log(n)^2) time. closure  ==  closure ( x) ==  x x closure ( x x) ==  x x closure ( x y) ==   [(x,x), (x,y), (y,y)] closure ( $  xs) == - ( $  xs) closure == - . / closure == / . -$ closure . closure == closure  x (closure y) == Set. ( # y x) -algebraic-graphs Compute the reflexive closure of a graph by adding a self-loop to every vertex. Complexity:  O(n * log(n)) time. reflexiveClosure  ==  reflexiveClosure ( x) ==  x x reflexiveClosure ( x x) ==  x x reflexiveClosure ( x y) ==   [(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure .algebraic-graphs Compute the symmetric closure of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time. symmetricClosure  ==  symmetricClosure ( x) ==  x symmetricClosure ( x y) ==  7 [(x,y), (y,x)] symmetricClosure x ==  x (&< x) symmetricClosure . symmetricClosure == symmetricClosure /algebraic-graphs Compute the transitive closure of a graph. Complexity: O(n * m * log(n)^2) time. transitiveClosure  ==  transitiveClosure ( x) ==  x transitiveClosure ( x y) ==  x y transitiveClosure ( $  xs) ==  ( xs) transitiveClosure . transitiveClosure == transitiveClosure 0algebraic-graphsCheck that the internal graph representation is consistent, i.e. that all edges refer to existing vertices. It should be impossible to create an inconsistent adjacency map, and we use this function in testing.  consistent  == True consistent ( x) == True consistent ( x y) == True consistent ( x y) == True consistent ( x y) == True consistent (  xs) == True consistent ( xs) == True 1algebraic-graphs Defined via  and .2algebraic-graphs Defined via .5algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.0  !"#$%&'()*+,-./00  !"#$%&'()*+,-./0(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?2:algebraic-graphsThe : data type represents a graph by a map of vertices to their adjacency sets. We define a ; instance as a convenient notation for working with graphs: 0 == > 0 1 + 2 == @ (> 1) (> 2) 1 * 2 == A (> 1) (> 2) 1 + 2 * 3 == @ (> 1) (A (> 2) (> 3)) 1 * (2 + 3) == A (> 1) (@ (> 2) (> 3)) Note: the 7 instance does not satisfy several "customary laws" of , which dictate that  0 and  1; should act as additive and multiplicative identities, and 0 as additive inverse. Nevertheless, overloading ,  and  is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ? instance is defined using basic graph construction primitives: show (empty :: AdjacencyIntMap Int) == "empty" show (1 :: AdjacencyIntMap Int) == "vertex 1" show (1 + 2 :: AdjacencyIntMap Int) == "vertices [1,2]" show (1 * 2 :: AdjacencyIntMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyIntMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyIntMap Int) == "overlay (vertex 3) (edge 1 2)"The 3 instance satisfies all axioms of algebraic graphs:@ is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + zA is associative and has = as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * zA distributes over @: 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * zA can be decomposed: "x * y * z == x * y + x * z + y * zThe following useful theorems can be proved from the above set of axioms.@ has =# as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of A: -x * y + x + y == x * y x * x * x == x * xWhen specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges in the graph, respectively.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples: > 1 < > 2 > 3 < ? 1 2 > 1 < ? 1 1 ? 1 1 < ? 1 2 ? 1 2 < ? 1 1 + ? 2 2 ? 1 2 < ? 1 3*Note that the resulting order refines the F! relation and is compatible with @ and A operations: F x y ==> x <= y =# <= x x <= x + y x + y <= x * y;algebraic-graphsThe  adjacency map of a graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory. adjacencyIntMap = == IntMap.  adjacencyIntMap (> x) == IntMap.  x IntSet.  adjacencyIntMap (? 1 1) == IntMap.  1 (IntSet.  1) adjacencyIntMap (? 1 2) == IntMap.  [(1,IntSet.  2), (2,IntSet. )] <algebraic-graphs Construct an : from an  with vertices of type  . Complexity: O(n + m) time and memory. fromAdjacencyMap == X . AdjacencyMap. =algebraic-graphsConstruct the  empty graph. G empty == True H x empty == False J empty == 0 K empty == 0 >algebraic-graphsConstruct the graph comprising a single isolated vertex. G (vertex x) == False H x (vertex y) == (x == y) J (vertex x) == 1 K (vertex x) == 0 ?algebraic-graphsConstruct the graph comprising  a single edge. edge x y == A (> x) (> y) I x y (edge x y) == True K (edge x y) == 1 J (edge 1 1) == 1 J (edge 1 2) == 2 @algebraic-graphsOverlay two graphs. This is a commutative, associative and idempotent operation with the identity =. Complexity: O((n + m) * log(n)) time and O(n + m) memory. G (overlay x y) == G x && G y H z (overlay x y) == H z x || H z y J (overlay x y) >= J x J (overlay x y) <= J x + J y K (overlay x y) >= K x K (overlay x y) <= K x + K y J (overlay 1 2) == 2 K (overlay 1 2) == 0 Aalgebraic-graphsConnect two graphs. This is an associative operation with the identity =, which distributes over @1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2). G (connect x y) == G x && G y H z (connect x y) == H z x || H z y J (connect x y) >= J x J (connect x y) <= J x + J y K (connect x y) >= K x K (connect x y) >= K y K (connect x y) >= J x * J y K (connect x y) <= J x * J y + K x + K y J (connect 1 2) == 2 K (connect 1 2) == 1 Balgebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices [] == = vertices [x] == > x vertices == D . map > H x . vertices ==  x J . vertices ==  .  N . vertices == IntSet.  Calgebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] == = edges [(x,y)] == ? x y edges == D .  ( ?) K . edges ==  .  M . edges ==  .   Dalgebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == =/ overlays [x] == x overlays [x,y] == @ x y overlays ==  @ = G . overlays ==  G Ealgebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] == =/ connects [x] == x connects [x,y] == A x y connects ==  A = G . connects ==  G Falgebraic-graphsThe F' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf =. x == True isSubgraphOf (> x) =/ == False isSubgraphOf x (@ x y) == True isSubgraphOf (@ x y) (A x y) == True isSubgraphOf (S xs) (T xs) == True isSubgraphOf x y ==> x <= y Galgebraic-graphs(Check if a graph is empty. Complexity: O(1) time. isEmpty =( == True isEmpty (@ = =) == True isEmpty (>' x) == False isEmpty (\ x $ > x) == True isEmpty (] x y $ ? x y) == False Halgebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x =" == False hasVertex x (>$ y) == (x == y) hasVertex x . \ x ==   False Ialgebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y =" == False hasEdge x y (> z) == False hasEdge x y (?" x y) == True hasEdge x y . ] x y ==  ' False hasEdge x y ==  (x,y) . M Jalgebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount = == 0 vertexCount (>3 x) == 1 vertexCount ==  . L) vertexCount x < vertexCount y ==> x < y Kalgebraic-graphs-The number of edges in a graph. Complexity: O(n) time.  edgeCount = == 0 edgeCount (> x) == 0 edgeCount (?# x y) == 1 edgeCount ==  . M Lalgebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList = == [] vertexList (> x) == [x] vertexList . B ==  .   Malgebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList = == [] edgeList (> x) == [] edgeList (? x y) == [(x,y)] edgeList (W' 2 [3,1]) == [(2,1), (2,3)] edgeList . C ==  .   edgeList . ` ==   .  !" . edgeList Nalgebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexIntSet = == IntSet.  vertexIntSet . > == IntSet.  vertexIntSet . B == IntSet.  vertexIntSet . U == IntSet.  Oalgebraic-graphs0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet = == Set. edgeSet (> x) == Set. edgeSet (? x y) == Set. (x,y) edgeSet . C == Set. Palgebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and memory. adjacencyList = == [] adjacencyList (>$ x) == [(x, [])] adjacencyList (?0 1 2) == [(1, [2]), (2, [])] adjacencyList (W, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] X . adjacencyList == id Qalgebraic-graphsThe preset (here  preIntSet) of an element x is the set of its direct predecessors. Complexity:  O(n * log(n)) time and O(n) memory.  preIntSet x = == Set. preIntSet x (> x) == Set. preIntSet 1 (? 1 2) == Set. preIntSet y (? x y) == Set. [x] Ralgebraic-graphsThe postset (here  postIntSet!) of a vertex is the set of its direct successors.  postIntSet x = == IntSet.  postIntSet x (> x) == IntSet.  postIntSet x (? x y) == IntSet.  [y] postIntSet 2 (? 1 2) == IntSet.  Salgebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] == = path [x] == > x path [x,y] == ? x y path .   == ` . path Talgebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] == = circuit [x] == ? x x circuit [x,y] == C [(x,y), (y,x)] circuit .   == ` . circuit Ualgebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique [] == = clique [x] == > x clique [x,y] == ? x y clique [x,y,z] == C, [(x,y), (x,z), (y,z)] clique (xs ++ ys) == A" (clique xs) (clique ys) clique .   == ` . clique Valgebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique [] [] == = biclique [x] [] == > x biclique [] [y] == > y biclique [x1,x2] [y1,y2] == C [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == A (B xs) (B ys) Walgebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] == > x star x [y] == ? x y star x [y,z] == C [(x,y), (x,z)] star x ys == A (> x) (B ys) Xalgebraic-graphsThe stars formed by overlaying a list of Ws. An inverse of P. Complexity:  O(L * log(n)) time, memory and size, where L! is the total size of the input. !stars [] == =" stars [(x, [])] == >$ x stars [(x, [y])] == ?& x y stars [(x, ys)] == W' x ys stars == D .  ( W ) stars . P == id @+ (stars xs) (stars ys) == stars (xs ++ ys) Yalgebraic-graphsConstruct a graph from a list of adjacency sets; a variation of X. Complexity: O((n + m) * log(n)) time and O(n + m) memory. ?fromAdjacencyIntSets [] == =" fromAdjacencyIntSets [(x, IntSet. )] == >$ x fromAdjacencyIntSets [(x, IntSet.  y)] == ? x y fromAdjacencyIntSets .  (  IntSet. ) == X @ (fromAdjacencyIntSets xs) (fromAdjacencyIntSets ys) == fromAdjacencyIntSets (xs ++ ys) Zalgebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. ? x tree (Node x [Node y [Node z []]]) == S [x,y,z] tree (Node x [Node y [], Node z []]) == W x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == C [(1,2), (1,3), (3,4), (3,5)] [algebraic-graphsThe  forest graph constructed from a given   data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. >forest [] == =? forest [x] == Z x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == C [(1,2), (1,3), (4,5)] forest == D .  Z \algebraic-graphs1Remove a vertex from a given graph. Complexity:  O(n*log(n)) time. removeVertex x (> x) == = removeVertex 1 (> 2) == > 2 removeVertex x (? x x) == = removeVertex 1 (? 1 2) == >5 2 removeVertex x . removeVertex x == removeVertex x ]algebraic-graphs0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y (? x y) == B [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . \ x == \ x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 ^algebraic-graphs The function ^ x y replaces vertex x with vertex y in a given :. If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time. 6replaceVertex x x == id replaceVertex x y (> x) == ># y replaceVertex x y == _ (== x) y _algebraic-graphsMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))8 time, assuming that the predicate takes constant time. mergeVertices ( 7 False) x == id mergeVertices (== x) y == ^ x y mergeVertices  & 1 (0 * 2) == 1 * 1 mergeVertices   1 (3 + 4 * 5) == 4 * 1 `algebraic-graphs&Transpose a given graph. Complexity:  O(m * log(n)) time, O(n + m) memory.  transpose = == = transpose (> x) == > x transpose (? x y) == ?! y x transpose . transpose == id M . transpose ==   .  !" . M aalgebraic-graphsTransform a graph by applying a function to each of its vertices. This is similar to Functor's  , but can be used with non-fully-parametric :. Complexity: O((n + m) * log(n)) time. gmap f = == = gmap f (> x) == > (f x) gmap f (? x y) == ? (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) balgebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(n + m)7 time, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x == = induce (/= x) == \< x induce p . induce q == induce (\x -> p x && q x) F (induce p x) x == True calgebraic-graphsLeft-to-right relational composition of graphs: vertices x and z< are connected in the resulting graph if there is a vertex y , such that x is connected to y in the first graph, and y is connected to z in the second graph. There are no isolated vertices in the result. This operation is associative, has = and single-> graphs as annihilating zeroes, and distributes over @. Complexity: O(n * m * log(n)) time and O(n + m) memory. compose = x == = compose x = == = compose (> x) y == = compose x (> y) == = compose x (compose y z) == compose (compose x y) z compose x (@ y z) == @& (compose x y) (compose x z) compose (@ x y) z == @& (compose x z) (compose y z) compose (? x y) (? y z) == ? x z compose (S [1..5]) (S [1..5]) == C [(1,3), (2,4), (3,5)] compose (T [1..5]) (T [1..5]) == T [1,3,5,2,4] dalgebraic-graphs Compute the  reflexive and transitive closure of a graph. Complexity: O(n * m * log(n)^2) time. closure = == = closure (> x) == ? x x closure (? x x) == ? x x closure (? x y) == C [(x,x), (x,y), (y,y)] closure (S $  xs) == e (U $ ! xs) closure == e . g closure == g . e% closure . closure == closure R x (closure y) == IntSet.  ( # y x) ealgebraic-graphs Compute the reflexive closure of a graph by adding a self-loop to every vertex. Complexity:  O(n * log(n)) time. reflexiveClosure = == = reflexiveClosure (> x) == ? x x reflexiveClosure (? x x) == ? x x reflexiveClosure (? x y) == C [(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure falgebraic-graphs Compute the symmetric closure of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time. symmetricClosure = == = symmetricClosure (> x) == > x symmetricClosure (? x y) == C7 [(x,y), (y,x)] symmetricClosure x == @ x (`< x) symmetricClosure . symmetricClosure == symmetricClosure galgebraic-graphs Compute the transitive closure of a graph. Complexity: O(n * m * log(n)^2) time. transitiveClosure = == = transitiveClosure (> x) == > x transitiveClosure (? x y) == ? x y transitiveClosure (S $  xs) == U ( xs) transitiveClosure . transitiveClosure == transitiveClosure halgebraic-graphsCheck that the internal graph representation is consistent, i.e. that all edges refer to existing vertices. It should be impossible to create an inconsistent adjacency map, and we use this function in testing.  consistent = == True consistent (> x) == True consistent (@ x y) == True consistent (A x y) == True consistent (? x y) == True consistent (C xs) == True consistent (X xs) == True ialgebraic-graphs Defined via @ and =.jalgebraic-graphs Defined via @.lalgebraic-graphsNote:0 this does not satisfy the usual ring laws; see : for more details./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefgh/:;<=>?@ABCDEFGHIJKLMPNOQRSTUVWXYZ[\]^_`abcdefgh(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone'(-58>?c ralgebraic-graphs Compute the breadth-first search forest of a graph, such that adjacent vertices are explored in the increasing order. The search is seeded by a list of vertices that will become the roots of the resulting forest. Duplicates in the list will have their first occurrence explored and subsequent ones ignored. The seed vertices that do not belong to the graph are also ignored. Complexity: O((L + m) * log n) time and O(n) space, where L! is the number of seed vertices. [ $ bfsForest (? 1 2) [0] == = [ $ bfsForest (? 1 2) [1] == ? 1 2 [ $ bfsForest (? 1 2) [2] == > 2 [ $ bfsForest (? 1 2) [0,1,2] == B [1,2] [ $ bfsForest (? 1 2) [2,1,0] == B [1,2] [ $ bfsForest (? 1 1) [1] == > 1 F ([* $ bfsForest x vs) x == True bfsForest x (L x) ==  (\v -> Node v []) ( $ L= x) bfsForest x [] == [] bfsForest = vs == [] bfsForest (3 * (1 + 4) * (1 + 5)) [1,4] == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 4 , subForest = [] }] [ $ bfsForest (T [1..5] + T [5,4..1]) [3] == S [3,2,1] + S [3,4,5] salgebraic-graphs A version of r where the resulting forest is converted to a level structure. Adjacent vertices are explored in the increasing order. Flattening the result via   . s x gives an enumeration of reachable vertices in the breadth-first search order. Complexity: O((L + m) * min(n,W)) time and O(n) space, where L! is the number of seed vertices. bfs (?$ 1 2) [0] == [] bfs (?, 1 2) [1] == [[1], [2]] bfs (?' 1 2) [2] == [[2]] bfs (?) 1 2) [1,2] == [[1,2]] bfs (?) 1 2) [2,1] == [[2,1]] bfs (?& 1 1) [1] == [[1]] bfs = vs == [] bfs x [] == [] bfs (1 * 2 + 3 * 4 + 5 * 6) [1,2] == [[1,2]] bfs (1 * 2 + 3 * 4 + 5 * 6) [1,3] == [[1,3], [2,4]] bfs (3 * (1 + 4) * (1 + 5)) [3] == [[3], [1,4,5]] bfs (T [1..5] + T/ [5,4..1]) [3] == [[2], [1,3], [5,4]]   $ bfs (T [1..5] + T [5,4..1]) [3] == [3,2,4,1,5]    .   .    . r x == bfs x talgebraic-graphs Compute the depth-first search forest of a graph, where adjacent vertices are explored in the increasing order. Complexity: O((n + m) * min(n,W)) time and O(n) space. [ $ dfsForest = == = [ $ dfsForest (? 1 1) == > 1 [ $ dfsForest (? 1 2) == ? 1 2 [ $ dfsForest (? 2 1) == B [1,2] F ([ $ dfsForest x) x == True z- (dfsForest x) x == True dfsForest . [, . dfsForest == dfsForest dfsForest (B vs) ==  (\v -> Node v []) ( $   vs) dfsForest $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 3 , subForest = [ Node { rootLabel = 4 , subForest = [] }]}] [ (dfsForest $ T [1..5] + T [5,4..1]) == S [1,2,3,4,5] ualgebraic-graphs Compute the depth-first search forest of a graph starting from the given seed vertices, where adjacent vertices are explored in the increasing order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. The seed vertices which do not belong to the graph are ignored. Complexity: O((L + m) * log n) time and O(n) space, where L! is the number of seed vertices. [ $ dfsForestFrom = vs == = [ $ dfsForestFrom (? 1 1) [1] == > 1 [ $ dfsForestFrom (? 1 2) [0] == = [ $ dfsForestFrom (? 1 2) [1] == ? 1 2 [ $ dfsForestFrom (? 1 2) [2] == > 2 [ $ dfsForestFrom (? 1 2) [1,2] == ? 1 2 [ $ dfsForestFrom (? 1 2) [2,1] == B [1,2] F ([% $ dfsForestFrom x vs) x == True z (dfsForestFrom x (L x)) x == True dfsForestFrom x (L x) == t x dfsForestFrom x [] == [] dfsForestFrom (3 * (1 + 4) * (1 + 5)) [1,4] == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] } , Node { rootLabel = 4 , subForest = [] }] [ $ dfsForestFrom (T [1..5] + T [5,4..1]) [3] == S [3,2,1,5,4] valgebraic-graphs(Return the list vertices visited by the depth-first search in a graph, starting from the given seed vertices. Adjacent vertices are explored in the increasing order. Complexity: O((L + m) * log n) time and O(n) space, where L! is the number of seed vertices. dfs = vs == [] dfs (? 1 1) [1] == [1] dfs (? 1 2) [0] == [] dfs (? 1 2) [1] == [1,2] dfs (? 1 2) [2] == [2] dfs (? 1 2) [1,2] == [1,2] dfs (?1 1 2) [2,1] == [2,1] dfs x [] == [] $ [ H v x | v <- dfs x vs ] == True dfs (3 * (1 + 4) * (1 + 5)) [1,4] == [1,5,4] dfs (T [1..5] + T [5,4..1]) [3] == [3,2,1,5,4] walgebraic-graphsReturn the list of vertices  reachable from a source vertex in a graph. The vertices in the resulting list appear in the depth-first search order. Complexity:  O(m * log n) time and O(n) space.  reachable =! x == [] reachable (> 1) 1 == [1] reachable (?" 1 1) 1 == [1] reachable (?! 1 2) 0 == [] reachable (?$ 1 2) 1 == [1,2] reachable (?" 1 2) 2 == [2] reachable (S% [1..8] ) 4 == [4..8] reachable (T, [1..8] ) 4 == [4..8] ++ [1..3] reachable (U [8,7..1]) 8 == [8] ++ [1..7] $ [ H$ v x | v <- reachable x y ] == True xalgebraic-graphs:Compute a topological sort of a graph or discover a cycle.Vertices are explored in the decreasing order according to their   instance. This gives the lexicographically smallest topological ordering in the case of success. In the case of failure, the cycle is characterized by being the lexicographically smallest up to rotation with respect to Ord (Dual Int) in the first connected component of the graph containing a cycle, where the connected components are ordered by their largest vertex with respect to Ord a. Complexity: O((n + m) * min(n,W)) time and O(n) space. topSort (1 * 2 + 3 * 1) == Right [3,1,2] topSort (S [1..5]) == Right [1..5] topSort (3 * (1 * 4 + 2 * 5)) == Right [3,1,2,4,5] topSort (1 * 2 + 2 * 1) == Left (2   [1]) topSort (S [5,4..1] + ? 2 4) == Left (4   [3,2]) topSort (T& [1..3]) == Left (3   [1,2]) topSort (T [1..3] + T [3,2,1]) == Left (3  < [2]) topSort (1 * 2 + (5 + 2) * 1 + 3 * 4 * 3) == Left (1   [2]) fmap (  {. x) (topSort x) /= Right False topSort . B$ == Right . nub . sort yalgebraic-graphsCheck if a given graph is acyclic. Complexity: O((n + m) * min(n,W)) time and O(n) space. isAcyclic (1 * 2 + 3 * 1) == True isAcyclic (1 * 2 + 2 * 1) == False isAcyclic . T ==   isAcyclic ==   . x zalgebraic-graphs%Check if a given forest is a correct depth-first search forest of a graph. The implementation is based on the paper "Depth-First Search and Strong Connectivity in Coq" by Franois Pottier. .isDfsForestOf [] = == True isDfsForestOf [] (> 1) == False isDfsForestOf [Node 1 []] (> 1) == True isDfsForestOf [Node 1 []] (> 2) == False isDfsForestOf [Node 1 [], Node 1 []] (> 1) == False isDfsForestOf [Node 1 []] (? 1 1) == True isDfsForestOf [Node 1 []] (? 1 2) == False isDfsForestOf [Node 1 [], Node 2 []] (? 1 2) == False isDfsForestOf [Node 2 [], Node 1 []] (? 1 2) == True isDfsForestOf [Node 1 [Node 2 []]] (? 1 2) == True isDfsForestOf [Node 1 [], Node 2 []] (B? [1,2]) == True isDfsForestOf [Node 2 [], Node 1 []] (B? [1,2]) == True isDfsForestOf [Node 1 [Node 2 []]] (B [1,2]) == False isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] (S [1,2,3]) == True isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] (S [1,2,3]) == False isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (S [1,2,3]) == True isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (S [1,2,3]) == True isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] (S [1,2,3]) == False {algebraic-graphs/Check if a given list of vertices is a correct topological sort of a graph. isTopSortOf [3,1,2] (1 * 2 + 3 * 1) == True isTopSortOf [1,2,3] (1 * 2 + 3 * 1) == False isTopSortOf [] (1 * 2 + 3 * 1) == False isTopSortOf [] =( == True isTopSortOf [x] (>& x) == True isTopSortOf [x] (? x x) == False qrstuvwxyz{ rstuvwxyz{q(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?|algebraic-graphsThe focus of a graph expression is a flattened representation of the subgraph under focus, its context, as well as the list of all encountered vertices. See % for a use-case example.}algebraic-graphs.All vertices (leaves) of the graph expression.~algebraic-graphs4True if focus on the specified subgraph is obtained.algebraic-graphs!Inputs into the focused subgraph.algebraic-graphs$Outputs out of the focused subgraph.algebraic-graphs An abstract list data type with O(1) time concatenation (the current implementation uses difference lists). Here a is the type of list elements.  a is a  :   corresponds to the empty list and two lists can be concatenated with   (or operator &':). Singleton lists can be constructed using the function   from the   instance.  a is also an instance of IsList-, therefore you can use list literals, e.g. [1,4] ::  Int is the same as   1 &'   4; note that this requires the OverloadedLists GHC extension. To extract plain Haskell lists you can use the   function from the   instance.algebraic-graphsFocus on the empty graph.algebraic-graphsFocus on the graph with a single vertex, given a predicate indicating whether the vertex is of interest.algebraic-graphsOverlay two foci.algebraic-graphsConnect two foci.algebraic-graphsA safe version of  .algebraic-graphsAn auxiliary function that tries to apply a function to a base case and a   value and returns   the result or   the base case.algebraic-graphsCompute the Cartesian product of two sets, applying a function to each resulting pair.algebraic-graphs0Help GHC with type inference when direct use of   does not compile.algebraic-graphs0Help GHC with type inference when direct use of   does not compile.algebraic-graphs0Help GHC with type inference when direct use of   does not compile.algebraic-graphs0Help GHC with type inference when direct use of   does not compile.algebraic-graphs0Help GHC with type inference when direct use of   does not compile.algebraic-graphs0Help GHC with type inference when direct use of   does not compile.|}~|}~(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?n ;algebraic-graphsThe  of a subgraph comprises its  and , i.e. all the vertices that are connected to the subgraph's vertices. Note that inputs and outputs can belong to the subgraph itself. In general, there are no guarantees on the order of vertices in  and ); furthermore, there may be repetitions.algebraic-graphsThe  data type is a deep embedding of the core graph construction primitives , ,  and . We define a ; instance as a convenient notation for working with graphs: 0 ==  0 1 + 2 ==  ( 1) ( 2) 1 * 2 ==  ( 1) ( 2) 1 + 2 * 3 ==  ( 1) ( ( 2) ( 3)) 1 * (2 + 3) ==  ( 1) ( ( 2) ( 3)) Note: the 7 instance does not satisfy several "customary laws" of , which dictate that  0 and  1; should act as additive and multiplicative identities, and 0 as additive inverse. Nevertheless, overloading ,  and  is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The - instance is currently implemented using the  as the canonical graph representation. and satisfies all axioms of algebraic graphs: is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z is associative and has  as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * zThe following useful theorems can be proved from the above set of axioms. has # as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of : -x * y + x + y == x * y x * x * x == x * xWhen specifying the time and memory complexity of graph algorithms, n2 will denote the number of vertices in the graph, m3 will denote the number of edges in the graph, and s will denote the size of the corresponding  expression. For example, if g is a  then n, m and s can be computed as follows: n ==  g m ==  g s ==  g Note that % counts all leaves of the expression:   == 0   == 1  ( x) == 1  ( x) == 1  ( + ) == 0  ( + ) == 2 Converting a  to the corresponding  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 adjacency maps.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:  1 <  2  3 <  1 2  1 <  1 1  1 1 <  1 2  1 2 <  1 1 +  2 2  1 2 <  1 3*Note that the resulting order refines the ! relation and is compatible with  and  operations:  x y ==> x <= y # <= x x <= x + y x + y <= x * yDeforestation (fusion) is implemented for some functions in this module. This means that when a function tagged as a "good producer" is composed with a function tagged as a "good consumer", the intermediate structure will not be built.algebraic-graphsConstruct the  empty graph. An alias for the constructor .  empty == True  x empty == False  empty == 0  empty == 0  empty == 1 algebraic-graphsConstruct the graph comprising a single isolated vertex . An alias for the constructor .  (vertex x) == False  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0  (vertex x) == 1 algebraic-graphsConstruct the graph comprising  a single edge. edge x y ==  ( x) ( y)  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 algebraic-graphsOverlay* two graphs. An alias for the constructor . This is a commutative, associative and idempotent operation with the identity . Complexity: O(1) time and memory,  O(s1 + s2) size.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) ==  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphsConnect* two graphs. An alias for the constructor 6. This is an associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O(1) time and memory,  O(s1 + s2) size. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  (connect x y) ==  x &&  y  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) <=  x *  y +  x +  y  (connect x y) ==  x +  y  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list..Good consumer of lists and producer of graphs. vertices [] ==  vertices [x] ==  x vertices ==  . map   x . vertices ==  x  . vertices ==  .   . vertices == Set. algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list..Good consumer of lists and producer of graphs. edges [] ==  edges [(x,y)] ==  x y edges ==  .  ( )  . edges ==  .  algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list..Good consumer of lists and producer of graphs. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list..Good consumer of lists and producer of graphs. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==   algebraic-graphs Generalised ! folding: recursively collapse a  by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: empty, vertex, overlay and connect. Complexity: O(s) applications of the given functions. As an example, the complexity of  is O(s), since   and  have constant costs.Good consumer. foldg     == id foldg    (  ) ==  foldg 1 ( " 1) (+) (+) ==  foldg True ( " False) (&&) (&&) == 5 foldg False (== x) (||) (||) ==  x algebraic-graphsBuild a graph given an interpretation of the four graph construction primitives , ,  and 9, in this order. See examples for further clarification.Functions expressed with  are good producers. buildg f == f    ? buildg (\e _ _ _ -> e) == ? buildg (\_ v _ _ -> v x) ==  x buildg (\e v o c -> o ( e v o c x) ( e v o c y)) ==  x y buildg (\e v o c -> c ( e v o c x) ( e v o c y)) ==  x y buildg (\e v o _ ->  o e ( v xs)) ==  xs buildg (\e v o c ->  e v o (  c) g) ==  g  e v o c (buildg f) == f e v o c algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s. Good consumer of both arguments.  isSubgraphOf . x == True isSubgraphOf ( x) / == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True isSubgraphOf x y ==> x <= y algebraic-graphs7Structural equality on graph expressions. Complexity: O(s) time. * x === x == True x === x +  == False x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False algebraic-graphs(Check if a graph is empty. Complexity: O(s) time.Good consumer. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty ( x $  x) == True isEmpty ( x y $  x y) == False algebraic-graphsThe size of a graph, i.e. the number of leaves of the expression including  leaves. Complexity: O(s) time.Good consumer. size  == 1 size ( x) == 1 size ( x y) == size x + size y size ( x y) == size x + size y size x >= 1 size x >=  x algebraic-graphs7Check if a graph contains a given vertex. Complexity: O(s) time.Good consumer.  hasVertex x " == False hasVertex x ($ y) == (x == y) hasVertex x .  x ==   False algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.Good consumer.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y .  x y ==  ' False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity:  O(s * log(n)) time.Good consumer.  vertexCount  == 0 vertexCount (3 x) == 1 vertexCount ==  . ) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(s + m * log(m))% time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.Good consumer.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory..Good consumer of graphs and producer of lists.  vertexList  == [] vertexList ( x) == [x] vertexList .  ==  .   algebraic-graphs2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges m of a graph can be quadratic with respect to the expression size s..Good consumer of graphs and producer of lists.  edgeList  == [] edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList .  ==  .   edgeList .  ==   .  !" . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.Good consumer.  vertexSet  == Set. vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory.Good consumer. edgeSet  == Set. edgeSet ( x) == Set. edgeSet ( x y) == Set. (x,y) edgeSet .  == Set. algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and memory.Good consumer. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (0 1 2) == [(1, [2]), (2, [])] adjacencyList (, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]  . adjacencyList == id algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.Good producer. path [] ==  path [x] ==  x path [x,y] ==  x y path .   ==  . path algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.Good producer. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] circuit .   ==  . circuit algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list..Good consumer of lists and producer of graphs. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) == " (clique xs) (clique ys) clique .   ==  . clique algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists.7Good consumer of both arguments and producer of graphs. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] ==  [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list.3Good consumer of lists and good producer of graphs. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity: O(L) time, memory and size, where L! is the total size of the input..Good consumer of lists and producer of graphs. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  .  (  ) stars .  == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O(T) time, memory and size, where T is the size of the given tree (i.e. the number of vertices in the tree). forest [] == ? forest [x] ==  x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==  [(1,2), (1,3), (4,5)] forest ==  .   algebraic-graphs Construct a  mesh graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists. mesh xs [] ==  mesh [] ys ==  mesh [x] [y] ==  (x, y) mesh xs ys ==  ( xs) ( ys) mesh [1..3] "ab" ==  [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(2,'b')), ((2,'a'),(2,'b')) , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ] algebraic-graphs Construct a  torus graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists. torus xs [] ==  torus [] ys ==  torus [x] [y] == ! (x,y) (x,y) torus xs ys ==  ( xs) ( ys) torus [1,2] "ab" ==  [ ((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')) ] algebraic-graphs Construct a De Bruijn graph of a given non-negative dimension using symbols from a given alphabet. Complexity:  O(A^(D + 1)) time, memory and size, where A" is the size of the alphabet and D is the dimension of the graph. ) deBruijn 0 xs == 0 [] [] n > 0 ==> deBruijn n [] == * deBruijn 1 [0,1] ==  [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == 4 "00" "00" deBruijn 2 "01" ==  [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]  (deBruijn n xs) ==     $ deBruijn n xs  (deBruijn n xs) == ( $  xs)^n n > 0 ==>  (deBruijn n xs) == ( $  xs)^(n + 1) algebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size.Good consumer and producer. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y ( x y) ==  [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x ==  x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 # (removeEdge x y z) <= 3 *  z algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O(s) time, memory and size.Good consumer and producer. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time.Good consumer and producer. mergeVertices ( 7 False) x == id mergeVertices (== x) y ==  x y mergeVertices  & 1 (0 * 2) == 1 * 1 mergeVertices   1 (3 + 4 * 5) == 4 * 1 algebraic-graphsSplit a vertex into a list of vertices with the same connectivity. Complexity:  O(s + k * L) time, memory and size, where k is the number of occurrences of the vertex in the expression and L" is the length of the given list..Good consumer of lists and producer of graphs. %splitVertex x [] ==  x splitVertex x [x] == id splitVertex x [y] == < x y splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3) algebraic-graphs&Transpose a given graph. Complexity: O(s) time, memory and size.Good consumer and producer.  transpose  ==  transpose ( x) ==  x transpose ( x y) == , y x transpose . transpose == id transpose ( x y) ==  (transpose x) (transpose y)  . transpose ==   .  !" .  algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time.Good consumer and producer. induce (  True ) x == x induce (  False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are  . Complexity: O(s) time, memory and size.Good consumer and producer.  induceJust (  #) ==  induceJust ( (  x)  ) ==  x induceJust .    ' ==   induceJust .   (\x -> if p x then   x else  ) ==  p algebraic-graphsSimplify 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.Good consumer. simplify == id  (simplify x) <=  x simplify    simplify 1  1 simplify (1 + 1)  1 simplify (1 + 2 + 1)  1 + 2 simplify (1 * 1 * 1)  1 * 1 algebraic-graphsLeft-to-right relational composition of graphs: vertices x and z< are connected in the resulting graph if there is a vertex y , such that x is connected to y in the first graph, and y is connected to z in the second graph. There are no isolated vertices in the result. This operation is associative, has  and single- graphs as annihilating zeroes, and distributes over . Complexity: O(n * m * log(n)) time, O(n + m) memory, and  O(m1 + m2) size, where n and m stand for the number of vertices and edges in the resulting graph, while m1 and m2 are the number of edges in the original graphs. Note that the number of edges in the resulting graph may be quadratic, i.e. m = O(m1 * m2)2, but the algebraic representation requires only  O(m1 + m2) operations to list them.2Good consumer of both arguments and good producer. compose  x ==  compose x  ==  compose ( x) y ==  compose x ( y) ==  compose x (compose y z) == compose (compose x y) z compose x ( y z) == & (compose x y) (compose x z) compose ( x y) z == & (compose x z) (compose y z) compose ( x y) ( y z) ==  x z compose ( [1..5]) ( [1..5]) ==  [(1,3), (2,4), (3,5)] compose ( [1..5]) ( [1..5]) ==  [1,3,5,2,4] ) (compose x y) <=  x +  y + 1 algebraic-graphs Compute the Cartesian product of graphs. Complexity:  O(s1 * s2) time, memory and size, where s1 and s2$ are the sizes of the given graphs. box ( [0,1]) ( "ab") ==  [ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((0,'b'), (1,'b')) , ((1,'a'), (1,'b')) ] Up to isomorphism between the resulting vertex types, this operation is  commutative,  associative,  distributes over , has singleton graphs as  identities and  as the annihilating zero. Below ~~1 stands for 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 z) ==  (box x y) (box x z) box x ( ()) ~~ x box x  ~~   (box x y) == box ( x) ( y)  (box x y) ==  x *  y  (box x y) <=  x *  y +  x *  y algebraic-graphsSparsify a graph by adding intermediate   Int vertices between the original vertices (wrapping the latter in  $) such that the resulting graph is sparse, i.e. contains only O(s) edges, but preserves the reachability relation between the original vertices. Sparsification is useful when working with dense graphs, as it can reduce the number of edges from O(n^2) down to O(n) by replacing cliques, bicliques and similar densely connected structures by sparse subgraphs built out of intermediate vertices. Complexity: O(s) time, memory and size.   .  # x ==   . () .  # (sparsify x) . (*  (sparsify x) <=  x +  x + 1  (sparsify x) <= 3 *  x  (sparsify x) <= 3 *  x algebraic-graphs:Sparsify a graph whose vertices are integers in the range [1..n] , where n is the first argument of the function, producing an array-based graph representation from  Data.Graph (introduced by King and Launchbury, hence the name of the function). In the resulting graph, vertices [1..n] correspond to the original vertices, and all vertices greater than n1 are introduced by the sparsification procedure. Complexity: O(s) time and memory. Note that thanks to sparsification, the resulting graph has a linear number of edges with respect to the size of the original algebraic representation even though the latter can potentially contain a quadratic O(s^2) number of edges.   .  # x ==   .   (<= n) . +# (sparsifyKL n x)  (+, $ sparsifyKL n x) <=  x +  x + 1  (+- $ sparsifyKL n x) <= 3 *  x algebraic-graphs Extract the 8 of a subgraph specified by a given predicate. Returns Nothing$ if the specified subgraph is empty.Good consumer.  context ( > False) x == Nothing context (== 1) ( 1 2) == Just (% [ ] [2 ]) context (== 2) ( 1 2) == Just ( [1 ] [ ]) context (  True ) ( 1 2) == Just ( [1 ] [2 ]) context (== 4) (3 * 1 * 4 * 1 * 5) == Just ( [3,1] [1,5]) algebraic-graphs Defined via  and .algebraic-graphs Defined via .algebraic-graphs ! is a good consumer and producer.algebraic-graphs > is a good consumer of its first argument and a good producer.algebraic-graphs & is a good consumer of both arguments.algebraic-graphs & is a good consumer of both arguments.algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.algebraic-graphs ! is a good consumer and producer.::4(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?/algebraic-graphs The class of preorder graphs( that are both reflexive and transitive.algebraic-graphs The class of transitive graphs- that satisfy the following additional axiom.The closure8 axiom: graphs with equal transitive closures are equal. 5y /= empty ==> x * y + x * z + y * z == x * y + y * zBy repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction.algebraic-graphs The class of reflexive graphs- that satisfy the following additional axiom.Each vertex has a  self-loop: vertex x == vertex x * vertex x'Or, alternatively, if we remember that  is an alias for  : pure x == pure x * pure xNote that by applying the axiom in the reverse direction, one can always remove all self-loops resulting in an irreflexive graph. This type class can therefore be also used in the context of irreflexive graphs.algebraic-graphs The class of undirected graphs- that satisfy the following additional axiom. is commutative: x * y == y * xalgebraic-graphsThe core type class for constructing algebraic graphs is defined by introducing the  method to the standard  2 class and reusing the following existing methods:The  method comes from the   class and corresponds to the  empty graph#. This module simply re-exports it.The . graph construction primitive is an alias for   of the   type class.Graph  is an alias for mplus of the   type class.The  type class is characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for  and , respectively. is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z is associative and has  as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * zThe following useful theorems can be proved from the above set of axioms. has # as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of : -x * y + x + y == x * y x * x * x == x * xThe core type class , corresponds to unlabelled directed graphs. , ,  and ? graphs can be obtained by extending the minimal set of axioms.When specifying the time and memory complexity of graph algorithms, n2 will denote the number of vertices in the graph, m3 will denote the number of edges in the graph, and s will denote the size of the corresponding  expression.algebraic-graphsConnect two graphs.algebraic-graphsConstruct the graph comprising a single isolated vertex. An alias for  .algebraic-graphs!Overlay two graphs. An alias for  .algebraic-graphs-Construct the graph comprising a single edge. edge x y ==  ( x) ( y)  vertexCount (edge 1 1) == 1  vertexCount (edge 1 2) == 2 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x vertices ==  . map   hasVertex x . vertices ==  x  vertexCount . vertices ==  .   vertexSet . vertices == Set../ algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] ==  edges [(x,y)] ==  x y algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==    isEmpty . overlays ==  isEmpty algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==    isEmpty . connects ==  isEmpty algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph3 of the second. Here is the current implementation: isSubgraphOf x y =  x y == y The complexity therefore depends on the complexity of equality testing of the specific graph instance.  isSubgraphOf - x == True isSubgraphOf ( x) . == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (4 x y) == True hasEdge x y ==  (x,y) . edgeList algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] ==  path [x] ==  x path [x,y] ==  x y algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) ==  (clique xs) (clique ys) algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] ==  [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of  adjacencyList. Complexity: O(L) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  .  (  ) stars .  adjacencyList == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O(T) time, memory and size, where T is the size of the given tree (i.e. the number of vertices in the tree). forest [] == ? forest [x] ==  x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==  [(1,2), (1,3), (4,5)] forest ==  .   algebraic-graphs Construct a  mesh graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists. mesh xs [] ==  mesh [] ys ==  mesh [x] [y] ==  (x, y) mesh xs ys == box ( xs) ( ys) mesh [1..3] "ab" ==  [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(2,'b')), ((2,'a'),(2,'b')) , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ] algebraic-graphs Construct a  torus graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists. torus xs [] ==  torus [] ys ==  torus [x] [y] == ! (x,y) (x,y) torus xs ys == box ( xs) ( ys) torus [1,2] "ab" ==  [ ((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')) ] algebraic-graphs Construct a De Bruijn graph of a given non-negative dimension using symbols from a given alphabet. Complexity:  O(A^(D + 1)) time, memory and size, where A" is the size of the alphabet and D is the dimension of the graph. ) deBruijn 0 xs == 0 [] [] n > 0 ==> deBruijn n [] == * deBruijn 1 [0,1] ==  [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == 4 "00" "00" deBruijn 2 "01" ==  [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ] transpose (deBruijn n xs) ==     $ deBruijn n xs  vertexCount (deBruijn n xs) == ( $  xs)^n n > 0 ==>  edgeCount (deBruijn n xs) == ( $  xs)^(n + 1) algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True algebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O(s) time, memory and size. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time. mergeVertices ( 7 False) x == id mergeVertices (== x) y ==  x y mergeVertices  & 1 (0 * 2) == 1 * 1 mergeVertices   1 (3 + 4 * 5) == 4 * 1 algebraic-graphsSplit a vertex into a list of vertices with the same connectivity. Complexity:  O(s + k * L) time, memory and size, where k is the number of occurrences of the vertex in the expression and L" is the length of the given list. %splitVertex x [] ==  x splitVertex x [x] == id splitVertex x [y] == < x y splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)  (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?9algebraic-graphsA list of values of two alternating types. The first type argument denotes the type of the value at the head. With the OverloadedLists extension it is possible to use the standard list notation to construct a + where the two types coincide, for example:  [1, 2, 3, 4, 5] :: List Int Int =We make use of this shorthand notation in the examples below.algebraic-graphsThe 01 data type represents an undirected bipartite graph. The two type parameters determine the types of vertices of each part. If the types coincide, the vertices of the left part are still treated as disjoint from the vertices of the right part. See examples for more details. We define a  instance as a convenient notation for working with bipartite graphs: 0 ==  0  1 ==  1  1 + 2 ==  [1] [2]  1 * 2 ==  1 2  1 + 2 *  3 ==  ( 1) ( 3 2)  1 * (2 +  3) ==  ( 1) ( [3] [2]) Note: the 7 instance does not satisfy several "customary laws" of , which dictate that  0 and  1; should act as additive and multiplicative identities, and 0 as additive inverse. Nevertheless, overloading ,  and  is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ? instance is defined using basic graph construction primitives: show empty == "empty" show 1 == "rightVertex 1" show ( 2) == "leftVertex 2" show (1 + 2) == "vertices [] [1,2]" show (. (1 + 2)) == "vertices [1,2] []" show (% 1 * 2) == "edge 1 2" show ( 1 * 2 * # 3) == "edges [(1,2),(3,2)]" show ( 1 * 2 + + 3) == "overlay (leftVertex 3) (edge 1 2)" The  instance satisfies all axioms of undirected bipartite algebraic graphs: is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z% is commutative, associative and has  as the identity:  x * empty == x empty * x == x x * y == y * x x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * z has the same effect as  on vertices of the same part:  leftVertex x * leftVertex y == leftVertex x + leftVertex y rightVertex x * rightVertex y == rightVertex x + rightVertex yThe following useful theorems can be proved from the above set of axioms. has # as the identity and is idempotent: ,x + empty == x empty + x == x x + x == xAbsorption and saturation of : -x * y + x + y == x * y x * x * x == x * xWhen specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges of the graph, respectively. In addition, l and r will denote the number of vertices in the left and right parts of the graph, respectively.algebraic-graphsThe  adjacency map of the left part of the graph: each left vertex is associated with a set of its right neighbours. Complexity: O(1) time and memory. leftAdjacencyMap  == Map. leftAdjacencyMap ( x) == Map. x Set. leftAdjacencyMap ( x) == Map. leftAdjacencyMap ( x y) == Map. x (Set. y) algebraic-graphsThe  adjacency map of the right part of the graph: each right vertex is associated with a set of its left neighbours. Complexity: O(1) time and memory. rightAdjacencyMap  == Map. rightAdjacencyMap ( x) == Map. rightAdjacencyMap ( x) == Map. x Set. rightAdjacencyMap ( x y) == Map. y (Set. x) algebraic-graphsConstruct the  empty graph.  empty == True  empty == Map.  empty == Map.  x empty == False algebraic-graphsConstruct the graph comprising a single isolated vertex in the left part.  (leftVertex x) == Map. x Set.  (leftVertex x) == Map.  x (leftVertex y) == (x == y)  x (leftVertex y) == False # x y (leftVertex z) == False algebraic-graphsConstruct the graph comprising a single isolated vertex in the right part.  (rightVertex x) == Map.  (rightVertex x) == Map. x Set.  x (rightVertex y) == False  x (rightVertex y) == (x == y) $ x y (rightVertex z) == False algebraic-graphsConstruct the graph comprising a single isolated vertex. vertex . Left ==  vertex . Right ==  algebraic-graphsConstruct the graph comprising  a single edge.  edge x y ==  ( x) ( y)  (edge x y) == Map. x (Set. y)  (edge x y) == Map. y (Set. x)  x y (edge x y) == True  1 2 (edge 2 1) == False algebraic-graphsOverlay two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O((n + m) * log(n)) time and O(n + m) memory.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y algebraic-graphsConnect two graphs, filtering out the edges between vertices of the same part. This is a commutative and associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices in the arguments: O(m1 + m2 + l1 * r2 + l2 * r1).  connect ( x) ( y) ==  [x,y] [] connect ( x) ( y) ==  x y connect ( x) ( y) ==  y x connect ( x) ( y) ==  [] [x,y] connect ( xs1 ys1) ( xs2 ys2) ==  ( xs1 ys2) ( xs2 ys1) * (connect x y) ==  x &&  y ( z (connect x y) ==  z x ||  z y & (connect x y) >=  x & (connect x y) <=  x +  y ( (connect x y) >=  x ( (connect x y) >=  x *  y ( (connect x y) <=  x *  y +  x *  y +  x +  y algebraic-graphsConstruct the graph comprising given lists of isolated vertices in each part. Complexity:  O(L * log(L)) time and O(L) memory, where L# is the total length of two lists. %vertices [] [] == & vertices [x] [] == ( x vertices [] [x] == ( x vertices xs ys ==  (  xs ++   ys)  x (vertices xs ys) ==  x xs  y (vertices xs ys) ==  y ys algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] ==  edges [(x,y)] ==  x y edges ==  .  ( )  x y . edges ==  (x,y)  . edges ==  . nub algebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] ==  connects [x] == x connects [x,y] == connect x y connects ==     . connects ==   algebraic-graphs.Swap the parts of a given graph. Complexity: O(1) time and memory. swap  ==  swap .  ==  swap ( xs ys) ==  ys xs swap ( x y) ==  y x swap .  ==  .  Data.Tuple.  swap . swap ==   algebraic-graphsConstruct a bipartite  from an Algebra.Graph.AdjacencyMap, adding any missing edges to make the graph undirected and filtering out the edges within the same parts. Complexity:  O(m * log(n)).  toBipartite 2 ==  toBipartite (3 (Left x)) ==  x toBipartite (3 (Right x)) ==  x toBipartite (4 (Left x) (Left y)) ==  [x,y] [] toBipartite (4 (Left x) (Right y)) ==  x y toBipartite (4 (Right x) (Left y)) ==  y x toBipartite (4 (Right x) (Right y)) ==  [] [x,y] toBipartite . 5 ==   .   toBipartite .  ==   algebraic-graphsConstruct a bipartite  from an Algebra.Graph.AdjacencyMap, where the two parts are identified by a separate function, adding any missing edges to make the graph undirected and filtering out the edges within the same parts. Complexity:  O(m * log(n)). toBipartiteWith f 2 ==  toBipartiteWith Left x ==  (" x) [] toBipartiteWith Right x ==  [] ( x) toBipartiteWith f ==  . 6 f toBipartiteWith id ==  algebraic-graphs Construct an Algebra.Graph.AdjacencyMap from a bipartite . Complexity:  O(m * log(n)). fromBipartite  == 2 fromBipartite ( x) == 3 (Left x) fromBipartite ( x y) == -( [(Left x, Right y), (Right y, Left x)]  . fromBipartite ==   algebraic-graphs Construct an Algebra.Graph.AdjacencyMap from a bipartite  given a way to inject vertices of the two parts into the resulting vertex type. Complexity:  O(m * log(n)). ,fromBipartiteWith Left Right ==  fromBipartiteWith id id ( xs ys) == ,& (xs ++ ys) fromBipartiteWith id id .  == 7 . - algebraic-graphs(Check if a graph is empty. Complexity: O(1) time. isEmpty " == True isEmpty (  ) == True isEmpty (> x) == False isEmpty == (==)  algebraic-graphsCheck if a graph contains a given vertex in the left part. Complexity:  O(log(l)) time. hasLeftVertex x % == False hasLeftVertex x (" y) == (x == y) hasLeftVertex x ( y) == False algebraic-graphsCheck if a graph contains a given vertex in the right part. Complexity:  O(log(r)) time. hasRightVertex x & == False hasRightVertex x ( y) == False hasRightVertex x ( y) == (x == y) algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time. hasVertex . Left ==  hasVertex . Right ==  algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y  == False hasEdge x y ( z) == False hasEdge x y (( x y) == True hasEdge x y ==  (x,y) .  algebraic-graphsThe number of vertices in the left part of a graph. Complexity: O(1) time. leftVertexCount ! == 0 leftVertexCount ( x) == 1 leftVertexCount ( x) == 0 leftVertexCount (" x y) == 1 leftVertexCount .  ==  . nub .    algebraic-graphsThe number of vertices in the right part of a graph. Complexity: O(1) time. rightVertexCount " == 0 rightVertexCount ( x) == 0 rightVertexCount ( x) == 1 rightVertexCount (# x y) == 1 rightVertexCount .  ==  . nub .    algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount ( x) == 1 vertexCount (% x y) == 2 vertexCount x ==  x +  x algebraic-graphs-The number of edges in a graph. Complexity: O(l) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount ( x y) == 1 edgeCount .  ==  . nub algebraic-graphsThe sorted list of vertices of the left part of a graph. Complexity: O(l) time and memory. leftVertexList $ == [] leftVertexList ( x) == [x] leftVertexList ( x) == [] leftVertexList .    [] == nub .   algebraic-graphsThe sorted list of vertices of the right part of a graph. Complexity: O(r) time and memory. rightVertexList " == [] rightVertexList ( x) == [] rightVertexList ( x) == [x] rightVertexList .  [] == nub .   algebraic-graphs5The sorted list of vertices of a graph. Complexity: O(n) time and memory  vertexList / == [] vertexList (. x) == [x] vertexList (> x y) == [Left x, Right y] vertexList ( (  xs) (  xs)) == nub (  xs) algebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList  == [] edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList .  == nub .   algebraic-graphs>The set of vertices of the left part of a graph. Complexity: O(l) time and memory. leftVertexSet  == Set. leftVertexSet .  == Set. leftVertexSet .  ==   Set. leftVertexSet .    [] == Set. algebraic-graphs?The set of vertices of the right part of a graph. Complexity: O(r) time and memory. rightVertexSet  == Set. rightVertexSet .  ==   Set. rightVertexSet .  == Set. rightVertexSet .  [] == Set. algebraic-graphs-The set of vertices of a graph. Complexity: O(n) time and memory.  vertexSet $ == Set. vertexSet . ! == Set. vertexSet ($ x y) == Set. [Left x, Right y] vertexSet ( (  xs) (  xs)) == Set. xs algebraic-graphs*The set of edges of a graph. Complexity: O(n + m) time and O(m) memory. edgeSet  == Set.82 edgeSet ( x) == Set.82 edgeSet ( x y) == Set.89 (x,y) edgeSet .  == Set.8/ algebraic-graphs The sorted adjacency list+ of the left part of a graph. Complexity: O(n + m) time and memory. leftAdjacencyList % == [] leftAdjacencyList (! [] xs) == [] leftAdjacencyList ( xs []) == [(x, []) | x <- nub (  xs)] leftAdjacencyList (- x y) == [(x, [y])] leftAdjacencyList ( x ys) == [(x, nub (  ys))] algebraic-graphs The sorted adjacency list, of the right part of a graph. Complexity: O(n + m) time and memory. rightAdjacencyList & == [] rightAdjacencyList ( [] xs) == [(x, []) | x <- nub (  xs)] rightAdjacencyList (" xs []) == [] rightAdjacencyList (. x y) == [(y, [x])] rightAdjacencyList (! x ys) == [(y, [x]) | y <- nub (  ys)] algebraic-graphs Construct a % of even length from a list of pairs. evenList [] == 0 evenList [(1,2), (3,4)] == [1, 2, 3, 4] :: ( Int Int evenList [(1,'a'), (2,'b')] ==  1 ( 'a' ( 2 ( 'b' ))) algebraic-graphs Construct a ; of odd length given the first element and a list of pairs.  oddList 1 [] ==  1 4 oddList 1 [(2,3), (4,5)] == [1, 2, 3, 4, 5] :: ) Int Int oddList 1 [('a',2), ('b',3)] ==  1 ( 'a' ( 2 ( 'b' ( 3 )))) algebraic-graphsThe path on a  of vertices. Complexity:  O(L * log(L)) time, where L! is the length of the given list. path  ==  path ( x ) ==  x path ( x ( y )) == # x y path [1, 2, 3, 4, 5] ==  [(1,2), (3,2), (3,4), (5,4)] algebraic-graphsThe circuit. on a list of pairs of vertices. Complexity:  O(L * log(L))/ time, where L is the length of the given list. !circuit [] == " circuit [(x,y)] == & x y circuit [(1,2), (3,4), (5,6)] == 6 [(1,2), (3,2), (3,4), (5,4), (5,6), (1,6)] circuit .   ==  . circuit .  Data.Tuple.  algebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique [] [] ==  biclique xs [] ==  xs [] biclique [] ys ==  [] ys biclique xs ys ==  ( xs []) ( [] ys) algebraic-graphsThe star formed by a center vertex connected to a list of leaves. Complexity:  O(L * log(L)) time, where L! is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( [] ys) algebraic-graphsThe stars formed by overlaying a list of s. Complexity:  O(L * log(L)) time, where L is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  .  ( ) + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsRemove a vertex from the left part of a given graph. Complexity:  O(r * log(l)) time. removeLeftVertex x ( x) ==  removeLeftVertex 1 ( 2) ==  2 removeLeftVertex x ( y) ==  y removeLeftVertex x ( x y) ==  y removeLeftVertex x . removeLeftVertex x == removeLeftVertex x algebraic-graphsRemove a vertex from the right part of a given graph. Complexity:  O(l * log(r)) time. removeRightVertex x ( x) ==  removeRightVertex 1 ( 2) ==  2 removeRightVertex x ( y) ==  y removeRightVertex y ( x y) ==  x removeRightVertex x . removeRightVertex x == removeRightVertex x algebraic-graphs0Remove an edge from a given graph. Complexity: O(log(l) + log(r)) time. removeEdge x y ( x y) ==  [x] [y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x ==  x removeEdge x y .  y ==  y algebraic-graphsTransform a graph by applying given functions to the vertices of each part. Complexity: O((n + m) * log(n)) time.  bimap f g  ==  bimap f g .  ==  . Data.Bifunctor.:; f g bimap f g ( x y) ==  (f x) (g y) bimap     ==  8 bimap f1 g1 . bimap f2 g2 == bimap (f1 . f2) (g1 . g2) algebraic-graphs Construct a mesh0 graph from two lists of vertices. Complexity: O(L1 * L2 * log(L1 * L2)) time, where L1 and L2% are the lengths of the given lists. mesh xs [] ==  mesh [] ys ==  mesh [x] [y] ==  (x,y) mesh [1,1] ['a','b'] == ? [(1,'a'), (1,'b')] [(1,'a'), (1,'b')] mesh [1,2] ['a','b'] == ' [(1,'a'), (2,'b')] [(1,'b'), (2,'a')] algebraic-graphs Compute the Cartesian product of two graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.  ( [0,1]) ( ['a','b']) ==  [ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((1,'b'), (0,'b')) , ((1,'b'), (1,'a')) ] Up to isomorphism between the resulting vertex types, this operation is  commutative,  associative,  distributes over , has singleton graphs as  identities and swapping identities, and  as the annihilating zero. Below ~~1 stands for 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 z) ==  (box x y) (box x z) box x ( ()) ~~ x box x ( ()) ~~  x box x  ~~   (box x y) ==  x *  y  (box x y) ==  x *  y +  x *  y algebraic-graphsCompute the generalised Cartesian product of two graphs. The resulting vertices are obtained using the given vertex combinators. Complexity: O((n + m) * log(n)) time and O(n + m) memory.See  for some examples. box == boxWith (,) (,) (,) (,) algebraic-graphsCheck that the internal graph representation is consistent, i.e. that all edges that are present in the  are also present in the  map. It should be impossible to create an inconsistent adjacency map, and we use this function in testing.  consistent  == True consistent ( x) == True consistent ( x y) == True consistent ( x) == True consistent ( x) == True consistent ( x) == True consistent ( x) == True consistent ( x y) == True algebraic-graphs Defined via  and .algebraic-graphs Defined via .algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.88(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?/algebraic-graphsAn independent set of a bipartite graph.An independent set is a subset of vertices such that no two of them are adjacent. We represent independent sets by storing two sets of vertices, one for each part. An equivalent representation, which is slightly less memory efficient, is Set (Either a b).algebraic-graphsA  vertex cover of a bipartite graph.A  vertex cover is a subset of vertices such that every edge is incident to some vertex in the subset. We represent vertex covers by storing two sets of vertices, one for each part. An equivalent representation, which is slightly less memory efficient, is Set (Either a b).algebraic-graphsA matching is a set of pairwise non-adjacent edges between the two parts of a bipartite graph.The  instance is defined using the  function, with the edges listed in the ascending order of left vertices. show (, []) == "matching []" show (5 [(2,'a'), (1,'b')]) == "matching [(1,'b'),(2,'a')]" algebraic-graphsThe map of vertices covered by the matching in the left part to their neighbours in the right part. Complexity: O(1) time.  pairOfLeft ( []) == Map.<2 pairOfLeft ( [(2,'a'), (1,'b')]) == Map.</ [(1,'b'), (2,'a')] Map. ( . pairOfLeft == Map.  . pairOfRight algebraic-graphsThe map of vertices covered by the matching in the right part to their neighbours in the left part. Complexity: O(1).  pairOfRight ( []) == Map.<2 pairOfRight ( [(2,'a'), (1,'b')]) == Map.</ [('a',2), ('b',1)] Map. ) . pairOfRight == Map.  . pairOfLeft algebraic-graphs$A cycle of odd length. For example, [1,2,3] represents the cycle 1 -> 2 -> 3 -> 1.algebraic-graphs"Test the bipartiteness of a given Algebra.Graph.AdjacencyMap!. In case of success, return an  with the same set of edges and each vertex marked with the part it belongs to. In case of failure, return any cycle of odd length in the graph.The returned partition is lexicographically smallest, assuming that vertices of the left part precede all the vertices of the right part.The returned cycle is optimal in the following sense: there exists a path that is either empty or ends in a vertex adjacent to the first vertex in the cycle, such that all vertices in path ++ cycle are distinct and path ++ cycle is lexicographically smallest among all such pairs of paths and cycles.Note: since  represents  undirected bipartite graphs, all edges in the input graph are treated as undirected. See the examples and the correctness property for a clarification. Complexity: O((n + m) * log(n)) time and O(n + m) memory.  detectParts 20 == Right  detectParts (3/ x) == Right ( x) detectParts (4 x x) == Left [x] detectParts (41 1 2) == Right ( 1 2) detectParts (1 * (2 + 3)) == Right ( [(1,2), (1,3)]) detectParts (1 * 2 * 3) == Left [1, 2, 3] detectParts ((1 + 3) * (2 + 4) + 6 * 5) == Right ( (1 + 3) * (2 + 4) +  5 * 6) detectParts ((1 * 3 * 4) + 2 * (1 + 2)) == Left [2] detectParts (5 [1..10]) == Left [1, 2, 3] detectParts (=. [1..10]) == Right (/ [(x, x + 1) | x <- [1,3,5,7,9]]) detectParts (= [1..11]) == Left [1..11] detectParts (>- [] xs) == Right ( xs []) detectParts (> ( Left (x:xs)) ( Right ys)) == Right ( ( Left (x:xs)) ( Right ys)) isRight (detectParts (?! x ys)) ==   x ys isRight (detectParts ( ( x))) == True The correctness of , can be expressed by the following property: let undirected = 76 input in case detectParts input of Left cycle ->   (length cycle) 2 == 1 && @ (=' cycle) undirected Right result -> 6 AB ( result) == undirected algebraic-graphs Construct a $ from a list of edges. Complexity:  O(L * log(L)) time, where L! is the length of the given list.Edges that appear closer to the end of the list supersede all previous edges. That is, if two edges from the list share a vertex, the one that appears closer to the beginning is ignored. + (matching []) == Map.<2 * (matching []) == Map.<2 + (matching [(2,'a'), (1,'b')]) == Map.</ [(2,'a'), (1,'b')] + (matching [(1,'a'), (1,'b')]) == Map.<9 1 'b' matching [(1,'a'), (1,'b'), (2,'b'), (2,'a')] == matching [(2,'a')] algebraic-graphsCheck if a given  is a valid matching$ of a bipartite graph. Complexity:  O(S * log(n)), where S is the size of the matching. isMatchingOf (+ []) x == True isMatchingOf ( xs)  ==   xs isMatchingOf ( [(x,y)]) ( x y) == True isMatchingOf ( [(1,2)]) ( 2 1) == False algebraic-graphs0The number of edges in a matching. Complexity: O(1) time. matchingSize (( []) == 0 matchingSize (( [(2,'a'), (1,'b')]) == 2 matchingSize (( [(1,'a'), (1,'b')]) == 1 matchingSize ( xs) <= 6 xs matchingSize == Map.<C .  algebraic-graphsFind a maximum matching in a bipartite graph. A matching is maximum if it has the largest possible size. Complexity: O(m * sqrt(n) * log(n)) time.  maxMatching - ==  [] maxMatching () xs ys) ==  [] maxMatching (- [1,2,3,4]) ==  [(1,2), (3,4)]  (maxMatching ( [(1,2), (3,4), (5,6)])) == 3  (maxMatching (! x (y:ys))) == 1  (maxMatching ( xs ys)) ==   ( ( xs)) ( ( ys)) 7 (maxMatching x) x == True algebraic-graphs#Check if a given pair of sets is a  vertex cover$ of a bipartite graph. Complexity:  O(m * log(n)). 3isVertexCoverOf (xs , ys )  == Set.  xs && Set. 8 ys isVertexCoverOf (xs , ys ) ( x) == Set.  xs (Set. x) && Set.  ys isVertexCoverOf (Set. , Set. ) (( x y) == False isVertexCoverOf (Set. x, ys ) ( x y) == Set.  ys (Set.* y) isVertexCoverOf (xs , Set. y) ( x y) == Set.  xs (Set. x) algebraic-graphs7The number of vertices in a vertex cover. Complexity: O(1) time.algebraic-graphsFind a minimum vertex cover in a bipartite graph. A vertex cover is minimum if it has the smallest possible size. Complexity: O(m * sqrt(n) * log(n)). minVertexCover & == (Set., Set.) minVertexCover (" xs ys) == (Set., Set.) minVertexCover (& [1,2,3]) == (Set., Set. 2) minVertexCover (& x (1:2:ys)) == (Set. x, Set.)  (minVertexCover ( xs ys)) ==   ( ( xs)) ( ( ys)) & . minVertexCover ==  .  + (minVertexCover x) x == True algebraic-graphs$Check if a given pair of sets is an independent set$ of a bipartite graph. Complexity:  O(m * log(n)). 6isIndependentSetOf (xs , ys )  == Set.  xs && Set. ; ys isIndependentSetOf (xs , ys ) ( x) == Set.  xs (Set. x) && Set.  ys isIndependentSetOf (Set. , Set. ) (* x y) == True isIndependentSetOf (Set. x, ys ) ( x y) == Set. - ys isIndependentSetOf (xs , Set. y) ( x y) == Set.  xs algebraic-graphs;The number of vertices in an independent set. Complexity: O(1) time.algebraic-graphsFind a maximum independent set in a bipartite graph. An independent set is maximum if it has the largest possible size. Complexity: O(m * sqrt(n) * log(n)). maxIndependentSet ) == (Set., Set.) maxIndependentSet (% xs ys) == (Set. xs, Set. ys) maxIndependentSet () [1,2,3]) == (Set. [1,3], Set.) maxIndependentSet () x (1:2:ys)) == (Set., Set. (1:2:ys))  (maxIndependentSet ( xs ys)) ==   ( ( xs)) ( ( ys)) ) (maxIndependentSet x) ==  x -  ( x) . (maxIndependentSet x) x == True algebraic-graphs5Given a matching in a bipartite graph, find either a  vertex cover of the same size or an augmenting path with respect to the matching, thereby demonstrating that the matching is not maximum. Complexity: O((m + n) * log(n)).An alternating path is a path whose edges belong alternately to the matching and not to the matching. An augmenting path is an alternating path that starts from and ends on the vertices that are not covered by the matching. A matching is maximum if and only if there is no augmenting path with respect to it. augmentingPath ( [])  == Left (Set., Set.) augmentingPath ( []) (+ 1 2) == Right [1,2] augmentingPath ( [(1,2)]) ( [1,2,3]) == Left (Set., Set. 2) augmentingPath ( [(3,2)]) (7 [1,2,3,4]) == Right [1,2,3,4] isLeft (augmentingPath ( x) x) == True algebraic-graphsCheck if the internal representation of a matching is consistent, i.e. that every edge that is present in  is also present in . Complexity:  O(S * log(S)), where S is the size of the matching. consistentMatching (# xs) == True consistentMatching ( x) == True  (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?E!algebraic-graphsThe  semiring specialised to 2finding the lexicographically smallest widest path.algebraic-graphsThe  semiring specialised to counting all shortest paths.algebraic-graphsThe  semiring specialised to finding all shortest paths.algebraic-graphsThe  semiring specialised to 4finding the lexicographically smallest shortest path.algebraic-graphsA path is a list of edges.algebraic-graphsAn optimum semiring" obtained by combining a semiring o that defines an optimisation criterion, and a semiring a that describes the  arguments7 of an optimisation problem. For example, by choosing o =  Int and and a =  ( String), we obtain the shortest path semiring( for computing the shortest path in an Int-labelled graph with String vertices.We assume that the semiring o is  selective i.e. for all x and y: x <+> y == x || x <+> y == yIn words, the operation ? always simply selects one of its arguments. For example, the  and + semirings are selective, whereas the the  semiring is not.algebraic-graphsA type synonym for regular expressions, built on top of  free labels.algebraic-graphs The type of  free labels$ over the underlying set of symbols a,. This data type is an instance of classes  and .algebraic-graphsThe  power set% over the underlying set of elements a. If a* is a monoid, then the power set forms a  as follows:  = PowerSet Set.  = PowerSet $ Set.   x  y = PowerSet $ Set. # (getPowerSet x) (getPowerSet y) x  y = PowerSet $   ! (getPowerSet x) (getPowerSet y) algebraic-graphsIf a is a monoid,  a forms the following :  =   =     () =     () =     $To create a singleton value of type  a use the   function. For example:  getMinimum (  "Hello, "   ) "World!") == Just "Hello, " getMinimum (  "Hello, "   # "World!") == Just "Hello, World!" algebraic-graphsA distance% is a non-negative value that can be  or . Distances form a  as follows:  =    = 0 () =   () = () algebraic-graphsA count% is a non-negative value that can be  or . Counts form a  as follows:  = 0  = 1 () = () () = () algebraic-graphsA capacity% is a non-negative value that can be  or . Capacities form a  as follows:  = 0  =   () =   () =   algebraic-graphs!A non-negative value that can be  or +. Note: the current implementation of the ; instance raises an error on negative literals and on the  method.algebraic-graphsA dioid is an idempotent semiring", i.e. it satisfies the following  idempotence law in addition to the  laws:  x <+> x == xalgebraic-graphsA  star semiring is a # with an additional unary operator # satisfying the following two laws: ;star a = one <+> a <.> star a star a = one <+> star a <.> aalgebraic-graphsA semiring extends a commutative   with operation  that acts similarly to multiplication over the underlying (additive) monoid and has  as the identity. This module also provides two convenient aliases:  for  , and  for  ), which makes the interface more uniform.Instances of this type class must satisfy the following semiring laws:Associativity of  and : x <+> (y <+> z) == (x <+> y) <+> z x <.> (y <.> z) == (x <.> y) <.> zIdentities of  and : :zero <+> x == x == x <+> zero one <.> x == x == x <.> oneCommutativity of : x <+> y == y <+> x Annihilating : %x <.> zero == zero zero <.> x == zeroDistributivity: x <.> (y <+> z) == x <.> y <+> x <.> z (x <+> y) <.> z == x <.> z <+> y <.> zalgebraic-graphs An alias for  .algebraic-graphs An alias for  .algebraic-graphsA finite non-negative value or Nothing if the argument is negative.algebraic-graphs A finite  .algebraic-graphs%A non-negative finite value, created unsafely:: the argument is not checked for being non-negative, so unsafeFinite (-1) compiles just fine.algebraic-graphs"The (non-negative) infinite value.algebraic-graphsGet a finite value or Nothing if the value is infinite.algebraic-graphsA non-negative capacity.algebraic-graphsGet the value of a capacity.algebraic-graphsA non-negative count.algebraic-graphsGet the value of a count.algebraic-graphsA non-negative distance.algebraic-graphsGet the value of a distance.algebraic-graphsExtract the minimum or Nothing if it does not exist.algebraic-graphsThe value corresponding to the lack of minimum, e.g. the minimum of the empty set.algebraic-graphs Check if a  is .)) 6 776 (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?&,algebraic-graphsThe  data type represents a graph by a map of vertices to their adjacency sets. We define a ; instance as a convenient notation for working with graphs: 0 ==  0 1 + 2 ==  ( 1) ( 2) 1 * 2 ==  ( 1) ( 2) 1 + 2 * 3 ==  ( 1) ( ( 2) ( 3)) 1 * (2 + 3) ==  ( 1) ( ( 2) ( 3)) Note: the   method of the type class  cannot be implemented and will throw an error. Furthermore, the 7 instance does not satisfy several "customary laws" of , which dictate that  0 and  1; should act as additive and multiplicative identities, and 0 as additive inverse. Nevertheless, overloading ,  and  is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ? instance is defined using basic graph construction primitives: show (1 :: AdjacencyMap Int) == "vertex 1" show (1 + 2 :: AdjacencyMap Int) == "vertices1 [1,2]" show (1 * 2 :: AdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyMap Int) == "edges1 [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"The ; instance satisfies the following laws of algebraic graphs:, is commutative, associative and idempotent:  x + y == y + x x + (y + z) == (x + y) + z x + x == x is associative: x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * z% satisfies absorption and saturation: -x * y + x + y == x * y x * x * x == x * xWhen specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges in the graph, respectively.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:  1 <  2  3 <  1 2  1 <  1 1  1 1 <  1 2  1 2 <  1 1 +  2 2  1 2 <  1 3*Note that the resulting order refines the ! relation and is compatible with  and  operations:  x y ==> x <= y x <= x + y x + y <= x * yalgebraic-graphsConvert a possibly empty  into NonEmpty. . Returns   if the argument is . Complexity: O(1) time, memory and size.  toNonEmpty  ==   toNonEmpty .  ==   algebraic-graphsConvert a NonEmpty. into an . The resulting graph is guaranteed to be non-empty. Complexity: O(1) time, memory and size. isEmpty . fromNonEmpty ==      . fromNonEmpty ==   algebraic-graphsConstruct the graph comprising a single isolated vertex.  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0 algebraic-graphsConstruct the graph comprising  a single edge. edge x y ==  ( x) ( y)  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 algebraic-graphsOverlay two graphs. This is a commutative, associative and idempotent operation with the identity empty. Complexity: O((n + m) * log(n)) time and O(n + m) memory.  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphsConnect two graphs. This is an associative operation with the identity empty, which distributes over 1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) <=  x *  y +  x +  y  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices1 [x] ==  x  x . vertices1 ==  x  . vertices1 ==  . D  . vertices1 == Set. .   algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges1 [(x,y)] ==  x y edges1 ==  .   ( )  . edges1 == DE . D algebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. (overlays1 [x] == x overlays1 [x,y] ==  x y algebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. (connects1 [x] == x connects1 [x,y] ==  x y algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time. isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True isSubgraphOf x y ==> x <= y algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x ( y) == (x == y) algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y .  x y ==  ' False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount (3 x) == 1 vertexCount ==  .  vertexList) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(n) time.  edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList1 ( x) == [x] vertexList1 .  == D . D  algebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList . edges == D .   edgeList .  ==   .  !" . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexSet .  == Set. vertexSet .  == Set. .   vertexSet .  == Set. .   algebraic-graphs0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory.  edgeSet ( x) == Set. edgeSet ( x y) == Set. (x,y) edgeSet . edges == Set. algebraic-graphsThe preset of an element x is the set of its direct predecessors. Complexity:  O(n * log(n)) time and O(n) memory.  preSet x ( x) == Set. preSet 1 ( 1 2) == Set. preSet y ( x y) == Set. [x] algebraic-graphsThe postset of a vertex is the set of its direct successors. Complexity:  O(log(n)) time and O(1) memory.  postSet x ( x) == Set. postSet x ( x y) == Set. [y] postSet 2 ( 1 2) == Set. algebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path1 [x] ==  x path1 [x,y] ==  x y path1 .   ==  . path1 algebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit1 [x] ==  x x circuit1 [x,y] ==  [(x,y), (y,x)] circuit1 .   ==  . circuit1 algebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique1 [x] ==  x clique1 [x,y] ==  x y clique1 [x,y,z] == # [(x,y), (x,z), (y,z)] clique1 (xs   ys) == % (clique1 xs) (clique1 ys) clique1 .   ==  . clique1 algebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique1 [x1,x2] [y1,y2] ==  [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique1 xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] algebraic-graphsThe stars formed by overlaying a list of s. An inverse of  adjacencyList. Complexity:  O(L * log(n)) time, memory and size, where L! is the total size of the input. #stars1 [(x, [] )] == & x stars1 [(x, [y])] == ( x y stars1 [(x, ys )] == ) x ys stars1 ==  .   ( ) ' (stars1 xs) (stars1 ys) == stars1 (xs   ys) algebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory.  p x && q x) algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are   . Returns  / if the resulting graph is empty. Complexity: O(n + m) time.  induceJust1 (  #) ==   induceJust1 ( (  x)  ) ==   ( x) induceJust1 .   ' ==   induceJust1 .  (\x -> if p x then   x else  ) ==  p algebraic-graphs Compute the  reflexive and transitive closure of a graph. Complexity: O(n * m * log(n)^2) time.  closure ( x) ==  x x closure ( x x) ==  x x closure ( x y) ==  [(x,x), (x,y), (y,y)] closure ( $ D xs) ==  ( $ D! xs) closure ==  .  closure ==  . % closure . closure == closure  x (closure y) == Set. ( # y x) algebraic-graphs Compute the reflexive closure of a graph by adding a self-loop to every vertex. Complexity:  O(n * log(n)) time. reflexiveClosure ( x) ==  x x reflexiveClosure ( x x) ==  x x reflexiveClosure ( x y) ==  [(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure algebraic-graphs Compute the symmetric closure of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time. symmetricClosure ( x) ==  x symmetricClosure ( x y) == 7 [(x,y), (y,x)] symmetricClosure x ==  x (< x) symmetricClosure . symmetricClosure == symmetricClosure algebraic-graphs Compute the transitive closure of a graph. Complexity: O(n * m * log(n)^2) time. transitiveClosure ( x) ==  x transitiveClosure ( x y) ==  x y transitiveClosure ( $ D xs) ==  (D xs) transitiveClosure . transitiveClosure == transitiveClosure algebraic-graphsCheck that the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and the graph is non-empty. It should be impossible to create an inconsistent adjacency map, and we use this function in testing.  consistent ( x) == True consistent ( x y) == True consistent ( x y) == True consistent ( x y) == True consistent (edges xs) == True consistent (stars xs) == True algebraic-graphs Defined via .algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.** (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone'(-58>? algebraic-graphs Compute the breadth-first search forest of a graph, such that adjacent vertices are explored in increasing order according to their   instance. The search is seeded by a list of vertices that will become the roots of the resulting forest. Duplicates in the list will have their first occurrence explored and subsequent ones ignored. The seed vertices that do not belong to the graph are also ignored. Complexity: O((L + m) * log n) time and O(n) space, where L! is the number of seed vertices. ! $ bfsForest ( 1 2) [0] ==  ! $ bfsForest ( 1 2) [1] ==  1 2 ! $ bfsForest ( 1 2) [2] ==  2 ! $ bfsForest ( 1 2) [0,1,2] ==  [1,2] ! $ bfsForest ( 1 2) [2,1,0] ==  [1,2] ! $ bfsForest ( 1 1) [1] ==  1   (!* $ bfsForest x vs) x == True bfsForest x ( x) ==  (\v -> Node v []) ( $ = x) bfsForest x [] == [] bfsForest  vs == [] bfsForest (3 * (1 + 4) * (1 + 5)) [1,4] == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 4 , subForest = [] }] ! $ bfsForest ( [1..5] +  [5,4..1]) [3] ==  [3,2,1] +  [3,4,5] algebraic-graphs A version of  where the resulting forest is converted to a level structure. Adjacent vertices are explored in the increasing order according to their  % instance. Flattening the result via   .  x gives an enumeration of reachable vertices in the breadth-first search order. Complexity: O((L + m) * min(n,W)) time and O(n) space, where L! is the number of seed vertices. bfs ($ 1 2) [0] == [] bfs (, 1 2) [1] == [[1], [2]] bfs (' 1 2) [2] == [[2]] bfs () 1 2) [1,2] == [[1,2]] bfs () 1 2) [2,1] == [[2,1]] bfs (& 1 1) [1] == [[1]] bfs  vs == [] bfs x [] == [] bfs (1 * 2 + 3 * 4 + 5 * 6) [1,2] == [[1,2]] bfs (1 * 2 + 3 * 4 + 5 * 6) [1,3] == [[1,3], [2,4]] bfs (3 * (1 + 4) * (1 + 5)) [3] == [[3], [1,4,5]] bfs ( [1..5] + / [5,4..1]) [3] == [[2], [1,3], [5,4]]   $ bfs ( [1..5] +  [5,4..1]) [3] == [3,2,4,1,5]    .   .    .  x == bfs x algebraic-graphs Compute the depth-first search forest of a graph, where adjacent vertices are explored in the increasing order according to their   instance. Complexity: O((n + m) * min(n,W)) time and O(n) space. ! $ dfsForest  ==  ! $ dfsForest ( 1 1) ==  1 ! $ dfsForest ( 1 2) ==  1 2 ! $ dfsForest ( 2 1) ==  [1,2]   (! $ dfsForest x) x == True - (dfsForest x) x == True dfsForest . !, . dfsForest == dfsForest dfsForest ( vs) ==  (\v -> Node v []) ( $   vs) dfsForest $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 3 , subForest = [ Node { rootLabel = 4 , subForest = [] }]}] ! (dfsForest $  [1..5] +  [5,4..1]) ==  [1,2,3,4,5] algebraic-graphs Compute the depth-first search forest of a graph starting from the given seed vertices, where adjacent vertices are explored in the increasing order according to their   instance. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. The seed vertices which do not belong to the graph are ignored. Complexity: O((L + m) * log n) time and O(n) space, where L! is the number of seed vertices. ! $ dfsForestFrom  vs ==  ! $ dfsForestFrom ( 1 1) [1] ==  1 ! $ dfsForestFrom ( 1 2) [0] ==  ! $ dfsForestFrom ( 1 2) [1] ==  1 2 ! $ dfsForestFrom ( 1 2) [2] ==  2 ! $ dfsForestFrom ( 1 2) [1,2] ==  1 2 ! $ dfsForestFrom ( 1 2) [2,1] ==  [1,2]   (!% $ dfsForestFrom x vs) x == True  (dfsForestFrom x ( x)) x == True dfsForestFrom x ( x) ==  x dfsForestFrom x [] == [] dfsForestFrom (3 * (1 + 4) * (1 + 5)) [1,4] == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] } , Node { rootLabel = 4 , subForest = [] }] ! $ dfsForestFrom ( [1..5] +  [5,4..1]) [3] ==  [3,2,1,5,4] algebraic-graphs(Return the list vertices visited by the depth-first search in a graph, starting from the given seed vertices. Adjacent vertices are explored in the increasing order according to their   instance. Complexity: O((L + m) * log n) time and O(n) space, where L! is the number of seed vertices. dfs  vs == [] dfs ( 1 1) [1] == [1] dfs ( 1 2) [0] == [] dfs ( 1 2) [1] == [1,2] dfs ( 1 2) [2] == [2] dfs ( 1 2) [1,2] == [1,2] dfs (1 1 2) [2,1] == [2,1] dfs x [] == [] $ [  v x | v <- dfs x vs ] == True dfs (3 * (1 + 4) * (1 + 5)) [1,4] == [1,5,4] dfs ( [1..5] +  [5,4..1]) [3] == [3,2,1,5,4] algebraic-graphsReturn the list of vertices  reachable from a source vertex in a graph. The vertices in the resulting list appear in the depth-first search order. Complexity:  O(m * log n) time and O(n) space.  reachable ! x == [] reachable ( 1) 1 == [1] reachable (" 1 1) 1 == [1] reachable (! 1 2) 0 == [] reachable ($ 1 2) 1 == [1,2] reachable (" 1 2) 2 == [2] reachable (% [1..8] ) 4 == [4..8] reachable (, [1..8] ) 4 == [4..8] ++ [1..3] reachable ( [8,7..1]) 8 == [8] ++ [1..7] $ [ $ v x | v <- reachable x y ] == True algebraic-graphs:Compute a topological sort of a graph or discover a cycle.Vertices are explored in the decreasing order according to their   instance. This gives the lexicographically smallest topological ordering in the case of success. In the case of failure, the cycle is characterized by being the lexicographically smallest up to rotation with respect to Ord (Dual Int) in the first connected component of the graph containing a cycle, where the connected components are ordered by their largest vertex with respect to Ord a. Complexity: O((n + m) * min(n,W)) time and O(n) space. topSort (1 * 2 + 3 * 1) == Right [3,1,2] topSort ( [1..5]) == Right [1..5] topSort (3 * (1 * 4 + 2 * 5)) == Right [3,1,2,4,5] topSort (1 * 2 + 2 * 1) == Left (2   [1]) topSort ( [5,4..1] +  2 4) == Left (4   [3,2]) topSort (& [1..3]) == Left (3   [1,2]) topSort ( [1..3] +  [3,2,1]) == Left (3  < [2]) topSort (1 * 2 + (5 + 2) * 1 + 3 * 4 * 3) == Left (1   [2]) fmap (  $ x) (topSort x) /= Right False  ' . topSort ==  topSort . $ == Right . nub . sort algebraic-graphsCheck if a given graph is acyclic. Complexity: O((n+m)*log n) time and O(n) space. isAcyclic (1 * 2 + 3 * 1) == True isAcyclic (1 * 2 + 2 * 1) == False isAcyclic .  ==   isAcyclic ==   .  algebraic-graphs Compute the  condensation1 of a graph, where each vertex corresponds to a strongly-connected component of the original graph. Note that component graphs are non-empty, and are therefore of type #Algebra.Graph.NonEmpty.AdjacencyMap.2Details about the implementation can be found at  :https://github.com/jitwit/alga-notes/blob/master/gabow.org gabow-notes. Complexity: O((n+m)*log n) time and O(n+m) space. scc  ==  scc ( x) ==  (NonEmpty. x) scc ( xs) ==  (  xs) scc ( 1 1) ==  (NonEmpty. 1 1) scc ( 1 2) ==  (NonEmpty. 1) (NonEmpty. 2) scc ( (1:xs)) ==  (NonEmpty. (1  ! xs)) scc (3 * 1 * 4 * 1 * 5) ==   [ (NonEmpty. 3 , NonEmpty.9 5 ) , (NonEmpty. 3 , NonEmpty.8 [1,4,1]) , (NonEmpty. [1,4,1], NonEmpty. 5 ) ]  . scc ==   True  x == (scc x == ' NonEmpty. x) algebraic-graphs%Check if a given forest is a correct depth-first search forest of a graph. The implementation is based on the paper "Depth-First Search and Strong Connectivity in Coq" by Franois Pottier. .isDfsForestOf []  == True isDfsForestOf [] ( 1) == False isDfsForestOf [Node 1 []] ( 1) == True isDfsForestOf [Node 1 []] ( 2) == False isDfsForestOf [Node 1 [], Node 1 []] ( 1) == False isDfsForestOf [Node 1 []] ( 1 1) == True isDfsForestOf [Node 1 []] ( 1 2) == False isDfsForestOf [Node 1 [], Node 2 []] ( 1 2) == False isDfsForestOf [Node 2 [], Node 1 []] ( 1 2) == True isDfsForestOf [Node 1 [Node 2 []]] ( 1 2) == True isDfsForestOf [Node 1 [], Node 2 []] (? [1,2]) == True isDfsForestOf [Node 2 [], Node 1 []] (? [1,2]) == True isDfsForestOf [Node 1 [Node 2 []]] ( [1,2]) == False isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] ( [1,2,3]) == True isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] ( [1,2,3]) == False isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] ( [1,2,3]) == True isDfsForestOf [Node 2 [Node 3 []], Node 1 []] ( [1,2,3]) == True isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] ( [1,2,3]) == False algebraic-graphs/Check if a given list of vertices is a correct topological sort of a graph. isTopSortOf [3,1,2] (1 * 2 + 3 * 1) == True isTopSortOf [1,2,3] (1 * 2 + 3 * 1) == False isTopSortOf [] (1 * 2 + 3 * 1) == False isTopSortOf [] ( == True isTopSortOf [x] (& x) == True isTopSortOf [x] ( x x) == False   (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?!algebraic-graphsThe  data type represents an acyclic graph by a map of vertices to their adjacency sets. Although the internal representation allows for cycles, the methods provided by this module cannot be used to construct a graph with cycles.The  instance is defined using basic graph construction primitives where possible, falling back to  and Algebra.Graph.AdjacencyMap otherwise: show empty == "empty" show (shrink 1) == "vertex 1" show (shrink $ 1 + 2) == "vertices [1,2]" show (shrink $ 1 * 2) == "(fromJust . toAcyclic) (edge 1 2)" show (shrink $ 1 * 2 * 3) == "(fromJust . toAcyclic) (edges [(1,2),(1,3),(2,3)])" show (shrink $ 1 * 2 + 3) == "(fromJust . toAcyclic) (overlay (vertex 3) (edge 1 2))" +The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.*Note that the resulting order refines the  relation:  x y ==> x <= yalgebraic-graphsExtract the underlying acyclic Algebra.Graph.AdjacencyMap. Complexity: O(1) time and memory.  fromAcyclic  ==  fromAcyclic .  == / fromAcyclic (shrink $ 1 * 3 + 2) == 1 * 3 + 2  . fromAcyclic ==   . fromAcyclic ==   . fromAcyclic ==   True algebraic-graphsConstruct the  empty graph.  empty == True  x empty == False  empty == 0  empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex.  (vertex x) == False  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x  x . vertices ==  x  . vertices ==  .   . vertices == Set. algebraic-graphsConstruct the disjoint union of two graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.  (union x y) == Set.  [ Set.    (. x) , Set.    ( y) ]  (union x y) == Set.  [ Set.  (:;     ) (. x) , Set.  (:;    ) ( y) ] algebraic-graphsConstruct the join of two graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.  (join x y) == Set.  [ Set.    (- x) , Set.    ( y) ]  (join x y) == Set.  [ Set.  (:;     ) (- x) , Set.  (:;    ) (- y) , Set.  (:;    ) (Set.  ( x) ( y)) ] algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf 5 x == True isSubgraphOf ( x) ) == False isSubgraphOf ( p x) x == True isSubgraphOf x ( x) == True isSubgraphOf x y ==> x <= y algebraic-graphs(Check if a graph is empty. Complexity: O(1) time. isEmpty . == True isEmpty (- x) == False isEmpty ( x $  x) == True isEmpty ( 1 2 $ shrink $ 1 * 2) == False algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ($ y) == (x == y) hasVertex x .  x ==   False algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge 1 2 (shrink $ 1 * 2) == True hasEdge x y .  x y ==  ' False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (3 x) == 1 vertexCount ==  . ) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(n) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (shrink $ 1 * 2) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  ==  .   algebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList  == [] edgeList ( x) == [] edgeList (shrink $ 2 * 1) == [(2,1)] edgeList .  ==   .  !" . edgeList algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and memory. adjacencyList ! == [] adjacencyList ( x) == [(x, [])] adjacencyList (shrink $ 1 * 2) == [(1, [2]), (2, [])] algebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexSet  == Set. vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet  == Set. edgeSet ( x) == Set.! edgeSet (shrink $ 1 * 2) == Set. (1,2) algebraic-graphsThe preset of an element x is the set of its direct predecessors. Complexity:  O(n * log(n)) time and O(n) memory.  preSet x  == Set. preSet x ( x) == Set." preSet 1 (shrink $ 1 * 2) == Set." preSet 2 (shrink $ 1 * 2) == Set. [1] Set.  x . preSet x ==   False algebraic-graphsThe postset of a vertex is the set of its direct successors. Complexity:  O(log(n)) time and O(1) memory.  postSet x  == Set. postSet x ( x) == Set.# postSet 1 (shrink $ 1 * 2) == Set.' [2] postSet 2 (shrink $ 1 * 2) == Set. Set.  x . postSet x ==   False algebraic-graphs9Remove a vertex from a given acyclic graph. Complexity:  O(n*log(n)) time. removeVertex x ( x) ==  removeVertex 1 ( 2) == & 2 removeVertex 1 (shrink $ 1 * 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs8Remove an edge from a given acyclic graph. Complexity:  O(log(n)) time. 'removeEdge 1 2 (shrink $ 1 * 2) ==  [1,2] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x == ? x removeEdge 1 2 (shrink $ 1 * 2 * 3) == shrink ((1 + 2) * 3) algebraic-graphs.Transpose a given acyclic graph. Complexity:  O(m * log(n)) time, O(n + m) memory.  transpose  ==  transpose ( x) ==  x transpose . transpose == id  . transpose ==   .  !" .  algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(n + m)7 time, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x ==  induce (/= x) == ; x induce p . induce q == induce (x -> p x && q x)  (induce p x) x == True algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are  . Complexity: O(n + m) time.  induceJust (  ) ==  induceJust .  .   ==  algebraic-graphs Compute the Cartesian product of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.  (box ( $ 1 * 2) ( $ 10 * 20)) == [ ((1,10), (1,20)) , ((1,10), (2,10)) , ((1,20), (2,20)) , ((2,10), (2,20)) ] Up to isomorphism between the resulting vertex types, this operation is  commutative and  associative, has singleton graphs as  identities and  as the annihilating zero. Below ~~1 stands for 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 ( ()) ~~ x box x  ~~   (box x y) == box ( x) ( y)  (box x y) ==  x *  y  (box x y) <=  x *  y +  x *  y algebraic-graphs Compute the transitive closure of a graph. Complexity: O(n * m * log(n)^2) time. transitiveClosure  ==  transitiveClosure ( x) ==  x transitiveClosure (shrink $ 1 * 2 + 2 * 3) == shrink (1 * 2 + 1 * 3 + 2 * 3) transitiveClosure . transitiveClosure == transitiveClosure algebraic-graphs Compute a topological sort of an acyclic graph. topSort ) == [] topSort ( x) == [x] topSort (shrink $ 1 * (2 + 4) + 3 * 4) == [1, 2, 3, 4] topSort ( x y) ==     (topSort x) ++     (topSort y)  % . topSort ==  .  algebraic-graphsCompute the acyclic  condensation1 of a graph, where each vertex corresponds to a strongly-connected component of the original graph. Note that component graphs are non-empty, and are therefore of type #Algebra.Graph.NonEmpty.AdjacencyMap.  scc  ==  scc ( x) ==  (NonEmpty.H3 x) scc ( 1 1) ==  (NonEmpty.H4 1 1)  $ scc ( 1 2) == [ (NonEmpty.H3 1 , NonEmpty.H3 2 ) ] * $ scc (3 * 1 * 4 * 1 * 5) == [ (NonEmpty.H3 3 , NonEmpty.H3= 5 ) , (NonEmpty.H3 3 , NonEmpty.HI< [1,4,1]) , (NonEmpty.HI [1,4,1], NonEmpty.H3 5 ) ] algebraic-graphsConstruct an acyclic graph from a given adjacency map, or return   if the input contains cycles.  toAcyclic ( [1,2,3]) ==  % (shrink $ 1 * 2 + 2 * 3) toAcyclic ( [3,2,1]) ==   (" (shrink $ 1 * 2 * 3)) toAcyclic ( [1,2,3]) ==   toAcyclic .  ==   algebraic-graphsConstruct an acyclic graph from a given adjacency map, keeping only edges (x,y) where x < y according to the supplied   a instance.  toAcyclicOrd  ==  toAcyclicOrd .  ==  toAcyclicOrd (1 + 2) == shrink (1 + 2) toAcyclicOrd (1 * 2) == shrink (1 * 2) toAcyclicOrd (2 * 1) == shrink (1 + 2) toAcyclicOrd (1 * 2 * 1) == shrink (1 * 2) toAcyclicOrd (1 * 2 * 3) == shrink (1 * 2 * 3) algebraic-graphs? 'algebraic-graphsThe  type class captures data types that can be converted to algebraic graphs. Instances of this type class should satisfy the laws specified by the default method definitions.algebraic-graphs,The type of vertices of the resulting graph.algebraic-graphs:Convert a value to the corresponding algebraic graph, see  Algebra.Graph.  toGraph ==      algebraic-graphs The method  is used for generalised graph folding. It collapses a given value by applying the provided graph construction primitives. The order of arguments is: empty, vertex, overlay and connect, and it is assumed that the arguments satisfy the axioms of the graph algebra. foldg == Algebra.Graph. .  algebraic-graphsCheck if a graph is empty.  isEmpty ==  True (  False) (&&) (&&) algebraic-graphs)Check if a graph contains a given vertex. hasVertex x ==  False (==x) (||) (||) algebraic-graphs'Check if a graph contains a given edge. hasEdge x y == Algebra.Graph. x y .  algebraic-graphs"The number of vertices in a graph. vertexCount == Set.  .  algebraic-graphsThe number of edges in a graph. edgeCount == Set.  .  algebraic-graphs-The sorted list of vertices of a given graph. vertexList == Set.  .  algebraic-graphs$The sorted list of edges of a graph. edgeList == Set.  .  algebraic-graphsThe set of vertices of a graph.  vertexSet ==  Set. Set. Set.  Set.  algebraic-graphs%The set of vertices of a graph. Like 3 but specialised for graphs with vertices of type  . vertexIntSet ==  IntSet.  IntSet.  IntSet.  IntSet.  algebraic-graphsThe set of edges of a graph. &edgeSet == Algebra.Graph.AdjacencyMap. .  algebraic-graphsThe preset of a vertex is the set of its direct predecessors. 'preSet x == Algebra.Graph.AdjacencyMap. x .  algebraic-graphsThe preset (here  preIntSet!) of a vertex is the set of its direct predecessors. Like 3 but specialised for graphs with vertices of type  . -preIntSet x == Algebra.Graph.AdjacencyIntMap.Q x .  algebraic-graphsThe postset of a vertex is the set of its direct successors. (postSet x == Algebra.Graph.AdjacencyMap. x .  algebraic-graphsThe postset (here  postIntSet!) of a vertex is the set of its direct successors. Like 3 but specialised for graphs with vertices of type  . .postIntSet x == Algebra.Graph.AdjacencyIntMap.R x .  algebraic-graphs The sorted adjacency list of a graph. ,adjacencyList == Algebra.Graph.AdjacencyMap. .  algebraic-graphs Compute the depth-first search forest of a graph that corresponds to searching from each of the graph vertices in the   a order. (dfsForest == Algebra.Graph.AdjacencyMap. . toAdjacencyMap algebraic-graphs Compute the depth-first search forest of a graph, searching from each of the given vertices in order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. ,dfsForestFrom == Algebra.Graph.AdjacencyMap. . toAdjacencyMap algebraic-graphs,Compute the list of vertices visited by the depth-first search in a graph, when searching from each of the given vertices in order. "dfs == Algebra.Graph.AdjacencyMap. . toAdjacencyMap algebraic-graphs&Compute the list of vertices that are  reachable from a given source vertex in a graph. The vertices in the resulting list appear in the depth-first order. (reachable == Algebra.Graph.AdjacencyMap. . toAdjacencyMap algebraic-graphs Compute the topological sort of a graph or a AM.Cycle if the graph is cyclic. &topSort == Algebra.Graph.AdjacencyMap. . toAdjacencyMap algebraic-graphsCheck if a given graph is acyclic. (isAcyclic == Algebra.Graph.AdjacencyMap. . toAdjacencyMap algebraic-graphs%Convert a value to the corresponding . toAdjacencyMap ==      algebraic-graphs%Convert a value to the corresponding  and transpose the result. toAdjacencyMapTranspose ==     (  ) algebraic-graphs%Convert a value to the corresponding :. toAdjacencyIntMap ==  = > @ A algebraic-graphs%Convert a value to the corresponding : and transpose the result. toAdjacencyIntMapTranspose ==  = > @ (  A) algebraic-graphs#Check if a given forest is a valid depth-first search forest of a graph. .isDfsForestOf f == Algebra.Graph.AdjacencyMap. f . toAdjacencyMap algebraic-graphs-Check if a given list of vertices is a valid topological sort of a graph. -isTopSortOf vs == Algebra.Graph.AdjacencyMap. vs . toAdjacencyMap algebraic-graphsThe  adjacency map: of a graph: each vertex is associated with a set of its direct successors. +adjacencyMap == Algebra.Graph.AdjacencyMap.J .  algebraic-graphsThe  adjacency map: of a graph: each vertex is associated with a set of its direct successors. Like 3 but specialised for graphs with vertices of type  . 1adjacencyIntMap == Algebra.Graph.AdjacencyIntMap.K .  algebraic-graphsThe transposed  adjacency map: of a graph: each vertex is associated with a set of its direct predecessors. 4adjacencyMapTranspose == Algebra.Graph.AdjacencyMap.J .  algebraic-graphsThe transposed  adjacency map: of a graph: each vertex is associated with a set of its direct predecessors. Like 3 but specialised for graphs with vertices of type  . :adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap.K .  algebraic-graphsSee #Algebra.Graph.NonEmpty.AdjacencyMap.algebraic-graphsSee Algebra.Graph.AdjacencyIntMap.algebraic-graphsSee Algebra.Graph.AdjacencyMap.algebraic-graphsSee  Algebra.Graph.##(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?^^2algebraic-graphsThe # data type represents a graph as a binary relation. We define a ; instance as a convenient notation for working with graphs: 0 ==  0 1 + 2 ==  ( 1) ( 2) 1 * 2 ==  ( 1) ( 2) 1 + 2 * 3 ==  ( 1) ( ( 2) ( 3)) 1 * (2 + 3) ==  ( 1) ( ( 2) ( 3)) Note: the 7 instance does not satisfy several "customary laws" of , which dictate that  0 and  1; should act as additive and multiplicative identities, and 0 as additive inverse. Nevertheless, overloading ,  and  is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ? instance is defined using basic graph construction primitives: show (empty :: Relation Int) == "empty" show (1 :: Relation Int) == "vertex 1" show (1 + 2 :: Relation Int) == "vertices [1,2]" show (1 * 2 :: Relation Int) == "edge 1 2" show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"The 3 instance satisfies all axioms of algebraic graphs: is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z is associative and has  as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * zThe following useful theorems can be proved from the above set of axioms. has ' as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of : -x * y + x + y == x * y x * x * x == x * xWhen specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges in the graph, respectively.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:  1 <  2  3 <  1 2  1 <  1 1  1 1 <  1 2  1 2 <  1 1 +  2 2  1 2 <  1 3*Note that the resulting order refines the ! relation and is compatible with  and  operations:  x y ==> x <= y # <= x x <= x + y x + y <= x * yalgebraic-graphsThe domain of the relation. Complexity: O(1) time and memory.algebraic-graphs&The set of pairs of elements that are related. It is guaranteed that each element belongs to the domain. Complexity: O(1) time and memory.algebraic-graphsConstruct the  empty graph.  empty == True  x empty == False  empty == 0  empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex.  (vertex x) == False  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0 algebraic-graphsConstruct the graph comprising  a single edge. edge x y ==  ( x) ( y)  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 algebraic-graphsOverlay two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O((n + m) * log(n)) time and O(n + m) memory.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphsConnect two graphs. This is an associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  (connect x y) ==  x &&  y  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) <=  x *  y +  x +  y  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x vertices ==  . map   x . vertices ==  x  . vertices ==  .   . vertices == Set. algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] ==  edges [(x,y)] ==  x y edges ==  .  ( )  . edges ==  .  algebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==   algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf . x == True isSubgraphOf ( x) / == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True isSubgraphOf x y ==> x <= y algebraic-graphs+Check if a relation is empty. Complexity: O(1) time. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty ( x $  x) == True isEmpty ( x y $  x y) == False algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ($ y) == (x == y) hasVertex x .  x ==   False algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y .  x y ==  ' False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (3 x) == 1 vertexCount ==  . ) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(1) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  ==  .   algebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList  == [] edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList .  ==  .   edgeList .  ==   .    . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity: O(1) time.  vertexSet  == Set. vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs0The set of edges of a given graph. Complexity: O(1) time. edgeSet  == Set. edgeSet ( x) == Set. edgeSet ( x y) == Set. (x,y) edgeSet .  == Set. algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and memory. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (0 1 2) == [(1, [2]), (2, [])] adjacencyList (, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]  . adjacencyList == id algebraic-graphsThe preset of an element x7 is the set of elements that are related to it on the left, i.e. preSet x == { a | aRx }. In the context of directed graphs, this corresponds to the set of direct predecessors of vertex x. Complexity: O(n + m) time and O(n) memory.  preSet x  == Set. preSet x ( x) == Set. preSet 1 ( 1 2) == Set. preSet y ( x y) == Set. [x] algebraic-graphsThe postset of an element x7 is the set of elements that are related to it on the right, i.e. postSet x == { a | xRa }. In the context of directed graphs, this corresponds to the set of direct successors of vertex x. Complexity: O(n + m) time and O(n) memory.  postSet x  == Set. postSet x ( x) == Set. postSet x ( x y) == Set. [y] postSet 2 ( 1 2) == Set. algebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] ==  path [x] ==  x path [x,y] ==  x y path .   ==  . path algebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] circuit .   ==  . circuit algebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) == " (clique xs) (clique ys) clique .   ==  . clique algebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] ==  [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity:  O(L * log(n)) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  .  (  ) stars .  == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. forest [] == ? forest [x] ==  x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==  [(1,2), (1,3), (4,5)] forest ==  .   algebraic-graphs1Remove a vertex from a given graph. Complexity: O(n + m) time. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity:  O(log(m)) time. removeEdge x y (14 x y) ==  [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x ==  x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 algebraic-graphs The function  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. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))8 time, assuming that the predicate takes constant time. mergeVertices ( 7 False) x == id mergeVertices (== x) y ==  x y mergeVertices  & 1 (0 * 2) == 1 * 1 mergeVertices   1 (3 + 4 * 5) == 4 * 1 algebraic-graphs&Transpose a given graph. Complexity:  O(m * log(m)) time.  transpose  ==  transpose ( x) ==  x transpose ( x y) == ! y x transpose . transpose == id  . transpose ==   .    .  algebraic-graphsTransform a graph by applying a function to each of its vertices. This is similar to Functor's  , but can be used with non-fully-parametric . Complexity: O((n + m) * log(n)) time. gmap f  ==  gmap f ( x) ==  (f x) gmap f ( x y) ==  (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(n + m)7 time, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are  . Complexity: O(n + m) time.  induceJust (  #) ==  induceJust ( (  x)  ) ==  x induceJust .   ' ==   induceJust .  (\x -> if p x then   x else  ) ==  p algebraic-graphsLeft-to-right relational composition of graphs: vertices x and z< are connected in the resulting graph if there is a vertex y , such that x is connected to y in the first graph, and y is connected to z in the second graph. There are no isolated vertices in the result. This operation is associative, has  and single- graphs as annihilating zeroes, and distributes over . Complexity: O(n * m * log(m)) time and O(n + m) memory. compose  x ==  compose x  ==  compose ( x) y ==  compose x ( y) ==  compose x (compose y z) == compose (compose x y) z compose x ( y z) == & (compose x y) (compose x z) compose ( x y) z == & (compose x z) (compose y z) compose ( x y) ( y z) ==  x z compose ( [1..5]) ( [1..5]) ==  [(1,3), (2,4), (3,5)] compose ( [1..5]) ( [1..5]) ==  [1,3,5,2,4] algebraic-graphs Compute the  reflexive and transitive closure of a graph. Complexity: O(n * m * log(n) * log(m)) time. closure  ==  closure ( x) ==  x x closure ( x x) ==  x x closure ( x y) ==  [(x,x), (x,y), (y,y)] closure ( $  xs) ==  ( $  xs) closure ==  .  closure ==  . $ closure . closure == closure  x (closure y) == Set. ( # y x) algebraic-graphs Compute the reflexive closure of a graph. Complexity:  O(n * log(m)) time. reflexiveClosure  ==  reflexiveClosure ( x) ==  x x reflexiveClosure ( x x) ==  x x reflexiveClosure ( x y) ==  [(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure algebraic-graphs Compute the symmetric closure of a graph. Complexity:  O(m * log(m)) time. symmetricClosure  ==  symmetricClosure ( x) ==  x symmetricClosure ( x y) == 7 [(x,y), (y,x)] symmetricClosure x ==  x (< x) symmetricClosure . symmetricClosure == symmetricClosure algebraic-graphs Compute the transitive closure of a graph. Complexity: O(n * m * log(n) * log(m)) time. transitiveClosure  ==  transitiveClosure ( x) ==  x transitiveClosure ( x y) ==  x y transitiveClosure ( $  xs) ==  ( xs) transitiveClosure . transitiveClosure == transitiveClosure algebraic-graphsCheck that the internal representation of a relation is consistent, i.e. if all pairs of elements in the # refer to existing elements in the 5. It should be impossible to create an inconsistent ', and we use this function in testing.  consistent  == True consistent ( x) == True consistent ( x y) == True consistent ( x y) == True consistent ( x y) == True consistent ( xs) == True consistent ( xs) == True algebraic-graphs Defined via  and .algebraic-graphs Defined via .algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.//(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?,algebraic-graphsThis data type represents a symmetric binary relation over a set of elements of type a.. Symmetric relations satisfy all laws of the L, type class, including the commutativity of :  x y ==  y xThe 6 instance lists edge vertices in non-decreasing order: show (empty :: Relation Int) == "empty" show (1 :: Relation Int) == "vertex 1" show (1 + 2 :: Relation Int) == "vertices [1,2]" show (1 * 2 :: Relation Int) == "edge 1 2" show (2 * 1 :: Relation Int) == "edge 1 2" show (1 * 2 * 1 :: Relation Int) == "edges [(1,1),(1,2)]" show (3 * 2 * 1 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:  1 <  2  3 <  1 2  1 <  1 1  1 1 <  1 2  1 2 <  1 1 +  2 2  2 1 <  1 3  1 2 ==  2 1*Note that the resulting order refines the ! relation and is compatible with  and  operations:  x y ==> x <= y # <= x x <= x + y x + y <= x * yalgebraic-graphs!Extract the underlying symmetric Algebra.Graph.Relation. Complexity: O(1) time and memory. fromSymmetric ( 1 2) ==  [(1,2), (2,1)]  . fromSymmetric ==   . fromSymmetric <= (*2) .  algebraic-graphs,Construct a symmetric relation from a given Algebra.Graph.Relation. Complexity:  O(m * log(m)) time.  toSymmetric (4 1 2) ==  1 2 toSymmetric .  == id  . toSymmetric == 7  . toSymmetric == M (*2) .  . toSymmetric >= N algebraic-graphsConstruct the  empty graph.  empty == True  x empty == False  empty == 0  empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex.  (vertex x) == False  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0 algebraic-graphsConstruct the graph comprising  a single edge. edge x y ==  ( x) ( y) edge x y ==  y x edge x y ==  [(x,y), (y,x)]  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 algebraic-graphsOverlay two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O((n + m) * log(n)) time and O(n + m) memory.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphsConnect two graphs. This is a commutative and associative operation with the identity , which distributes over 2 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2). )connect x y == connect y x  (connect x y) ==  x &&  y  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y `div` 2  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x vertices ==  . map   x . vertices ==  x  . vertices ==  .   . vertices == Set. algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] ==  edges [(x,y)] ==  x y edges [(x,y), (y,x)] ==  x y algebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==  " connects == connects .   algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf . x == True isSubgraphOf ( x) / == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True isSubgraphOf ( x y) ( y x) == True isSubgraphOf x y ==> x <= y algebraic-graphs+Check if a relation is empty. Complexity: O(1) time. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty ( x $  x) == True isEmpty ( x y $  x y) == False algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ($ y) == (x == y) hasVertex x .  x ==   False algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (! x y) == True hasEdge x y (" y x) == True hasEdge x y .  x y ==  ' False hasEdge x y ==  (  x y,   x y) .  algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (3 x) == 1 vertexCount ==  . ) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(1) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  ==  .   algebraic-graphsThe sorted list of edges of a graph, where edge vertices appear in the non-decreasing order. Complexity: O(n + m) time and O(m) memory.Note: If you need the sorted list of edges where an edge appears in both directions, use O . .  edgeList  == [] edgeList ( x) == [] edgeList ( x y) == [(  x y,   y x)] edgeList ( 2 [3,1]) == [(1,2), (2,3)] algebraic-graphs3The set of vertices of a given graph. Complexity: O(1) time.  vertexSet  == Set. vertexSet .  == Set. vertexSet .  == Set. algebraic-graphsThe set of edges of a given graph, where edge vertices appear in the non-decreasing order. Complexity: O(m) time.Note: If you need the set of edges where an edge appears in both directions, use  . . The latter is much faster than this function, and takes only O(1) time and memory. edgeSet  == Set. edgeSet ( x) == Set. edgeSet ( x y) == Set. (  x y,   x y) algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and memory. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (1 1 2) == [(1, [2]), (2, [1])] adjacencyList (. 2 [3,1]) == [(1, [2]), (2, [1,3]), (3, [2])]  . adjacencyList == id algebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] ==  path [x] ==  x path [x,y] ==  x y path == path .   algebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  x y circuit == circuit .   algebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) == 7 (clique xs) (clique ys) clique == clique .   algebraic-graphsThe biclique( on two lists of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] ==  [(x1,y1), (x1,y2), (x2,x2), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity:  O(L * log(n)) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  .  (  ) stars .  == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsThe  tree graph constructed from a given PP data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. forest [] == ? forest [x] ==  x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==  [(1,2), (1,3), (4,5)] forest ==  .   algebraic-graphs1Remove a vertex from a given graph. Complexity: O(n + m) time. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity:  O(log(m)) time. removeEdge x y ( x y) ==  [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y == removeEdge y x removeEdge x y .  x ==  x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))8 time, assuming that the predicate takes constant time. mergeVertices ( 7 False) x == id mergeVertices (== x) y ==  x y mergeVertices  & 1 (0 * 2) == 1 * 1 mergeVertices   1 (3 + 4 * 5) == 4 * 1 algebraic-graphsTransform a graph by applying a function to each of its vertices. This is similar to Functor's  , but can be used with non-fully-parametric . Complexity: O((n + m) * log(n)) time. gmap f  ==  gmap f ( x) ==  (f x) gmap f ( x y) ==  (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(n + m)7 time, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are  . Complexity: O(n + m) time.  induceJust (  #) ==  induceJust ( (  x)  ) ==  x induceJust .   ' ==   induceJust .  (\x -> if p x then   x else  ) ==  p algebraic-graphs The set of  neighbours of an element x6 is the set of elements that are related to it, i.e. neighbours x == { a | aRx }. In the context of undirected graphs, this corresponds to the set of adjacent vertices of vertex x.  neighbours x  == Set. neighbours x ( x) == Set. neighbours x ( x y) == Set. [y] neighbours y ( x y) == Set. [x] algebraic-graphsCheck that the internal representation of a symmetric relation is consistent, i.e. that (i) that all edges refer to existing vertices, and (ii) all edges have their symmetric counterparts. It should be impossible to create an inconsistent &, and we use this function in testing.  consistent  == True consistent ( x) == True consistent ( x y) == True consistent ( x y) == True consistent ( x y) == True consistent ( xs) == True consistent ( xs) == True algebraic-graphs Defined via  and the  instance of .algebraic-graphs Defined via  and .algebraic-graphs Defined via .algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.(((c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?.algebraic-graphsNon-empty algebraic graphs, which are constructed using three primitives: ,  and  . See module  Algebra.Graph( for algebraic graphs that can be empty. We define a ; instance as a convenient notation for working with graphs: 0 ==  0 1 + 2 ==  ( 1) ( 2) 1 * 2 ==  ( 1) ( 2) 1 + 2 * 3 ==  ( 1) ( ( 2) ( 3)) 1 * (2 + 3) ==  ( 1) ( ( 2) ( 3)) Note: the   method of the type class  cannot be implemented and will throw an error. Furthermore, the 7 instance does not satisfy several "customary laws" of , which dictate that  0 and  1; should act as additive and multiplicative identities, and 0 as additive inverse. Nevertheless, overloading ,  and  is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The  instance satisfies the following laws of non-empty algebraic graphs., is commutative, associative and idempotent:  x + y == y + x x + (y + z) == (x + y) + z x + x == x is associative: x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * z% satisfies absorption and saturation: -x * y + x + y == x * y x * x * x == x * xWhen specifying the time and memory complexity of graph algorithms, n2 will denote the number of vertices in the graph, m3 will denote the number of edges in the graph, and s will denote the size of the corresponding ? expression, defined as the number of vertex leaves (note that n <= s). If g is a , the corresponding n, m and s can be computed as follows: n ==  g m ==  g s ==  g Converting a  to the corresponding  1 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 adjacency maps.The total order   on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:  1 <  2  3 <  1 2  1 <  1 1  1 1 <  1 2  1 2 <  1 1 +  2 2  1 2 <  1 3*Note that the resulting order refines the ! relation and is compatible with  and  operations:  x y ==> x <= y x <= x + y x + y <= x * yalgebraic-graphs!Convert an algebraic graph (from  Algebra.Graph-) into a non-empty algebraic graph. Returns   if the argument is . Complexity: O(s) time, memory and size.  toNonEmpty  == Nothing toNonEmpty ( x) == Just (x ::  a) algebraic-graphsConstruct the graph comprising a single isolated vertex . An alias for the constructor .  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0  (vertex x) == 1 algebraic-graphsConstruct the graph comprising  a single edge. edge x y ==  ( x) ( y)  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 algebraic-graphsOverlay* two graphs. An alias for the constructor . This is a commutative, associative and idempotent operation. Complexity: O(1) time and memory,  O(s1 + s2) size.  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) ==  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphs%Overlay a possibly empty graph (from  Algebra.Graph4) with a non-empty graph. If the first argument is , the function returns the second argument; otherwise it is semantically the same as . Complexity: O(s1) time and memory, and  O(s1 + s2) size.  overlay1  x == x x /= = ==> overlay1 x y == overlay (fromJust $ toNonEmpty x) y algebraic-graphsConnect* two graphs. An alias for the constructor <. This is an associative operation, which distributes over 2 and obeys the decomposition axiom. Complexity: O(1) time and memory,  O(s1 + s2) size. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) <=  x *  y +  x +  y  (connect x y) ==  x +  y  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. vertices1 [x] ==  x  x . vertices1 ==  x  . vertices1 ==  . D  . vertices1 == Set. . DR algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges1 [(x,y)] ==  x y edges1 ==  .   ( )  . edges1 == DE . D algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. (overlays1 [x] == x overlays1 [x,y] ==  x y algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. (connects1 [x] == x connects1 [x,y] ==  x y algebraic-graphs2Generalised graph folding: recursively collapse a  by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: vertex, overlay and connect. Complexity: O(s) applications of the given functions. As an example, the complexity of  is O(s), since   and  have constant costs. foldg1    == id foldg1   (  ) ==  foldg1 (  1) (+) (+) == , foldg1 (== x) (||) (||) ==  x algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s. isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True isSubgraphOf x y ==> x <= y algebraic-graphs7Structural equality on graph expressions. Complexity: O(s) time.  x === x == True x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False algebraic-graphsThe size of a graph, i.e. the number of leaves of the expression. Complexity: O(s) time. size ( x) == 1 size ( x y) == size x + size y size ( x y) == size x + size y size x >= 1 size x >=  x algebraic-graphs7Check if a graph contains a given vertex. Complexity: O(s) time.  hasVertex x ( y) == (x == y) algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y .  x y ==  ' False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount (3 x) == 1 vertexCount ==  .  vertexList) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(s + m * log(m))% time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.  edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList1 ( x) == [x] vertexList1 .  == D . D  algebraic-graphs2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.  edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList .  ==  .   . DR edgeList .  ==   .  !" . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet .  == Set. vertexSet .  == Set. . DR vertexSet .  == Set. . DR algebraic-graphs0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory.  edgeSet ( x) == Set. edgeSet ( x y) == Set. (x,y) edgeSet .  == Set. . DR algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path1 [x] ==  x path1 [x,y] ==  x y path1 . DS ==  . path1 algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit1 [x] ==  x x circuit1 [x,y] ==  [(x,y), (y,x)] circuit1 . DS ==  . circuit1 algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique1 [x] ==  x clique1 [x,y] ==  x y clique1 [x,y,z] == # [(x,y), (x,z), (y,z)] clique1 (xs   ys) == % (clique1 xs) (clique1 ys) clique1 . DS ==  . clique1 algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique1 [x1,x2] [y1,y2] ==  [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique1 xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] algebraic-graphsThe stars* formed by overlaying a non-empty list of s. Complexity: O(L) time, memory and size, where L! is the total size of the input. #stars1 [(x, [] )] == & x stars1 [(x, [y])] == ( x y stars1 [(x, ys )] == ) x ys stars1 ==  .   ( ) ' (stars1 xs) (stars1 ys) == stars1 (xs   ys) algebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O(T) time, memory and size, where T is the size of the given tree (i.e. the number of vertices in the tree).  p x && q x) algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are   . Returns  / if the resulting graph is empty. Complexity: O(s) time, memory and size.  induceJust1 (  #) ==   induceJust1 ( (  x)  ) ==   ( x) induceJust1 .    ' ==   induceJust1 .   (\x -> if p x then   x else  ) ==  p algebraic-graphsSimplify 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 == id  (simplify x) <=  x simplify 1  1 simplify (1 + 1)  1 simplify (1 + 2 + 1)  1 + 2 simplify (1 * 1 * 1)  1 * 1 algebraic-graphs Compute the Cartesian product of graphs. Complexity:  O(s1 * s2) time, memory and size, where s1 and s2$ are the sizes of the given graphs. box ( [0,1]) ( ['a','b']) ==  [ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((0,'b'), (1,'b')) , ((1,'a'), (1,'b')) ] Up to isomorphism between the resulting vertex types, this operation is  commutative,  associative,  distributes over , and has singleton graphs as  identities. Below ~~1 stands for 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 z) ==  (box x y) (box x z) box x ( ()) ~~ x  (box x y) == box ( x) ( y)  (box x y) ==  x *  y  (box x y) <=  x *  y +  x *  y algebraic-graphsSparsify a graph by adding intermediate   Int vertices between the original vertices (wrapping the latter in  $) such that the resulting graph is sparse, i.e. contains only O(s) edges, but preserves the reachability relation between the original vertices. Sparsification is useful when working with dense graphs, as it can reduce the number of edges from O(n^2) down to O(n) by replacing cliques, bicliques and similar densely connected structures by sparse subgraphs built out of intermediate vertices. Complexity: O(s) time, memory and size.   .  # x ==   . () .  # (sparsify x) . (*  (sparsify x) <=  x +  x + 1  (sparsify x) <= 3 *  x  (sparsify x) <= 3 *  x algebraic-graphs:Sparsify a graph whose vertices are integers in the range [1..n] , where n is the first argument of the function, producing an array-based graph representation from  Data.Graph (introduced by King and Launchbury, hence the name of the function). In the resulting graph, vertices [1..n] correspond to the original vertices, and all vertices greater than n1 are introduced by the sparsification procedure. Complexity: O(s) time and memory. Note that thanks to sparsification, the resulting graph has a linear number of edges with respect to the size of the original algebraic representation even though the latter can potentially contain a quadratic O(s^2) number of edges.   .  # x ==   .   (<= n) . +# (sparsifyKL n x)  (+, $ sparsifyKL n x) <=  x +  x + 1  (+- $ sparsifyKL n x) <= 3 *  x algebraic-graphs Defined via .algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.//4(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?7-algebraic-graphs.Edge-labelled graphs, where the type variable e' stands for edge labels. For example,  Bool a is isomorphic to unlabelled graphs defined in the top-level module Algebra.Graph.AdjacencyMap, where False and True denote the lack of and the existence of an unlabelled edge, respectively.algebraic-graphsThe  adjacency map of an edge-labelled graph: each vertex is associated with a map from its direct successors to the corresponding edge labels.algebraic-graphsConstruct the  empty graph.  empty == True  x empty == False  empty == 0  empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex.  (vertex x) == False  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0 algebraic-graphsConstruct the graph comprising  a single edge. edge e x y ==  e ( x) ( y) edge  x y ==  [x,y]  x y (edge e x y) == (e /= )  x y (edge e x y) == e  (edge e x y) == if e ==  then 0 else 1  (edge e 1 1) == 1  (edge e 1 2) == 2 algebraic-graphs8The left-hand part of a convenient ternary-ish operator x--y for creating labelled edges.  x -- y ==  e x y algebraic-graphs9The right-hand part of a convenient ternary-ish operator x--y for creating labelled edges.  x -- y ==  e x y algebraic-graphsOverlay two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O((n + m) * log(n)) time and O(n + m) memory.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 Note: / composes edges in parallel using the operator  with  acting as the identity:  x y $ overlay ( e x y) (  x y) == e  x y $ overlay ( e x y) ( f x y) == e  f 0Furthermore, when applied to transitive graphs, 0 composes edges in sequence using the operator  with  acting as the identity:  x z $  (overlay ( e x y) (  y z)) == e  x z $  (overlay ( e x y) ( f y z)) == e  f algebraic-graphsConnect two graphs with edges labelled by a given label. When applied to the same labels, this is an associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  (connect e x y) ==  x &&  y  z (connect e x y) ==  z x ||  z y  (connect e x y) >=  x  (connect e x y) <=  x +  y  (connect e x y) <=  x *  y +  x +  y  (connect e 1 2) == 2  (connect e 1 2) == if e ==  then 0 else 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x vertices ==  . map   x . vertices ==  x  . vertices ==  .   . vertices == Set. algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] ==  edges [(e,x,y)] ==  e x y edges ==  .  (\(e, x, y) ->  e x y) algebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs>Construct a graph from a list of adjacency sets. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 9fromAdjacencyMaps [] ==  fromAdjacencyMaps [(x, Map.)] ==  x fromAdjacencyMaps [(x, Map. y e)] == if e ==  then  [x,y] else  e x y  (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == fromAdjacencyMaps (xs   ys) algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.  isSubgraphOf # x == True isSubgraphOf ( x) 4 == False isSubgraphOf x y ==> x <= y algebraic-graphs(Check if a graph is empty. Complexity: O(1) time. isEmpty * == True isEmpty (  ) == True isEmpty () x) == False isEmpty ( x $  x) == True isEmpty ( x y $  e x y) == False algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ($ y) == (x == y) hasVertex x .  x ==   False algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y ( e x y) == (e /= ) hasEdge x y .  x y ==  ' False hasEdge x y ==   .   .  & (\(_,ex,ey) -> ex == x && ey == y) .  algebraic-graphs?Extract the label of a specified edge in a graph. Complexity:  O(log(n)) time. edgeLabel x y  ==  edgeLabel x y ( z) ==  edgeLabel x y ( e x y) == e edgeLabel s t ( x y) == edgeLabel s t x  + edgeLabel s t y algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (3 x) == 1 vertexCount ==  . ) vertexCount x < vertexCount y ==> x < y algebraic-graphsThe number of (non-!) edges in a graph. Complexity: O(n) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount ( e x y) == if e == ) then 0 else 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  ==  .   algebraic-graphsThe list of edges of a graph, sorted lexicographically with respect to pairs of connected vertices (i.e. edge-labels are ignored when sorting). Complexity: O(n + m) time and O(m) memory.  edgeList  == [] edgeList ( x) == [] edgeList ( e x y) == if e ==  then [] else [(e,x,y)] algebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexSet  == Set. vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs0The set of edges of a given graph. Complexity: O(n + m) time and O(m) memory. edgeSet  == Set. edgeSet ( x) == Set. edgeSet ( e x y) == if e ==  then Set. else Set. (e,x,y) algebraic-graphsThe preset of an element x is the set of its direct predecessors. Complexity:  O(n * log(n)) time and O(n) memory.  preSet x  == Set. preSet x ( x) == Set. preSet 1 ( e 1 2) == Set. preSet y ( e x y) == if e ==  then Set. else Set. [x] algebraic-graphsThe postset of a vertex is the set of its direct successors. Complexity:  O(log(n)) time and O(1) memory.  postSet x  == Set. postSet x ( x) == Set. postSet x ( e x y) == if e ==  then Set. else Set. [y] postSet 2 ( e 1 2) == Set. algebraic-graphs0Convert a graph to the corresponding unlabelled " by forgetting labels on all non- edges. Complexity: O((n + m) * log(n)) time and memory.  x y ==  x y . skeleton algebraic-graphs1Remove a vertex from a given graph. Complexity:  O(n*log(n)) time. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( e x x) ==  removeVertex 1 ( e 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y ( e x y) ==  [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x ==  x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y == ! (\v -> if v == x then y else v) algebraic-graphsReplace an edge from a given graph. If it doesn't exist, it will be created. Complexity:  O(log(n)) time. 'replaceEdge e x y z ==  (removeEdge x y z) ( e x y) replaceEdge e x y ( f x y) ==  e x y  x y (replaceEdge e x y z) == e algebraic-graphs&Transpose a given graph. Complexity:  O(m * log(n)) time, O(n + m) memory.  transpose  ==  transpose ( x) ==  x transpose ( e x y) == $ e y x transpose . transpose == id algebraic-graphsTransform a graph by applying a function to each of its vertices. This is similar to Functor's  , but can be used with non-fully-parametric . Complexity: O((n + m) * log(n)) time. gmap f  ==  gmap f ( x) ==  (f x) gmap f ( e x y) ==  e (f x) (f y) gmap   ==  % gmap f . gmap g == gmap (f . g) algebraic-graphs)Transform a graph by applying a function h* to each of its edge labels. Complexity: O((n + m) * log(n)) time. The function h is required to be a  homomorphism# on the underlying type of labels e%. At the very least it must preserve  and : h  ==  h x  h y == h (x  y) If e is also a semiring, then h2 must also preserve the multiplicative structure: h  ==  h x  h y == h (x  y) If the above requirements hold, then the implementation provides the following guarantees. emap h  ==  emap h ( x) ==  x emap h ( e x y) ==  (h e) x y emap h ( x y) ==  (emap h x) (emap h y) emap h ( e x y) == " (h e) (emap h x) (emap h y) emap   ==  ( emap g . emap h == emap (g . h) algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(n + m)7 time, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are  . Complexity: O(n + m) time.  induceJust (  #) ==  induceJust ( (  x)  ) ==  x induceJust .   ' ==   induceJust .  (\x -> if p x then   x else  ) ==  p algebraic-graphs Compute the  reflexive and transitive closure of a graph over the underlying star semiring using the Warshall-Floyd-Kleene algorithm. closure  ==  closure ( x) ==   x x closure ( e x x) ==   x x closure ( e x y) ==  [(,x,x), (e,x,y), ( ,y,y)] closure ==  .  closure ==  . " closure . closure == closure  x (closure y) == Set. ( # y x) algebraic-graphs Compute the reflexive closure of a graph over the underlying semiring by adding a self-loop of weight  to every vertex. Complexity:  O(n * log(n)) time. reflexiveClosure  ==  reflexiveClosure ( x) ==   x x reflexiveClosure ( e x x) ==   x x reflexiveClosure ( e x y) ==  [(,x,x), (e,x,y), (?,y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure algebraic-graphs Compute the symmetric closure of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time. symmetricClosure  ==  symmetricClosure ( x) ==  x symmetricClosure ( e x y) == ; [(e,x,y), (e,y,x)] symmetricClosure x ==  x (< x) symmetricClosure . symmetricClosure == symmetricClosure algebraic-graphs Compute the transitive closure of a graph over the underlying star semiring using a modified version of the Warshall-Floyd-Kleene algorithm, which omits the reflexivity step. transitiveClosure  ==  transitiveClosure ( x) ==  x transitiveClosure ( e x y) ==  e x y transitiveClosure . transitiveClosure == transitiveClosure algebraic-graphsCheck that the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and there are no -labelled edges. It should be impossible to create an inconsistent adjacency map, and we use this function in testing.algebraic-graphs Defined via  and the  instance of .algebraic-graphs Defined via  and .algebraic-graphs Defined via .algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.))55(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?xe+algebraic-graphsThe  of a subgraph comprises its  and , i.e. all the vertices that are connected to the subgraph's vertices (along with the corresponding edge labels). Note that inputs and outputs can belong to the subgraph itself. In general, there are no guarantees on the order of vertices in  and (; furthermore, there may be repetitions.algebraic-graphsA network4 is a graph whose edges are labelled with distances.algebraic-graphsA type synonym for automata or labelled transition systems.algebraic-graphsA type synonym for unlabelled graphs.algebraic-graphs.Edge-labelled graphs, where the type variable e' stands for edge labels. For example,  Bool a is isomorphic to unlabelled graphs defined in the top-level module Algebra.Graph.Graph, where False and True denote the lack of and the existence of an unlabelled edge, respectively.algebraic-graphs Generalised ! folding: recursively collapse a  by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: empty, vertex and connect. Complexity: O(s) applications of the given functions. As an example, the complexity of  is O(s), since   and  have constant costs. foldg    ==   foldg   (    ) ==  foldg 1 (  1) (  (+)) ==  foldg True (  False) (  (&&)) ==  foldg False (== x) (  (||)) ==  x foldg Set. Set. (  Set. ) ==  algebraic-graphsBuild a graph given an interpretation of the three graph construction primitives ,  and 9, in this order. See examples for further clarification.  e) == ; buildg (\_ v _ -> v x) ==  x buildg (\e v c -> c l ( e v c x) ( e v c y)) ==  l x y buildg (\e v c ->  (c ) e ( v xs)) ==  xs buildg (\e v c ->  e v (  . c) g) ==  g = e v c (buildg f) == f e v c algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.  isSubgraphOf . x == True isSubgraphOf ( x) / == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf x y ==> x <= y algebraic-graphsConstruct the  empty graph. An alias for the constructor .  empty == True  x empty == False  M empty == 0  N empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex . An alias for the constructor .  (vertex x) == False  x (vertex y) == (x == y)  M (vertex x) == 1  N (vertex x) == 0 algebraic-graphsConstruct the graph comprising a single labelled edge. edge e x y ==  e ( x) ( y) edge  x y ==  [x,y]  x y (edge e x y) == (e /= )  x y (edge e x y) == e  N (edge e x y) == if e ==  then 0 else 1  M (edge e 1 1) == 1  M (edge e 1 2) == 2 algebraic-graphs8The left-hand part of a convenient ternary-ish operator x--y for creating labelled edges.  x -- y ==  e x y algebraic-graphs9The right-hand part of a convenient ternary-ish operator x--y for creating labelled edges.  x -- y ==  e x y algebraic-graphsOverlay two graphs. An alias for  . Complexity: O(1) time and memory,  O(s1 + s2) size.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  M (overlay x y) >=  M x  M (overlay x y) <=  M x +  M y  N (overlay x y) >=  N x  N (overlay x y) <=  N x +  N y  M (overlay 1 2) == 2  N (overlay 1 2) == 0 Note: / composes edges in parallel using the operator  with  acting as the identity:  x y $ overlay ( e x y) (  x y) == e  x y $ overlay ( e x y) ( f x y) == e  f 0Furthermore, when applied to transitive graphs, 0 composes edges in sequence using the operator  with  acting as the identity:  x z $  (overlay ( e x y) (  y z)) == e  x z $  (overlay ( e x y) ( f y z)) == e  f algebraic-graphsConnect two graphs with edges labelled by a given label. An alias for . Complexity: O(1) time and memory,  O(s1 + s2) size. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  (connect e x y) ==  x &&  y  z (connect e x y) ==  z x ||  z y  M (connect e x y) >=  M x  M (connect e x y) <=  M x +  M y  N (connect e x y) <=  M x *  M y +  N x +  N y  M (connect e 1 2) == 2  N (connect e 1 2) == if e ==  then 0 else 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x vertices ==  . map   x . vertices ==  x  M . vertices ==  .   T . vertices == Set. algebraic-graphsConstruct the graph from a list of labelled edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] ==  edges [(e,x,y)] ==  e x y edges ==  .  (\(e, x, y) ->  e x y) algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs(Check if a graph is empty. Complexity: O(s) time. isEmpty * == True isEmpty (  ) == True isEmpty () x) == False isEmpty ( x $  x) == True isEmpty ( x y $  e x y) == False algebraic-graphsThe size of a graph, i.e. the number of leaves of the expression including  leaves. Complexity: O(s) time. size  == 1 size ( x) == 1 size ( x y) == size x + size y size ( x y) == size x + size y size x >= 1 size x >=  M x algebraic-graphs7Check if a graph contains a given vertex. Complexity: O(s) time.  hasVertex x " == False hasVertex x ($ y) == (x == y) hasVertex x .  x ==   False algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y ( e x y) == (e /= ) hasEdge x y .  x y ==  ' False hasEdge x y ==   .   .  & (\(_,ex,ey) -> ex == x && ey == y) .  algebraic-graphs3Extract the label of a specified edge from a graph.algebraic-graphs;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  ==  .   algebraic-graphsThe list of edges of a graph, sorted lexicographically with respect to pairs of connected vertices (i.e. edge-labels are ignored when sorting). Complexity: O(n + m) time and O(m) memory.  edgeList  == [] edgeList ( x) == [] edgeList ( e x y) == if e ==  then [] else [(e,x,y)] algebraic-graphs3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet  == Set. vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs0The set of edges of a given graph. Complexity: O(n + m) time and O(m) memory. edgeSet  == Set. edgeSet ( x) == Set. edgeSet ( e x y) == if e ==  then Set. else Set. (e,x,y) algebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( e x x) ==  removeVertex 1 ( e 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y ( e x y) ==  [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x ==  x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O(s) time, memory and size. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  ! (\v -> if v == x then y else v) algebraic-graphsReplace an edge from a given graph. If it doesn't exist, it will be created. Complexity:  O(log(n)) time. 'replaceEdge e x y z ==  (removeEdge x y z) ( e x y) replaceEdge e x y ( f x y) ==  e x y  x y (replaceEdge e x y z) == e algebraic-graphs&Transpose a given graph. Complexity: O(s) time, memory and size.  transpose  ==  transpose ( x) ==  x transpose ( e x y) == $ e y x transpose . transpose == id algebraic-graphsTransform a graph by applying a function to each of its edge labels. Complexity: O(s) time, memory and size. The function h is required to be a  homomorphism# on the underlying type of labels e%. At the very least it must preserve  and : h  ==  h x  h y == h (x  y) If e is also a semiring, then h2 must also preserve the multiplicative structure: h  ==  h x  h y == h (x  y) If the above requirements hold, then the implementation provides the following guarantees. emap h  ==  emap h ( x) ==  x emap h ( e x y) ==  (h e) x y emap h ( x y) ==  (emap h x) (emap h y) emap h ( e x y) == " (h e) (emap h x) (emap h y) emap   ==  ( emap g . emap h == emap (g . h) algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are  . Complexity: O(s) time, memory and size.  induceJust (  #) ==  induceJust ( (  x)  ) ==  x induceJust .    ' ==   induceJust .   (\x -> if p x then   x else  ) ==  p algebraic-graphs Compute the  reflexive and transitive closure of a graph over the underlying star semiring using the Warshall-Floyd-Kleene algorithm. closure  ==  closure ( x) ==   x x closure ( e x x) ==   x x closure ( e x y) ==  [(,x,x), (e,x,y), ( ,y,y)] closure ==  .  closure ==  . " closure . closure == closure  U x (closure y) == Set. ( # y x) algebraic-graphs Compute the reflexive closure of a graph over the underlying semiring by adding a self-loop of weight  to every vertex. Complexity:  O(n * log(n)) time. reflexiveClosure  ==  reflexiveClosure ( x) ==   x x reflexiveClosure ( e x x) ==   x x reflexiveClosure ( e x y) ==  [(,x,x), (e,x,y), (?,y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure algebraic-graphs Compute the symmetric closure of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time. symmetricClosure  ==  symmetricClosure ( x) ==  x symmetricClosure ( e x y) == ; [(e,x,y), (e,y,x)] symmetricClosure x ==  x (< x) symmetricClosure . symmetricClosure == symmetricClosure algebraic-graphs Compute the transitive closure of a graph over the underlying star semiring using a modified version of the Warshall-Floyd-Kleene algorithm, which omits the reflexivity step. transitiveClosure  ==  transitiveClosure ( x) ==  x transitiveClosure ( e x y) ==  e x y transitiveClosure . transitiveClosure == transitiveClosure algebraic-graphs Extract the 8 of a subgraph specified by a given predicate. Returns Nothing$ if the specified subgraph is empty.  context ( > False) x == Nothing context (== 1) ( e 1 2) == if e ==  then Just ( [] []) else Just () [ ] [(e,2)]) context (== 2) ( e 1 2) == if e ==  then Just ( [] []) else Just ( [(e,1)] [ ]) context (  True ) ( e 1 2) == if e ==  then Just ( [] []) else Just ( [(e,1)] [(e,2)]) context (== 4) (3 * 1 * 4 * 1 * 5) == Just ( [(,3), (,1)] [(,1), (,5)]) algebraic-graphs Defined via  and .algebraic-graphs Defined via .algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details...55(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?|algebraic-graphsFor simplicity we measure  journey times in integer number of minutes.algebraic-graphsOur example networks have cities as vertices.algebraic-graphs.A part of the EastCoast train network between  and .  eastCoast =  [  150  ,   90  ,  170  ] algebraic-graphs-A part of the ScotRail train network between  and .  scotRail =  [  140  ,   50  ,   70  ] algebraic-graphsAn example train network.  network =     (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone!'(-58>? algebraic-graphsThe state of the order.algebraic-graphsChoosing what to orderalgebraic-graphsMaking the paymentalgebraic-graphsThe order is completealgebraic-graphs3The alphabet of actions for ordering coffee or tea.algebraic-graphs Order coffeealgebraic-graphs Order teaalgebraic-graphsCancel payment or orderalgebraic-graphsPay for the orderalgebraic-graphs0An example automaton for ordering coffee or tea. coffeeTeaAutomaton =  [  [, ] ! ,  [ ] ! ,  [ ] ! ,  [ ]  ] algebraic-graphs The map of  reachability. reachability = Map.  $ map (     skeleton) [. ..] where skeleton = emap (Any . not . ) coffeeTeaAutomaton Or, when evaluated: reachability = Map.  [ ( , [ , , "]) , ( , [ ,  , "]) , (, [ ]) ]  (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone '(-58>? algebraic-graphs$An abstract document data type with O(1) time concatenation (the current implementation uses difference lists). Here s? is the type of abstract symbols or strings (text or binary).  s is a   , therefore   corresponds to the empty document- and two documents can be concatenated with   (or operator V'). Documents comprising a single symbol or string can be constructed using the function . Alternatively, you can construct documents as string literals, e.g. simply as "alga", by using the OverloadedStrings GHC extension. To extract the document contents use the function .Note that the document comprising a single empty string is considered to be different from the empty document. This design choice is motivated by the desire to support string types s that have no  instance, such as Data.ByteString.Builder, for which there is no way to check whether a string is empty or not. As a consequence, the  and  # instances are defined as follows:   /=  ""   <  "" algebraic-graphsCheck if a document is empty. The result is the same as when comparing the given document to  ), but this function does not require the  s constraint. Note that the document comprising a single empty string is considered to be different from the empty document. isEmpty   == True isEmpty (, "") == False isEmpty x == (x ==  ) algebraic-graphs>Construct a document comprising a single symbol or string. If s is an instance of class  , then documents of type  s can be constructed directly from string literals (see the second example below). literal "Hello, " V' literal "World!" == literal "Hello, World!" literal "I am just a string literal" == "I am just a string literal" # . literal ==   algebraic-graphsRender the document as a single string. An inverse of the function . render ( "al" V'  "ga") :: (  s,   s) => s render ( "al" V'  "ga") == "alga" render   ==   render .  ==   algebraic-graphsConcatenate two documents, separated by a single space, unless one of the documents is empty. The operator <+> is associative with identity  . x <+>   == x   <+> x == x x <+> (y <+> z) == (x <+> y) <+> z "name" <+> "surname" == "name surname" algebraic-graphs#Wrap a document in square brackets. "brackets "i" == "[i]" brackets   == "[]" algebraic-graphs#Wrap a document into double quotes. doubleQuotes "/path/with spaces" == "\"/path/with spaces\"" doubleQuotes (doubleQuotes  ) == "\"\"\"\"" algebraic-graphs/Prepend a given number of spaces to a document. indent 0 ==   indent 1   == " " algebraic-graphsConcatenate documents after appending a terminating newline symbol to each. !unlines [] ==   unlines [ ] == "\n" unlines ["title", "subtitle"] == "title\nsubtitle\n" algebraic-graphsExport a graph into a document given two functions that construct documents for individual vertices and edges. The order of export is: vertices, sorted by   a, and then edges, sorted by   (a, a). For example:  vDoc x =  (  x) <> "\n" eDoc x y =  (  x) <> " -> " <>  (  y) <> "\n" > putStrLn $ ( $ export vDoc eDoc (1 + 2 * (3 + 4) :: W Int) 1 2 3 4 2 -> 3 2 -> 4 algebraic-graphsThe empty document is smallest.  7(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone #$'(-58>?algebraic-graphs The record  a s specifies the style to use when exporting a graph in the DOT format. Here a( is the type of the graph vertices, and s is the type of string to represent the resulting DOT document (e.g. String, Text, etc.). The only field that has no obvious default value is !, which holds a function of type a -> s, to compute vertex names. See the function  for an example.algebraic-graphsName of the graph.algebraic-graphsPreamble (a list of lines) is added at the beginning of the DOT file body.algebraic-graphsGraph style, e.g. ["bgcolor" := "azure"].algebraic-graphsDefault vertex style, e.g. ["shape" := "diamond"].algebraic-graphsDefault edge style, e.g. ["style" := "dashed"].algebraic-graphsCompute a vertex name.algebraic-graphs Attributes of a specific vertex.algebraic-graphsAttributes of a specific edge.algebraic-graphs&The quoting style used for attributes.algebraic-graphs5The style of quoting used when exporting attributes;  is the default.algebraic-graphs3An attribute is just a key-value pair, for example "shape" := "box". Attributes are used to specify the style of graph elements during export.algebraic-graphs(Default style for exporting graphs. The  field is provided as the only argument; the other fields are set to trivial defaults.algebraic-graphs(Default style for exporting graphs with -able vertices. The  field is computed using  0; the other fields are set to trivial defaults. defaultStyleViaShow =  (  .  ) algebraic-graphs"Export a graph with a given style. For example:  style ::  Int String style =  { ! = "Example" , 8 = [" // This is an example", ""] , = = ["label" := "Example", "labelloc" := "top"] ,  = ["shape" := "circle"] ,  =   ,  = \x -> "v" ++   x , ) = \x -> ["color" := "blue" |   x ] , + = \x y -> ["style" := "dashed" |   (x * y)] ,  = 4 } > putStrLn $ export style (1 * 2 + 3 * 4 * 5 :: Graph Int) digraph Example { // This is an example graph [label="Example" labelloc="top"] node [shape="circle"] "v1" [color="blue"] "v2" "v3" [color="blue"] "v4" "v5" [color="blue"] "v1" -> "v2" "v3" -> "v4" "v3" -> "v5" [style="dashed"] "v4" -> "v5" } algebraic-graphsExport a graph whose vertices are represented simply by their names. For example: > Text.putStrLn $ exportAsIs (= ["a", "b", "c"] :: 1 Text) digraph { "a" "b" "c" "a" -> "b" "b" -> "c" "c" -> "a" } algebraic-graphsExport a graph using the . For example: /> putStrLn $ exportViaShow (1 + 2 * (3 + 4) :: W Int) digraph { "1" "2" "3" "4" "2" -> "3" "2" -> "4" } (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?8-algebraic-graphsThe  data type provides the four algebraic graph construction primitives , ,  and , as well as various derived functions. The only difference compared to the W data type defined in  Algebra.Graph is that the  operation is  commutative. We define a  instance as a convenient notation for working with undirected graphs: 0 ==  0 1 + 2 ==  ( 1) ( 2) 1 * 2 ==  ( 1) ( 2) 1 + 2 * 3 ==  ( 1) ( ( 2) ( 3)) 1 * (2 + 3) ==  ( 1) ( ( 2) ( 3)) Note: the 7 instance does not satisfy several "customary laws" of , which dictate that  0 and  1; should act as additive and multiplicative identities, and 0 as additive inverse. Nevertheless, overloading ,  and  is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The - instance is currently implemented using the  as the canonical graph representation. and satisfies all axioms of algebraic graphs: is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z% is associative, commutative and has  as the identity:  x * empty == x empty * x == x x * y == y * x x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * zThe following useful theorems can be proved from the above set of axioms. has # as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of : -x * y + x + y == x * y x * x * x == x * xWhen specifying the time and memory complexity of graph algorithms, n2 will denote the number of vertices in the graph, m3 will denote the number of edges in the graph, and s will denote the size of the corresponding  expression. For example, if g is a  then n, m and s can be computed as follows: n ==  g m ==  g s ==  g Note that % counts all leaves of the expression:   == 0   == 1  ( x) == 1  ( x) == 1  ( + ) == 0  ( + ) == 2Converting an undirected  to the corresponding  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 adjacency maps.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:  1 <  2  3 <  1 2  1 <  1 1  1 1 <  1 2  1 2 <  1 1 +  2 2  1 2 <  1 3  1 2 ==  2 1*Note that the resulting order refines the ! relation and is compatible with  and  operations:  x y ==> x <= y # <= x x <= x + y x + y <= x * yalgebraic-graphs+Construct an undirected graph from a given  Algebra.Graph. Complexity: O(1) time. toUndirected (4 1 2) ==  1 2 toUndirected .  == id  . toUndirected == M (*2) .  . toUndirected >= N algebraic-graphsExtract the underlying  Algebra.Graph. Complexity: O(n + m) time. fromUndirected (4 1 2) == - [(1,2),(2,1)]  .  == id M . fromUndirected ==  N . fromUndirected <= (*2) .  algebraic-graphsConstruct the  empty graph.  empty == True  x empty == False  empty == 0  empty == 0  empty == 1 algebraic-graphsConstruct the graph comprising a single isolated vertex.  (vertex x) == False  x (vertex y) == (x == y)  (vertex x) == 1  (vertex x) == 0  (vertex x) == 1 algebraic-graphsConstruct the graph comprising  a single edge. edge x y ==  ( x) ( y) edge x y ==  y x edge x y ==  [(x,y), (y,x)]  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 algebraic-graphsOverlay two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O(1) time and memory,  O(s1 + s2) size.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) ==  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphsConnect two graphs. This is a commutative and associative operation with the identity , which distributes over 2 and obeys the decomposition axiom. Complexity: O(1) time and memory,  O(s1 + s2) size. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  x y ==  y x  (connect x y) ==  x &&  y  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) >=  x *  y   2  (connect x y) ==  x +  y  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x vertices ==  . map   x . vertices ==  x  . vertices ==  .   . vertices == Set .  algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] ==  edges [(x,y)] ==  x y edges [(x,y), (y,x)] ==  x y algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==  " connects == connects .   algebraic-graphs Generalised ! folding: recursively collapse a  by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: empty, vertex, overlay and connect. Complexity: O(s) applications of the given functions. As an example, the complexity of  is O(s), since   and  have constant costs. foldg     == id foldg    (  ) == id foldg 1 ( " 1) (+) (+) ==  foldg True ( " False) (&&) (&&) == 5 foldg False (== x) (||) (||) ==  x algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.  isSubgraphOf . x == True isSubgraphOf ( x) / == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True isSubgraphOf ( x y) ( y x) == True isSubgraphOf x y ==> x <= y algebraic-graphs+Convert an undirected graph to a symmetric .algebraic-graphs(Check if a graph is empty. Complexity: O(s) time. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty ( x $  x) == True isEmpty ( x y $  x y) == False algebraic-graphsThe size of a graph, i.e. the number of leaves of the expression including  leaves. Complexity: O(s) time. size  == 1 size ( x) == 1 size ( x y) == size x + size y size ( x y) == size x + size y size x >= 1 size x >=  x algebraic-graphs7Check if a graph contains a given vertex. Complexity: O(s) time.  hasVertex x " == False hasVertex x ($ y) == (x == y) hasVertex x .  x ==   False algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (! x y) == True hasEdge x y (" y x) == True hasEdge x y .  x y ==  ' False hasEdge x y ==  (min x y, max x y) .  algebraic-graphs0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount  == 0 vertexCount (3 x) == 1 vertexCount ==  . ) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(s + m * log(m))% time. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  ==  .   algebraic-graphs2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges m of a graph can be quadratic with respect to the expression size s.  edgeList  == [] edgeList ( x) == [] edgeList (, x y) == [(min x y, max y x)] edgeList ( 2 [3,1]) == [(1,2), (2,3)] algebraic-graphs3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet  == Set. vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory. edgeSet  == Set. edgeSet ( x) == Set. edgeSet ( x y) == Set. (  x y,   x y) algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and memory. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (1 1 2) == [(1, [2]), (2, [1])] adjacencyList (. 2 [3,1]) == [(1, [2]), (2, [1,3]), (3, [2])]  . adjacencyList == id algebraic-graphsThe set of vertices adjacent to a given vertex.  neighbours x  == Set. neighbours x ( x) == Set. neighbours x ( x y) == Set. [y] neighbours y ( x y) == Set. [x] algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] ==  path [x] ==  x path [x,y] ==  x y path .   == path algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  (x,y) circuit .   == circuit algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) == " (clique xs) (clique ys) clique .   == clique algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] ==  [(x1,y1), (x1,y2), (x2,x2), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity: O(L) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  .  (  ) stars .  == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O(T) time, memory and size, where T is the size of the given tree (i.e. the number of vertices in the tree). forest [] == ? forest [x] ==  x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==  [(1,2), (1,3), (4,5)] forest ==  .   algebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y ( x y) ==  [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y == removeEdge y x removeEdge x y .  x ==  x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O(s) time, memory and size. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time. mergeVertices ( 7 False) x == id mergeVertices (== x) y ==  x y mergeVertices  & 1 (0 * 2) == 1 * 1 mergeVertices   1 (3 + 4 * 5) == 4 * 1 algebraic-graphsConstruct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time. induce (  True ) x == x induce (  False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True algebraic-graphsConstruct the induced subgraph5 of a given graph by removing the vertices that are  . Complexity: O(s) time, memory and size.  induceJust (  #) ==  induceJust ( (  x)  ) ==  x induceJust .    ' ==   induceJust .   (\x -> if p x then   x else  ) ==  p algebraic-graphsThe edge complement of a graph. Note that, as can be seen from the examples below, this operation ignores self-loops. Complexity: O(n^2 * log n) time, O(n^2) memory.  complement  ==  complement ( x) == ( x) complement ( 1 2) == ( [1, 2]) complement ( 0 0) == ( 0 0) complement ( 1 [2, 3]) == ( ( 1) (( 2 3)) complement . complement == id algebraic-graphs Defined via  and .algebraic-graphs Defined via .algebraic-graphsNote:0 this does not satisfy the usual ring laws; see  for more details.**(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>? algebraic-graphs The class of preorder graphs( that are both reflexive and transitive.algebraic-graphs The class of transitive graphs- that satisfy the following additional axiom.The closure8 axiom: graphs with equal transitive closures are equal. 5y /= empty ==> x * y + x * z + y * z == x * y + y * zBy repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction.algebraic-graphs The class of reflexive graphs- that satisfy the following additional axiom.Each vertex has a  self-loop: vertex x == vertex x * vertex xNote that by applying the axiom in the reverse direction, one can always remove all self-loops resulting in an irreflexive graph. This type class can therefore be also used in the context of irreflexive graphs.algebraic-graphs The class of undirected graphs- that satisfy the following additional axiom. is commutative: x * y == y * xalgebraic-graphsThe core type class for constructing algebraic graphs, characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for  and , respectively. is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z is associative and has  as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * zThe following useful theorems can be proved from the above set of axioms. has # as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of : -x * y + x + y == x * y x * x * x == x * xThe core type class , corresponds to unlabelled directed graphs. , ,  and ? graphs can be obtained by extending the minimal set of axioms.When specifying the time and memory complexity of graph algorithms, n2 will denote the number of vertices in the graph, m3 will denote the number of edges in the graph, and s will denote the size of the corresponding  expression.algebraic-graphsThe type of graph vertices.algebraic-graphsConstruct the empty graph.algebraic-graphs)Construct the graph with a single vertex.algebraic-graphsOverlay two graphs.algebraic-graphsConnect two graphs.algebraic-graphs-Construct the graph comprising a single edge.  edge x y ==  ( x) ( y) algebraic-graphsConstruct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x vertices ==  . map  algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] ==  edges [(x,y)] ==  x y algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. overlays [] == ' overlays [x] == x overlays [x,y] ==  x y overlays ==    algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. connects [] == ' connects [x] == x connects [x,y] ==  x y connects ==    algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph3 of the second. Here is the current implementation: isSubgraphOf x y =  x y == y The complexity therefore depends on the complexity of equality testing of the specific graph instance.  isSubgraphOf - x == True isSubgraphOf ( x) . == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] ==  path [x] ==  x path [x,y] ==  x y algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) ==  (clique xs) (clique ys) algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] ==  [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe star formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe  tree graph constructed from a given   data structure. Complexity: O(T) time, memory and size, where T is the size of the given tree (i.e. the number of vertices in the tree). forest [] == ? forest [x] ==  x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==  [(1,2), (1,3), (4,5)] forest ==  .   (c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?3algebraic-graphsThe  data type represents a transitive binary relation over a set of elements. Transitive relations satisfy all laws of the  Transitive$ type class and, in particular, the closure axiom: y /= + ==> x * y + x * z + y * z == x * y + y * z!For example, the following holds:  xs == ( xs :: TransitiveRelation Int)The 3 instance produces transitively closed expressions: show (1 * 2 :: TransitiveRelation Int) == "edge 1 2" show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"algebraic-graphs'Construct a transitive relation from a . Complexity: O(1) time.algebraic-graphs.Extract the underlying relation. Complexity: O(n * m * log(m)) time.(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?lalgebraic-graphsThe  data type represents a reflexive binary relation over a set of elements. Reflexive relations satisfy all laws of the  Reflexive$ type class and, in particular, the  self-loop axiom:  x ==  x *  xThe 2 instance produces reflexively closed expressions: show (1 :: ReflexiveRelation Int) == "edge 1 1" show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"algebraic-graphs&Construct a reflexive relation from a . Complexity: O(1) time.algebraic-graphs.Extract the underlying relation. Complexity:  O(n*log(m)) time.(c) Andrey Mokhov 2016-2022MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone'(-58>?algebraic-graphsThe  data type represents a 5binary relation that is both reflexive and transitive$. Preorders satisfy all laws of the Preorder$ type class and, in particular, the  self-loop axiom:  x ==  x *  xand the closure axiom: y /= + ==> x * y + x * z + y * z == x * y + y * z!For example, the following holds:  xs == ( xs :: PreorderRelation Int)The  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)]" show (1 * 2 + 2 * 3 :: PreorderRelation Int) == "edges [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"algebraic-graphs%Construct a preorder relation from a . Complexity: O(1) time.algebraic-graphs.Extract the underlying relation. Complexity: O(n * m * log(m)) time.None '(-58>? +(c) Anton Lorenzen, Andrey Mokhov 2016-2022MIT (see the file LICENSE)*anfelor@posteo.de, andrey.mokhov@gmail.comunstableNone'(-58>?.\ algebraic-graphs encapsulates King-Launchbury graphs, which are implemented in the  Data.Graph module of the  containers library.algebraic-graphs=Array-based graph representation (King and Launchbury, 1995).algebraic-graphs A mapping of Data.Graph.Vertex to vertices of type a?. This is partial and may fail if the vertex is out of bounds.algebraic-graphs A mapping from vertices of type a to Data.Graph.Vertex . Returns  % if the argument is not in the graph.algebraic-graphsBuild  from an . If fromAdjacencyMap g == h then the following holds: map ( h) (+, $ % h) ==  g map (\(x, y) -> ( h x,  h y)) (+- $  h) ==  g  (fromAdjacencyMap (1 * 2 + 3 * 1)) == array" (0,2) [(0,[1]), (1,[]), (2,[0])]  (fromAdjacencyMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])] algebraic-graphsBuild  from an :. If fromAdjacencyIntMap g == h then the following holds: map ( h) (+, $ % h) == XY (Z g) map (\(x, y) -> ( h x,  h y)) (+- $  h) == O g  (fromAdjacencyIntMap (1 * 2 + 3 * 1)) == array" (0,2) [(0,[1]), (1,[]), (2,[0])]  (fromAdjacencyIntMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])] algebraic-graphs Compute the depth-first search forest of a graph.:In the following examples we will use the helper function: (%) :: Ord a => ( a -> b) ->  a -> b f % x = f ( x) for greater clarity. ! (dfsForest %  1 1) ==  1 ! (dfsForest %  1 2) ==  1 2 ! (dfsForest %  2 1) ==  [1,2]   (!( $ dfsForest % x) x == True dfsForest % !3 (dfsForest % x) == dfsForest % x dfsForest %  vs ==  (\v -> Node v []) ( $   vs) dfsForest % (3 * (1 + 4) * (1 + 5)) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 3 , subForest = [ Node { rootLabel = 4 , subForest = [] }]}] algebraic-graphs Compute the depth-first search forest of a graph, searching from each of the given vertices in order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable.:In the following examples we will use the helper function: (%) :: Ord a => ( a -> b) ->  a -> b f % x = f ( x) for greater clarity. ! $ (dfsForestFrom %  1 1) [1] ==  1 ! $ (dfsForestFrom %  1 2) [0] ==  ! $ (dfsForestFrom %  1 2) [1] ==  1 2 ! $ (dfsForestFrom %  1 2) [2] ==  2 ! $ (dfsForestFrom %  1 2) [2,1] ==  [1,2]   (!9 $ dfsForestFrom % x $ vs) x == True dfsForestFrom % x $  x ==  % x dfsForestFrom %  vs $ vs ==  (\v -> Node v []) ( vs) dfsForestFrom % x $ [] == [] dfsForestFrom % (3 * (1 + 4) * (1 + 5)) $ [1,4] == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] } , Node { rootLabel = 4 , subForest = [] }] algebraic-graphs,Compute the list of vertices visited by the depth-first search in a graph, when searching from each of the given vertices in order.:In the following examples we will use the helper function: (%) :: Ord a => ( a -> b) ->  a -> b f % x = f ( x) for greater clarity. dfs %  1 1 $ [1] == [1] dfs %  1 2 $ [0] == [] dfs %  1 2 $ [1] == [1,2] dfs %  1 2 $ [2] == [2] dfs %  1 2 $ [1,2] == [1,2] dfs %  1 2 $ [2,1] == [2,1] dfs % x $ [] == [] dfs % (3 * (1 + 4) * (1 + 5)) $ [1,4] == [1,5,4] $ [ # v x | v <- dfs % x $ vs ] == True algebraic-graphs Compute the topological sort of a graph. Note that this function returns a result even if the graph is cyclic.:In the following examples we will use the helper function: (%) :: Ord a => ( a -> b) ->  a -> b f % x = f ( x) for greater clarity. topSort % (1 * 2 + 3 * 1) == [3,1,2] topSort % (1 * 2 + 2 * 1) == [1,2]   [\21J234]^,-_`@abcMNdOTefgUh=5>?ijklm%nop6qrstuv7wxyz{|}~K234]^,-_`@abcMNdOZefh=5>?iklm%nop6qsuv7wx#W234]^,-_`@aCbcMNdOTefh=5>?iklm%nopqrstLW^3]4,-_`@ch=5>?iklqmno1234]^,-_`"abcMNdOTeh=>?i%;txyz~}                      ?                                                                                                    1   3 4 ] ^     @ b c M N  O T e g U   I  ?  k  % n o p 6   u v 7 w x z ~ }   | {        #       1  2 3 ,   @ a b c M N d O f T e g U m % p q r t w      x ~       a b c M N d O T Z e g  U  f    #         J K      234]^,-_`@abcMNdOTefgUh=5>?iklm%nop6qrsuv7wx234]^,-_`@abcMNdOTefh=5>?iklm%no6qrxW34]^@CbcMNOTeI?k%nopt1J234]^,-_@abcMNdOTegUm%np6qruv7wxyz|}~{W@234]^,-_aCbcdOTem%npqruv7waW234]^,-_`@aCbcMNdOTefh=5>?iklm%noqrLW23]^4,-_`@h=5>?kl[[[[[[2929/[[E/[\[![[[\[S[\[\PQ[[[\[[2929//[[p[\[\[[([\[\[\[\[\[R[[[[([(*[[\[\[\[\[\[!"[([![![ [([()C[[[\[\'  [[DR[DSCY[FG/[[[[[+algebraic-graphs-0.7-DxCmXygYU3a8wvsz565Q5f Algebra.Graph.HigherKinded.ClassAlgebra.Graph.AdjacencyMapAlgebra.Graph.AdjacencyIntMap'Algebra.Graph.AdjacencyIntMap.AlgorithmAlgebra.Graph.Internal Algebra.Graph$Algebra.Graph.Bipartite.AdjacencyMap.Algebra.Graph.Bipartite.AdjacencyMap.AlgorithmAlgebra.Graph.Label#Algebra.Graph.NonEmpty.AdjacencyMap$Algebra.Graph.AdjacencyMap.Algorithm"Algebra.Graph.Acyclic.AdjacencyMapAlgebra.Graph.ToGraphAlgebra.Graph.Relation Algebra.Graph.Relation.SymmetricAlgebra.Graph.NonEmpty#Algebra.Graph.Labelled.AdjacencyMapAlgebra.Graph.Labelled&Algebra.Graph.Labelled.Example.Network(Algebra.Graph.Labelled.Example.AutomatonAlgebra.Graph.ExportAlgebra.Graph.Export.DotAlgebra.Graph.UndirectedAlgebra.Graph.Class!Algebra.Graph.Relation.Transitive Algebra.Graph.Relation.ReflexiveAlgebra.Graph.Relation.PreorderAlgebra.Graph.Example.TodoData.Graph.Typed Data.Listnubsort Data.Tupleswap reachableand removeEdgeData.Semigroup<> Data.EitherrightsRight Data.GraphverticesedgesSetfromList Bipartite AdjacencyMapemptyvertexedgecliquegmapsymmetricClosureData.Set singletonData.BifunctorbimapData.Map.Strictcircuitbicliquestar isSubgraphOfData.Either.Extra fromEithersizeData.List.NonEmptylength Control.Monad>=>NonEmptyclique1 adjacencyMapadjacencyIntMap Undirected vertexCount edgeCountedgeListTreeForesttoListreverse vertexSetpostSet Data.MonoidGraph Data.IntSet toAscList vertexIntSetbaseGHC.BaseoverlayconnectoverlaysconnectsisEmpty hasVertexhasEdge vertexListedgeSet adjacencyListpreSetpathstarsfromAdjacencySetstreeforest removeVertex replaceVertex mergeVertices transposeinduce induceJustcomposeboxclosurereflexiveClosuretransitiveClosure consistent$fMonoidAdjacencyMap$fSemigroupAdjacencyMap$fNFDataAdjacencyMap$fIsStringAdjacencyMap$fNumAdjacencyMap$fShowAdjacencyMap$fOrdAdjacencyMap$fEqAdjacencyMap$fGenericAdjacencyMapAdjacencyIntMapfromAdjacencyMap preIntSet postIntSetfromAdjacencyIntSets$fMonoidAdjacencyIntMap$fSemigroupAdjacencyIntMap$fNFDataAdjacencyIntMap$fNumAdjacencyIntMap$fOrdAdjacencyIntMap$fShowAdjacencyIntMap$fEqAdjacencyIntMap$fGenericAdjacencyIntMapCycle bfsForestbfs dfsForest dfsForestFromdfstopSort isAcyclic isDfsForestOf isTopSortOfFocusokisosvsList emptyFocus vertexFocus overlayFoci connectFoci foldr1SafemaybeFcartesianProductWithcoerce00coerce10coerce20coerce01coerce11coerce21 $fMonadList$fApplicativeList $fFunctorList$fFoldableList $fIsListList $fOrdList$fEqList $fShowList $fMonoidList$fSemigroupListContextinputsoutputsEmptyVertexOverlayConnectfoldgbuildg===meshtorusdeBruijn splitVertexsimplifysparsify sparsifyKLcontext $fMonoidGraph$fSemigroupGraph$fMonadPlusGraph$fAlternativeGraph $fMonadGraph$fApplicativeGraph $fOrdGraph $fEqGraph$fIsStringGraph $fNumGraph $fNFDataGraph$fFunctorGraph $fEqContext $fShowContext $fShowGraph$fGenericGraphPreorder Transitive Reflexive $fGraphGraphNilConsleftAdjacencyMaprightAdjacencyMap leftVertex rightVertex toBipartitetoBipartiteWith fromBipartitefromBipartiteWith hasLeftVertexhasRightVertexleftVertexCountrightVertexCountleftVertexListrightVertexList leftVertexSetrightVertexSetleftAdjacencyListrightAdjacencyListevenListoddListremoveLeftVertexremoveRightVertexboxWith $fGenericListIndependentSet VertexCoverMatching pairOfLeft pairOfRightOddCycle detectPartsmatching isMatchingOf matchingSize maxMatchingisVertexCoverOfvertexCoverSizeminVertexCoverisIndependentSetOfindependentSetSizemaxIndependentSetaugmentingPathconsistentMatching $fOrdMatching $fEqMatching$fShowMatching$fGenericMatching $fShowPart$fEqPart WidestPathCountShortestPathsAllShortestPaths ShortestPathPathOptimum getOptimum getArgumentRegularExpressionLabelPowerSet getPowerSetMinimumDistanceCountCapacity NonNegativeDioid StarSemiringSemiringone<.>zero<+>finite finiteWord unsafeFiniteinfinite getFinitecapacity getCapacitycountgetCountdistance getDistance getMinimum noMinimumisZero $fSemiringAny$fStarSemiringAny $fDioidAny $fNumExtended$fMonadExtended$fApplicativeExtended$fNumNonNegative$fBoundedNonNegative$fShowNonNegative$fDioidDistance$fStarSemiringDistance$fSemiringDistance$fShowDistance$fStarSemiringCount$fSemiringCount $fShowCount$fDioidCapacity$fStarSemiringCapacity$fSemiringCapacity$fShowCapacity$fIsListMinimum $fShowMinimum$fDioidMinimum$fSemiringMinimum$fMonoidMinimum$fSemigroupMinimum$fDioidPowerSet$fSemiringPowerSet$fStarSemiringLabel$fSemiringLabel $fMonoidLabel$fSemigroupLabel $fShowLabel $fIsListLabel$fDioidOptimum$fStarSemiringOptimum$fSemiringOptimum$fMonoidOptimum$fSemigroupOptimum $fEqOptimum $fOrdOptimum $fShowOptimum$fFunctorLabel $fEqPowerSet$fMonoidPowerSet $fOrdPowerSet$fSemigroupPowerSet$fShowPowerSet$fApplicativeMinimum $fEqMinimum$fFunctorMinimum $fOrdMinimum$fMonadMinimum$fBoundedCapacity $fEqCapacity$fMonoidCapacity $fNumCapacity $fOrdCapacity$fSemigroupCapacity$fBoundedCount $fEqCount $fMonoidCount $fNumCount $fOrdCount$fSemigroupCount$fBoundedDistance $fEqDistance$fMonoidDistance $fNumDistance $fOrdDistance$fSemigroupDistance$fApplicativeNonNegative$fEqNonNegative$fFunctorNonNegative$fOrdNonNegative$fMonadNonNegative $fEqExtended$fFunctorExtended $fOrdExtended$fShowExtended toNonEmpty fromNonEmpty vertices1edges1 overlays1 connects1 vertexList1path1circuit1 biclique1stars1 removeVertex1induce1 induceJust1scc$fShowStateSCC fromAcyclicunionjoin toAcyclic toAcyclicOrdshrinkToGraphToVertextoGraphtoAdjacencyMaptoAdjacencyMapTransposetoAdjacencyIntMaptoAdjacencyIntMapTransposeadjacencyMapTransposeadjacencyIntMapTranspose$fToGraphAdjacencyMap$fToGraphAdjacencyIntMap$fToGraphAdjacencyMap0$fToGraphGraphRelationdomainrelation$fToGraphRelation$fMonoidRelation$fSemigroupRelation$fIsStringRelation $fNumRelation$fNFDataRelation $fOrdRelation$fShowRelation $fEqRelation fromSymmetric toSymmetric neighboursoverlay1foldg1mesh1torus1 splitVertex1-<>-fromAdjacencyMaps edgeLabelskeleton replaceEdgeemapNetwork AutomatonUnlabelledGraph$fBifunctorGraph JourneyTimeCityAberdeen EdinburghGlasgowLondon Newcastle eastCoastscotRailnetwork $fBoundedCity $fEnumCity$fEqCity $fOrdCity $fShowCityStateChoicePaymentCompleteAlphabetCoffeeTeaCancelPaycoffeeTeaAutomaton reachability$fBoundedState $fEnumState $fEqState $fOrdState $fShowState$fBoundedAlphabet$fEnumAlphabet $fEqAlphabet $fOrdAlphabet$fShowAlphabetDocliteralrenderbrackets doubleQuotesindentunlinesexport $fIsStringDoc$fOrdDoc$fEqDoc $fShowDoc $fMonoidDoc$fSemigroupDocStyle graphNamepreamblegraphAttributesdefaultVertexAttributesdefaultEdgeAttributes vertexNamevertexAttributesedgeAttributesattributeQuotingQuoting DoubleQuotesNoQuotes Attribute:= defaultStyledefaultStyleViaShow exportAsIs exportViaShow toUndirectedfromUndirected toRelation complement $fGraph(,,) $fGraph(,) $fGraph-> $fGraphMaybe $fGraph()$fGraphRelation$fGraphRelation0$fGraphAdjacencyMap$fGraphAdjacencyIntMap$fGraphAdjacencyMap0 $fGraphGraph0 $fGraphGraph1$fUndirected(,,)$fUndirected(,)$fUndirected->$fUndirectedMaybe$fUndirected()$fUndirectedRelation$fUndirectedGraph$fReflexive(,,)$fReflexive(,) $fReflexive->$fReflexiveMaybe $fReflexive()$fTransitive(,,)$fTransitive(,)$fTransitive->$fTransitiveMaybe$fTransitive()$fPreorder(,,) $fPreorder(,) $fPreorder->$fPreorderMaybe $fPreorder()TransitiveRelation fromRelation$fTransitiveTransitiveRelation$fGraphTransitiveRelation$fShowTransitiveRelation$fOrdTransitiveRelation$fEqTransitiveRelation$fIsStringTransitiveRelation$fNFDataTransitiveRelation$fNumTransitiveRelationReflexiveRelation$fReflexiveReflexiveRelation$fGraphReflexiveRelation$fShowReflexiveRelation$fOrdReflexiveRelation$fEqReflexiveRelation$fIsStringReflexiveRelation$fNFDataReflexiveRelation$fNumReflexiveRelationPreorderRelation$fPreorderPreorderRelation$fTransitivePreorderRelation$fReflexivePreorderRelation$fGraphPreorderRelation$fOrdPreorderRelation$fEqPreorderRelation$fShowPreorderRelation$fIsStringPreorderRelation$fNFDataPreorderRelation$fNumPreorderRelationTodolowhighpriority~*~>*<todo $fGraphTodo $fNumTodo$fIsStringTodo$fEqTodo $fShowTodoGraphKL toGraphKL fromVertexKL toVertexKLfromAdjacencyIntMapGHC.NumNum fromIntegernegate+*GHC.ShowShowghc-prim GHC.ClassesEqcontainers-0.6.2.1Data.Map.InternalData.Map.Strict.InternalData.Set.Internal Data.Foldableelemmapuncurryfoldrall GHC.TypesTrueconstGHC.List++fmap Data.TreeGHC.Realevenoddid GHC.MaybeNothingJustData.IntMap.InternalData.IntMap.Strict.InternalData.IntSet.InternalIntconcat Data.OldListlevelsOrd:|flipnullisRightMonoidmemptymappendpure ApplicativeFoldablefoldr1MaybeGHC.PrimcoerceLeftfilter>>=<*>compare== MonadPlus Alternative<|>partitionEithersfstsndleftsnotElemmodmin isSubsetOfmaxliftA2Word:+::*:signumFalseunionscartesianProductmembernot Control.Arrow&&& Data.StringIsStringshow fromStringdiv