H      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                  ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T UVWXYZ[\]^_`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 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)] 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] ==  & [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] 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).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). 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 graphC of given dimension and symbols of a given alphabet. Complexity:  O(A * D^A) time, memory and size, where A" is the size of the alphabet and D is the dimention of the graph. deBruijn k [] ==  deBruijn 1 [0,1] ==  D [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" ==   "00" "00" deBruijn 2 "01" ==   [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ] "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. Mbox 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  ~~  '  !"#$%&'(  !"#$%&'(   !#$%&"'%  !"#$%&'(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.4 is commutative: x * y == y * x/The core type class for constructing algebraic graphs, characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for 3 and 4, respectively.3 is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z4 is associative and has 1 as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z4 distributes over 3: 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z4 can be decomposed: "x * y * z == x * y + x * z + y * zIThe following useful theorems can be proved from the above set of axioms.3 has 1# as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of 4: -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.0The type of graph vertices.1Construct the empty graph.2)Construct the graph with a single vertex.3Overlay two graphs.4Connect two graphs.5;Construct the graph comprising a single edge. Complexity: O(1) time, memory and size.  edge x y == 4 (2 x) (2 y) 6OConstruct 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 [] == 1 vertices [x] == 2 x 77Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] == 1 edges [(x,y)] == 5 x y 8-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 [] == 1' overlays [x] == x overlays [x,y] == 3 x y 9-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 [] == 1' connects [x] == x connects [x,y] == 4 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 [] [] == 1 graph [x] [] == 2 x graph [] [(x,y)] == 5 x y graph vs es == 3 (6 vs) (7 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 = 3 x y == y gThe complexity therefore depends on the complexity of equality testing of the specific graph instance.  isSubgraphOf 1- x == True isSubgraphOf (2 x) 1. == False isSubgraphOf x (3 x y) == True isSubgraphOf (3 x y) (4 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 [] == 1 path [x] == 2 x path [x,y] == 5 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 [] == 1 circuit [x] == 5 x x circuit [x,y] == 7 [(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 [] == 1 clique [x] == 2 x clique [x,y] == 5 x y clique [x,y,z] == 7 [(x,y), (x,z), (y,z)] ?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 [] [] == 1 biclique [x] [] == 2 x biclique [] [y] == 2 y biclique [x1,x2] [y1,y2] == 7& [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] @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 [] == 2 x star x [y] == 5 x y star x [y,z] == 7 [(x,y), (x,z)] AThe  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).BThe  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).4()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[()*+,-./0123456789:;<=>?@AB/01234.-,+56897:;<=>?@AB()*-()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone :DILRT\The \d data type represents a graph by a map of vertices to their adjacency sets. We define a law-abiding ; 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 (`Y :: 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:b is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + zc is associative and has ` as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * zc distributes over b: 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * zc can be decomposed: "x * y * z == x * y + x * z + y * zIThe following useful theorems can be proved from the above set of axioms.b has `# as the identity and is idempotent: 2 x + empty == x empty + x == x x + x == xAbsorption and saturation of c: -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._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.  consistent `& == True consistent (a$ x) == True consistent (b# x y) == True consistent (c# x y) == True consistent (& x y) == True consistent (e% xs) == True consistent (% xs ys) == True consistent (f xs) == True `Construct the  empty graph. Complexity: O(1) time and memory.  empty == True  x empty == False  empty == 0  empty == 0 aConstruct 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 bOverlay] 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 cConnectA 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 dOConstruct 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] == a x  x . vertices ==  x  . vertices ==  .   . vertices == IntSet. e7Construct 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 ==  .  g . edges ==  .  f7Construct a graph from an adjacency list. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 9fromAdjacencyList [] == `: fromAdjacencyList [(x, [])] == a< x fromAdjacencyList [(x, [y])] ==  x y fromAdjacencyList . h == id bO (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys) g2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList ` == [] edgeList (a x) == [] edgeList ( x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList . e ==  .  h The sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory. adjacencyList `$ == [] adjacencyList (a) x) == [(x, [])] adjacencyList (5 1 2) == [(1, [2]), (2, [])] adjacencyList (1 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] f . adjacencyList == id i1Remove a vertex from a given graph. Complexity:  O(n*log(n)) time. removeVertex x (a x) == `3 removeVertex x . removeVertex x == removeVertex x j0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y ( x y) == dK [x, y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . i x == ia x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 kVTransform a graph by applying a function to each of its vertices. This is similar to Functor's , but can be used with non-fully-parametric \. Complexity: O((n + m) * log(n)) time. gmap f ` == ` gmap f (a x) == a (f x) gmap f ( x y) == G (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) lConstruct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(m)) time, assuming that the predicate takes O(1) to be evaluated. @induce (const True) x == x induce (const False) x == ` induce (/= x) == i< x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True \]^_`abcdefghijklmno\]^_`abcdefghijkl\]^_`abcdefghijkl\]^_`abcdefghijklmno(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRTqqD encapsulates King-Launchbury graphs, which are implemented in the  Data.Graph module of the  containers library. If graphKL g == h then the following holds: map (s h) ( ! $ r) h) == IntSet. ( g) map (\(x, y) -> (s h x, s h y)) ( " $ r h) == g g r=Array-based graph representation (King and Launchbury, 1995).s A mapping of Data.Graph.Vertex to vertices of type a.tConstruct the graph comprising  a single edge. Complexity: O(1) time, memory. edge x y == c (a x) (a y) { x y (edge x y) == True } (edge x y) == 1 | (edge 1 1) == 1 | (edge 1 2) == 2 u-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] == b x y y . overlays ==  y v-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] == c x y y . connects ==  y 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 [] [] == ` graph [x] [] == a x graph [] [(x,y)] == t x y graph vs es == b (d vs) (e es) xThe x' 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 (a x) `. == False isSubgraphOf x (b x y) == True isSubgraphOf (b x y) (c x y) == True isSubgraphOf ( xs) ( xs) == True y(Check if a graph is empty. Complexity: O(1) time. isEmpty `( == True isEmpty (b ` `) == True isEmpty (a' x) == False isEmpty (i x $ a x) == True isEmpty (j x y $ t x y) == False z7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x `" == False hasVertex x (a x) == True hasVertex x . i x == const False {5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y `" == False hasEdge x y (a z) == False hasEdge x y (t" x y) == True hasEdge x y . j x y == const False |0The number of vertices in a graph. Complexity: O(1) time.  vertexCount ` == 0 vertexCount (a# x) == 1 vertexCount ==  . ~ }-The number of edges in a graph. Complexity: O(n) time.  edgeCount ` == 0 edgeCount (a x) == 0 edgeCount (t# x y) == 1 edgeCount ==  . g ~;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList ` == [] vertexList (a x) == [x] vertexList . d ==  .  3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexSet ` == IntSet. vertexSet . a == IntSet. vertexSet . d == IntSet. vertexSet .  == IntSet. 0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet ` == Set. edgeSet (a x) == Set. edgeSet (t x y) == Set. (x,y) edgeSet . e == Set. The postset of a vertex is the set of its direct successors.  postset x ` == IntSet. postset x (a x) == IntSet. postset x (t x y) == IntSet. [y] postset 2 (t 1 2) == IntSet. The path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] == ` path [x] == a x path [x,y] == t x y The circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] == ` circuit [x] == t x x circuit [x,y] == e [(x,y), (y,x)] The clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique [] == ` clique [x] == a x clique [x,y] == t x y clique [x,y,z] == e [(x,y), (x,z), (y,z)] The biclique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. biclique [] [] == ` biclique [x] [] == a x biclique [] [y] == a y biclique [x1,x2] [y1,y2] == e& [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] 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 [] == a x star x [y] == t x y star x [y,z] == e [(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.The  forest graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 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 (a x) == a# 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 Build q# from the adjacency map of a graph.  . graphKL == id 5Extract the adjacency map of a King-Launchbury graph. fromGraphKL .  == id  Compute the depth-first search forest of a graph.  (dfsForest $ t 1 1) == a 1  (dfsForest $ t 1 2) == t 1 2  (dfsForest $ t 2 1) == d [1, 2] x (& $ dfsForest x) x == True dfsForest .  . dfsForest == dfsForest dfsForest $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 3 , subForest = [ Node { rootLabel = 4 , subForest = [] }]}]  Compute the topological sort of a graph or return Nothing if the graph is cyclic. ntopSort (1 * 2 + 3 * 1) == Just [3,1,2] topSort (1 * 2 + 2 * 1) == Nothing fmap (flip  x) (topSort x) /= Just False -Check if a given list of vertices is a valid topological sort of a graph. isTopSort [3, 1, 2] (1 * 2 + 3 * 1) == True isTopSort [1, 2, 3] (1 * 2 + 3 * 1) == False isTopSort [] (1 * 2 + 3 * 1) == False isTopSort [] `( == True isTopSort [x] (a& x) == True isTopSort [x] (t x x) == False qrstuvwxyz{|}~.\^`abcdefghijklqsrtuvwxyz{|}~1\^^`atbcdeuvwfxyz{|}~ghijklqrsrsqrstuvwxyz{|}~(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone :DILRTThe  data type represents a binary relation over a set of elements that is both transitive and reflexive. Preorders satisfy all laws of the #$ type class and, in particular, the closure axiom: y /= 1+ ==> x * y + x * z + y * z == x * y + y * zand the  self-loop axiom: 2 x == 2 x * 2 x!For example, the following holds: < xs == > xsThe 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 /= 1+ ==> x * y + x * z + y * z == x * y + y * z!For example, the following holds: < xs == > xsThe 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: 4 x y == 4 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: 2 x == 2 x * 2 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)]"The # data type represents a graph as a binary relation. We define a law-abiding ; 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 (/ :: 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.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.  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 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 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 ==  .  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) 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 [1,3]) == [(2,1), (2,3)] edgeList .  ==  .  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.empty preset x ( x) == Set.empty preset 1 ( 1 2) == Set.empty preset y ( x y) == Set.fromList [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.empty postset x ( x) == Set.empty postset x (% x y) == Set.fromList [y] postset 2 ( 1 2) == Set.empty 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 VTransform a graph by applying a function to each of its vertices. This is similar to Functor's , but can be used with non-fully-parametric . Complexity: O((n + m) * log(n)) time. gmap f  ==  gmap f ( x) ==  (f x) gmap f ( x y) == G (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) Construct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(m)) time, assuming that the predicate takes O(1) to be evaluated. @induce (const True) x == x induce (const False) x ==  induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x)  (induce p x) x == True  Compute the 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(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) 9##.(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRTConstruct 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 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) 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 .  x y == const False 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 .  ==  .  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 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 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)] 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)] The biclique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] == & [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] 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.The  forest graph constructed from a given Forest data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 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 ,.(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 :DILRTThe d data type represents a graph by a map of vertices to their adjacency sets. We define a law-abiding ; 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 (G :: 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.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.  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 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 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 ==  .  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) 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 .  ==  .   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 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 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  (c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILRT D encapsulates King-Launchbury graphs, which are implemented in the  Data.Graph module of the  containers library. If graphKL g == h then the following holds: map ( h) ( ! $ & h) == Set. ( 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.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 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)  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 .  x y == const False  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 .  ==  .  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 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)] 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)] The biclique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] == & [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] 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.The  forest graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. 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 Build # from the adjacency map of a graph.  . graphKL == id 5Extract the adjacency map of a King-Launchbury graph. fromGraphKL .  == id  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 $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] }]} , Node { rootLabel = 3 , subForest = [ Node { rootLabel = 4 , subForest = [] }]}]  Compute the topological sort of a graph or return Nothing if the graph is cyclic. ntopSort (1 * 2 + 3 * 1) == Just [3,1,2] topSort (1 * 2 + 2 * 1) == Nothing fmap (flip   x) (topSort x) /= Just False  -Check if a given list of vertices is a valid topological sort of a graph. isTopSort [3, 1, 2] (1 * 2 + 3 * 1) == True isTopSort [1, 2, 3] (1 * 2 + 3 * 1) == False isTopSort [] (1 * 2 + 3 * 1) == False isTopSort [] ( == True isTopSort [x] (& x) == True isTopSort [x] ( x x) == False ! 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] )] !      !/      !2      !      ! (c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone :DILORT$"The "U datatype is the Boehm-Berarducci encoding of the core graph construction primitives #, $, & and '. We define a law-abiding ; 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 (# :: 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:& 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 graph expression. For example, if g is a " then n, m and s can be computed as follows: n == 1 g m == 2 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. Complexity: O(1) time, memory and size. - empty == True / x empty == False 1 empty == 0 2 empty == 0 . empty == 1 $Construct the graph comprising a single isolated vertex. Complexity: O(1) time, memory and size. - (vertex x) == False / x (vertex x) == True / 1 (vertex 2) == False 1 (vertex x) == 1 2 (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) 0 x y (edge x y) == True 2 (edge x y) == 1 1 (edge 1 1) == 1 1 (edge 1 2) == 2 &Overlay] two graphs. 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 1 (overlay x y) >= 1 x 1 (overlay x y) <= 1 x + 1 y 2 (overlay x y) >= 2 x 2 (overlay x y) <= 2 x + 2 y . (overlay x y) == . x + . y 1 (overlay 1 2) == 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(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 1 (connect x y) >= 1 x 1 (connect x y) <= 1 x + 1 y 2 (connect x y) >= 2 x 2 (connect x y) >= 2 y 2 (connect x y) >= 1 x * 1 y 2 (connect x y) <= 1 x * 1 y + 2 x + 2 y . (connect x y) == . x + . y 1 (connect 1 2) == 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 1 . vertices ==  .  5 . 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 2 . 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 ==  - ,2Generalised graph folding: recursively collapse a " by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: 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) (&&) (&&) == - -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 >= 1 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 05Check 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 . < x y == const False 10The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount # == 0 vertexCount ($# x) == 1 vertexCount ==  . 3 2-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 ==  . 4 3;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList # == [] vertexList ($ x) == [x] vertexList . ( ==  .  42The 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 (star' 2 [3,1]) == [(2,1), (2,3)] edgeList . ) ==  .  53The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet # == Set. vertexSet . $ == Set. vertexSet . ( == Set. vertexSet . clique == Set. 6+The set of vertices of a given graph. Like 53 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 . clique == IntSet. 70The 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. 8 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 == E (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')) ] 9 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 == E (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')) ] : Construct a De Bruijn graphC of given dimension and symbols of a given alphabet. Complexity:  O(A * D^A) time, memory and size, where A" is the size of the alphabet and D is the dimention of the graph. deBruijn k [] == # deBruijn 1 [0,1] == )D [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == % "00" "00" deBruijn 2 "01" == ) [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ] ;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) time and memory. 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 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) == $# 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 A\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 # == # gmap f ($ x) == $ (f x) gmap f (% x y) == %G (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) BoTransform 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 # f == # bind ($ x) f == f x bind (% x y) f == ' (f x) (f y) bind (( xs) f == * ( f xs) bind x (const #) == # bind x $A == x bind (bind x f) g == bind x (\y -> bind (f y) g) CConstruct 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)  isSubgraphOf (induce p x) x == True DVSimplify 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 . (simplify x) <= . x simplify # ~> #q simplify 1 ~> 1 simplify (1 + 1) ~> 1 simplify (1 + 2 + 1) ~> 1 + 2 simplify (1 * 1 * 1) ~> 1 * 1 E 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 &, has singleton graphs as  identities and # as the annihilating zero. Below ~~5 stands for the equality up to an isomorphism, e.g.  (x, ()) ~~ x. Mbox 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 # ~~ # @"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRST-:;<=>?@AB"#$%&'()*+,-./0123456789:;<=>?@ABCDE-"#$%&'()*+:,;-./01234567<=>?@AB89:;<=>?@ABCDE:"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRST(c) Andrey Mokhov 2016-2017MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone 234:DILRT,UThe UH datatype is a deep embedding of the core graph construction primitives Z, [, ] and ^. We define a law-abiding ; 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 Z 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 Z# 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 U$ expression. For example, if g is a U then n, m and s can be computed as follows: n == k g m == l g s == h g Note that h is slightly different from the  method of the * type class, as the latter does not count Z leaves of the expression:  Z == 0 h Z == 1  ([ x) == 1 h ([ x) == 1  (Z + Z) == 0 h (Z + Z) == 2The h. of any graph is positive, and the difference (h g -  g)- corresponds to the number of occurrences of Z in an expression g. Converting a U 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.ZConstruct the  empty graph. An alias for the constructor V. Complexity: O(1) time, memory and size. g empty == True i x empty == False k empty == 0 l empty == 0 h empty == 1 [Construct the graph comprising a single isolated vertex . An alias for the constructor W. Complexity: O(1) time, memory and size. g (vertex x) == False i x (vertex x) == True i 1 (vertex 2) == False k (vertex x) == 1 l (vertex x) == 0 h (vertex x) == 1 \Construct the graph comprising  a single edge. Complexity: O(1) time, memory and size. edge x y == ^ ([ x) ([ y) j x y (edge x y) == True l (edge x y) == 1 k (edge 1 1) == 1 k (edge 1 2) == 2 ]Overlay* two graphs. An alias for the constructor XR. This is an idempotent, commutative and associative operation with the identity Z. Complexity: O(1) time and memory,  O(s1 + s2) size. g (overlay x y) == g x && g y i z (overlay x y) == i z x || i z y k (overlay x y) >= k x k (overlay x y) <= k x + k y l (overlay x y) >= l x l (overlay x y) <= l x + l y h (overlay x y) == h x + h y k (overlay 1 2) == 2 l (overlay 1 2) == 0 ^Connect* two graphs. An alias for the constructor Y6. This is an associative operation with the identity ZV, 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). g (connect x y) == g x && g y i z (connect x y) == i z x || i z y k (connect x y) >= k x k (connect x y) <= k x + k y l (connect x y) >= l x l (connect x y) >= l y l (connect x y) >= k x * k y l (connect x y) <= k x * k y + l x + l y h (connect x y) == h x + h y k (connect 1 2) == 2 l (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 [] == Z vertices [x] == [ x i x . vertices ==  x k . vertices ==  .  o . 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 [] == Z edges [(x,y)] == \ x y l . edges ==  .  a-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 [] == Z/ overlays [x] == x overlays [x,y] == ] x y g . overlays ==  g b-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 [] == Z/ connects [x] == x connects [x,y] == ^ x y g . connects ==  g c1Construct 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 [] [] == Z graph [x] [] == [ x graph [] [(x,y)] == \ x y graph vs es == ] (_ vs) (` es) d Generalised U! folding: recursively collapse a U 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 h is O(s) , since all functions have cost O(1). foldg Z [ ] ^ == id foldg Z [ ] (flip ^) == 5 foldg [] return (++) (++) == )*5 foldg 0 (const 1) (+) (+) == )+5 foldg 1 (const 1) (+) (+) == h5 foldg True (const False) (&&) (&&) == g eThe e' 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 Z- x == True isSubgraphOf ([ x) Z. == False isSubgraphOf x (] x y) == True isSubgraphOf (] x y) (^ x y) == True isSubgraphOf (r xs) (s xs) == True f7Structural equality on graph expressions. Complexity: O(s) time. * x === x == True x === x + Z` == False x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False g2Check if a graph is empty. A convenient alias for . Complexity: O(s) time. isEmpty Z( == True isEmpty (] Z Z) == True isEmpty ([' x) == False isEmpty (| x $ [ x) == True isEmpty (} x y $ \ x y) == False hThe sizeD of a graph, i.e. the number of leaves of the expression including Z leaves. Complexity: O(s) time. size Z == 1 size ([ x) == 1 size (] x y) == size x + size y size (^G x y) == size x + size y size x >= 1 size x >= k x iACheck if a graph contains a given vertex. A convenient alias for . Complexity: O(s) time.  hasVertex x Z" == False hasVertex x ([ x) == True hasVertex x . | x == const False j5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y Z" == False hasEdge x y ([ z) == False hasEdge x y (\" x y) == True hasEdge x y . } x y == const False k0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount Z == 0 vertexCount ([# x) == 1 vertexCount ==  . m l-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 Z == 0 edgeCount ([ x) == 0 edgeCount (\# x y) == 1 edgeCount ==  . n m;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList Z == [] vertexList ([ x) == [x] vertexList . _ ==  .  n2The 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 Z == [] edgeList ([ x) == [] edgeList (\ x y) == [(x,y)] edgeList (v' 2 [3,1]) == [(2,1), (2,3)] edgeList . ` ==  .  o3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet Z == Set. vertexSet . [ == Set. vertexSet . _ == Set. vertexSet . t == Set. p+The set of vertices of a given graph. Like o3 but specialised for graphs with vertices of type . Complexity:  O(s * log(n)) time and O(n) memory.  vertexIntSet Z == IntSet. vertexIntSet . [ == IntSet. vertexIntSet . _ == IntSet. vertexIntSet . t == IntSet. q0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory. edgeSet Z == Set. edgeSet ([ x) == Set. edgeSet (\ x y) == Set. (x,y) edgeSet . ` == Set. rThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] == Z path [x] == [ x path [x,y] == \ x y sThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] == Z circuit [x] == \ x x circuit [x,y] == ` [(x,y), (y,x)] tThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] == Z clique [x] == [ x clique [x,y] == \ x y clique [x,y,z] == ` [(x,y), (x,z), (y,z)] uThe 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 [] [] == Z biclique [x] [] == [ x biclique [] [y] == [ y biclique [x1,x2] [y1,y2] == `& [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] vThe 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)] wThe  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).xThe  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).y 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 [] == Z mesh [] ys == Z mesh [x] [y] == [ (x, y) mesh xs ys ==  (r xs) (r 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')) ] z 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 [] == Z torus [] ys == Z torus [x] [y] == \# (x, y) (x, y) torus xs ys ==  (s xs) (s 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 graphC of given dimension and symbols of a given alphabet. Complexity:  O(A * D^A) time, memory and size, where A" is the size of the alphabet and D is the dimention of the graph. deBruijn k [] == Z deBruijn 1 [0,1] == `D [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == \ "00" "00" deBruijn 2 "01" == ` [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ] |1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x ([ x) == Z3 removeVertex x . removeVertex x == removeVertex x }0Remove an edge from a given graph. Complexity: O(s) time and memory. 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 U. 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 Z == Z transpose ([ x) == [ x transpose (\ x y) == \! y x transpose . transpose == id 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 == Z induce (/= x) == |< x induce p . induce q == induce (\x -> p x && q x) e (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 h (simplify x) <= h x simplify Z f Z simplify 1 f 1 simplify (1 + 1) f 1 simplify (1 + 2 + 1) f 1 + 2 simplify (1 * 1 * 1) f 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 (r [0,1]) (r "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 Z as the annihilating zero. Below ~~5 stands for the equality up to an isomorphism, e.g.  (x, ()) ~~ x. Mbox 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 Z ~~ Z DUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~0UVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~0UVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~=UVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~f4./'01#2345(6!"789:%;&<=>?@AB-CDEF0G1#234H'(65!"78%;&<=>IJKLMNOPQRSTUVWXYZ[\]^_`abbcd'(65!"efg-hiBjklmnop78q9rs%;&<=>CDtuvwxyyz{{|}}~d'(65!"efs-hiB78q9:r%;&<=>CD $ $ c d ' ( 6 5 ! " e f g - h i B n o p  7 8     q   9  r s % ; & <  = > C D t u v w x  ' (  6 5 ! " 7 8   q   9 f  : r ? @ A - h C D E i B F H'(65!"78q9f:r%;&<=>?@A-hCDEBF../././././.).)+.).)''.../n n.).)*././     -algebraic-graphs-0.0.3-AAEBuopFD7jBRpfbH3panq Algebra.Graph.HigherKinded.ClassAlgebra.Graph.Class&Algebra.Graph.IntAdjacencyMap.InternalAlgebra.Graph.IntAdjacencyMapAlgebra.Graph.Relation.InternalAlgebra.Graph.RelationAlgebra.Graph.Relation.Preorder Algebra.Graph.Relation.Reflexive Algebra.Graph.Relation.Symmetric!Algebra.Graph.Relation.Transitive#Algebra.Graph.AdjacencyMap.InternalAlgebra.Graph.AdjacencyMapAlgebra.Graph.Fold Algebra.GraphGraphFoldControl.Applicative Alternative Data.ListnubsortRelationedgegraphisEmpty hasVertex vertexCount edgeCount vertexSetstar isSubgraphOf Data.GraphverticesedgesPreorder AdjacencyMappathcliqueemptyvertex Data.FoldabletoListlengthAlgebra.Graph.HigherKinded.Util removeVertexbaseGHC.BaseToGraphtoGraph Transitive Reflexive Undirectedconnectoverlayoverlaysconnects vertexList vertexIntSetcircuitbicliquetreeforestmeshtorusdeBruijninduce 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()IntAdjacencyMap adjacencyMap consistentfromAdjacencyListedgeList adjacencyList removeEdgegmap$fNumIntAdjacencyMap$fGraphIntAdjacencyMap$fShowIntAdjacencyMap$fEqIntAdjacencyMapGraphKLgetGraph getVertexhasEdgeedgeSetpostsetgraphKL fromGraphKL dfsForesttopSort isTopSortPreorderRelation fromPreorderTransitiveRelationfromTransitiveSymmetricRelation fromSymmetricReflexiveRelation fromReflexivedomainrelationpresetreflexiveClosuresymmetricClosuretransitiveClosurepreorderClosure$fPreorderPreorderRelation$fTransitivePreorderRelation$fReflexivePreorderRelation$fGraphPreorderRelation$fEqPreorderRelation$fShowPreorderRelation$fTransitiveTransitiveRelation$fGraphTransitiveRelation$fShowTransitiveRelation$fEqTransitiveRelation$fUndirectedSymmetricRelation$fGraphSymmetricRelation$fShowSymmetricRelation$fEqSymmetricRelation$fReflexiveReflexiveRelation$fGraphReflexiveRelation$fShowReflexiveRelation$fEqReflexiveRelation $fNumRelation$fGraphRelation$fShowRelation $fEqRelation$fNumReflexiveRelation$fNumSymmetricRelation$fNumTransitiveRelation$fNumPreorderRelation fromRelation toRelation neighbours$fNumAdjacencyMap$fGraphAdjacencyMap$fShowAdjacencyMap$fEqAdjacencyMapsccfoldgsize transposebindsimplify $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.TreeTreeForestGHC.NumNumShow GHC.ClassesEqfmap toAscList><Foldable>>=mapPiecesPiecepieceintacttrivialrunFold edgelessPiecebreakIf nonTrivialsmashsimple