z      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                  ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT'The 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 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 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. The class of undirected graphs- that satisfy the following additional axiom. is commutative: x * y == y * xTThe core type class for constructing algebraic graphs is defined by introducing the  method to the standard 2 class and reusing the following existing methods:The  method comes from the  class and corresponds to the  empty graph#. This module simply re-exports it.The  . graph construction primitive is an alias for  of the  type class.Graph   is an alias for  of the  type class.The Y type class is characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for   and , respectively.  is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z is associative and has  as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z distributes over  : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * 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.Connect 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 ==  (  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 ==   -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 ==   1Construct the graph from given lists of vertices V and edges E-. The resulting graph contains the vertices V7 as well as all the vertices referred to by the edges E. Complexity:  O(|V| + |E|) time, memory and size. graph [] [] ==  graph [x] [] ==   x graph [] [(x,y)] ==   x y graph vs es ==   (  vs) (  es) 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 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 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 . Complexity:  O(s * log(n)) time and O(n) memory.  vertexIntSet  == IntSet. vertexIntSet .   == IntSet. vertexIntSet .   == IntSet. vertexIntSet .  == IntSet. 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 a list 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 star> formed by a centre vertex and 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)] 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 dimention 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) == 3 removeVertex x . removeVertex x == removeVertex x % 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 with 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 (  !"#$%&'()  !"#$%&'()   !"$%&'#(&  !"#$%&'((c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT)The )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 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.5 is commutative: x * y == y * x0The core type class for constructing algebraic graphs, characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for 4 and 5, respectively.4 is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z5 is associative and has 2 as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z5 distributes over 4: 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z5 can be decomposed: "x * y * z == x * y + x * z + y * zIThe following useful theorems can be proved from the above set of axioms.4 has 2# as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of 5: -x * y + x + y == x * y x * x * x == x * xThe core type class 0, 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 0 expression.1The type of graph vertices.2Construct the empty graph.3)Construct the graph with a single vertex.4Overlay two graphs.5Connect two graphs.6;Construct the graph comprising a single edge. Complexity: O(1) time, memory and size.  edge x y == 5 (3 x) (3 y) 7OConstruct 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 [] == 2 vertices [x] == 3 x 87Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] == 2 edges [(x,y)] == 6 x y 9-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 [] == 2' overlays [x] == x overlays [x,y] == 4 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. connects [] == 2' connects [x] == x connects [x,y] == 5 x y ;1Construct the graph from given lists of vertices V and edges E-. The resulting graph contains the vertices V7 as well as all the vertices referred to by the edges E. Complexity:  O(|V| + |E|) time, memory and size. graph [] [] == 2 graph [x] [] == 3 x graph [] [(x,y)] == 6 x y graph vs es == 4 (7 vs) (8 es) <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 = 4 x y == y gThe complexity therefore depends on the complexity of equality testing of the specific graph instance.  isSubgraphOf 2- x == True isSubgraphOf (3 x) 2. == False isSubgraphOf x (4 x y) == True isSubgraphOf (4 x y) (5 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 [] == 2 path [x] == 3 x path [x,y] == 6 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 [] == 2 circuit [x] == 6 x x circuit [x,y] == 8 [(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 [] == 2 clique [x] == 3 x clique [x,y] == 6 x y clique [x,y,z] == 8, [(x,y), (x,z), (y,z)] clique (xs ++ ys) == 5 (clique xs) (clique ys) @The biclique% on a list of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique [] [] == 2 biclique [x] [] == 3 x biclique [] [y] == 3 y biclique [x1,x2] [y1,y2] == 8B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == 5 (7 xs) (7 ys) AThe star> formed by a centre vertex and a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] == 3 x star x [y] == 6 x y star x [y,z] == 8 [(x,y), (x,z)] BThe  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 []) == 3? x tree (Node x [Node y [Node z []]]) == =E [x,y,z] tree (Node x [Node y [], Node z []]) == AE x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == 8 [(1,2), (1,3), (3,4), (3,5)] CThe  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 [] == 2? forest [x] == BA x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == 8U [(1,2), (1,3), (4,5)] forest == 9 . map B 4)*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\)*+,-./0123456789:;<=>?@ABC012345/.-,679:8;<=>?@ABC)*+-)*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone :DILRT ]]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 A mapping from vertices of type Int to Data.Graph.Vertex . Returns % if the argument is not in the graph.bThe bX 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: dshow (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) == "graph [1,2,3] [(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.dThe  adjacency mapN of the graph: each vertex is associated with a set of its direct successors.e(Cached King-Launchbury representation. )Note: this field is for internal use only.f 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.gCheck 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 hBuild ] from a map of successor sets. ,Note: this function is for internal use only.]^_`abcdefghijklm ]^_`abcdefgh bcdefg]^_`ah ]^_`abcdefghijklm(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT*nConstruct the  empty graph. Complexity: O(1) time and memory. z empty == True { x empty == False } empty == 0 ~ empty == 0 oConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory. z (vertex x) == False { x (vertex x) == True { 1 (vertex 2) == False } (vertex x) == 1 ~ (vertex x) == 0 pConstruct the graph comprising  a single edge. Complexity: O(1) time, memory. edge x y == r (o x) (o y) | x y (edge x y) == True ~ (edge x y) == 1 } (edge 1 1) == 1 } (edge 1 2) == 2 qOverlay] two graphs. This is an idempotent, commutative and associative operation with the identity n. Complexity: O((n + m) * log(n)) time and O(n + m) memory. z (overlay x y) == z x && z 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 rConnectA two graphs. This is an associative operation with the identity nU, which distributes over the overlay and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2). z (connect x y) == z x && z y { 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 sOConstruct 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 [] == n vertices [x] == o x { x . vertices ==  x } . vertices ==  .   . vertices == IntSet. t7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] == n edges [(x, y)] == p x y ~ . edges ==  .   . edges ==  .  u-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == n/ overlays [x] == x overlays [x,y] == q x y z . overlays ==  z v-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] == n/ connects [x] == x connects [x,y] == r x y z . connects ==  z w1Construct the graph from given lists of vertices V and edges E-. The resulting graph contains the vertices V7 as well as all the vertices referred to by the edges E. Complexity: O((n + m) * log(n)) time and O(n + m) memory. graph [] [] == n graph [x] [] == o x graph [] [(x,y)] == p x y graph vs es == q (s vs) (t es) x7Construct a graph from an adjacency list. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 9fromAdjacencyList [] == n: fromAdjacencyList [(x, [])] == o< x fromAdjacencyList [(x, [y])] == p x y fromAdjacencyList .  == id qO (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys) yThe y' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf n- x == True isSubgraphOf (o x) n. == False isSubgraphOf x (q x y) == True isSubgraphOf (q x y) (r x y) == True isSubgraphOf ( xs) ( xs) == True z(Check if a graph is empty. Complexity: O(1) time. isEmpty n( == True isEmpty (q n n) == True isEmpty (o' x) == False isEmpty ( x $ o x) == True isEmpty ( x y $ p x y) == False {7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x n" == False hasVertex x (o x) == True hasVertex x .  x == const False |5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y n" == False hasEdge x y (o z) == False hasEdge x y (p" 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 n == 0 vertexCount (o# x) == 1 vertexCount ==  .  ~-The number of edges in a graph. Complexity: O(n) time.  edgeCount n == 0 edgeCount (o x) == 0 edgeCount (p# x y) == 1 edgeCount ==  .  ;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList n == [] vertexList (o x) == [x] vertexList . s ==  .  2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList n == [] edgeList (o x) == [] edgeList (p x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList . t ==  .  edgeList .  ==  . map &' . edgeList  The sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory. adjacencyList n$ == [] adjacencyList (o) x) == [(x, [])] adjacencyList (p5 1 2) == [(1, [2]), (2, [])] adjacencyList (1 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] x . adjacencyList == id 3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexIntSet n == IntSet. vertexIntSet . o == IntSet. vertexIntSet . s == IntSet. vertexIntSet .  == IntSet. 0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet n == Set. edgeSet (o x) == Set. edgeSet (p x y) == Set. (x,y) edgeSet . t == Set. The postset of a vertex is the set of its direct successors.  postIntSet x n == IntSet. postIntSet x (o x) == IntSet. postIntSet x (p x y) == IntSet. [y] postIntSet 2 (p 1 2) == IntSet. The path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] == n path [x] == o x path [x,y] == p x y path .  ==  . path The circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] == n circuit [x] == p x x circuit [x,y] == t [(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 [] == n clique [x] == o x clique [x,y] == p x y clique [x,y,z] == t, [(x,y), (x,z), (y,z)] clique (xs ++ ys) == r" (clique xs) (clique ys) clique .  ==  . clique The biclique% on a list of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique [] [] == n biclique [x] [] == o x biclique [] [y] == o y biclique [x1,x2] [y1,y2] == tB [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == r (s xs) (s ys) The star> formed by a centre vertex and a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] == o x star x [y] == p x y star x [y,z] == t [(x,y), (x,z)] The  tree graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. <tree (Node x []) == o? 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 []]]) == t [(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 [] == n? forest [x] == A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == tU [(1,2), (1,3), (4,5)] forest == u . map  1Remove a vertex from a given graph. Complexity:  O(n*log(n)) time. removeVertex x (o x) == n3 removeVertex x . removeVertex x == removeVertex x 0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y (p x y) == sK [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 b. If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time. 6replaceVertex x x == id replaceVertex x y (o x) == o# y replaceVertex x y ==  (== x) y NMerge vertices satisfying a given predicate with 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 n == n transpose (o x) == o x transpose (p x y) == p- y x transpose . transpose == id transpose .  ==  .  transpose .  ==  .  transpose .  ==  .   . 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 b. Complexity: O((n + m) * log(n)) time. gmap f n == n gmap f (o x) == o (f x) gmap f (p x y) == pG (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 == n induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x) y (induce p x) x == True  Compute the depth-first search forest of a graph.  (dfsForest $ p 1 1) == o 1  (dfsForest $ p 1 2) == p 1 2  (dfsForest $ p 2 1) == s [1, 2] y (& $ dfsForest x) x == True dfsForest . , . dfsForest == dfsForest dfsForest (s- 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] $ p 1 1) == o 1  (dfsForestFrom [1] $ p 1 2) == p 1 2  (dfsForestFrom [2] $ p 1 2) == o 2  (dfsForestFrom [3] $ p 1 2) == n  (dfsForestFrom [2, 1] $ p 1 2) == s [1, 2] y (0 $ dfsForestFrom vs x) x == True dfsForestFrom ( x) x == ! x dfsForestFrom vs (s! 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] $ p( 1 1 == [1] dfs [1] $ p+ 1 2 == [1, 2] dfs [2] $ p( 1 2 == [2] dfs [3] $ p' 1 2 == [] dfs [1, 2] $ p+ 1 2 == [1, 2] dfs [2, 1] $ p{ 1 2 == [2, 1] dfs [] $ x == [] dfs [1, 4] $ 3 * (1 + 4) * (1 + 5) == [1, 5, 4] y (s $ 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 [] n( == True isTopSort [x] (o& x) == True isTopSort [x] (p x x) == False *nopqrstuvwxyz{|}~,bdnopqrstuvwxyz{|}~-bddnopqrstuvwxyz{|}~*nopqrstuvwxyz{|}~(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone :DILRTThe # 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: :show (empty :: Relation Int) == "empty" show (1 :: Relation Int) == "vertex 1" show (1 + 2 :: Relation Int) == "vertices [1,2]" show (1 * 2 :: Relation Int) == "edge 1 2" show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Relation Int) == "graph [1,2,3] [(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-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT+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  1 (vertex 2) == False  (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 an idempotent, commutative and associative 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 U, which distributes over the overlay 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 ==   -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 ==   1Construct the graph from given lists of vertices V and edges E-. The resulting graph contains the vertices V7 as well as all the vertices referred to by the edges E. Complexity: O((n + m) * log(n)) time and O(n + m) memory. graph [] [] ==  graph [x] [] ==  x graph [] [(x,y)] ==  x y graph vs es ==  ( vs) ( es) 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 ( 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 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(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 (' 2 [3,1]) == [(2,1), (2,3)] edgeList .  ==  .  edgeList .  ==  . map  . 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 . Complexity: O(n) time.  vertexIntSet  == IntSet. vertexIntSet .  == IntSet. vertexIntSet .  == IntSet. vertexIntSet .  == IntSet. 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 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 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 .  ==  . 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 a list 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 star> formed by a centre vertex and 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)] The  tree graph constructed from a given Tree 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 Forest 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 + m) time. removeVertex x ( x) == 3 removeVertex x . removeVertex x == removeVertex x 0Remove 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 .  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  AdjacencyMap. If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y NMerge vertices satisfying a given predicate with 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(m)) time.  transpose  ==  transpose ( x) ==  x transpose ( x y) == - y x transpose . transpose == id transpose .  ==  .  transpose .  ==  .  transpose .  ==  .   . 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 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) +.0+(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone :DILRTThe  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: 3 x == 3 x * 3 xand the closure axiom: y /= 2+ ==> 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 /= 2+ ==> 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: 5 x y == 5 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: 3 x == 3 x * 3 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-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT%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-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT&Construct a reflexive relation from a . Complexity: O(1) time..Extract the underlying relation. Complexity:  O(n*log(m)) time. (c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT&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-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT'Construct a transitive relation from a . Complexity: O(1) time..Extract the underlying relation. Complexity: O(n * m * log(m)) time. (c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone :DILRT 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 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: Rshow (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) == "graph [1,2,3] [(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.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-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT+ 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  1 (vertex 2) == False  (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 an idempotent, commutative and associative 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  U, which distributes over the overlay 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 ==  .   . 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 ==   -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 ==   1Construct the graph from given lists of vertices V and edges E-. The resulting graph contains the vertices V7 as well as all the vertices referred to by the edges E. Complexity: O((n + m) * log(n)) time and O(n + m) memory. graph [] [] ==   graph [x] [] ==   x graph [] [(x,y)] ==   x y graph vs es ==  ( vs) ( es) 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 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.  vertexSet   == Set. vertexSet .   == Set. vertexSet .  == Set. vertexSet . $ == Set.  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 of a vertex is the set of its direct successors.  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 .  == - . 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 a list 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 star> formed by a centre vertex and 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)] '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) ==  3 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 with 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 . " == " .  transpose . # == # .  transpose . $ == $ .   . 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 0 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) 1 ( 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 = [] }]}] 1 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 == 0! 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 = [] }] 2,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 3 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 4 x) (topSort x) /= Just False 4-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 5 Compute the  condensation1 of a graph, where each vertex corresponds to a strongly-connected component of the original graph. scc   ==   scc (  x) ==   (Set. x) scc (  x y) ==   (Set. x) (Set. y) scc (# (1:xs)) ==   (Set. (1:xs)) (Set.$ (1:xs)) scc (3 * 1 * 4 * 1 * 5) ==  [ (Set. [1,4], Set.0 [1,4]) , (Set. [1,4], Set.0 [5] ) , (Set. [3] , Set.0 [1,4]) , (Set. [3] , Set. [5] )] +    !"#$%&'()*+,-./012345-    !"#$%&'()*+,-./012345.    !"#$%&'()*+,-./012345+    !"#$%&'()*+,-./012345(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT 6!An abstract document type, where s4 is the type of strings or words (text or binary). 6 s is a  , therefore O corresponds to the empty document and two documents can be concatenated with  (or operator )*). Note that most functions on 6 s# require that the underlying type s is also a .7<Construct a document comprising a single string or word. If s is an instance of class , then documents of type 6 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  ==  8# . literal ==  literal . 8 ==  8JRender a document as a single string or word. An inverse of the function 7. render (7 "al" <> 7 "ga") :: ( s,  s) => s render (7 "al" <> 7 "ga") == "alga" render  ==  render . 7 ==  7" . render ==  9Concatenate two documents, separated by a single space, unless one of the documents is empty. The operator <+> is associative with identity . x <+>  == x c <+> x == x x <+> (y <+> z) == (x <+> y) <+> z "name" <+> "surname" == "name surname" :#Wrap a document in square brackets. "brackets "i" == "[i]" brackets  == "[]" ;#Wrap a document into double quotes. YdoubleQuotes "/path/with spaces" == "\"/path/with spaces\"" doubleQuotes (doubleQuotes ) == "\"\"\"\"" </Prepend a given number of spaces to a document. indent 0 ==  indent 1  == " " =KConcatenate documents after appending a terminating newline symbol to each. !unlines [] ==  unlines [L] == "\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  a, and then edges, sorted by  (a, a). For example:  vDoc x = 7 ( x) <> "\n" eDoc x y = 7 ( x) <> " -> " <> 7 ( y) <> "\n" > putStrLn $ 8( $ export vDoc eDoc (1 + 2 * (3 + 4) ::  Int) 1 2 3 4 2 -> 3 2 -> 4 6789:;<=>?@AB 6789:;<=> 6789:;<=> 6789:;<=>?@AB97(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone !":DILRTE The record E 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 L!, which holds a function of type a -> s< to compute vertex names. See the example for the function S.GName of the graph.H8Preamble is added at the beginning of the DOT file body.IGraph style, e.g. ["bgcolor" := "azure"].JDefault vertex style, e.g. ["shape" := "diamond"].KDefault edge style, e.g. ["style" := "dashed"].LCompute a vertex name.M Attributes of a specific vertex.NAttributes of a specific edge.O3An attribute is just a key-value pair, for example "shape" := "box"L. Attributes are used to specify the style of graph elements during export.QMDefault style for exporting graphs. All style settings are empty except for L), which is provided as the only argument.R6Default style for exporting graphs whose vertices are 0-able. All style settings are empty except for L, which is computed from . defaultStyleViaShow = Q ( . ) S"Export a graph with a given style. For example:  style :: E Int String style = E { G! = "Example" , H4 = " // This is an example\n" , I= = ["label" := "Example", "labelloc" := "top"] , J = ["shape" := "circle"] , K =  , L = \x -> "v" ++  x , M) = \x -> ["color" := "blue" |  x ] , N+ = \x y -> ["style" := "dashed" | = (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" } TDExport 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" } UExport a graph using the R. For example: /> putStrLn $ exportViaShow (1 + 2 * (3 + 4) :: E Int) digraph { "1" "2" "3" "4" "2" -> "3" "2" -> "4" } EFGHIJKLMNOPQRSTUEFGHIJKLMNOPQRSTUOPEFGHIJKLMNQRSTUE FGHIJKLMNOPQRSTU(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILORT$VThe VU datatype is the Boehm-Berarducci encoding 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 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) == "graph [1,2,3] [(1,2)]"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 graph expression. For example, if g is a V then n, m and s can be computed as follows: n == e g m == f g s == b g Note that b is slightly different from the  method of the * type class, as the latter does not count W leaves of the expression:  W == 0 b W == 1  (X x) == 1 b (X x) == 1  (W + W) == 0 b (W + W) == 2The b. of any graph is positive, and the difference (b g -  g)- corresponds to the number of occurrences of W in an expression g. Converting a V 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. Complexity: O(1) time, memory and size. a empty == True c x empty == False e empty == 0 f empty == 0 b empty == 1 XConstruct the graph comprising a single isolated vertex. Complexity: O(1) time, memory and size. a (vertex x) == False c x (vertex x) == True c 1 (vertex 2) == False e (vertex x) == 1 f (vertex x) == 0 b (vertex x) == 1 YConstruct the graph comprising  a single edge. Complexity: O(1) time, memory and size. edge x y == [ (X x) (X y) d x y (edge x y) == True f (edge x y) == 1 e (edge 1 1) == 1 e (edge 1 2) == 2 ZOverlay] two graphs. This is an idempotent, commutative and associative operation with the identity W. Complexity: O(1) time and memory,  O(s1 + s2) size. a (overlay x y) == a x && a y c z (overlay x y) == c z x || c z y e (overlay x y) >= e x e (overlay x y) <= e x + e y f (overlay x y) >= f x f (overlay x y) <= f x + f y b (overlay x y) == b x + b y e (overlay 1 2) == 2 f (overlay 1 2) == 0 [ConnectA two graphs. This is an associative operation with the identity WU, which distributes over the overlay 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). a (connect x y) == a x && a y c z (connect x y) == c z x || c z y e (connect x y) >= e x e (connect x y) <= e x + e y f (connect x y) >= f x f (connect x y) >= f y f (connect x y) >= e x * e y f (connect x y) <= e x * e y + f x + f y b (connect x y) == b x + b y e (connect 1 2) == 2 f (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 c x . vertices ==  x e . vertices ==  .  i . 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 f . 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 a . overlays ==  a _-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 a . connects ==  a `2Generalised graph folding: recursively collapse a V 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 b is O(s) , since all functions have cost O(1). foldg W X Z [ == id foldg W X Z (flip [) == t5 foldg [] return (++) (++) == 5 foldg 0 (const 1) (+) (+) == 5 foldg 1 (const 1) (+) (+) == b5 foldg True (const False) (&&) (&&) == a a2Check 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 (o x $ X x) == True isEmpty (p x y $ Y x y) == False bThe 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 >= e x cACheck 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 x . o x == const False d5Check 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 . p4 x y == const False hasEdge x y ==  (x,y) . h e0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount W == 0 vertexCount (X# x) == 1 vertexCount ==  . g f-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 ==  . h g;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 . \ ==  .  h2The 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 (star' 2 [3,1]) == [(2,1), (2,3)] edgeList . ] ==  .  edgeList . t ==  . map &' . edgeList i3The 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 . clique == Set. j+The set of vertices of a given graph. Like i3 but specialised for graphs with vertices of type . Complexity:  O(s * log(n)) time and O(n) memory.  vertexIntSet W == IntSet. vertexIntSet . X == IntSet. vertexIntSet . \ == IntSet. vertexIntSet . clique == IntSet. k0The 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. l 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 == y (path xs) (path 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')) ] m 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 == y (circuit xs) (circuit 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')) ] n 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 dimention 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") ] t (deBruijn n xs) == u  $ deBruijn n xs e (deBruijn n xs) == ( $  xs)^n n > 0 ==> f (deBruijn n xs) == ( $  xs)^(n + 1) o1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x (X x) == W3 removeVertex x . removeVertex x == removeVertex x p0Remove an edge from a given graph. Complexity: O(s)4 time and memory. The worst case size complexity is O(s^2)2, although in practice it is usually also linear O(s). removeEdge x y (Y x y) == \K [x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . o x == oa x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 q The function q 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 (X x) == X# y replaceVertex x y == r (== x) y rNMerge vertices satisfying a given predicate with 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 == qY x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 sPSplit 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 [] == oP x splitVertex x [x] == id splitVertex x [y] == q< x y splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3) t&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 . = == = .  transpose . > == > .  transpose . ? == ? .  transpose (y x y) == y (transpose x) (transpose y) h . transpose ==  . map &' . h u\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 W == W gmap f (X x) == X (f x) gmap f (Y x y) == YG (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) voTransform a given graph by substituting each of its vertices with a subgraph. This is similar to Monad's bind 3 but can be used with non-fully-parametric graphs. bind W f == W bind (X x) f == f x bind (Y x y) f == [ (f x) (f y) bind (\ xs) f == ^ ( f xs) bind x (const W) == W bind x XA == x bind (bind x f) g == bind x (\y -> bind (f y) g) wConstruct 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) == o< x induce p . induce q == induce (\x -> p x && q x)  isSubgraphOf (induce p x) x == True xVSimplify 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 b (simplify x) <= b x simplify W ~> Wq simplify 1 ~> 1 simplify (1 + 1) ~> 1 simplify (1 + 2 + 1) ~> 1 + 2 simplify (1 * 1 * 1) ~> 1 * 1 y 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") == ] [ ((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 t (box x y) == box (t x) (t y) e (box x y) == e x * e y f (box x y) <= e x * f y + f x * e y ?VWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~-;<=>?@ABCVWXYZ[\]^_`abcdefghijklmnopqrstuvwxy-VWXYZ[\]^_;`<abcdefghijk=>?@ABClmnopqrstuvwxy9VWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone 234:DILRT,The H datatype is a deep embedding of the core graph construction primitives , ,  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: 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, n2 will denote the number of vertices in the graph, m3 will denote the number of edges in the graph, and s will denote the size of the corresponding $ expression. For example, if g is a  then n, m and s can be computed as follows: n ==  g m ==  g s ==  g Note that  is slightly different from the  method of the * type class, as the latter does not count  leaves of the expression:   == 0   == 1  ( x) == 1  ( x) == 1  ( + ) == 0  ( + ) == 2The . of any graph is positive, and the difference ( g -  g)- corresponds to the number of occurrences of  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.Construct the  empty graph. An alias for the constructor . Complexity: O(1) time, memory and size.  empty == True  x empty == False  empty == 0  empty == 0  empty == 1 Construct the graph comprising a single isolated vertex . An alias for the constructor . Complexity: O(1) time, memory and size.  (vertex x) == False  x (vertex x) == True  1 (vertex 2) == False  (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 R. This is an idempotent, commutative and associative operation with the identity . Complexity: O(1) time and memory,  O(s1 + s2) size.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) ==  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 Connect* two graphs. An alias for the constructor 6. This is an associative operation with the identity V, which distributes over the overlay 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 [] ==  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  . 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 [] == / 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 ==   1Construct the graph from given lists of vertices V and edges E-. The resulting graph contains the vertices V7 as well as all the vertices referred to by the edges E. Complexity:  O(|V| + |E|) time, memory and size. graph [] [] ==  graph [x] [] ==  x graph [] [(x,y)] ==  x y graph vs es ==  ( vs) ( es)  Generalised ! folding: recursively collapse a  by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: empty, vertex, overlay and connect. Complexity: O(s)D applications of given functions. As an example, the complexity of  is O(s) , since all functions have cost O(1). foldg     == id foldg    (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 - x == True isSubgraphOf ( x) . == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True 7Structural equality on graph expressions. Complexity: O(s) time. * x === x == True x === x + ` == False x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False 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 isEmpty ( x y $  x y) == False The sizeD of a graph, i.e. the number of leaves of the expression including  leaves. Complexity: O(s) time. size  == 1 size ( x) == 1 size ( x y) == size x + size y size (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 " == False hasVertex x ( x) == True 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 (" 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  == 0 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  == 0 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.  vertexList  == [] vertexList ( 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  == [] edgeList ( x) == [] edgeList ( 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  == 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 . Complexity:  O(s * log(n)) time and O(n) memory.  vertexIntSet  == IntSet. vertexIntSet .  == IntSet. vertexIntSet .  == IntSet. vertexIntSet .  == IntSet. 0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory. edgeSet  == Set. edgeSet ( x) == Set. edgeSet ( x y) == Set. (x,y) 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 [] ==  path [x] ==  x path [x,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 [] ==  circuit [x] ==  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 [] ==  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 a list 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 star> formed by a centre vertex and 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)] The  tree graph constructed from a given Tree 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 Forest 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 dimention 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") ]  (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) == 3 removeVertex x . removeVertex x == removeVertex x 0Remove an edge from a given graph. Complexity: O(s)4 time and memory. The worst case size complexity is O(s^2)2, although in practice it is usually also linear O(s). removeEdge x y ( x y) == K [x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . /0 x == /0a 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(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 with 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  ==  transpose ( x) ==  x transpose ( x y) == - y x transpose . transpose == id transpose .  ==  .  transpose .  ==  .  transpose .  ==  .  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 ==  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    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 , 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) == box ( x) ( y)  (box x y) ==  x *  y  (box x y) <=  x *  y +  x *  y D 00= 4 12!345678 "#9:$;<=>?@AB+CDEFGHIJK0LMNO3P45678Q!" #9:$;B+CDEFGRSTUVWXYZ[\]^_`abcdefghijkklmnopqrstuvwxyz!"# 9:$%;<=>?{|A}~B+CDEFG0LMKt!"# 9:$%;<=>?{@A}B+CDEFG0LMK k k l m n ( p q r s t u ! " #    9 : $ % ; < = > ? {   | @ } B + C D E F G 0  L M K !"# 9:<=>?{@A}HIJ0LMNKOQ!"# 9:$;<=>?{@A}B+CDEFGHIJ0LMNKO112121212121,1,.   1,  1,  !    !     1211211  1&'  12!12"12#1$%12& '1$(1)*+1,,1,-12-12./0012345678/001256789-algebraic-graphs-0.0.5-1mrfZHETQhQ3FyDUjYAlwR Algebra.Graph.HigherKinded.ClassAlgebra.Graph.Class&Algebra.Graph.IntAdjacencyMap.InternalAlgebra.Graph.IntAdjacencyMapAlgebra.Graph.Relation.InternalAlgebra.Graph.Relation&Algebra.Graph.Relation.InternalDerivedAlgebra.Graph.Relation.Preorder Algebra.Graph.Relation.Reflexive Algebra.Graph.Relation.Symmetric!Algebra.Graph.Relation.Transitive#Algebra.Graph.AdjacencyMap.InternalAlgebra.Graph.AdjacencyMapAlgebra.Graph.ExportAlgebra.Graph.Export.DotAlgebra.Graph.Fold Algebra.GraphGraphFoldControl.Applicative Alternative Data.ListnubsortRelation Data.Graphvertices vertexListedgesedgeListoverlayconnectemptyvertexedgegraphfromAdjacencyList Data.Tupleswap AdjacencyMap Data.Monoid<>circuit Data.FoldabletoListlengthAlgebra.Graph.HigherKinded.Util removeVertexbaseGHC.BaseToGraphtoGraphPreorder Transitive Reflexive Undirectedoverlaysconnects isSubgraphOfisEmpty hasVertexhasEdge vertexCount vertexSet vertexIntSetpathcliquebicliquestartreeforestmeshtorusdeBruijninduce replaceVertex mergeVertices splitVertexboxToVertexVertex$fPreorder(,,)$fTransitive(,,)$fReflexive(,,)$fUndirected(,,) $fGraph(,,) $fPreorder(,)$fTransitive(,)$fReflexive(,)$fUndirected(,) $fGraph(,)$fPreorder(->)$fTransitive(->)$fReflexive(->)$fUndirected(->) $fGraph(->)$fPreorderMaybe$fTransitiveMaybe$fReflexiveMaybe$fUndirectedMaybe $fGraphMaybe $fPreorder()$fTransitive() $fReflexive()$fUndirected() $fGraph()GraphKL toGraphKL fromVertexKL toVertexKLIntAdjacencyMapAM adjacencyMapgraphKLmkAM consistent mkGraphKL$fToGraphIntAdjacencyMap$fNumIntAdjacencyMap$fGraphIntAdjacencyMap$fShowIntAdjacencyMap$fEqIntAdjacencyMap edgeCount adjacencyListedgeSet postIntSet removeEdge transposegmap dfsForest dfsForestFromdfstopSort isTopSortdomainrelation setProductreferredToVertexSet$fToGraphRelation $fNumRelation$fGraphRelation$fShowRelation $fEqRelationpreSetpostSetcomposereflexiveClosuresymmetricClosuretransitiveClosurepreorderClosurePreorderRelation fromPreorderTransitiveRelationfromTransitiveSymmetricRelation fromSymmetricReflexiveRelation fromReflexive$fPreorderPreorderRelation$fTransitivePreorderRelation$fReflexivePreorderRelation$fGraphPreorderRelation$fEqPreorderRelation$fShowPreorderRelation$fTransitiveTransitiveRelation$fGraphTransitiveRelation$fShowTransitiveRelation$fEqTransitiveRelation$fUndirectedSymmetricRelation$fGraphSymmetricRelation$fShowSymmetricRelation$fEqSymmetricRelation$fReflexiveReflexiveRelation$fGraphReflexiveRelation$fShowReflexiveRelation$fEqReflexiveRelation$fNumReflexiveRelation$fNumSymmetricRelation$fNumTransitiveRelation$fNumPreorderRelation fromRelation toRelation neighbours$fToGraphAdjacencyMap$fNumAdjacencyMap$fGraphAdjacencyMap$fShowAdjacencyMap$fEqAdjacencyMapsccDocliteralrender<+>brackets doubleQuotesindentunlinesexport $fIsStringDoc$fOrdDoc$fEqDoc $fShowDoc $fMonoidDoc$fSemigroupDocStyle graphNamepreamblegraphAttributesdefaultVertexAttributesdefaultEdgeAttributes vertexNamevertexAttributesedgeAttributes Attribute:= defaultStyledefaultStyleViaShow exportAsIs exportViaShowfoldgsizebindsimplify $fGraphPiece $fToGraphFold$fToGraphFold0$fTraversableFold$fFoldableFold $fGraphFold $fMonadFold$fMonadPlusFold$fAlternativeFold$fApplicativeFold $fFunctorFold $fNumFold $fGraphFold0$fEqFold $fShowFoldEmptyOverlayConnect===$fMonadPlusGraph$fAlternativeGraph $fMonadGraph$fApplicativeGraph $fEqGraph $fNumGraph $fGraphGraph$fToGraphGraph$fToGraphGraph0 $fGraphGraph0$fFoldableGraph$fFunctorGraph $fShowGraph$fTraversableGraphGHC.Showshowpure MonadPlus Applicativemplus<|>elemcontainers-0.5.7.1 Data.Set.BasefromListallghc-prim GHC.TypesTruenull singletonIntData.IntSet.Base Data.TreeTreeForestfmapGHC.ListreverseNothingGHC.NumNumShow GHC.ClassesEqinternalEdgeListMonoidmemptymappend Data.StringIsStringidOrd fromStringGHC.Realodd attributesFoldable>>=mapPiecesPiecepieceintacttrivialrunFoldbreakIf nonTrivialsmashsimple