0g      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                  ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~                                                        (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTVThe o type class captures data types that can be converted to polymorphic graph expressions. The conversion method  semantically acts as the identity on graph data structures, but allows to convert graphs between different data representations.  toGraph (g ::   a ) ::   a == g  (toGraph (1 * 2 ::   Int) ::   Int) == "edge 1 2" The second method I is used for generalised graph folding. It recursively collapses a given data type by applying the provided graph construction primitives. The order of arguments is: empty, vertex, overlay and connect, and it is assumed that the functions satisfy the axioms of the algebra. The following law establishes the relation between  and : toGraph == foldg         The class of preorder graphs( that are both reflexive and transitive. 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 * zpBy repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction. The class of reflexive graphs- that satisfy the following additional axiom.Each vertex has a  self-loop: vertex x == vertex x * vertex xoNote that by applying the axiom in the reverse direction, one can always remove all self-loops resulting in an irreflexive graphR. This type class can therefore be also used in the context of irreflexive graphs. The class of undirected graphs- that satisfy the following additional axiom. is commutative: x * y == y * x The 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 * zIThe 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.DWhen 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. The type of graph vertices. Construct the empty graph. )Construct the graph with a single vertex. Overlay two graphs.Connect two graphs.;Construct the graph comprising a single edge. Complexity: O(1) time, memory and size.  edge x y ==  (  x) (  y) OConstruct 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 7Construct 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 -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 ==      -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 ==     The ' 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 gThe 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 The 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 The 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)] The 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) The 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] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) The starG 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) The star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] ==   x starTranspose x [y] ==  y x starTranspose x [y,z] == ) [(y,x), (z,x)] starTranspose x ys ==  ( ys) ( ( x) starTranspose x ys == transpose ( x ys) The  tree graph constructed from a given  data structure. Complexity: O(T) time, memory and size, where TJ is the size of the given tree (i.e. the number of vertices in the tree). <tree (Node x []) ==  ? x tree (Node x [Node y [Node z []]]) == E [x,y,z] tree (Node x [Node y [], Node z []]) == E x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) ==  [(1,2), (1,3), (3,4), (3,5)] The  forest graph constructed from a given  data structure. Complexity: O(F) time, memory and size, where FN is the size of the given forest (i.e. the number of vertices in the forest). >forest [] ==  ? forest [x] == A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == U [(1,2), (1,3), (4,5)] forest ==  . map      (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone <FKNTVr 77D encapsulates King-Launchbury graphs, which are implemented in the  Data.Graph module of the  containers library. 2Note: this data structure is for internal use only.If mkGraphKL (adjacencyMap g) == h then the following holds: map (: h) ( $ 9% h) ==  g map (\(x, y) -> (: h x, : h y)) ( $ 9 h) ==  g 9=Array-based graph representation (King and Launchbury, 1995).: A mapping of Data.Graph.Vertex to vertices of type a.; A mapping from vertices of type a to Data.Graph.Vertex . Returns % if the argument is not in the graph.<The <X 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 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))The  ? instance is defined using basic graph construction primitives: Zshow (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 * zIThe 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 * xDWhen specifying the time and memory complexity of graph algorithms, n and mI will denote the number of vertices and edges in the graph, respectively.>The  adjacency mapN of the graph: each vertex is associated with a set of its direct successors.?(Cached King-Launchbury representation. )Note: this field is for internal use only.@ Construct an <g from a map of successor sets and (lazily) compute the corresponding King-Launchbury representation. ,Note: this function is for internal use only.ACheck if 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. ,Note: this function is for internal use only.  consistent & == True consistent ($ x) == True consistent (# x y) == True consistent (# x y) == True consistent (& x y) == True consistent (% xs) == True consistent ( % xs ys) == True consistent (! xs) == True BBuild 7 from a map of successor sets. ,Note: this function is for internal use only. 789:;<=>?@AB <=>?@A789:;B789:;<=>?(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV+HConstruct the  empty graph. Complexity: O(1) time and memory. S empty == True T x empty == False V empty == 0 W empty == 0 IConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory. S (vertex x) == False T x (vertex x) == True V (vertex x) == 1 W (vertex x) == 0 JConstruct the graph comprising  a single edge. Complexity: O(1) time, memory. edge x y == L (I x) (I y) U x y (edge x y) == True W (edge x y) == 1 V (edge 1 1) == 1 V (edge 1 2) == 2 KOverlay\ two graphs. This is a commutative, associative and idempotent operation with the identity H. Complexity: O((n + m) * log(n)) time and O(n + m) memory. S (overlay x y) == S x && S y T z (overlay x y) == T z x || T z y V (overlay x y) >= V x V (overlay x y) <= V x + V y W (overlay x y) >= W x W (overlay x y) <= W x + W y V (overlay 1 2) == 2 W (overlay 1 2) == 0 LConnectA two graphs. This is an associative operation with the identity H, which distributes over K1 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). S (connect x y) == S x && S y T z (connect x y) == T z x || T z y V (connect x y) >= V x V (connect x y) <= V x + V y W (connect x y) >= W x W (connect x y) >= W y W (connect x y) >= V x * V y W (connect x y) <= V x * V y + W x + W y V (connect 1 2) == 2 W (connect 1 2) == 1 MOConstruct 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 [] == H vertices [x] == I x T x . vertices == " x V . vertices == # . "# [ . vertices == Set.$ N7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] == H edges [(x, y)] == J x y W . edges == # . "# Y . edges == "# . "$ O-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == H/ overlays [x] == x overlays [x,y] == K x y overlays ==  K H S . overlays == % S P-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] == H/ connects [x] == x connects [x,y] == L x y connects ==  L H S . connects == % S Q7Construct a graph from an adjacency list. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 9fromAdjacencyList [] == H: fromAdjacencyList [(x, [])] == I< x fromAdjacencyList [(x, [y])] == J x y fromAdjacencyList . Z == id KO (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys) RThe R' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf H- x == True isSubgraphOf (I x) H. == False isSubgraphOf x (K x y) == True isSubgraphOf (K x y) (L x y) == True isSubgraphOf (^ xs) (_ xs) == True S(Check if a graph is empty. Complexity: O(1) time. isEmpty H( == True isEmpty (K H H) == True isEmpty (I' x) == False isEmpty (f x $ I x) == True isEmpty (g x y $ J x y) == False T7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x H" == False hasVertex x (I x) == True hasVertex 1 (I! 2) == False hasVertex x . f x == const False U5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y H" == False hasEdge x y (I z) == False hasEdge x y (J" x y) == True hasEdge x y . g4 x y == const False hasEdge x y == " (x,y) . Y V0The number of vertices in a graph. Complexity: O(1) time.  vertexCount H == 0 vertexCount (I# x) == 1 vertexCount == # . X W-The number of edges in a graph. Complexity: O(n) time.  edgeCount H == 0 edgeCount (I x) == 0 edgeCount (J# x y) == 1 edgeCount == # . Y X;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList H == [] vertexList (I x) == [x] vertexList . M == "# . "$ Y2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList H == [] edgeList (I x) == [] edgeList (J x y) == [(x,y)] edgeList (b' 2 [3,1]) == [(2,1), (2,3)] edgeList . N == "# . "$ edgeList . j == "$ . map %& . edgeList Z The sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory. adjacencyList H$ == [] adjacencyList (I) x) == [(x, [])] adjacencyList (J5 1 2) == [(1, [2]), (2, [])] adjacencyList (b1 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] Q . adjacencyList == id [3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexSet H == Set.& vertexSet . I == Set.' vertexSet . M == Set.$ vertexSet . ` == Set.$ \0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet H == Set.& edgeSet (I x) == Set.& edgeSet (J x y) == Set.' (x,y) edgeSet . N == Set.$ ]The postset (here ] ) of a vertex is the set of its direct successors.  postSet x H == Set.& postSet x (I x) == Set.& postSet x (J x y) == Set.$ [y] postSet 2 (J 1 2) == Set.& ^The path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] == H path [x] == I x path [x,y] == J x y path . ( == j . path _The circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] == H circuit [x] == J x x circuit [x,y] == N [(x,y), (y,x)] circuit . ( == j . circuit `The clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique [] == H clique [x] == I x clique [x,y] == J x y clique [x,y,z] == N, [(x,y), (x,z), (y,z)] clique (xs ++ ys) == L" (clique xs) (clique ys) clique . ( == j . clique aThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique [] [] == H biclique [x] [] == I x biclique [] [y] == I y biclique [x1,x2] [y1,y2] == NB [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == L (M xs) (M ys) bThe starG 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 [] == I x star x [y] == J x y star x [y,z] == N [(x,y), (x,z)] star x ys == L (I x) (M ys) cThe star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] == I x starTranspose x [y] == J y x starTranspose x [y,z] == N) [(y,x), (z,x)] starTranspose x ys == L (M ys) (I x) starTranspose x ys == j (b x ys) dThe  tree graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. <tree (Node x []) == I? x tree (Node x [Node y [Node z []]]) == ^E [x,y,z] tree (Node x [Node y [], Node z []]) == bE x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == N [(1,2), (1,3), (3,4), (3,5)] eThe  forest graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. >forest [] == H? forest [x] == dA x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == NU [(1,2), (1,3), (4,5)] forest == O . map d f1Remove a vertex from a given graph. Complexity:  O(n*log(n)) time. removeVertex x (I x) == H removeVertex 1 (I 2) == I 2 removeVertex x (J x x) == H removeVertex 1 (J 1 2) == I5 2 removeVertex x . removeVertex x == removeVertex x g0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y (J x y) == MK [x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . f x == fa x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 h The function h 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 (I x) == I# y replaceVertex x y == i (== x) y iNMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))* time, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == hY x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 j&Transpose a given graph. Complexity:  O(m * log(n)) time, O(n + m) memory.  transpose H == H transpose (I x) == I x transpose (J x y) == J! y x transpose . transpose == id Y . transpose == "$ . map %& . Y kVTransform 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 H == H gmap f (I x) == I (f x) gmap f (J x y) == JG (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) lConstruct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(m)) time, assuming that the predicate takes O(1) to be evaluated. @induce (const True ) x == x induce (const False) x == H induce (/= x) == f< x induce p . induce q == induce (\x -> p x && q x) R (induce p x) x == True m Compute the depth-first search forest of a graph. e (dfsForest $ J 1 1) == I 1 e (dfsForest $ J 1 2) == J 1 2 e (dfsForest $ J 2 1) == M [1, 2] R (e& $ dfsForest x) x == True dfsForest . e, . dfsForest == dfsForest dfsForest (M- vs) == map (\v -> Node v []) ("# $ "$ vs) n (X x) x == dfsForest x dfsForest $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 3 , subForest = [ Node { rootLabel = 4 , subForest = [] }]}] n 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. e (dfsForestFrom [1] $ J 1 1) == I 1 e (dfsForestFrom [1] $ J 1 2) == J 1 2 e (dfsForestFrom [2] $ J 1 2) == I 2 e (dfsForestFrom [3] $ J 1 2) == H e (dfsForestFrom [2, 1] $ J 1 2) == M [1, 2] R (e0 $ dfsForestFrom vs x) x == True dfsForestFrom (X x) x == m! x dfsForestFrom vs (M! vs) == map (\v -> Node v []) ("# vs) dfsForestFrom [] x == [] dfsForestFrom [1, 4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] } , Node { rootLabel = 4 , subForest = [] }] o,Compute the list of vertices visited by the depth-first searchF in a graph, when searching from each of the given vertices in order.  dfs [1] $ J( 1 1 == [1] dfs [1] $ J+ 1 2 == [1, 2] dfs [2] $ J( 1 2 == [2] dfs [3] $ J' 1 2 == [] dfs [1, 2] $ J+ 1 2 == [1, 2] dfs [2, 1] $ J{ 1 2 == [2, 1] dfs [] $ x == [] dfs [1, 4] $ 3 * (1 + 4) * (1 + 5) == [1, 5, 4] R (M $ dfs vs x) x == True p Compute the topological sort of a graph or return Nothing if the graph is cyclic. ntopSort (1 * 2 + 3 * 1) == Just [3,1,2] topSort (1 * 2 + 2 * 1) == Nothing fmap (flip q x) (topSort x) /= Just False q-Check if a given list of vertices is a valid topological sort of a graph. isTopSort [3, 1, 2] (1 * 2 + 3 * 1) == True isTopSort [1, 2, 3] (1 * 2 + 3 * 1) == False isTopSort [] (1 * 2 + 3 * 1) == False isTopSort [] H( == True isTopSort [x] (I& x) == True isTopSort [x] (J x x) == False r Compute the  condensation1 of a graph, where each vertex corresponds to a strongly-connected component of the original graph. scc H == H scc (I x) == I (Set.' x) scc (J x y) == J (Set.' x) (Set.' y) scc (_ (1:xs)) == J (Set.$ (1:xs)) (Set.$$ (1:xs)) scc (3 * 1 * 4 * 1 * 5) == N [ (Set.$ [1,4], Set.$0 [1,4]) , (Set.$ [1,4], Set.$0 [5] ) , (Set.$ [3] , Set.$0 [1,4]) , (Set.$ [3] , Set.$ [5] )] -<>HIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr.<>>HIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTVq'sThe so type class captures data types that can be converted to polymorphic graph expressions. The conversion method t semantically acts as the identity on graph data structures, but allows to convert graphs between different data representations.  toGraph (g ::   a ) ::   a == g  (toGraph (1 * 2 ::   Int) ::  ' Int) == "edge 1 2" u The class of preorder graphs( that are both reflexive and transitive.v 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 * zpBy repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction.w 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 xoNote that by applying the axiom in the reverse direction, one can always remove all self-loops resulting in an irreflexive graphR. This type class can therefore be also used in the context of irreflexive graphs.x The class of undirected graphs- that satisfy the following additional axiom.z is commutative: x * y == y * xyTThe core type class for constructing algebraic graphs is defined by introducing the z 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 yY type class is characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for | and z, respectively.| is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + zz is associative and has  as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * zz distributes over |: 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * zz can be decomposed: "x * y * z == x * y + x * z + y * zIThe 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 z: -x * y + x + y == x * y x * x * x == x * xThe core type class y, corresponds to unlabelled directed graphs. x, w, v and u? graphs can be obtained by extending the minimal set of axioms.DWhen 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 y expression.zConnect two graphs.{FConstruct the graph comprising a single isolated vertex. An alias for *.|!Overlay two graphs. An alias for ..};Construct the graph comprising a single edge. Complexity: O(1) time, memory and size. edge x y == z ({ x) ({ y)  (edge 1 1) == 1  (edge 1 2) == 2 ~OConstruct 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  x . vertices == " x  . vertices == # . "#  . vertices == Set.$ 7Construct 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 -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 == %  -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] == z x y connects ==  z   . connects == %  The ' 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 gThe 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) (z x y) == True isSubgraphOf ( xs) ( xs) == True 2Check if a graph is empty. A convenient alias for /. Complexity: O(s) time. isEmpty ( == True isEmpty (|  ) == True isEmpty ({' x) == False isEmpty ( x $ { x) == True ACheck if a graph contains a given vertex. A convenient alias for ". Complexity: O(s) time.  hasVertex x " == False hasVertex x ({ x) == True hasVertex 1 ({! 2) == False hasVertex x .  x == const False 5Check 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 0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount  == 0 vertexCount ({# x) == 1 vertexCount == # .  ;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList  == [] vertexList ({ x) == [x] vertexList . ~ == "# . "$ 3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet  == Set.& vertexSet . { == Set.' vertexSet . ~ == Set.$ vertexSet .  == Set.$ +The set of vertices of a given graph. Like 3 but specialised for graphs with vertices of type 0. Complexity:  O(s * log(n)) time and O(n) memory.  vertexIntSet  == IntSet.1 vertexIntSet . { == IntSet.2 vertexIntSet . ~ == IntSet.3 vertexIntSet .  == IntSet.3 The 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 The 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)] The 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) == z (clique xs) (clique ys) The 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] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == z (~ xs) (~ ys) The starG 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 == z ({ x) (~ ys) The star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] == { x starTranspose x [y] == } y x starTranspose x [y,z] == ) [(y,x), (z,x)] starTranspose x ys == z (~ ys) ({( x) starTranspose x ys == transpose ( x ys) The  tree graph constructed from a given  data structure. Complexity: O(T) time, memory and size, where TJ is the size of the given tree (i.e. the number of vertices in the tree). <tree (Node x []) == {? x tree (Node x [Node y [Node z []]]) == E [x,y,z] tree (Node x [Node y [], Node z []]) == E x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) ==  [(1,2), (1,3), (3,4), (3,5)] The  forest graph constructed from a given  data structure. Complexity: O(F) time, memory and size, where FN is the size of the given forest (i.e. the number of vertices in the forest). >forest [] == ? forest [x] == A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == U [(1,2), (1,3), (4,5)] forest ==  . map   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')) ]  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')) ]  Construct a De Bruijn graphV 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] == Y [ ([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  (deBruijn n xs) == (# $ "# xs)^n n > 0 ==>  edgeCount (deBruijn n xs) == (# $ "# xs)^(n + 1) Construct 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 O(1) to be evaluated. @induce (const True ) x == x induce (const False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True 1Remove 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  The function  x y replaces vertex x with vertex y in a given y. 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 NMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 PSplit a vertex into a list of vertices with the same connectivity. Complexity:  O(s + k * L) time, memory and size, where kC is the number of occurrences of the vertex in the expression and L" is the length of the given list. %splitVertex x [] == P x splitVertex x [x] == id splitVertex x [y] == < x y splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)  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')) ] LUp to an isomorphism between the resulting vertex types, this operation is  commutative,  associative,  distributes over |, has singleton graphs as  identities and  as the annihilating zero. Below ~~5 stands for the equality up to an isomorphism, e.g.  (x, ()) ~~ x. Qbox 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) ==  x *  y  edgeCount (box x y) <=  x *  edgeCount y +  edgeCount x *  y )stuvwxyz{|}~)yz{|xwvu}~ststyz(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone <FKNTV D encapsulates King-Launchbury graphs, which are implemented in the  Data.Graph module of the  containers library. 2Note: this data structure is for internal use only.If mkGraphKL (adjacencyMap g) == h then the following holds: map ( h) ( $ % h) ==  g map (\(x, y) -> ( h x,  h y)) ( $  h) ==  g =Array-based graph representation (King and Launchbury, 1995). A mapping of Data.Graph.Vertex to vertices of type Int. A mapping from vertices of type Int to Data.Graph.Vertex . Returns % if the argument is not in the graph.The X 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 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))The  ? instance is defined using basic graph construction primitives: lshow (empty :: IntAdjacencyMap Int) == "empty" show (1 :: IntAdjacencyMap Int) == "vertex 1" show (1 + 2 :: IntAdjacencyMap Int) == "vertices [1,2]" show (1 * 2 :: IntAdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: IntAdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: IntAdjacencyMap 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 * zIThe 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 * xDWhen specifying the time and memory complexity of graph algorithms, n and mI will denote the number of vertices and edges in the graph, respectively.The  adjacency mapN of the graph: each vertex is associated with a set of its direct successors.(Cached King-Launchbury representation. )Note: this field is for internal use only. Construct an  AdjacencyMapg from a map of successor sets and (lazily) compute the corresponding King-Launchbury representation. ,Note: this function is for internal use only.Check if 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. ,Note: this function is for internal use only.  consistent & == True consistent ($ x) == True consistent (# x y) == True consistent (# x y) == True consistent (& x y) == True consistent (% xs) == True consistent ( % xs ys) == True consistent (! xs) == True Build  from a map of successor sets. ,Note: this function is for internal use only. (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV|w*Construct the  empty graph. Complexity: O(1) time and memory.  empty == True  x empty == False  empty == 0  empty == 0 Construct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.  (vertex x) == False  x (vertex x) == True  (vertex x) == 1  (vertex x) == 0 Construct the graph comprising  a single edge. Complexity: O(1) time, memory. edge x y ==  ( x) ( y)  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 Overlay\ 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 ConnectA 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 OConstruct 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 == IntSet.3 7Construct 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 == "# . "$ -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 == %  -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 == %  7Construct a graph from an adjacency list. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 9fromAdjacencyList [] == : fromAdjacencyList [(x, [])] == < x fromAdjacencyList [(x, [y])] ==  x y fromAdjacencyList .  == id O (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys) The ' 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 (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 7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x .  x == const False 5Check 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 . 4 x y == const False hasEdge x y == " (x,y) .  0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (# x) == 1 vertexCount == # .  -The number of edges in a graph. Complexity: O(n) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount == # .  ;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  == "# . "$ 2The 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 .  == "$ . map %& . edgeList  The sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory. adjacencyList $ == [] adjacencyList () x) == [(x, [])] adjacencyList (5 1 2) == [(1, [2]), (2, [])] adjacencyList (1 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]  . adjacencyList == id 3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexIntSet  == IntSet.1 vertexIntSet .  == IntSet.2 vertexIntSet .  == IntSet.3 vertexIntSet .  == IntSet.3 0The 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.$ The postset (here  ) of a vertex is the set of its direct successors.  postIntSet x  == IntSet.1 postIntSet x ( x) == IntSet.1 postIntSet x ( x y) == IntSet.3 [y] postIntSet 2 ( 1 2) == IntSet.1 The 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 The 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 The 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 The 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] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) The starG 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) The star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] ==  x starTranspose x [y] ==  y x starTranspose x [y,z] == ) [(y,x), (z,x)] starTranspose x ys ==  ( ys) ( x) starTranspose x ys ==  ( x ys) The  tree graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. <tree (Node x []) == ? x tree (Node x [Node y [Node z []]]) == E [x,y,z] tree (Node x [Node y [], Node z []]) == E x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) ==  [(1,2), (1,3), (3,4), (3,5)] The  forest graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. >forest [] == ? forest [x] == A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == U [(1,2), (1,3), (4,5)] forest ==  . map  1Remove 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 0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y ( x y) == K [x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x == a x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2  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 NMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))* time, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 &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 == "$ . map %& .  VTransform 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) == G (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) Construct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(m)) time, assuming that the predicate takes O(1) to be evaluated. @induce (const True ) x == x induce (const False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True  Compute the depth-first search forest of a graph.  (dfsForest $  1 1) ==  1  (dfsForest $  1 2) ==  1 2  (dfsForest $  2 1) ==  [1, 2]  (& $ dfsForest x) x == True dfsForest . , . dfsForest == dfsForest dfsForest (- vs) == map (\v -> Node v []) ("# $ "$ vs)  ( x) x == dfsForest x dfsForest $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 3 , subForest = [ Node { rootLabel = 4 , subForest = [] }]}]  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 [1] $  1 1) ==  1  (dfsForestFrom [1] $  1 2) ==  1 2  (dfsForestFrom [2] $  1 2) ==  2  (dfsForestFrom [3] $  1 2) ==   (dfsForestFrom [2, 1] $  1 2) ==  [1, 2]  (0 $ dfsForestFrom vs x) x == True dfsForestFrom ( x) x == ! x dfsForestFrom vs (! vs) == map (\v -> Node v []) ("# vs) dfsForestFrom [] x == [] dfsForestFrom [1, 4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] } , Node { rootLabel = 4 , subForest = [] }] ,Compute the list of vertices visited by the depth-first searchF in a graph, when searching from each of the given vertices in order.  dfs [1] $ ( 1 1 == [1] dfs [1] $ + 1 2 == [1, 2] dfs [2] $ ( 1 2 == [2] dfs [3] $ ' 1 2 == [] dfs [1, 2] $ + 1 2 == [1, 2] dfs [2, 1] $ { 1 2 == [2, 1] dfs [] $ x == [] dfs [1, 4] $ 3 * (1 + 4) * (1 + 5) == [1, 5, 4]  ( $ dfs vs x) x == True  Compute the topological sort of a graph or return Nothing if the graph is cyclic. ntopSort (1 * 2 + 3 * 1) == Just [3,1,2] topSort (1 * 2 + 2 * 1) == Nothing fmap (flip  x) (topSort x) /= Just False -Check if a given list of vertices is a valid topological sort of a graph. isTopSort [3, 1, 2] (1 * 2 + 3 * 1) == True isTopSort [1, 2, 3] (1 * 2 + 3 * 1) == False isTopSort [] (1 * 2 + 3 * 1) == False isTopSort [] ( == True isTopSort [x] (& x) == True isTopSort [x] ( x x) == False ,-(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV3 The focus of a graph expression is a flattened represenentation of the subgraph under focus, its context, as well as the list of all encountered vertices. See  ( for a use-case example.4.All vertices (leaves) of the graph expression.54True if focus on the specified subgraph is obtained.6!Inputs into the focused subgraph.7$Outputs out of the focused subgraph.The context of a subgraph comprises the input and output vertices outside the subgraph that are connected to the vertices inside the subgraph. An abstract list data type with O(1)N time concatenation (the current implementation uses difference lists). Here a is the type of list elements.  a is a 8: 9G 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.=Focus on the empty graph.>iFocus on the graph with a single vertex, given a predicate indicating whether the vertex is of interest.?Overlay two foci.@Connect two foci.!Extract the context from a graph  . Returns Nothing% if the focus could not be obtained. on a specified subgraph. 4567A(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV $An abstract document data type with O(1)N time concatenation (the current implementation uses difference lists). Here s? is the type of abstract symbols or strings (text or binary).  s is a 8 , therefore 9O corresponds to the empty document and two documents can be concatenated with : (or operator )*Z). Documents comprising a single symbol or string can be constructed using the function Q. Alternatively, you can construct documents as string literals, e.g. simply as "alga", by using the OverloadedStringsC GHC extension. To extract the document contents use the function . See some examples below.>Construct a document comprising a single symbol or string. If s is an instance of class B, then documents of type  sR can be constructed directly from string literals (see the second example below). literal "Hello, " )*{ literal "World!" == literal "Hello, World!" literal "I am just a string literal" == "I am just a string literal" literal 9 == 9 # . literal == C literal .  == C CRender the document as a single string. An inverse of the function . render ( "al" )*  "ga") :: (B s, 8 s) => s render ( "al" )*  "ga") == "alga" render 9 == 9 render .  == C " . render == C Concatenate two documents, separated by a single space, unless one of the documents is empty. The operator <+> is associative with identity 9. x <+> 9 == x 9c <+> x == x x <+> (y <+> z) == (x <+> y) <+> z "name" <+> "surname" == "name surname" #Wrap a document in square brackets. "brackets "i" == "[i]" brackets 9 == "[]" #Wrap a document into double quotes. YdoubleQuotes "/path/with spaces" == "\"/path/with spaces\"" doubleQuotes (doubleQuotes 9) == "\"\"\"\"" /Prepend a given number of spaces to a document. indent 0 == C indent 1 9 == " " KConcatenate documents after appending a terminating newline symbol to each. !unlines [] == 9 unlines [9L] == "\n" unlines ["title", "subtitle"] == "title\nsubtitle\n" Export a graph into a document given two functions that construct documents for individual vertices and edges. The order of export is: vertices, sorted by D a, and then edges, sorted by D (a, a). For example:  vDoc x =  ( x) <> "\n" eDoc x y =  ( x) <> " -> " <>  ( y) <> "\n" > putStrLn $ ( $ export vDoc eDoc (1 + 2 * (3 + 4) ::   Int) 1 2 3 4 2 -> 3 2 -> 4 E7 (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone "#<FKNTV The record  a sL 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.). Most fields can be empty. The only field that has no obvious default value is !, which holds a function of type a -> s< to compute vertex names. See the example for the function .Name of the graph.8Preamble is added at the beginning of the DOT file body.Graph style, e.g. ["bgcolor" := "azure"].Default vertex style, e.g. ["shape" := "diamond"].Default edge style, e.g. ["style" := "dashed"].Compute a vertex name. Attributes of a specific vertex.Attributes of a specific edge.3An attribute is just a key-value pair, for example "shape" := "box"L. Attributes are used to specify the style of graph elements during export.MDefault style for exporting graphs. All style settings are empty except for ), which is provided as the only argument.6Default style for exporting graphs whose vertices are  0-able. All style settings are empty except for , which is computed from . defaultStyleViaShow =  (F . ) "Export a graph with a given style. For example:  style ::  Int String style =  { ! = "Example" , 4 = " // This is an example\n" , = = ["label" := "Example", "labelloc" := "top"] ,  = ["shape" := "circle"] ,  = 9 ,  = \x -> "v" ++  x , ) = \x -> ["color" := "blue" | G x ] , + = \x y -> ["style" := "dashed" | G= (x * y)] } > 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" } DExport a graph whose vertices are represented simply by their names. For example: > Text.putStrLn $ exportAsIs (+ ["a", "b", "c"] :: ,M Text) digraph { "a" "b" "c" "a" -> "b" "b" -> "c" "c" -> "a" } Export a graph using the . For example: /> putStrLn $ exportViaShow (1 + 2 * (3 + 4) ::  E Int) digraph { "1" "2" "3" "4" "2" -> "3" "2" -> "4" }   (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone <FKNTV The  # data type represents a graph as a binary relation. We define a ; instance as a convenient notation for working with graphs: 0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))The  ? instance is defined using basic graph construction primitives: Bshow (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 * zIThe 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 * xDWhen specifying the time and memory complexity of graph algorithms, n and mI will denote the number of vertices and edges in the graph, respectively. The domain of the relation. &The set of pairs of elements that are related<. It is guaranteed that each element belongs to the domain. +Compute the Cartesian product of two sets. ,Note: this function is for internal use only.hCheck if 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. ,Note: this function is for internal use only.  consistent  & == True consistent ( $ x) == True consistent ( # x y) == True consistent ( # x y) == True consistent ( & x y) == True consistent ( % xs) == True consistent ( % xs ys) == True consistent ( ! xs) == True :The set of elements that appear in a given set of pairs. ,Note: this function is for internal use only.              (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTVҞ+Construct the  empty graph. Complexity: O(1) time and memory.   empty == True ! x empty == False # empty == 0 $ empty == 0 Construct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.   (vertex x) == False ! x (vertex x) == True # (vertex x) == 1 $ (vertex x) == 0 Construct the graph comprising  a single edge. Complexity: O(1) time, memory and size. edge x y ==  ( x) ( y) " x y (edge x y) == True $ (edge x y) == 1 # (edge 1 1) == 1 # (edge 1 2) == 2 Overlay\ 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 ConnectA 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 OConstruct 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.$ 7Construct 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 == # . "# -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 == %   -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 == %   7Construct a graph from an adjacency list. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 9fromAdjacencyList [] == : fromAdjacencyList [(x, [])] == < x fromAdjacencyList [(x, [y])] ==  x y O (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys) The ' 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  +Check if a relation is empty. Complexity: O(1) time. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty (4 x $  x) == True isEmpty (5 x y $  x y) == False !7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x . 4 x == const False "5Check 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 . 54 x y == const False hasEdge x y == " (x,y) . & #0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (# x) == 1 vertexCount == # . % $-The number of edges in a graph. Complexity: O(1) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount == # . & %;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  == "# . "$ &2The 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 (0' 2 [3,1]) == [(2,1), (2,3)] edgeList .  == "# . "$ edgeList . 8 == "$ . map H . edgeList '3The set of vertices of a given graph. Complexity: O(1) time.  vertexSet  == Set.& vertexSet .  == Set.' vertexSet .  == Set.$ vertexSet . . == Set.$ (+The set of vertices of a given graph. Like '3 but specialised for graphs with vertices of type 0. Complexity: O(n) time.  vertexIntSet  == IntSet.1 vertexIntSet .  == IntSet.2 vertexIntSet .  == IntSet.3 vertexIntSet . . == IntSet.3 )0The set of edges of a given graph. Complexity: O(1) time. edgeSet  == Set.& edgeSet ( x) == Set.& edgeSet ( x y) == Set.' (x,y) edgeSet .  == Set.$ *The preset (here *) of an element x7 is the set of elements that are related to it on the left, i.e. preSet x == { a | aRx }E. 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] +The postset (here +) of an element x7 is the set of elements that are related to it on the right, i.e. postSet x == { a | xRa }E. 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.& ,The 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 . ( == 8 . path -The 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 . ( == 8 . circuit .The 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 . ( == 8 . clique /The 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] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) 0The starG 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) 1The star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] ==  x starTranspose x [y] ==  y x starTranspose x [y,z] == ) [(y,x), (z,x)] starTranspose x ys ==  ( ys) ( x) starTranspose x ys == 8 (0 x ys) 2The  tree graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. <tree (Node x []) == ? x tree (Node x [Node y [Node z []]]) == ,E [x,y,z] tree (Node x [Node y [], Node z []]) == 0E x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) ==  [(1,2), (1,3), (3,4), (3,5)] 3The  forest graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. >forest [] == ? forest [x] == 2A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == U [(1,2), (1,3), (4,5)] forest ==  . map 2 41Remove 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 50Remove an edge from a given graph. Complexity:  O(log(m)) time. removeEdge x y (, x y) == K [x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . 4 x == 4a x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 6 The function 6 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 == 7 (== x) y 7NMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))* time, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == 6Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 8&Transpose a given graph. Complexity:  O(m * log(m)) time.  transpose  ==  transpose ( x) ==  x transpose ( x y) == ! y x transpose . transpose == id & . transpose == "$ . map H . & 9VTransform 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) == G (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) :Construct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(m)) time, assuming that the predicate takes O(1) to be evaluated. @induce (const True ) x == x induce (const False) x ==  induce (/= x) == 4< x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True ;Compose two relations: R = ; Q P. Two elements x and y. are related in the resulting relation, i.e. xRy, if there exists an element z , such that xPz and zQy-. This is an associative operation which has  as the annihilating zero. Complexity: O(n * m * log(m)) time and O(n + m) memory. compose  x ==  compose x  == O compose x (compose y z) == compose (compose x y) z compose ( y z) ( x y) ==  x z compose (, [1..5]) (, [1..5]) ==  [(1,3),(2,4),(3,5)] compose (- [1..5]) (- [1..5]) == - [1,3,5,2,4] < Compute the reflexive closure of a  . Complexity:  O(n * log(m)) time. reflexiveClosure  ==  reflexiveClosure ( x) ==  x x = Compute the symmetric closure of a  . Complexity:  O(m * log(m)) time. symmetricClosure  ==  symmetricClosure ( x) ==  x symmetricClosure ( x y) ==  [(x, y), (y, x)] > Compute the transitive closure of a  . Complexity: O(n * m * log(n) * log(m)) time. transitiveClosure  ==  transitiveClosure ( x) ==  x transitiveClosure (, $ "# xs) == . ("# xs) ? Compute the preorder closure of a  . Complexity: O(n * m * log(m)) time. preorderClosure  ==  preorderClosure ( x) ==  x x preorderClosure (, $ "# xs) == < (. $ "# xs) .    !"#$%&'()*+,-./0123456789:;<=>?0      !"#$%&'()*+,-./0123456789:;<=>? (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNQTV%@The @V data type is the Boehm-Berarducci encoding of the core graph construction primitives A, B, D and E. We define a ; instance as a convenient notation for working with graphs: 0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))The  ? instance is defined using basic graph construction primitives: *show (empty :: Fold Int) == "empty" show (1 :: Fold Int) == "vertex 1" show (1 + 2 :: Fold Int) == "vertices [1,2]" show (1 * 2 :: Fold Int) == "edge 1 2" show (1 * 2 * 3 :: Fold Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Fold Int) == "overlay (vertex 3) (edge 1 2)"The !- instance is currently implemented using the < as the canonical graph representation. and satisfies all axioms of algebraic graphs:D is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + zE is associative and has A as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * zE distributes over D: 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * zE can be decomposed: "x * y * z == x * y + x * z + y * zIThe following useful theorems can be proved from the above set of axioms.D has A# as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of E: -x * y + x + y == x * y x * x * x == x * xDWhen 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 graph expression. For example, if g is a @ then n, m and s can be computed as follows: n == O g m == P g s == L g Note that L is slightly different from the # method of the <* type class, as the latter does not count A leaves of the expression: # A == 0 L A == 1 # (B x) == 1 L (B x) == 1 # (A + A) == 0 L (A + A) == 2The L. of any graph is positive, and the difference (L g - # g)- corresponds to the number of occurrences of A in an expression g. 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.AConstruct the  empty graph. Complexity: O(1) time, memory and size. K empty == True M x empty == False O empty == 0 P empty == 0 L empty == 1 BConstruct the graph comprising a single isolated vertex. Complexity: O(1) time, memory and size. K (vertex x) == False M x (vertex x) == True O (vertex x) == 1 P (vertex x) == 0 L (vertex x) == 1 CConstruct the graph comprising  a single edge. Complexity: O(1) time, memory and size. edge x y == E (B x) (B y) N x y (edge x y) == True P (edge x y) == 1 O (edge 1 1) == 1 O (edge 1 2) == 2 DOverlay\ two graphs. This is a commutative, associative and idempotent operation with the identity A. Complexity: O(1) time and memory,  O(s1 + s2) size. K (overlay x y) == K x && K y M z (overlay x y) == M z x || M z y O (overlay x y) >= O x O (overlay x y) <= O x + O y P (overlay x y) >= P x P (overlay x y) <= P x + P y L (overlay x y) == L x + L y O (overlay 1 2) == 2 P (overlay 1 2) == 0 EConnectA two graphs. This is an associative operation with the identity A, which distributes over D1 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). K (connect x y) == K x && K y M z (connect x y) == M z x || M z y O (connect x y) >= O x O (connect x y) <= O x + O y P (connect x y) >= P x P (connect x y) >= P y P (connect x y) >= O x * O y P (connect x y) <= O x * O y + P x + P y L (connect x y) == L x + L y O (connect 1 2) == 2 P (connect 1 2) == 1 FOConstruct 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 [] == A vertices [x] == B x M x . vertices == " x O . vertices == # . "# S . vertices == Set.$ G7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] == A edges [(x,y)] == C x y P . edges == # . "# H-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 [] == A/ overlays [x] == x overlays [x,y] == D x y overlays ==  D A K . overlays == % K I-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 [] == A/ connects [x] == x connects [x,y] == E x y connects ==  E A K . connects == % K J2Generalised graph 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)D applications of given functions. As an example, the complexity of L is O(s) , since all functions have cost O(1). foldg A B D E == id foldg A B D (flip E) == ^5 foldg [] return (++) (++) == ;5 foldg 0 (const 1) (+) (+) == #5 foldg 1 (const 1) (+) (+) == L5 foldg True (const False) (&&) (&&) == K K2Check if a graph is empty. A convenient alias for /. Complexity: O(s) time. isEmpty A( == True isEmpty (D A A) == True isEmpty (B' x) == False isEmpty (Y x $ B x) == True isEmpty (Z x y $ C x y) == False LThe sizeD of a graph, i.e. the number of leaves of the expression including A leaves. Complexity: O(s) time. size A == 1 size (B x) == 1 size (D x y) == size x + size y size (EG x y) == size x + size y size x >= 1 size x >= O x MACheck if a graph contains a given vertex. A convenient alias for ". Complexity: O(s) time.  hasVertex x A" == False hasVertex x (B x) == True hasVertex 1 (B! 2) == False hasVertex x . Y x == const False N5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y A" == False hasEdge x y (B z) == False hasEdge x y (C" x y) == True hasEdge x y . Z4 x y == const False hasEdge x y == " (x,y) . R O0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount A == 0 vertexCount (B# x) == 1 vertexCount == # . Q P-The number of edges in a graph. Complexity: O(s + m * log(m))% time. Note that the number of edges mB of a graph can be quadratic with respect to the expression size s.  edgeCount A == 0 edgeCount (B x) == 0 edgeCount (C# x y) == 1 edgeCount == # . R Q;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList A == [] vertexList (B x) == [x] vertexList . F == "# . "$ R2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges mA of a graph can be quadratic with respect to the expression size s.  edgeList A == [] edgeList (B x) == [] edgeList (C x y) == [(x,y)] edgeList (star' 2 [3,1]) == [(2,1), (2,3)] edgeList . G == "# . "$ edgeList . ^ == "$ . map %& . edgeList S3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet A == Set.& vertexSet . B == Set.' vertexSet . F == Set.$ vertexSet . clique == Set.$ T+The set of vertices of a given graph. Like S3 but specialised for graphs with vertices of type 0. Complexity:  O(s * log(n)) time and O(n) memory.  vertexIntSet A == IntSet.1 vertexIntSet . B == IntSet.2 vertexIntSet . F == IntSet.3 vertexIntSet . clique == IntSet.3 U0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory. edgeSet A == Set.& edgeSet (B x) == Set.& edgeSet (C x y) == Set.' (x,y) edgeSet . G == Set.$ V 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 [] == A mesh [] ys == A mesh [x] [y] == B (x, y) mesh xs ys == c (path xs) (path ys) mesh [1..3] "ab" == G [ ((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')) ] W 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 [] == A torus [] ys == A torus [x] [y] == C# (x, y) (x, y) torus xs ys == c (circuit xs) (circuit ys) torus [1,2] "ab" == G [ ((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')) ] X Construct a De Bruijn graphV 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 == C0 [] [] n > 0 ==> deBruijn n [] == A* deBruijn 1 [0,1] == GY [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == C4 "00" "00" deBruijn 2 "01" == G [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ] ^ (deBruijn n xs) == _ ( $ deBruijn n xs O (deBruijn n xs) == (# $ "# xs)^n n > 0 ==> P (deBruijn n xs) == (# $ "# xs)^(n + 1) Y1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x (B x) == A removeVertex 1 (B 2) == B 2 removeVertex x (C x x) == A removeVertex 1 (C 1 2) == B5 2 removeVertex x . removeVertex x == removeVertex x Z0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y (C x y) == FK [x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . Y x == Ya x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 L# (removeEdge x y z) <= 3 * L z I&Filter vertices in a subgraph context.[ The function [ x y replaces vertex x with vertex y" in a given graph expression. If y already exists, x and y will be merged. Complexity: O(s) time, memory and size. 6replaceVertex x x == id replaceVertex x y (B x) == B# y replaceVertex x y == \ (== x) y \NMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == [Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 ]PSplit a vertex into a list of vertices with the same connectivity. Complexity:  O(s + k * L) time, memory and size, where kC is the number of occurrences of the vertex in the expression and L" is the length of the given list. %splitVertex x [] == YP x splitVertex x [x] == id splitVertex x [y] == [< x y splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3) ^&Transpose a given graph. Complexity: O(s) time, memory and size.  transpose A == A transpose (B x) == B x transpose (C x y) == C, y x transpose . transpose == id transpose (c x y) == c (transpose x) (transpose y) R . transpose == "$ . map %& . R _\Transform a given graph by applying a function to each of its vertices. This is similar to )2 but can be used with non-fully-parametric graphs. gmap f A == A gmap f (B x) == B (f x) gmap f (C x y) == CG (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) `oTransform a given graph by substituting each of its vertices with a subgraph. This is similar to Monad's bind J3 but can be used with non-fully-parametric graphs. bind A f == A bind (B x) f == f x bind (C x y) f == E (f x) (f y) bind (F xs) f == H (K f xs) bind x (const A) == A bind x BA == x bind (bind x f) g == bind x (\y -> bind (f y) g) aConstruct 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 O(1) to be evaluated. @induce (const True ) x == x induce (const False) x == A induce (/= x) == Y< x induce p . induce q == induce (\x -> p x && q x)  isSubgraphOf (induce p x) x == True bVSimplify a graph expression. Semantically, this is the identity function, but it simplifies a given polymorphic graph expression according to the laws of the algebra. The function does not compute the simplest possible expression, but uses heuristics to obtain useful simplifications in reasonable time. Complexity: the function performs O(s) graph comparisons. It is guaranteed that the size of the result does not exceed the size of the given expression. Below the operator ~> denotes the is simplified to relation. simplify == id L (simplify x) <= L x simplify A ~> Aq simplify 1 ~> 1 simplify (1 + 1) ~> 1 simplify (1 + 2 + 1) ~> 1 + 2 simplify (1 * 1 * 1) ~> 1 * 1 c 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 (path [0,1]) (path "ab") == G [ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((0,'b'), (1,'b')) , ((1,'a'), (1,'b')) ] LUp to an isomorphism between the resulting vertex types, this operation is  commutative,  associative,  distributes over D, has singleton graphs as  identities and A as the annihilating zero. Below ~~5 stands for the equality up to an isomorphism, e.g.  (x, ()) ~~ x. Qbox x y ~~ box y x box x (box y z) ~~ box (box x y) z box x (D y z) == D (box x y) (box x z) box x (B ()) ~~ x box x A ~~ A ^ (box x y) == box (^ x) (^ y) O (box x y) == O x * O y P (box x y) <= O x * P y + P x * O y -@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abc-@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abc@LM (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone 345<FKNTV-rThe rI data type is a deep embedding of the core graph construction primitives w, x, z and {. We define a ; instance as a convenient notation for working with graphs: 0 == Vertex 0 1 + 2 == Overlay (Vertex 1) (Vertex 2) 1 * 2 == Connect (Vertex 1) (Vertex 2) 1 + 2 * 3 == Overlay (Vertex 1) (Connect (Vertex 2) (Vertex 3)) 1 * (2 + 3) == Connect (Vertex 1) (Overlay (Vertex 2) (Vertex 3))The !- instance is currently implemented using the < as the canonical graph representation. and satisfies all axioms of algebraic graphs:z is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z{ is associative and has w as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z{ distributes over z: 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 * zIThe following useful theorems can be proved from the above set of axioms.z has w# 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 * xDWhen 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 r expression. For example, if g is a r then n, m and s can be computed as follows: n ==  g m ==  g s ==  g Note that  is slightly different from the # method of the <* type class, as the latter does not count w leaves of the expression: # w == 0  w == 1 # (x x) == 1  (x x) == 1 # (w + w) == 0  (w + w) == 2The . of any graph is positive, and the difference ( g - # g)- corresponds to the number of occurrences of w in an expression g. Converting a r 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.wConstruct the  empty graph. An alias for the constructor s. Complexity: O(1) time, memory and size.  empty == True  x empty == False  empty == 0  empty == 0  empty == 1 xConstruct the graph comprising a single isolated vertex . An alias for the constructor t. Complexity: O(1) time, memory and size.  (vertex x) == False  x (vertex x) == True  (vertex x) == 1  (vertex x) == 0  (vertex x) == 1 yConstruct the graph comprising  a single edge. Complexity: O(1) time, memory and size. edge x y == { (x x) (x y)  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 zOverlay* two graphs. An alias for the constructor uQ. This is a commutative, associative and idempotent operation with the identity w. 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 {Connect* two graphs. An alias for the constructor v6. This is an associative operation with the identity w, which distributes over z1 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 |OConstruct 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 [] == w vertices [x] == x x  x . vertices == " x  . vertices == # . "#  . vertices == Set.$ }7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] == w edges [(x,y)] == y x y  . edges == # . "# ~-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 [] == w/ overlays [x] == x overlays [x,y] == z x y overlays ==  z w  . overlays == %  -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 [] == w/ connects [x] == x connects [x,y] == { x y connects ==  { w  . connects == %   Generalised r! folding: recursively collapse a r 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)D applications of given functions. As an example, the complexity of  is O(s) , since all functions have cost O(1). foldg w x z { == id foldg w x z (flip {) == 5 foldg [] return (++) (++) == -.5 foldg 0 (const 1) (+) (+) == -/5 foldg 1 (const 1) (+) (+) == 5 foldg True (const False) (&&) (&&) ==  The ' 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 mB of a graph can be quadratic with respect to the expression size s.  isSubgraphOf w- x == True isSubgraphOf (x x) w. == False isSubgraphOf x (z x y) == True isSubgraphOf (z x y) ({ x y) == True isSubgraphOf ( xs) ( xs) == True 7Structural equality on graph expressions. Complexity: O(s) time. * x === x == True x === x + w` == False x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False 2Check if a graph is empty. A convenient alias for /. Complexity: O(s) time. isEmpty w( == True isEmpty (z w w) == True isEmpty (x' x) == False isEmpty ( x $ x x) == True isEmpty ( x y $ y x y) == False The sizeD of a graph, i.e. the number of leaves of the expression including w leaves. Complexity: O(s) time. size w == 1 size (x x) == 1 size (z x y) == size x + size y size ({G x y) == size x + size y size x >= 1 size x >=  x ACheck if a graph contains a given vertex. A convenient alias for ". Complexity: O(s) time.  hasVertex x w" == False hasVertex x (x x) == True hasVertex 1 (x! 2) == False hasVertex x .  x == const False 5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y w" == False hasEdge x y (x z) == False hasEdge x y (y" x y) == True hasEdge x y . 4 x y == const False hasEdge x y == " (x,y) .  0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount w == 0 vertexCount (x# x) == 1 vertexCount == # .  -The number of edges in a graph. Complexity: O(s + m * log(m))% time. Note that the number of edges mB of a graph can be quadratic with respect to the expression size s.  edgeCount w == 0 edgeCount (x x) == 0 edgeCount (y# x y) == 1 edgeCount == # .  ;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList w == [] vertexList (x x) == [x] vertexList . | == "# . "$ 2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges mA of a graph can be quadratic with respect to the expression size s.  edgeList w == [] edgeList (x x) == [] edgeList (y x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList . } == "# . "$ edgeList .  == "$ . map %& . edgeList 3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet w == Set.& vertexSet . x == Set.' vertexSet . | == Set.$ vertexSet .  == Set.$ +The set of vertices of a given graph. Like 3 but specialised for graphs with vertices of type 0. Complexity:  O(s * log(n)) time and O(n) memory.  vertexIntSet w == IntSet.1 vertexIntSet . x == IntSet.2 vertexIntSet . | == IntSet.3 vertexIntSet .  == IntSet.3 0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory. edgeSet w == Set.& edgeSet (x x) == Set.& edgeSet (y x y) == Set.' (x,y) edgeSet . } == Set.$ The path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] == w path [x] == x x path [x,y] == y x y path . ( ==  . path The circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] == w circuit [x] == y x x circuit [x,y] == } [(x,y), (y,x)] circuit . ( ==  . circuit The clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] == w clique [x] == x x clique [x,y] == y x y clique [x,y,z] == }, [(x,y), (x,z), (y,z)] clique (xs ++ ys) == {" (clique xs) (clique ys) clique . ( ==  . clique The 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 [] [] == w biclique [x] [] == x x biclique [] [y] == x y biclique [x1,x2] [y1,y2] == }B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == { (| xs) (| ys) The starG 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 x star x [y] == y x y star x [y,z] == } [(x,y), (x,z)] star x ys == { (x x) (| ys) The star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] == x x starTranspose x [y] == y y x starTranspose x [y,z] == }) [(y,x), (z,x)] starTranspose x ys == { (| ys) (x x) starTranspose x ys ==  ( x ys) The  tree graph constructed from a given  data structure. Complexity: O(T) time, memory and size, where TJ is the size of the given tree (i.e. the number of vertices in the tree). <tree (Node x []) == x? x tree (Node x [Node y [Node z []]]) == E [x,y,z] tree (Node x [Node y [], Node z []]) == E x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == } [(1,2), (1,3), (3,4), (3,5)] The  forest graph constructed from a given  data structure. Complexity: O(F) time, memory and size, where FN is the size of the given forest (i.e. the number of vertices in the forest). >forest [] == w? forest [x] == A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == }U [(1,2), (1,3), (4,5)] forest == ~ . map   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 [] == w mesh [] ys == w mesh [x] [y] == x (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')) ]  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 [] == w torus [] ys == w torus [x] [y] == 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')) ]  Construct a De Bruijn graphV 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 == y0 [] [] n > 0 ==> deBruijn n [] == w* deBruijn 1 [0,1] == }Y [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == y4 "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) 1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x (x x) == w removeVertex 1 (x 2) == x 2 removeVertex x (y x x) == w removeVertex 1 (y 1 2) == x5 2 removeVertex x . removeVertex x == removeVertex x 0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y (y x y) == |K [x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x == a 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 N&Filter vertices in a subgraph context. The function  x y replaces vertex x with vertex y in a given r. 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 x) == x# y replaceVertex x y ==  (== x) y NMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 PSplit a vertex into a list of vertices with the same connectivity. Complexity:  O(s + k * L) time, memory and size, where kC is the number of occurrences of the vertex in the expression and L" is the length of the given list. %splitVertex x [] == P x splitVertex x [x] == id splitVertex x [y] == < x y splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3) &Transpose a given graph. Complexity: O(s) time, memory and size.  transpose w == w transpose (x x) == x x transpose (y x y) == y, y x transpose . transpose == id transpose ( x y) ==  (transpose x) (transpose y)  . transpose == "$ . map %& .  Construct 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 O(1) to be evaluated. @induce (const True ) x == x induce (const False) x == w induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True DSimplify 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)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 w  w simplify 1  1 simplify (1 + 1)  1 simplify (1 + 2 + 1)  1 + 2 simplify (1 * 1 * 1)  1 * 1  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')) ] LUp to an isomorphism between the resulting vertex types, this operation is  commutative,  associative,  distributes over z, has singleton graphs as  identities and w as the annihilating zero. Below ~~5 stands for the equality up to an isomorphism, e.g.  (x, ()) ~~ x. Qbox x y ~~ box y x box x (box y z) ~~ box (box x y) z box x (z y z) == z (box x y) (box x z) box x (x ()) ~~ x box x w ~~ w  (box x y) == box ( x) ( y)  (box x y) ==  x *  y  (box x y) <=  x *  y +  x *  y 0rstuvwxyz{|}~0rstuvwxyz{|}~rstuv4(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone 345<FKNTVQ*The I data type is a deep embedding of the core graph construction primitives ,  and i. As one can guess from the name, the empty graph cannot be represented using this data type. See module  Algebra.GraphK for a graph data type that allows for the construction of the empty graph. We define a ; instance as a convenient notation for working with graphs: 0 == Vertex 0 1 + 2 == Overlay (Vertex 1) (Vertex 2) 1 * 2 == Connect (Vertex 1) (Vertex 2) 1 + 2 * 3 == Overlay (Vertex 1) (Connect (Vertex 2) (Vertex 3)) 1 * (2 + 3) == Connect (Vertex 1) (Overlay (Vertex 2) (Vertex 3))Note that the O method of the " type class cannot be implemented.The !- instance is currently implemented using the < as the canonical graph representation6 and 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 * xDWhen 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 E expression, defined as the number of vertex leaves. For example, if g is a  then n, m and s can be computed as follows: n ==  g m ==  g s ==  gThe ; of any graph is positive and coincides with the result of # method of the < type class. We define O only for the consistency with the API of other graph representations, such as  Algebra.Graph. 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. Convert a r into  . Returns  if the argument is w. Complexity: O(s) time, memory and size. toNonEmptyGraph w# == Nothing toNonEmptyGraph (# x) == Just (x :: NonEmptyGraph a) Construct the graph comprising a single isolated vertex . An alias for the constructor . Complexity: O(1) time, memory and size.  x (vertex x) == True  (vertex x) == 1  (vertex x) == 0  (vertex x) == 1 Construct the graph comprising  a single edge. Complexity: O(1) time, memory and size. edge x y ==  ( x) ( y)  x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 Overlay* two graphs. An alias for the constructor M. 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 QOverlay a possibly empty graph with a non-empty graph. If the first argument is wV, 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 w x == x x /= wB ==> overlay1 x y == overlay (fromJust $ toNonEmptyGraph x) y Connect* 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 OConstruct 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 P []) ==  x  x . vertices1 == " x  . vertices1 == # . 0#  . vertices1 == Set.$ . 0. 7Construct 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) P []) ==  x y  . edges1 == 0/ . 0# -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 P [] ) == x overlays1 (x P [y]) ==  x y -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 P [] ) == x connects1 (x P [y]) ==  x y 2Generalised 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)D applications of given functions. As an example, the complexity of  is O(s) , since all functions have cost O(1). foldg1 (const 1) (+) (+) ==  foldg1 (==x) (||) (||) ==  x The ' 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 mB 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 7Structural equality on graph expressions. Complexity: O(s) time. b x === x == True x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False The sizeG 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 (G x y) == size x + size y size x >= 1 size x >=  x ACheck if a graph contains a given vertex. A convenient alias for ". Complexity: O(s) time.  hasVertex x ( x) == True hasVertex 1 ( 2) == False 5Check 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 . 4 x y == const False hasEdge x y == " (x,y) .  0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount (? x) == 1 vertexCount x >= 1 vertexCount == # .  -The number of edges in a graph. Complexity: O(s + m * log(m))% time. Note that the number of edges mB of a graph can be quadratic with respect to the expression size s.  edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount == # .  ;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList1 ( x) == x P [] vertexList1 .  == 0# . 0$ 2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges mA 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 .  == "# . "$ . 0. edgeList .  == "$ . map %& . edgeList 3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet .  == Set.' vertexSet .  == Set.$ . 0. vertexSet .  == Set.$ . 0. +The set of vertices of a given graph. Like 3 but specialised for graphs with vertices of type 0. Complexity:  O(s * log(n)) time and O(n) memory. vertexIntSet .  == IntSet.2 vertexIntSet .  == IntSet.3 . 0. vertexIntSet .  == IntSet.3 . 0. 0The 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.$ . 0. The path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.  path1 (x P [] ) ==  x path1 (x P [y]) ==  x y path1 . 01 ==  . path1 The circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.  circuit1 (x P [] ) ==  x x circuit1 (x P [y]) ==  ((x,y) P [(y,x)]) circuit1 . 01 ==  . circuit1 The clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.  clique1 (x P [] ) ==  x clique1 (x P [y] ) ==  x y clique1 (x P [y,z]) ==  ((x,y) P [(x,z), (y,z)]) clique1 (xs Q ys) == % (clique1 xs) (clique1 ys) clique1 . 01 ==  . clique1 The 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 P [x2]) (y1 P [y2]) ==  ((x1,y1) PE [(x1,y2), (x2,y1), (x2,y2)]) biclique1 xs ys ==  ( xs) ( ys) The starG 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) P [(x,z)]) The star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] ==  x starTranspose x [y] ==  y x starTranspose x [y,z] ==  ((y,x) P# [(z,x)]) starTranspose x ys ==  ( x ys) The  tree graph constructed from a given  data structure. Complexity: O(T) time, memory and size, where TJ is the size of the given tree (i.e. the number of vertices in the tree). <tree (Node x []) == ? x tree (Node x [Node y [Node z []]]) ==  (x PD [y,z]) tree (Node x [Node y [], Node z []]) == E x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) ==  ((1,2) P [(1,3), (3,4), (3,5)])  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.  mesh1 (x P []) (y P []) == + (x, y) mesh1 xs ys ==  ( xs) ( ys) mesh1 (1 P [2,3]) ('a' P "b") ==  (02) [ ((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')) ])  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.  torus1 (x P []) (y P []) == 1 (x, y) (x, y) torus1 xs ys ==  ( xs) ( ys) torus1 (1 P [2]) ('a' P "b") ==  (029 [ ((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')) ]) ,Remove a vertex from a given graph. Returns Nothing0 if the resulting graph is empty. Complexity: O(s) time, memory and size. removeVertex1 x () x) == Nothing removeVertex1 1 ( 2) == Just ( 2) removeVertex1 x (+ x x) == Nothing removeVertex1 1 ( 1 2) == Just ( 2) removeVertex1 x R$ removeVertex1 x == removeVertex1 x 0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y ( x y) ==  (x P [y]) removeEdge x y . removeEdge x y == removeEdge x y 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  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 NMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 PSplit a vertex into a list of vertices with the same connectivity. Complexity:  O(s + k * L) time, memory and size, where kC is the number of occurrences of the vertex in the expression and L" is the length of the given list. splitVertex1 x (x P, [] ) == id splitVertex1 x (y P [] ) ==  x y splitVertex1 1 (0 P) [1]) $ 1 * (2 + 3) == (0 + 1) * (2 + 3) &Transpose a given graph. Complexity: O(s) time, memory and size.  transpose ( x) ==  x transpose ( x y) == , y x transpose . transpose == id transpose ( x y) ==  (transpose x) (transpose y)  . transpose == "$ . map %& .  Construct the induced subgraph[ of a given graph by removing the vertices that do not satisfy a given predicate. Returns Nothing0 if the resulting graph is empty. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. `induce1 (const True ) x == Just x induce1 (const False) x == Nothing induce1 (/= x) ==  x induce1 p R) induce1 q == induce1 (\x -> p x && q x) DSimplify 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)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  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 ( $ 02 [0,1]) ( $ 02 "ab") ==  (023 [ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((0,'b'), (1,'b')) , ((1,'a'), (1,'b')) ]) LUp to an isomorphism between the resulting vertex types, this operation is  commutative,  associative,  distributes over , and has singleton graphs as  identities. Below ~~5 stands for the equality up to an isomorphism, e.g.  (x, ()) ~~ x. Qbox 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 --4(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone <FKNTVThe  data type represents a 5binary relation that is both reflexive and transitive$. Preorders satisfy all laws of the $ 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  C 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)]"The  data type represents a transitive binary relationF over a set of elements. Transitive relations satisfy all laws of the $ 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)]"The  data type represents a symmetric binary relationE over a set of elements. Symmetric relations satisfy all laws of the = type class and, in particular, the commutativity of connect:  x y ==  y xThe  4 instance produces symmetrically closed expressions: rshow (1 :: SymmetricRelation Int) == "vertex 1" show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"The  data type represents a reflexive binary relationE over a set of elements. Reflexive relations satisfy all laws of the $ type class and, in particular, the  self-loop axiom:   x ==   x *   xThe  2 instance produces reflexively closed expressions: xshow (1 :: ReflexiveRelation Int) == "edge 1 1" show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"  (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTVw %Construct a preorder relation from a  . Complexity: O(1) time. .Extract the underlying relation. Complexity: O(n * m * log(m)) time.    (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV &Construct a reflexive relation from a  . Complexity: O(1) time..Extract the underlying relation. Complexity:  O(n*log(m)) time.  (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV x&Construct a symmetric relation from a  . Complexity: O(1) time..Extract the underlying relation. Complexity:  O(m*log(m)) time. The set of  neighbours of an element x6 is the set of elements that are related to it, i.e. neighbours x == { a | aRx }G. 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] (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV'Construct a transitive relation from a  . Complexity: O(1) time..Extract the underlying relation. Complexity: O(n * m * log(m)) time.S3456789:;<=>?@A+BCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abbcde,fghijklmnop>?!@qrstuvwxyA+BCDEFGz({|}~579:;<>?@qrstwA+BCDEFGz{|bbcdefghijk>?!@qrstuvxA+BCDEFGz({|}~       j        > ? ! @ q r s t u   w x y A + B C D E F G z ( { | } ~  '        > ? 8 q r s t u   w x z ( { | } ~    =          > ? 8 @ q r s t u   w x A + B C D E F G z ( { | }  =@rstuwxDEF({|}      !"#$%&'()*+,-./0101012013343-56789:;9:<=>?@A34B3CD33E6FG3-H3-/9I23-J9I9IK3L134M34N34O34P34Q34R3-S67T9U9UK9U2VWX34Y34Z34[3-.3-\]^_`a3bc34d6Fe3bf3gh3%& i34j34k ' l i3Cm30n3o*3pqr-algebraic-graphs-0.1.0-7LZPZd6rDr5Elm20hrioPi Algebra.Graph.HigherKinded.ClassAlgebra.Graph.Class#Algebra.Graph.AdjacencyMap.InternalAlgebra.Graph.AdjacencyMap&Algebra.Graph.IntAdjacencyMap.InternalAlgebra.Graph.IntAdjacencyMapAlgebra.Graph.InternalAlgebra.Graph.ExportAlgebra.Graph.Export.DotAlgebra.Graph.Relation.InternalAlgebra.Graph.RelationAlgebra.Graph.Fold Algebra.GraphAlgebra.Graph.NonEmpty&Algebra.Graph.Relation.InternalDerivedAlgebra.Graph.Relation.Preorder Algebra.Graph.Relation.Reflexive Algebra.Graph.Relation.Symmetric!Algebra.Graph.Relation.TransitiveGraphRelation Data.Graphvertices vertexListedgesedgeListoverlayconnectemptyvertexedgegraphfromAdjacencyList Data.Listnubsort Data.TupleswapFold removeEdge Data.Monoid<>circuit AdjacencyMap Data.FoldabletoListlengthData.List.NonEmptyreversefromListbaseGHC.BaseToGraphToVertextoGraphfoldgPreorder Transitive Reflexive UndirectedVertexoverlaysconnects isSubgraphOfpathcliquebicliquestar starTransposetreeforest $fGraph(,,) $fGraph(,) $fGraph(->) $fGraphMaybe $fGraph()$fUndirected(,,)$fUndirected(,)$fUndirected(->)$fUndirectedMaybe$fUndirected()$fReflexive(,,)$fReflexive(,)$fReflexive(->)$fReflexiveMaybe $fReflexive()$fTransitive(,,)$fTransitive(,)$fTransitive(->)$fTransitiveMaybe$fTransitive()$fPreorder(,,) $fPreorder(,)$fPreorder(->)$fPreorderMaybe $fPreorder()$fGraphGGraphKL toGraphKL fromVertexKL toVertexKLAM adjacencyMapgraphKLmkAM consistent mkGraphKL$fToGraphAdjacencyMap$fNumAdjacencyMap$fGraphAdjacencyMap$fShowAdjacencyMap$fEqAdjacencyMapisEmpty hasVertexhasEdge vertexCount edgeCount adjacencyList vertexSetedgeSetpostSet removeVertex replaceVertex mergeVertices transposegmapinduce dfsForest dfsForestFromdfstopSort isTopSortscc vertexIntSetmeshtorusdeBruijn splitVertexboxIntAdjacencyMap$fToGraphIntAdjacencyMap$fNumIntAdjacencyMap$fGraphIntAdjacencyMap$fShowIntAdjacencyMap$fEqIntAdjacencyMap postIntSetFocusContextinputsoutputsListcontextfocus $fMonadList$fApplicativeList $fFunctorList$fFoldableList $fIsListList $fOrdList$fEqList $fShowList $fMonoidList$fSemigroupListDocliteralrender<+>brackets doubleQuotesindentunlinesexport $fIsStringDoc$fOrdDoc$fEqDoc $fShowDoc $fMonoidDoc$fSemigroupDocStyle graphNamepreamblegraphAttributesdefaultVertexAttributesdefaultEdgeAttributes vertexNamevertexAttributesedgeAttributes Attribute:= defaultStyledefaultStyleViaShow exportAsIs exportViaShowdomainrelation setProductreferredToVertexSet$fToGraphRelation $fNumRelation$fGraphRelation$fShowRelation $fEqRelationpreSetcomposereflexiveClosuresymmetricClosuretransitiveClosurepreorderClosuresizebindsimplify $fToGraphFold$fToGraphFold0$fTraversableFold$fFoldableFold $fGraphFold $fMonadFold$fMonadPlusFold$fAlternativeFold$fApplicativeFold $fFunctorFold $fNumFold $fGraphFold0$fEqFold $fShowFoldEmptyOverlayConnect===$fMonadPlusGraph$fAlternativeGraph $fMonadGraph$fApplicativeGraph $fEqGraph $fNumGraph $fGraphGraph$fToGraphGraph$fToGraphGraph0 $fGraphGraph0 $fNFDataGraph$fFoldableGraph$fFunctorGraph $fShowGraph$fTraversableGraph NonEmptyGraphtoNonEmptyGraphoverlay1 vertices1edges1 overlays1 connects1foldg1 vertexList1path1circuit1clique1 biclique1mesh1torus1 removeVertex1 splitVertex1induce1$fMonadNonEmptyGraph$fApplicativeNonEmptyGraph$fEqNonEmptyGraph$fNumNonEmptyGraph$fToGraphNonEmptyGraph$fToGraphNonEmptyGraph0$fNFDataNonEmptyGraph$fFoldableNonEmptyGraph$fFunctorNonEmptyGraph$fShowNonEmptyGraph$fTraversableNonEmptyGraphPreorderRelation fromPreorderTransitiveRelationfromTransitiveSymmetricRelation fromSymmetricReflexiveRelation fromReflexive$fReflexiveReflexiveRelation$fGraphReflexiveRelation$fShowReflexiveRelation$fEqReflexiveRelation$fUndirectedSymmetricRelation$fGraphSymmetricRelation$fShowSymmetricRelation$fEqSymmetricRelation$fTransitiveTransitiveRelation$fGraphTransitiveRelation$fShowTransitiveRelation$fEqTransitiveRelation$fPreorderPreorderRelation$fTransitivePreorderRelation$fReflexivePreorderRelation$fGraphPreorderRelation$fEqPreorderRelation$fShowPreorderRelation$fNumReflexiveRelation$fNumSymmetricRelation$fNumTransitiveRelation$fNumPreorderRelation fromRelation toRelation neighboursGHC.Showshowfoldrghc-prim GHC.TypesTruecontainers-0.5.10.2 Data.TreeTreeForestGEVOCNothingGHC.NumNumShow GHC.ClassesEqelemData.Set.Internalall singletonGHC.Listfmappure MonadPlus Alternative Applicative<|>nullIntData.IntSet.InternalokisosMonoidmemptymappendFoldable emptyFocus vertexFocus overlayFoci connectFocivs Data.StringIsStringidOrd fromStringGHC.Realodd filterContext>>=maprunFoldsignum:|Data.Semigroup Control.Monad>=>