!  Ur      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                  ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopq(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone <FKNTViaalgebraic-graphsThe X data type represents a graph by a map of vertices to their adjacency sets. We define a r; 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 s? instance is defined using basic graph construction primitives: lshow (empty :: AdjacencyIntMap Int) == "empty" show (1 :: AdjacencyIntMap Int) == "vertex 1" show (1 + 2 :: AdjacencyIntMap Int) == "vertices [1,2]" show (1 * 2 :: AdjacencyIntMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyIntMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyIntMap Int) == "overlay (vertex 3) (edge 1 2)"The t3 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.algebraic-graphsThe  adjacency map[ of the graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory. adjacencyIntMap  == IntMap.u adjacencyIntMap ( x) == IntMap.v x IntSet.w adjacencyIntMap (  1 1) == IntMap.v 1 (IntSet.x 1) adjacencyIntMap (  1 2) == IntMap.y [(1,IntSet.x 2), (2,IntSet.w)] algebraic-graphsConstruct the  empty graph. Complexity: O(1) time and memory.   empty == True   x empty == False   empty == 0   empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.   (vertex x) == False   x (vertex x) == True   (vertex x) == 1   (vertex x) == 0 algebraic-graphsOverlay\ two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O((n + m) * log(n)) time and O(n + m) memory.   (overlay x y) ==   x &&   y   z (overlay x y) ==   z x ||   z y   (overlay x y) >=   x   (overlay x y) <=   x +   y   (overlay x y) >=   x   (overlay x y) <=   x +   y   (overlay 1 2) == 2   (overlay 1 2) == 0 algebraic-graphsConnectA two graphs. This is an associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).   (connect x y) ==   x &&   y   z (connect x y) ==   z x ||   z y   (connect x y) >=   x   (connect x y) <=   x +   y   (connect x y) >=   x   (connect x y) >=   y   (connect x y) >=   x *   y   (connect x y) <=   x *   y +   x +   y   (connect 1 2) == 2   (connect 1 2) == 1 algebraic-graphs>Construct a graph from a list of adjacency sets. Complexity: O((n + m) * log(n)) time and O(n + m) memory. EfromAdjacencyIntSets [] ==  " fromAdjacencyIntSets [(x, IntSet.w)] ==  $ x fromAdjacencyIntSets [(x, IntSet.x y)] ==  - x y fromAdjacencyIntSets . map (fmap IntSet.z) .  ! == id  ^ (fromAdjacencyIntSets xs) (fromAdjacencyIntSets ys) == fromAdjacencyIntSets (xs ++ ys) algebraic-graphsCheck 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) == True   (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone <FKNTValgebraic-graphsThe X data type represents a graph by a map of vertices to their adjacency sets. We define a r; 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 s? instance is defined using basic graph construction primitives: Zshow (empty :: AdjacencyMap Int) == "empty" show (1 :: AdjacencyMap Int) == "vertex 1" show (1 + 2 :: AdjacencyMap Int) == "vertices [1,2]" show (1 * 2 :: AdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"The t3 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.algebraic-graphsThe  adjacency map[ of the graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory.  adjacencyMap  == Map.{ adjacencyMap ( x) == Map.| x Set.} adjacencyMap (  1 1) == Map.| 1 (Set.~ 1) adjacencyMap (  1 2) == Map. [(1,Set.~ 2), (2,Set.})] algebraic-graphsConstruct the  empty graph. Complexity: O(1) time and memory.   empty == True   x empty == False   empty == 0   empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.   (vertex x) == False   x (vertex x) == True   (vertex x) == 1   (vertex x) == 0 algebraic-graphsOverlay\ two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O((n + m) * log(n)) time and O(n + m) memory.   (overlay x y) ==   x &&   y   z (overlay x y) ==   z x ||   z y   (overlay x y) >=   x   (overlay x y) <=   x +   y   (overlay x y) >=   x   (overlay x y) <=   x +   y   (overlay 1 2) == 2   (overlay 1 2) == 0 algebraic-graphsConnectA two graphs. This is an associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2). isEmpty (connect x y) == isEmpty x &&   y  hasVertex z (connect x y) ==  hasVertex z x ||   z y  vertexCount (connect x y) >=  vertexCount x  vertexCount (connect x y) <=  vertexCount x +   y  edgeCount (connect x y) >=  edgeCount x  edgeCount (connect x y) >=  edgeCount y  edgeCount (connect x y) >=  vertexCount x *   y  edgeCount (connect x y) <=  vertexCount x *   y +   x +   y  vertexCount (connect 1 2) == 2  edgeCount (connect 1 2) == 1 algebraic-graphs>Construct a graph from a list of adjacency sets. Complexity: O((n + m) * log(n)) time and O(n + m) memory. ?fromAdjacencySets [] ==   fromAdjacencySets [(x, Set.})] ==   x fromAdjacencySets [(x, Set.~ y)] ==  ' x y fromAdjacencySets . map (fmap Set.) .  ! == id  U (fromAdjacencySets xs) (fromAdjacencySets ys) == fromAdjacencySets (xs ++ ys) algebraic-graphsCheck 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) == True  (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV* algebraic-graphsAn auxiliary data type for hasEdge.: when searching for an edge, we can hit its $, i.e. the source vertex, the whole , or  it entirely.algebraic-graphsThe focus of a graph expression is a flattened represenentation of the subgraph under focus, its context, as well as the list of all encountered vertices. See  $ for a use-case example. algebraic-graphs.All vertices (leaves) of the graph expression.!algebraic-graphs4True if focus on the specified subgraph is obtained."algebraic-graphs!Inputs into the focused subgraph.#algebraic-graphs$Outputs out of the focused subgraph.%algebraic-graphs An abstract list data type with O(1)N time concatenation (the current implementation uses difference lists). Here a is the type of list elements. % a is a : G corresponds to the empty list and two lists can be concatenated with  (or operator %&:). Singleton lists can be constructed using the function  from the  instance. % a is also an instance of IsList-, therefore you can use list literals, e.g. [1,4] :: % Int is the same as  1 %&  4; note that this requires the OverloadedLists@ GHC extension. To extract plain Haskell lists you can use the  function from the  instance.'algebraic-graphsFocus on the empty graph.(algebraic-graphsiFocus on the graph with a single vertex, given a predicate indicating whether the vertex is of interest.)algebraic-graphsOverlay two foci.*algebraic-graphsConnect two foci.+algebraic-graphsA safe version of  #$"!%&'()*+%& #$"!'()*+(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV8algebraic-graphsA distance% is a non-negative value that can be 9 or :.;algebraic-graphsA dioid is an idempotent semiring', i.e. it satisfies the following laws:Associativity: x /\ (y /\ z) == (x /\ y) /\ z Identity: x /\ one == x one /\ x == xAnnihilating zero: #x /\ zero == zero zero /\ x == zeroDistributivity: Cx /\ (y \/ z) == x /\ y \/ x /\ z (x \/ y) /\ z == x /\ z \/ y /\ z>algebraic-graphsA bounded join semilattice , satisfying the following laws:Commutativity: x \/ y == y \/ xAssociativity: x \/ (y \/ z) == (x \/ y) \/ z Identity: x \/ zero == x Idempotence:  x \/ x == x 89:;<=>?@ >?@;<=89:=7@6(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone <FKNTV Jalgebraic-graphsThe J# data type represents a graph as a binary relation. We define a r; 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 s? instance is defined using basic graph construction primitives: Bshow (empty :: Relation Int) == "empty" show (1 :: Relation Int) == "vertex 1" show (1 + 2 :: Relation Int) == "vertices [1,2]" show (1 * 2 :: Relation Int) == "edge 1 2" show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"The t3 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.Lalgebraic-graphsThe domain of the relation.Malgebraic-graphs&The set of pairs of elements that are related<. It is guaranteed that each element belongs to the domain.Nalgebraic-graphsConstruct the  empty graph. Complexity: O(1) time and memory.  empty == True  x empty == False  empty == 0  empty == 0 Oalgebraic-graphsConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.  (vertex x) == False  x (vertex x) == True  (vertex x) == 1  (vertex x) == 0 Palgebraic-graphsOverlay\ two graphs. This is a commutative, associative and idempotent operation with the identity N. Complexity: O((n + m) * log(n)) time and O(n + m) memory.  (overlay x y) ==  x &&  'iAlgebra.Graph.Relation.sEmpty' 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 Qalgebraic-graphsConnectA two graphs. This is an associative operation with the identity N, which distributes over P1 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 Ralgebraic-graphs+Compute the Cartesian product of two sets. ,Note: this function is for internal use only.Salgebraic-graphshCheck if the internal representation of a relation is consistent, i.e. if all pairs of elements in the M# refer to existing elements in the L5. It should be impossible to create an inconsistent J), 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) == True Talgebraic-graphs:The set of elements that appear in a given set of pairs. ,Note: this function is for internal use only. JKLMNOPQRST JKLMNOPQRST(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV='Yalgebraic-graphsConstruct the graph comprising  a single edge. Complexity: O(1) time, memory and size. edge x y == Q (O x) (O y) a x y (edge x y) == True c (edge x y) == 1 b (edge 1 1) == 1 b (edge 1 2) == 2 Zalgebraic-graphsOConstruct 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 b . vertices ==  . '( f . vertices == Set. [algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] == N edges [(x,y)] == Y x y c . edges ==  . '( \algebraic-graphs-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] == P x y overlays ==  P N _ . overlays ==  _ ]algebraic-graphs-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] == Q x y connects ==  Q N _ . connects ==  _ ^algebraic-graphsThe ^' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf N- x == True isSubgraphOf (O x) N. == False isSubgraphOf x (P x y) == True isSubgraphOf (P x y) (Q x y) == True isSubgraphOf (l xs) (m xs) == True _algebraic-graphs+Check if a relation is empty. Complexity: O(1) time. isEmpty N( == True isEmpty (P N N) == True isEmpty (O' x) == False isEmpty (t x $ O x) == True isEmpty (u x y $ Y x y) == False `algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x N" == False hasVertex x (O x) == True hasVertex 1 (O! 2) == False hasVertex x . t x == const False aalgebraic-graphs5Check 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 (Y" x y) == True hasEdge x y . u4 x y == const False hasEdge x y ==  (x,y) . e balgebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount N == 0 vertexCount (O# x) == 1 vertexCount ==  . d calgebraic-graphs-The number of edges in a graph. Complexity: O(1) time.  edgeCount N == 0 edgeCount (O x) == 0 edgeCount (Y# x y) == 1 edgeCount ==  . e dalgebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList N == [] vertexList (O x) == [x] vertexList . Z == '( . ') ealgebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList N == [] edgeList (O x) == [] edgeList (Y x y) == [(x,y)] edgeList (p' 2 [3,1]) == [(2,1), (2,3)] edgeList . [ == '( . ') edgeList . x == ') . map  . edgeList falgebraic-graphs3The set of vertices of a given graph. Complexity: O(1) time.  vertexSet N == Set.} vertexSet . O == Set.~ vertexSet . Z == Set. vertexSet . n == Set. galgebraic-graphs+The set of vertices of a given graph. Like f3 but specialised for graphs with vertices of type . Complexity: O(n) time.  vertexIntSet N == IntSet.w vertexIntSet . O == IntSet.x vertexIntSet . Z == IntSet.z vertexIntSet . n == IntSet.z halgebraic-graphs0The set of edges of a given graph. Complexity: O(1) time. edgeSet N == Set.} edgeSet (O x) == Set.} edgeSet (Y x y) == Set.~ (x,y) edgeSet . [ == Set. ialgebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory. adjacencyList N == [] adjacencyList (O$ x) == [(x, [])] adjacencyList (Y0 1 2) == [(1, [2]), (2, [])] adjacencyList (p, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] q . adjacencyList == id jalgebraic-graphsThe preset of an element x7 is the set of elements that are related to it on the left, i.e. preSet x == { a | aRx }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 N == Set.} preSet x (O x) == Set.} preSet 1 (Y 1 2) == Set.} preSet y (Y x y) == Set. [x] kalgebraic-graphsThe postset of an element x7 is the set of elements that are related to it on the right, i.e. postSet x == { a | xRa }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 N == Set.} postSet x (O x) == Set.} postSet x (Y x y) == Set. [y] postSet 2 (Y 1 2) == Set.} lalgebraic-graphsThe 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] == Y x y path .  == x . path malgebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] == N circuit [x] == Y x x circuit [x,y] == [ [(x,y), (y,x)] circuit .  == x . circuit nalgebraic-graphsThe 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] == Y x y clique [x,y,z] == [, [(x,y), (x,z), (y,z)] clique (xs ++ ys) == Q" (clique xs) (clique ys) clique .  == x . clique oalgebraic-graphsThe biclique( on two lists 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] == [B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == Q (Z xs) (Z ys) palgebraic-graphsThe starG formed by a centre vertex connected to a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] == O x star x [y] == Y x y star x [y,z] == [ [(x,y), (x,z)] star x ys == Q (O x) (Z ys) qalgebraic-graphsThe stars formed by overlaying a list of ps. An inverse of i. Complexity:  O(L * log(n)) time, memory and size, where L! is the total size of the input. !stars [] == N" stars [(x, [])] == O$ x stars [(x, [y])] == Y& x y stars [(x, ys)] == p' x ys stars == \ . map (uncurry p ) stars . i == id P+ (stars xs) (stars ys) == stars (xs ++ ys) ralgebraic-graphsThe  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 []]]) == lE [x,y,z] tree (Node x [Node y [], Node z []]) == pE x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == [ [(1,2), (1,3), (3,4), (3,5)] salgebraic-graphsThe  forest graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. >forest [] == N? forest [x] == rA x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == [U [(1,2), (1,3), (4,5)] forest == \ . map r talgebraic-graphs1Remove a vertex from a given graph. Complexity: O(n + m) time. removeVertex x (O x) == N removeVertex 1 (O 2) == O 2 removeVertex x (Y x x) == N removeVertex 1 (Y 1 2) == O5 2 removeVertex x . removeVertex x == removeVertex x ualgebraic-graphs0Remove an edge from a given graph. Complexity:  O(log(m)) time. removeEdge x y (* x y) == ZJ [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . t x == ta x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 valgebraic-graphs The function v 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 (O x) == O# y replaceVertex x y == w (== x) y walgebraic-graphsNMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))* time, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == vY x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 xalgebraic-graphs&Transpose a given graph. Complexity:  O(m * log(m)) time.  transpose N == N transpose (O x) == O x transpose (Y x y) == Y! y x transpose . transpose == id e . transpose == ') . map  . e yalgebraic-graphsVTransform 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 J. Complexity: O((n + m) * log(n)) time. gmap f N == N gmap f (O x) == O (f x) gmap f (Y x y) == YG (f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g) zalgebraic-graphsConstruct 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) == t< x induce p . induce q == induce (\x -> p x && q x) ^ (induce p x) x == True {algebraic-graphsCompose 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 N as the annihilating zero. Complexity: O(n * m * log(m)) time and O(n + m) memory. compose N x == N compose x N == NO compose x (compose y z) == compose (compose x y) z compose (Y y z) (Y x y) == Y x z compose (l [1..5]) (l [1..5]) == [ [(1,3),(2,4),(3,5)] compose (m [1..5]) (m [1..5]) == m [1,3,5,2,4] |algebraic-graphs Compute the reflexive closure of a J. Complexity:  O(n * log(m)) time. reflexiveClosure N == N reflexiveClosure (O x) == Y x x }algebraic-graphs Compute the symmetric closure of a J. Complexity:  O(m * log(m)) time. symmetricClosure N == N symmetricClosure (O x) == O x symmetricClosure (Y x y) == [ [(x, y), (y, x)] ~algebraic-graphs Compute the transitive closure of a J. Complexity: O(n * m * log(n) * log(m)) time. transitiveClosure N == N transitiveClosure (O x) == O x transitiveClosure (l $ '( xs) == n ('( xs) algebraic-graphs Compute the preorder closure of a J. Complexity: O(n * m * log(m)) time. preorderClosure N == N preorderClosure (O x) == Y x x preorderClosure (l $ '( xs) == | (n $ '( xs) .JMLNOPQYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~.JLMNOYPQZ[\]^_`abcdeifghjklmnopqrstuvwxyz{|}~+(c) Anton Lorenzen, Andrey Mokhov 2016-2018MIT (see the file LICENSE)*anfelor@posteo.de, andrey.mokhov@gmail.comunstableNone <FKNTV algebraic-graphsD encapsulates King-Launchbury graphs, which are implemented in the  Data.Graph module of the  containers library.algebraic-graphs=Array-based graph representation (King and Launchbury, 1995).algebraic-graphs A mapping of Data.Graph.Vertex to vertices of type a?. This is partial and may fail if the vertex is out of bounds.algebraic-graphs A mapping from vertices of type a to Data.Graph.Vertex . Returns % if the argument is not in the graph.algebraic-graphsBuild  from an . If fromAdjacencyMap g == h then the following holds: map ( h) (+, $ % h) ==  - g map (\(x, y) -> ( h x,  h y)) (+" $  h) ==  . g F (fromAdjacencyMap (1 * 2 + 3 * 1)) == array" (0,2) [(0,[1]), (1,[]), (2,[0])] F (fromAdjacencyMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])] algebraic-graphsBuild  from an . If fromAdjacencyIntMap g == h then the following holds: map ( h) (+, $ % h) == /0 ( 1 g) map (\(x, y) -> ( h x,  h y)) (+" $  h) ==  . g F (fromAdjacencyIntMap (1 * 2 + 3 * 1)) == array" (0,2) [(0,[1]), (1,[]), (2,[0])] F (fromAdjacencyIntMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])] algebraic-graphs Compute the depth-first search forest of a graph.1In the following we will use the helper function: U(%) :: (GraphKL Int -> a) -> AM.AdjacencyMap Int -> a a % g = a $ fromAdjacencyMap g Dfor greater clarity. (One could use an AdjacencyIntMap just as well)  2 (dfsForest %   1 1) ==  1  2 (dfsForest %   1 2) ==   1 2  2 (dfsForest %   2 1) == 3, [1, 2] 34 ( 2( $ dfsForest % x) x == True dfsForest %  23 (dfsForest % x) == dfsForest % x dfsForest % 3,. vs == map (\v -> Node v []) ('( $ ') vs)  5 ( - 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 = [] }]}] algebraic-graphs Compute the depth-first search forest of a graph, searching from each of the given vertices in order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable.  2 (dfsForestFrom [1] %   1 1) ==  1  2 (dfsForestFrom [1] %   1 2) ==   1 2  2 (dfsForestFrom [2] %   1 2) ==  2  2 (dfsForestFrom [3] %   1 2) ==   2 (dfsForestFrom [2, 1] %   1 2) ==  , [1, 2]  4 ( 22 $ dfsForestFrom vs % x) x == True dfsForestFrom ( - x) % x == & % x dfsForestFrom vs %  , vs == map (\v -> Node v []) ('( vs) dfsForestFrom [] % x == [] dfsForestFrom [1, 4] % (3 * (1 + 4) * (1 + 5)) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] } , Node { rootLabel = 4 , subForest = [] }] algebraic-graphs,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]  4 ( , $ dfs vs x) x == True algebraic-graphs Compute the topological sorth of a graph. Unlike the (Int)AdjacencyMap algorithm this returns a result even if the graph is cyclic. HtopSort % (1 * 2 + 3 * 1) == [3,1,2] topSort % (1 * 2 + 2 * 1) == [1,2] (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV#+algebraic-graphsConstruct 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 algebraic-graphsOConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x  x . vertices ==  x  . vertices ==  . '(  . vertices == Set. algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] ==  edges [(x,y)] ==  x y  . edges ==  . '(  . edges == '( . ') algebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==   algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf - x == True isSubgraphOf ( x) . == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True algebraic-graphs(Check if a graph is empty. Complexity: O(1) time. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty ( x $  x) == True isEmpty ( x y $  x y) == False algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x .  x == const False algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y . 4 x y == const False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (# x) == 1 vertexCount ==  .  algebraic-graphs-The number of edges in a graph. Complexity: O(n) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  == '( . ') algebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList  == [] edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList .  == '( . ') edgeList .  == ') . map 67 . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexSet  == Set.} vertexSet .  == Set.~ vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs+The set of vertices of a given graph. Like 3 but specialised for graphs with vertices of type . Complexity: O(n) time and memory.  vertexIntSet  == IntSet.w vertexIntSet .  == IntSet.x vertexIntSet .  == IntSet.z vertexIntSet .  == IntSet.z algebraic-graphs0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet  == Set.} edgeSet ( x) == Set.} edgeSet ( x y) == Set.~ (x,y) edgeSet .  == Set. algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (0 1 2) == [(1, [2]), (2, [])] adjacencyList (, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]  . adjacencyList == id algebraic-graphsThe preset of an element x is the set of its direct predecessors. Complexity:  O(n * log(n)) time and O(n) memory.  preSet x  == Set.} preSet x ( x) == Set.} preSet 1 ( 1 2) == Set.} preSet y ( x y) == Set. [x] algebraic-graphsThe postset of a vertex is the set of its direct successors. Complexity:  O(log(n)) time and O(1) memory.  postSet x  == Set.} postSet x ( x) == Set.} postSet x ( x y) == Set. [y] postSet 2 ( 1 2) == Set.} algebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] ==  path [x] ==  x path [x,y] ==  x y path .  ==  . path algebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] circuit .  ==  . circuit algebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) == " (clique xs) (clique ys) clique .  ==  . clique algebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe starG formed by a centre vertex connected to a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity:  O(L * log(n)) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  . map (uncurry  ) stars .  == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsThe  tree graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. <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)] algebraic-graphsThe  forest graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. >forest [] == ? forest [x] == A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == U [(1,2), (1,3), (4,5)] forest ==  . map  algebraic-graphs1Remove a vertex from a given graph. Complexity:  O(n*log(n)) time. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y ( x y) == J [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 algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsNMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))* time, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 algebraic-graphs&Transpose a given graph. Complexity:  O(m * log(n)) time, O(n + m) memory.  transpose  ==  transpose ( x) ==  x transpose ( x y) == ! y x transpose . transpose == id  . transpose == ') . map 67 .  algebraic-graphsVTransform 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) algebraic-graphsConstruct 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 algebraic-graphs Compute the depth-first searchY forest of a graph that corresponds to searching from each of the graph vertices in the  a order.  dfsForest  == []  (dfsForest $  1 1) ==  1  (dfsForest $  1 2) ==  1 2  (dfsForest $  2 1) ==  [1,2]  ( $ dfsForest x) x == True - (dfsForest x) x == True dfsForest . , . dfsForest == dfsForest dfsForest (- vs) == 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 = [] }]}] algebraic-graphs Compute the depth-first search forest of a graph, searching from each of the given vertices in order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. dfsForestFrom vs ! == []  (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]  (% $ dfsForestFrom vs x) x == True  (dfsForestFrom ( x) x) x == True dfsForestFrom ( x) x == ! x dfsForestFrom vs (% vs) == map (\v -> Node v []) ('( vs) dfsForestFrom [] x == [] dfsForestFrom [1,4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] } , Node { rootLabel = 4 , subForest = [] }] algebraic-graphs,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 vs $ & == [] 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] $ y 1 2 == [2,1] dfs [] $ x == [] dfs [1,4] $ 3 * (1 + 4) * (1 + 5) == [1,5,4]  ( $ dfs vs x) x == True algebraic-graphs&Compute the list of vertices that are  reachable[ from a given source vertex in a graph. The vertices in the resulting list appear in the depth-first order. reachable x $ + == [] reachable 1 $ + 1 == [1] reachable 1 $ * 2 == [] reachable 1 $ - 1 1 == [1] reachable 1 $ / 1 2 == [1,2] reachable 4 $ 0 [1..8] == [4..8] reachable 4 $ 7 [1..8] == [4..8] ++ [1..3] reachable 8 $ ' [8,7..1] == [8] ++ [1..7]  ( $ reachable x y) y == True algebraic-graphs Compute the topological sort of a graph or return Nothing if the graph is cyclic. rtopSort (1 * 2 + 3 * 1) == Just [3,1,2] topSort (1 * 2 + 2 * 1) == Nothing fmap (flip  x) (topSort x) /= Just False # . topSort ==  algebraic-graphsCheck if a given graph is acyclic. QisAcyclic (1 * 2 + 3 * 1) == True isAcyclic (1 * 2 + 2 * 1) == False isAcyclic .  ==  isAcyclic ==  .  algebraic-graphs Compute the  condensation1 of a graph, where each vertex corresponds to a strongly-connected component of the original graph. 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] )] algebraic-graphs%Check if a given forest is a correct depth-first search forest of a graph. The implementation is based on the paper "Depth-First Search and Strong Connectivity in Coq" by Franois Pottier. .isDfsForestOf [] C == True isDfsForestOf [] (B 1) == False isDfsForestOf [Node 1 []] (A 1) == True isDfsForestOf [Node 1 []] (B 2) == False isDfsForestOf [Node 1 [], Node 1 []] (B 1) == False isDfsForestOf [Node 1 []] (C 1 1) == True isDfsForestOf [Node 1 []] (D 1 2) == False isDfsForestOf [Node 1 [], Node 2 []] (D 1 2) == False isDfsForestOf [Node 2 [], Node 1 []] (C 1 2) == True isDfsForestOf [Node 1 [Node 2 []]] (C 1 2) == True isDfsForestOf [Node 1 [], Node 2 []] (? [1,2]) == True isDfsForestOf [Node 2 [], Node 1 []] (? [1,2]) == True isDfsForestOf [Node 1 [Node 2 []]] (@ [1,2]) == False isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] (C [1,2,3]) == True isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] (D [1,2,3]) == False isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (C [1,2,3]) == True isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (C [1,2,3]) == True isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] ( [1,2,3]) == False algebraic-graphs/Check if a given list of vertices is a correct topological sort of a graph. isTopSortOf [3,1,2] (1 * 2 + 3 * 1) == True isTopSortOf [1,2,3] (1 * 2 + 3 * 1) == False isTopSortOf [] (1 * 2 + 3 * 1) == False isTopSortOf [] ( == True isTopSortOf [x] (& x) == True isTopSortOf [x] ( x x) == False 11 (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV%)algebraic-graphsConstruct 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 algebraic-graphsOConstruct the graph comprising a given list of isolated vertices. Complexity:  O(L * log(L)) time and O(L) memory, where L" is the length of the given list. vertices [] ==  vertices [x] ==  x  x . vertices ==  x  . vertices ==  . '(  . vertices == IntSet.z algebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory. edges [] ==  edges [(x,y)] ==  x y  . edges ==  . '(  . edges == '( . ') algebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==   algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.  isSubgraphOf - x == True isSubgraphOf ( x) . == False isSubgraphOf x ( x y) == True isSubgraphOf ( x y) ( x y) == True isSubgraphOf ( xs) ( xs) == True algebraic-graphs(Check if a graph is empty. Complexity: O(1) time. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty ( x $  x) == True isEmpty ( x y $  x y) == False algebraic-graphs7Check if a graph contains a given vertex. Complexity:  O(log(n)) time.  hasVertex x " == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x .  x == const False algebraic-graphs5Check if a graph contains a given edge. Complexity:  O(log(n)) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y . 4 x y == const False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.  vertexCount  == 0 vertexCount (# x) == 1 vertexCount ==  .  algebraic-graphs-The number of edges in a graph. Complexity: O(n) time.  edgeCount  == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  == '( . ') algebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.  edgeList  == [] edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList .  == '( . ') edgeList .  == ') . map 67 . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory.  vertexIntSet  == IntSet.w vertexIntSet .  == IntSet.x vertexIntSet .  == IntSet.z vertexIntSet .  == IntSet.z algebraic-graphs0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet  == Set.} edgeSet ( x) == Set.} edgeSet ( x y) == Set.~ (x,y) edgeSet .  == Set. algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (0 1 2) == [(1, [2]), (2, [])] adjacencyList (, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]  . adjacencyList == id algebraic-graphsThe preset (here  preIntSet) of an element x is the set of its direct predecessors. Complexity:  O(n * log(n)) time and O(n) memory.  preIntSet x  == Set.} preIntSet x ( x) == Set.} preIntSet 1 ( 1 2) == Set.} preIntSet y ( x y) == Set. [x] algebraic-graphsThe postset (here  postIntSet!) of a vertex is the set of its direct successors.  postIntSet x  == IntSet.w postIntSet x ( x) == IntSet.w postIntSet x ( x y) == IntSet.z [y] postIntSet 2 ( 1 2) == IntSet.w algebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. path [] ==  path [x] ==  x path [x,y] ==  x y path .  ==  . path algebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] circuit .  ==  . circuit algebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) == " (clique xs) (clique ys) clique .  ==  . clique algebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe starG formed by a centre vertex connected to a list of leaves. Complexity: O((n + m) * log(n)) time and O(n + m) memory. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity:  O(L * log(n)) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  . map (uncurry  ) stars .  == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsThe  tree graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. <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)] algebraic-graphsThe  forest graph constructed from a given  data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory. >forest [] == ? forest [x] == A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == U [(1,2), (1,3), (4,5)] forest ==  . map  algebraic-graphs1Remove a vertex from a given graph. Complexity:  O(n*log(n)) time. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity:  O(log(n)) time. removeEdge x y ( x y) == J [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 algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsNMerge vertices satisfying a given predicate into a given vertex. Complexity: O((n + m) * log(n))* time, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 algebraic-graphs&Transpose a given graph. Complexity:  O(m * log(n)) time, O(n + m) memory.  transpose  ==  transpose ( x) ==  x transpose ( x y) == ! y x transpose . transpose == id  . transpose == ') . map 67 .  algebraic-graphsVTransform 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) algebraic-graphsConstruct 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 algebraic-graphs Compute the depth-first searchY forest of a graph that corresponds to searching from each of the graph vertices in the  a order.  dfsForest  == []  (dfsForest $  1 1) ==  1  (dfsForest $  1 2) ==  1 2  (dfsForest $  2 1) ==  [1,2]  ( $ dfsForest x) x == True - (dfsForest x) x == True dfsForest . , . dfsForest == dfsForest dfsForest (- vs) == 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 = [] }]}] algebraic-graphs Compute the depth-first search forest of a graph, searching from each of the given vertices in order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. dfsForestFrom vs ! == []  (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]  (% $ dfsForestFrom vs x) x == True  (dfsForestFrom ( x) x) x == True dfsForestFrom ( x) x == ! x dfsForestFrom vs (% vs) == map (\v -> Node v []) ('( vs) dfsForestFrom [] x == [] dfsForestFrom [1,4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1 , subForest = [ Node { rootLabel = 5 , subForest = [] } , Node { rootLabel = 4 , subForest = [] }] algebraic-graphs,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 vs $ & == [] 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] $ y 1 2 == [2,1] dfs [] $ x == [] dfs [1,4] $ 3 * (1 + 4) * (1 + 5) == [1,5,4]  ( $ dfs vs x) x == True algebraic-graphs&Compute the list of vertices that are  reachable[ from a given source vertex in a graph. The vertices in the resulting list appear in the depth-first order. reachable x $ + == [] reachable 1 $ + 1 == [1] reachable 1 $ * 2 == [] reachable 1 $ - 1 1 == [1] reachable 1 $ / 1 2 == [1,2] reachable 4 $ 0 [1..8] == [4..8] reachable 4 $ 7 [1..8] == [4..8] ++ [1..3] reachable 8 $ ' [8,7..1] == [8] ++ [1..7]  ( $ reachable x y) y == True algebraic-graphs Compute the topological sort of a graph or return Nothing if the graph is cyclic. rtopSort (1 * 2 + 3 * 1) == Just [3,1,2] topSort (1 * 2 + 2 * 1) == Nothing fmap (flip  x) (topSort x) /= Just False # . topSort ==  algebraic-graphsCheck if a given graph is acyclic. QisAcyclic (1 * 2 + 3 * 1) == True isAcyclic (1 * 2 + 2 * 1) == False isAcyclic .  ==  isAcyclic ==  .  algebraic-graphs%Check if a given forest is a correct depth-first search forest of a graph. The implementation is based on the paper "Depth-First Search and Strong Connectivity in Coq" by Franois Pottier. .isDfsForestOf [] C == True isDfsForestOf [] (B 1) == False isDfsForestOf [Node 1 []] (A 1) == True isDfsForestOf [Node 1 []] (B 2) == False isDfsForestOf [Node 1 [], Node 1 []] (B 1) == False isDfsForestOf [Node 1 []] (C 1 1) == True isDfsForestOf [Node 1 []] (D 1 2) == False isDfsForestOf [Node 1 [], Node 2 []] (D 1 2) == False isDfsForestOf [Node 2 [], Node 1 []] (C 1 2) == True isDfsForestOf [Node 1 [Node 2 []]] (C 1 2) == True isDfsForestOf [Node 1 [], Node 2 []] (? [1,2]) == True isDfsForestOf [Node 2 [], Node 1 []] (? [1,2]) == True isDfsForestOf [Node 1 [Node 2 []]] (@ [1,2]) == False isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] (C [1,2,3]) == True isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] (D [1,2,3]) == False isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (C [1,2,3]) == True isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (C [1,2,3]) == True isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] ( [1,2,3]) == False algebraic-graphs/Check if a given list of vertices is a correct topological sort of a graph. isTopSortOf [3,1,2] (1 * 2 + 3 * 1) == True isTopSortOf [1,2,3] (1 * 2 + 3 * 1) == False isTopSortOf [] (1 * 2 + 3 * 1) == False isTopSortOf [] ( == True isTopSortOf [x] (& x) == True isTopSortOf [x] ( x x) == False // (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone 345<FKNTVT!?algebraic-graphsThe context of a subgraph comprises the input and output vertices outside the subgraph that are connected to the vertices inside the subgraph.algebraic-graphsThe I data type is a deep embedding of the core graph construction primitives , ,  and . We define a r; 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 t- 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.algebraic-graphs>Compare two graphs by converting them to their adjacency maps.algebraic-graphsLike equals2 but specialised for graphs with vertices of type .algebraic-graphsConstruct 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 algebraic-graphsConstruct 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  (vertex x) == 1  (vertex x) == 0  (vertex x) == 1 algebraic-graphsConstruct 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 algebraic-graphsOverlay* two graphs. An alias for the constructor Q. This is a commutative, associative and idempotent operation with the identity . Complexity: O(1) time and memory,  O(s1 + s2) size.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) ==  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphsConnect* two graphs. An alias for the constructor 6. This is an associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O(1) time and memory,  O(s1 + s2) size. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  (connect x y) ==  x &&  y  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) <=  x *  y +  x +  y  (connect x y) ==  x +  y  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsOConstruct 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. algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] ==  edges [(x,y)] ==  x y  . edges ==  . '( algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==   algebraic-graphsAuxiliary function, similar to .algebraic-graphs Generalised ! folding: recursively collapse a  by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: empty, vertex, overlay and connect. Complexity: O(s)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) (+) (+) == 895 foldg 1 (const 1) (+) (+) == 5 foldg True (const False) (&&) (&&) ==  algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges 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 algebraic-graphs7Structural equality on graph expressions. Complexity: O(s) time. * x === x == True x === x + ` == False x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False algebraic-graphs2Check 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 algebraic-graphsThe 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 algebraic-graphsACheck if a graph contains a given vertex. A convenient alias for . Complexity: O(s) time.  hasVertex x " == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x .   x == const False algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y . 4 x y == const False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount  == 0 vertexCount (# x) == 1 vertexCount ==  .  algebraic-graphsLike 2 but specialised for graphs with vertices of type .algebraic-graphs-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 ==  .  algebraic-graphsLike 2 but specialised for graphs with vertices of type .algebraic-graphs;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  == '( . ') algebraic-graphsLike 2 but specialised for graphs with vertices of type .algebraic-graphs2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges 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 67 . edgeList algebraic-graphsLike 2 but specialised for graphs with vertices of type .algebraic-graphs3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet  == Set.} vertexSet .  == Set.~ vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs+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.w vertexIntSet .  == IntSet.x vertexIntSet .  == IntSet.z vertexIntSet .  == IntSet.z algebraic-graphs0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory. edgeSet  == Set.} edgeSet ( x) == Set.} edgeSet ( x y) == Set.~ (x,y) edgeSet .  == Set. algebraic-graphsLike 2 but specialised for graphs with vertices of type .algebraic-graphs The sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (0 1 2) == [(1, [2]), (2, [])] adjacencyList (, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]  . adjacencyList == id algebraic-graphsThe  adjacency mapZ of a graph: each vertex is associated with a set of its direct successors. 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.algebraic-graphsConvert a graph to .algebraic-graphsLike 2 but specialised for graphs with vertices of type .algebraic-graphsLike toAdjacencyMap2 but specialised for graphs with vertices of type .algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] ==  path [x] ==  x path [x,y] ==  x y path .  ==  . path algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] circuit .  ==  . circuit algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) == " (clique xs) (clique ys) clique .  ==  . clique algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe starG formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity: O(L) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  . map (uncurry  ) stars .  == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphsThe  tree graph constructed from a given  data structure. Complexity: O(T) time, memory and size, where 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)]  algebraic-graphsThe  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   algebraic-graphs Construct a  mesh graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists. mesh xs [] ==  mesh [] ys ==  mesh [x] [y] ==  (x, y) mesh xs ys ==  ( xs) ( ys) mesh [1..3] "ab" ==  [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(2,'b')), ((2,'a'),(2,'b')) , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ]  algebraic-graphs Construct a  torus graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists. torus xs [] ==  torus [] ys ==  torus [x] [y] == ! (x,y) (x,y) torus xs ys ==  ( xs) ( ys) torus [1,2] "ab" ==  [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b')) , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ] algebraic-graphsAuxiliary function for   and   algebraic-graphs Construct a De Bruijn graphV of a given non-negative dimension using symbols from a given alphabet. Complexity:  O(A^(D + 1)) time, memory and size, where A" is the size of the alphabet and D is the dimension of the graph. ) deBruijn 0 xs == 0 [] [] n > 0 ==> deBruijn n [] == * deBruijn 1 [0,1] == Y [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == 4 "00" "00" deBruijn 2 "01" ==  [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]  (deBruijn n xs) ==   $ deBruijn n xs  (deBruijn n xs) == ( $ '( xs)^n n > 0 ==>  (deBruijn n xs) == ( $ '( xs)^(n + 1)  algebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y ( x y) == J [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .   x ==  a x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 # (removeEdge x y z) <= 3 *  z algebraic-graphs&Filter vertices in a subgraph context.algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O(s) time, memory and size. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsNMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 algebraic-graphsPSplit 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) algebraic-graphs&Transpose a given graph. Complexity: O(s) time, memory and size.  transpose  ==  transpose ( x) ==  x transpose ( x y) == , y x transpose . transpose == id transpose ( x y) ==  (transpose x) (transpose y)  . transpose == ') . map 67 .  algebraic-graphsConstruct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s); time, memory and size, assuming that the predicate takes 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 algebraic-graphsDSimplify 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 algebraic-graphs Compute the Cartesian product of graphs. Complexity:  O(s1 * s2) time, memory and size, where s1 and s2$ are the sizes of the given graphs. box ( [0,1]) ( "ab") ==  [ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((0,'b'), (1,'b')) , ((1,'a'), (1,'b')) ] 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 algebraic-graphs on a specified subgraph.algebraic-graphs!Extract the context from a graph  . Returns Nothing% if the focus could not be obtained.algebraic-graphsSparsify a graph by adding intermediate  IntA vertices between the original vertices (wrapping the latter in $) such that the resulting graph is sparse, i.e. contains only O(s) edges, but preserves the reachability relation between the original vertices. Sparsification is useful when working with dense graphs, as it can reduce the number of edges from O(n^2) down to O(n) by replacing cliques, bicliques and similar densely connected structures by sparse subgraphs built out of intermediate vertices. Complexity: O(s) time, memory and size. ') .  : x == ') . ;< .  : (;= x) . sparsify  (sparsify x) <=  x +  x + 1  (sparsify x) <= 3 *  x  (sparsify x) <= 3 *  x 9     9     4 (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <>FKNTVE##algebraic-graphsThe #K type class captures data types that can be converted to algebraic graphs.%algebraic-graphs:Convert a value to the corresponding algebraic graph, see  Algebra.Graph.  toGraph == &     &algebraic-graphs The method & is used for generalised graph folding. It collapses a given value by applying the provided graph construction primitives. The order of arguments is: empty, vertex, overlay and connect, and it is assumed that the arguments satisfy the axioms of the graph algebra. foldg == Algebra.Graph. . % 'algebraic-graphsCheck if a graph is empty.  isEmpty == & True (const False) (&&) (&&) (algebraic-graphsThe sizeD of a graph, i.e. the number of leaves of the expression including empty leaves. size == & 1 (const 1) (+) (+) )algebraic-graphs)Check if a graph contains a given vertex. hasVertex x == & False (==x) (||) (||) *algebraic-graphs'Check if a graph contains a given edge. hasEdge x y == Algebra.Graph. x y . % +algebraic-graphs"The number of vertices in a graph. vertexCount == Set. . / ,algebraic-graphsThe number of edges in a graph. edgeCount == Set. . 1 -algebraic-graphs-The sorted list of vertices of a given graph. vertexList == Set. . / .algebraic-graphs$The sorted list of edges of a graph. edgeList == Set. . 1 /algebraic-graphsThe set of vertices of a graph.  vertexSet == & Set.} Set.~ Set. Set. 0algebraic-graphs%The set of vertices of a graph. Like /3 but specialised for graphs with vertices of type . vertexIntSet == & IntSet.w IntSet.x IntSet. IntSet. 1algebraic-graphsThe set of edges of a graph. &edgeSet == Algebra.Graph.AdjacencyMap. . A 2algebraic-graphsThe preset of a vertex is the set of its direct predecessors. 'preSet x == Algebra.Graph.AdjacencyMap. x . A 3algebraic-graphsThe preset (here  preIntSet!) of a vertex is the set of its direct predecessors. Like 23 but specialised for graphs with vertices of type . -preIntSet x == Algebra.Graph.AdjacencyIntMap. x . C 4algebraic-graphsThe postset of a vertex is the set of its direct successors. (postSet x == Algebra.Graph.AdjacencyMap. x . A 5algebraic-graphsThe postset (here  postIntSet!) of a vertex is the set of its direct successors. Like 43 but specialised for graphs with vertices of type . .postIntSet x == Algebra.Graph.AdjacencyIntMap. x . C 6algebraic-graphs The sorted adjacency list of a graph. ,adjacencyList == Algebra.Graph.AdjacencyMap. . A 7algebraic-graphsThe  adjacency map: of a graph: each vertex is associated with a set of its direct successors. +adjacencyMap == Algebra.Graph.AdjacencyMap. > . A 8algebraic-graphsThe  adjacency map: of a graph: each vertex is associated with a set of its direct successors. Like 73 but specialised for graphs with vertices of type . 1adjacencyIntMap == Algebra.Graph.AdjacencyIntMap. ? . C 9algebraic-graphsThe transposed  adjacency map: of a graph: each vertex is associated with a set of its direct predecessors. 4adjacencyMapTranspose == Algebra.Graph.AdjacencyMap. > . B :algebraic-graphsThe transposed  adjacency map: of a graph: each vertex is associated with a set of its direct predecessors. Like 93 but specialised for graphs with vertices of type . :adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap. ? . D ;algebraic-graphs Compute the depth-first searchY forest of a graph that corresponds to searching from each of the graph vertices in the  a order. (dfsForest == Algebra.Graph.AdjacencyMap. . toAdjacencyMap <algebraic-graphs Compute the depth-first search forest of a graph, searching from each of the given vertices in order. Note that the resulting forest does not necessarily span the whole graph, as some vertices may be unreachable. /dfsForestFrom vs == Algebra.Graph.AdjacencyMap. vs . toAdjacencyMap =algebraic-graphs,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 vs == Algebra.Graph.AdjacencyMap. vs . toAdjacencyMap >algebraic-graphs&Compute the list of vertices that are  reachable[ from a given source vertex in a graph. The vertices in the resulting list appear in the depth-first order. *reachable x == Algebra.Graph.AdjacencyMap. x . toAdjacencyMap ?algebraic-graphs Compute the topological sort of a graph or return Nothing if the graph is cyclic. &topSort == Algebra.Graph.AdjacencyMap. . toAdjacencyMap @algebraic-graphsCheck if a given graph is acyclic. (isAcyclic == Algebra.Graph.AdjacencyMap. . toAdjacencyMap Aalgebraic-graphs%Convert a value to the corresponding . toAdjacencyMap == &     Balgebraic-graphs%Convert a value to the corresponding  and transpose the result. toAdjacencyMapTranspose == &    (flip ) Calgebraic-graphs%Convert a value to the corresponding . toAdjacencyIntMap == &     Dalgebraic-graphs%Convert a value to the corresponding  and transpose the result. toAdjacencyIntMapTranspose == &    (flip ) Ealgebraic-graphs#Check if a given forest is a valid depth-first search forest of a graph. .isDfsForestOf f == Algebra.Graph.AdjacencyMap. f . toAdjacencyMap Falgebraic-graphs-Check if a given list of vertices is a valid topological sort of a graph. -isTopSortOf vs == Algebra.Graph.AdjacencyMap. vs . toAdjacencyMap $#$(=?>&')*+,-./0167824;<@EFA%35CBD9:$#$(=?>&')*+,-./0167824;<@EFA%35CBD9: (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTVٛ Kalgebraic-graphs$An abstract document data type with O(1)N time concatenation (the current implementation uses difference lists). Here s? is the type of abstract symbols or strings (text or binary). K s is a  , therefore O corresponds to the empty document and two documents can be concatenated with  (or operator %&Z). Documents comprising a single symbol or string can be constructed using the function LQ. Alternatively, you can construct documents as string literals, e.g. simply as "alga", by using the OverloadedStringsC GHC extension. To extract the document contents use the function M. See some examples below.Lalgebraic-graphs>Construct a document comprising a single symbol or string. If s is an instance of class , then documents of type K 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  ==  M# . literal ==  literal . M ==  Malgebraic-graphsCRender the document as a single string. An inverse of the function L. render (L "al" %& L "ga") :: ( s,  s) => s render (L "al" %& L "ga") == "alga" render  ==  render . L ==  L" . render ==  Nalgebraic-graphsConcatenate 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" Oalgebraic-graphs#Wrap a document in square brackets. "brackets "i" == "[i]" brackets  == "[]" Palgebraic-graphs#Wrap a document into double quotes. YdoubleQuotes "/path/with spaces" == "\"/path/with spaces\"" doubleQuotes (doubleQuotes ) == "\"\"\"\"" Qalgebraic-graphs/Prepend a given number of spaces to a document. indent 0 ==  indent 1  == " " Ralgebraic-graphsKConcatenate documents after appending a terminating newline symbol to each. !unlines [] ==  unlines [L] == "\n" unlines ["title", "subtitle"] == "title\nsubtitle\n" Salgebraic-graphsExport a graph into a document given two functions that construct documents for individual vertices and edges. The order of export is: vertices, sorted by  a, and then edges, sorted by  (a, a). For example:  vDoc x = L ( x) <> "\n" eDoc x y = L ( x) <> " -> " <> L ( y) <> "\n" > putStrLn $ M( $ export vDoc eDoc (1 + 2 * (3 + 4) ::  @ Int) 1 2 3 4 2 -> 3 2 -> 4 KLMNOPQRS KLMNOPQRSN7(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone "#<FKNTVZalgebraic-graphs The record Z 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 a!, which holds a function of type a -> s< to compute vertex names. See the example for the function h.\algebraic-graphsName of the graph.]algebraic-graphs8Preamble is added at the beginning of the DOT file body.^algebraic-graphsGraph style, e.g. ["bgcolor" := "azure"]._algebraic-graphsDefault vertex style, e.g. ["shape" := "diamond"].`algebraic-graphsDefault edge style, e.g. ["style" := "dashed"].aalgebraic-graphsCompute a vertex name.balgebraic-graphs Attributes of a specific vertex.calgebraic-graphsAttributes of a specific edge.dalgebraic-graphs3An attribute is just a key-value pair, for example "shape" := "box"L. Attributes are used to specify the style of graph elements during export.falgebraic-graphsMDefault style for exporting graphs. All style settings are empty except for a), which is provided as the only argument.galgebraic-graphs6Default style for exporting graphs whose vertices are s0-able. All style settings are empty except for a, which is computed from . defaultStyleViaShow = f ( . ) halgebraic-graphs"Export a graph with a given style. For example:  style :: Z Int String style = Z { \! = "Example" , ]4 = " // This is an example\n" , ^= = ["label" := "Example", "labelloc" := "top"] , _ = ["shape" := "circle"] , ` =  , a = \x -> "v" ++  x , b) = \x -> ["color" := "blue" |  x ] , c+ = \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" } algebraic-graphs<A list of attributes formatted as a DOT document. Example: 3attributes ["label" := "A label", "shape" := "box"] corresponds to document:  [label="A label" shape="box"].ialgebraic-graphsDExport a graph whose vertices are represented simply by their names. For example: > Text.putStrLn $ exportAsIs ( A ["a", "b", "c"] ::  *M Text) digraph { "a" "b" "c" "a" -> "b" "b" -> "c" "c" -> "a" } jalgebraic-graphsExport a graph using the g. For example: /> putStrLn $ exportViaShow (1 + 2 * (3 + 4) ::  @E Int) digraph { "1" "2" "3" "4" "2" -> "3" "2" -> "4" } Z[\]^_`abcdefghijdeZ[\]^_`abcfghij(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone 345<FKNTV4kalgebraic-graphsThe kI data type is a deep embedding of the core graph construction primitives p, r and ti. As one can guess from the name, the empty graph cannot be represented using this data type. See module  Algebra.GraphK for a graph data type that allows for the construction of the empty graph. We define a r; instance as a convenient notation for working with graphs: 0 == Vertex 0 1 + 2 == Overlay (Vertex 1) (Vertex 2) 1 * 2 == Connect (Vertex 1) (Vertex 2) 1 + 2 * 3 == Overlay (Vertex 1) (Connect (Vertex 2) (Vertex 3)) 1 * (2 + 3) == Connect (Vertex 1) (Overlay (Vertex 2) (Vertex 3))Note that the  method of the r" type class cannot be implemented.The t- instance is currently implemented using the 3* as the canonical graph representation6 and satisfies the following laws of algebraic graphs:r, is commutative, associative and idempotent: @ x + y == y + x x + (y + z) == (x + y) + z x + x == xt is associative: x * (y * z) == (x * y) * zt distributes over r: 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * zt can be decomposed: "x * y * z == x * y + x * z + y * zt% satisfies absorption and saturation: -x * y + x + y == x * y x * x * x == x * xDWhen specifying the time and memory complexity of graph algorithms, n2 will denote the number of vertices in the graph, m3 will denote the number of edges in the graph, and s will denote the size of the corresponding kE expression, defined as the number of vertex leaves. For example, if g is a k then n, m and s can be computed as follows: n ==  g m ==  g s == | gThe |; of any graph is positive and coincides with the result of  method of the  type class. We define |O only for the consistency with the API of other graph representations, such as  Algebra.Graph. Converting a k to the corresponding 3* 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.algebraic-graphs>Compare two graphs by converting them to their adjacency maps.algebraic-graphsLike equals2 but specialised for graphs with vertices of type .oalgebraic-graphs Convert a  into k . Returns  if the argument is . Complexity: O(s) time, memory and size. toNonEmptyGraph # == Nothing toNonEmptyGraph (BC# x) == Just (x :: NonEmptyGraph a) palgebraic-graphsConstruct the graph comprising a single isolated vertex . An alias for the constructor l. Complexity: O(1) time, memory and size. } x (vertex x) == True  (vertex x) == 1  (vertex x) == 0 | (vertex x) == 1 qalgebraic-graphsConstruct the graph comprising  a single edge. Complexity: O(1) time, memory and size. edge x y == t (p x) (p y) ~ x y (edge x y) == True  (edge x y) == 1  (edge 1 1) == 1  (edge 1 2) == 2 ralgebraic-graphsOverlay* two graphs. An alias for the constructor mM. This is a commutative, associative and idempotent operation. Complexity: O(1) time and memory,  O(s1 + s2) size. } z (overlay x y) == } z x || } z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y | (overlay x y) == | x + | y  (overlay 1 2) == 2  (overlay 1 2) == 0 salgebraic-graphsQOverlay a possibly empty graph with a non-empty graph. If the first argument is V, the function returns the second argument; otherwise it is semantically the same as r. Complexity: O(s1) time and memory, and  O(s1 + s2) size.  overlay1  x == x x /= B ==> overlay1 x y == overlay (fromJust $ toNonEmptyGraph x) y talgebraic-graphsConnect* two graphs. An alias for the constructor n<. This is an associative operation, which distributes over r2 and obeys the decomposition axiom. Complexity: O(1) time and memory,  O(s1 + s2) size. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2). } z (connect x y) == } z x || } z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) <=  x *  y +  x +  y | (connect x y) == | x + | y  (connect 1 2) == 2  (connect 1 2) == 1 ualgebraic-graphsOConstruct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.  vertices1 (x  []) == p x } x . vertices1 ==  x  . vertices1 ==  . D(  . vertices1 == Set. . DE valgebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges1 ((x,y)  []) == q x y  . edges1 == D9 . D( walgebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list.  overlays1 (x  [] ) == x overlays1 (x  [y]) == r x y xalgebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list.  connects1 (x  [] ) == x connects1 (x  [y]) == t x y algebraic-graphsAuxiliary function, similar to sconcat.yalgebraic-graphs2Generalised graph folding: recursively collapse a k by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: vertex, overlay and connect. Complexity: O(s)D applications of given functions. As an example, the complexity of | is O(s) , since all functions have cost O(1). foldg1 (const 1) (+) (+) == | foldg1 (==x) (||) (||) == } x zalgebraic-graphsThe z' 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 (r x y) == True isSubgraphOf (r x y) (t x y) == True isSubgraphOf ( xs) ( xs) == True {algebraic-graphs7Structural equality on graph expressions. Complexity: O(s) time. b x === x == True x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False |algebraic-graphsThe sizeG of a graph, i.e. the number of leaves of the expression. Complexity: O(s) time. size (p x) == 1 size (r x y) == size x + size y size (tG x y) == size x + size y size x >= 1 size x >=  x }algebraic-graphsACheck if a graph contains a given vertex. A convenient alias for . Complexity: O(s) time.  hasVertex x (p x) == True hasVertex 1 (p 2) == False ~algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y (p z) == False hasEdge x y (q" x y) == True hasEdge x y . 4 x y == const False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount (p? x) == 1 vertexCount x >= 1 vertexCount ==  .  algebraic-graphsLike 9 but specialised for NonEmptyGraph with vertices of type .algebraic-graphs-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 (p x) == 0 edgeCount (q# x y) == 1 edgeCount ==  .  algebraic-graphsLike 2 but specialised for graphs with vertices of type .algebraic-graphs;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList1 (p x) == x  [] vertexList1 . u == D( . D) algebraic-graphsLike 9 but specialised for NonEmptyGraph with vertices of type .algebraic-graphs2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges mA of a graph can be quadratic with respect to the expression size s.  edgeList (p x) == [] edgeList (q x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList . v == '( . ') . DE edgeList .  == ') . map 67 . edgeList algebraic-graphsLike 9 but specialised for NonEmptyGraph with vertices of type .algebraic-graphs3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet . p == Set.~ vertexSet . u == Set. . DE vertexSet .  == Set. . DE algebraic-graphs+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 . p == IntSet.x vertexIntSet . u == IntSet.z . DE vertexIntSet .  == IntSet.z . DE algebraic-graphs0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory.  edgeSet (p x) == Set.} edgeSet (q x y) == Set.~ (x,y) edgeSet . v == Set. . DE algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.  path1 (x  [] ) == p x path1 (x  [y]) == q x y path1 . DF ==  . path1 algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.  circuit1 (x  [] ) == q x x circuit1 (x  [y]) == v ((x,y)  [(y,x)]) circuit1 . DF ==  . circuit1 algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.  clique1 (x  [] ) == p x clique1 (x  [y] ) == q x y clique1 (x  [y,z]) == v ((x,y)  [(x,z), (y,z)]) clique1 (xs  ys) == t% (clique1 xs) (clique1 ys) clique1 . DF ==  . clique1 algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique1 (x1  [x2]) (y1  [y2]) == v ((x1,y1) E [(x1,y2), (x2,y1), (x2,y2)]) biclique1 xs ys == t (u xs) (u ys) algebraic-graphsThe starG formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] == p x star x [y] == q x y star x [y,z] == v ((x,y)  [(x,z)]) algebraic-graphsThe stars* formed by overlaying a non-empty list of s. Complexity: O(L) time, memory and size, where L! is the total size of the input. stars1 ((x, [])  []) == p x stars1 ((x, [y])  []) == q x y stars1 ((x, ys)  []) == ) x ys stars1 == w . fmap (uncurry ) r. (stars1 xs) (stars1 ys) == stars1 (xs <> ys) algebraic-graphsThe  tree graph constructed from a given  data structure. Complexity: O(T) time, memory and size, where TJ is the size of the given tree (i.e. the number of vertices in the tree). <tree (Node x []) == p? x tree (Node x [Node y [Node z []]]) ==  (x D [y,z]) tree (Node x [Node y [], Node z []]) == E x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == v ((1,2)  [(1,3), (3,4), (3,5)]) algebraic-graphs Construct a  mesh graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists.  mesh1 (x  []) (y  []) == p+ (x, y) mesh1 xs ys ==  ( xs) ( ys) mesh1 (1  [2,3]) ('a'  "b") == v (DG) [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')) , ((1,'b'),(2,'b')), ((2,'a'),(2,'b')) , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')) , ((3,'a'),(3,'b')) ]) algebraic-graphs Construct a  torus graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists.  torus1 (x  []) (y  []) == q/ (x,y) (x,y) torus1 xs ys ==  ( xs) ( ys) torus1 (1  [2]) ('a'  "b") == v (DG9 [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')) , ((1,'b'),(1,'a')), ((1,'b'),(2,'b')) , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')) , ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ]) algebraic-graphsAuxiliary function for  and algebraic-graphs Append a list to a non-empty onealgebraic-graphs,Remove a vertex from a given graph. Returns Nothing0 if the resulting graph is empty. Complexity: O(s) time, memory and size. removeVertex1 x (p) x) == Nothing removeVertex1 1 (p 2) == Just (p 2) removeVertex1 x (q+ x x) == Nothing removeVertex1 1 (q 1 2) == Just (p 2) removeVertex1 x $ removeVertex1 x == removeVertex1 x algebraic-graphs0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y (q x y) == u (x  [y]) removeEdge x y . removeEdge x y == removeEdge x y removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 |# (removeEdge x y z) <= 3 * | z algebraic-graphs The function  x y replaces vertex x with vertex y in a given k. If y already exists, x and y will be merged. Complexity: O(s) time, memory and size. 6replaceVertex x x == id replaceVertex x y (p x) == p# y replaceVertex x y ==  (== x) y algebraic-graphsNMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 algebraic-graphsPSplit a vertex into a list of vertices with the same connectivity. Complexity:  O(s + k * L) time, memory and size, where kC is the number of occurrences of the vertex in the expression and L" is the length of the given list. splitVertex1 x (x , [] ) == id splitVertex1 x (y  [] ) ==  x y splitVertex1 1 (0 ) [1]) $ 1 * (2 + 3) == (0 + 1) * (2 + 3) algebraic-graphs&Transpose a given graph. Complexity: O(s) time, memory and size.  transpose (p x) == p x transpose (q x y) == q, y x transpose . transpose == id transpose ( x y) ==  (transpose x) (transpose y)  . transpose == ') . map 67 .  algebraic-graphsConstruct the induced subgraph[ of a given graph by removing the vertices that do not satisfy a given predicate. Returns Nothing0 if the resulting graph is empty. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. `induce1 (const True ) x == Just x induce1 (const False) x == Nothing induce1 (/= x) ==  x induce1 p ) induce1 q == induce1 (\x -> p x && q x) algebraic-graphsDSimplify a graph expression. Semantically, this is the identity function, but it simplifies a given expression according to the laws of the algebra. The function does not compute the simplest possible expression, but uses heuristics to obtain useful simplifications in reasonable time. Complexity: the function performs O(s)s graph comparisons. It is guaranteed that the size of the result does not exceed the size of the given expression. simplify == id | (simplify x) <= | x simplify 1 { 1 simplify (1 + 1) { 1 simplify (1 + 2 + 1) { 1 + 2 simplify (1 * 1 * 1) { 1 * 1 algebraic-graphs Compute the Cartesian product of graphs. Complexity:  O(s1 * s2) time, memory and size, where s1 and s2$ are the sizes of the given graphs. box ( $ DG [0,1]) ( $ DG "ab") == v (DG3 [ ((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 r, and has singleton graphs as  identities. Below ~~5 stands for the equality up to an isomorphism, e.g.  (x, ()) ~~ x. Qbox x y ~~ box y x box x (box y z) ~~ box (box x y) z box x (r y z) == r (box x y) (box x z) box x (p ()) ~~ x  (box x y) == box ( x) ( y)  (box x y) ==  x *  y  (box x y) <=  x *  y +  x *  y algebraic-graphsSparsify a graph by adding intermediate  IntA vertices between the original vertices (wrapping the latter in $) such that the resulting graph is sparse, i.e. contains only O(s) edges, but preserves the reachability relation between the original vertices. Sparsification is useful when working with dense graphs, as it can reduce the number of edges from O(n^2) down to O(n) by replacing cliques, bicliques and similar densely connected structures by sparse subgraphs built out of intermediate vertices. Complexity: O(s) time, memory and size. ') .  : x == ') . ;< .  : (;= x) . sparsify  (sparsify x) <=  x + | x + 1  (sparsify x) <= 3 * | x | (sparsify x) <= 3 * | x .klmnopqrstuvwxyz{|}~.klmnopqrstuvwxyz{|}~{4(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNQTV$algebraic-graphsThe V data type is the Boehm-Berarducci encoding of the core graph construction primitives , ,  and . We define a r; 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 s? instance is defined using basic graph construction primitives: *show (empty :: Fold Int) == "empty" show (1 :: Fold Int) == "vertex 1" show (1 + 2 :: Fold Int) == "vertices [1,2]" show (1 * 2 :: Fold Int) == "edge 1 2" show (1 * 2 * 3 :: Fold Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Fold Int) == "overlay (vertex 3) (edge 1 2)"The t- 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 ==  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.algebraic-graphsConstruct the  empty graph. Complexity: O(1) time, memory and size.  empty == True  x empty == False  empty == 0  empty == 0  empty == 1 algebraic-graphsConstruct the graph comprising a single isolated vertex. Complexity: O(1) time, memory and size.  (vertex x) == False  x (vertex x) == True  (vertex x) == 1  (vertex x) == 0  (vertex x) == 1 algebraic-graphsConstruct 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 algebraic-graphsOverlay\ two graphs. This is a commutative, associative and idempotent operation with the identity . Complexity: O(1) time and memory,  O(s1 + s2) size.  (overlay x y) ==  x &&  y  z (overlay x y) ==  z x ||  z y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) >=  x  (overlay x y) <=  x +  y  (overlay x y) ==  x +  y  (overlay 1 2) == 2  (overlay 1 2) == 0 algebraic-graphsConnectA two graphs. This is an associative operation with the identity , which distributes over 1 and obeys the decomposition axiom. Complexity: O(1) time and memory,  O(s1 + s2) size. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).  (connect x y) ==  x &&  y  z (connect x y) ==  z x ||  z y  (connect x y) >=  x  (connect x y) <=  x +  y  (connect x y) >=  x  (connect x y) >=  y  (connect x y) >=  x *  y  (connect x y) <=  x *  y +  x +  y  (connect x y) ==  x +  y  (connect 1 2) == 2  (connect 1 2) == 1 algebraic-graphsOConstruct 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. algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] ==  edges [(x,y)] ==  x y  . edges ==  . '( algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==   algebraic-graphs Generalised Graph! folding: recursively collapse a Graph 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 (++) (++) == 8E5 foldg 0 (const 1) (+) (+) == 895 foldg 1 (const 1) (+) (+) == 5 foldg True (const False) (&&) (&&) ==  algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges 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 algebraic-graphs2Check 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 algebraic-graphsThe 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 algebraic-graphsACheck if a graph contains a given vertex. A convenient alias for . Complexity: O(s) time.  hasVertex x " == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x .  x == const False algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y . 4 x y == const False hasEdge x y ==  (x,y) .  algebraic-graphs0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount  == 0 vertexCount (# x) == 1 vertexCount ==  .  algebraic-graphs-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 ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  == '( . ') algebraic-graphs2The sorted list of edges of a graph. Complexity: O(s + m * log(m)) time and O(m)( memory. Note that the number of edges 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 67 . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexSet  == Set.} vertexSet .  == Set.~ vertexSet .  == Set. vertexSet .  == Set. algebraic-graphs+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.w vertexIntSet .  == IntSet.x vertexIntSet .  == IntSet.z vertexIntSet .  == IntSet.z algebraic-graphs0The set of edges of a given graph. Complexity:  O(s * log(m)) time and O(m) memory. edgeSet  == Set.} edgeSet ( x) == Set.} edgeSet ( x y) == Set.~ (x,y) edgeSet .  == Set. algebraic-graphs The sorted adjacency list of 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. adjacencyList  == [] adjacencyList ($ x) == [(x, [])] adjacencyList (0 1 2) == [(1, [2]), (2, [])] adjacencyList (, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]  . adjacencyList == id algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] ==  path [x] ==  x path [x,y] ==  x y path .  ==  . path algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] circuit .  ==  . circuit algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) == " (clique xs) (clique ys) clique .  ==  . clique algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe starG formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe stars formed by overlaying a list of s. An inverse of . Complexity: O(L) time, memory and size, where L! is the total size of the input. !stars [] == " stars [(x, [])] == $ x stars [(x, [y])] == & x y stars [(x, ys)] == ' x ys stars ==  . map (uncurry  ) stars .  == id + (stars xs) (stars ys) == stars (xs ++ ys) algebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity: O(s) time, memory and size. removeEdge x y ( x y) == J [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .  x == a x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 # (removeEdge x y z) <= 3 *  z algebraic-graphs&Filter vertices in a subgraph context.algebraic-graphs&Transpose a given graph. Complexity: O(s) time, memory and size.  transpose  ==  transpose ( x) ==  x transpose ( x y) == , y x transpose . transpose == id transpose (box x y) == box (transpose x) (transpose y)  . transpose == ') . map 67 .  algebraic-graphsConstruct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s); time, memory and size, assuming that the predicate takes 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 algebraic-graphsVSimplify 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 ##(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV8&algebraic-graphs The class of preorder graphs( that are both reflexive and transitive.algebraic-graphs The class of transitive graphs- that satisfy the following additional axiom.The closure8 axiom: graphs with equal transitive closures are equal. 5y /= empty ==> x * y + x * z + y * z == x * y + y * zpBy repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction.algebraic-graphs The class of reflexive graphs- that satisfy the following additional axiom.Each vertex has a  self-loop: vertex x == vertex x * vertex x'Or, alternatively, if we remember that  is an alias for : pure x == pure x * pure 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.algebraic-graphs The class of undirected graphs- that satisfy the following additional axiom. is commutative: x * y == y * xalgebraic-graphsTThe core type class for constructing algebraic graphs is defined by introducing the  method to the standard 2 class and reusing the following existing methods:The  method comes from the  class and corresponds to the  empty graph#. This module simply re-exports it.The . graph construction primitive is an alias for  of the  type class.Graph  is an alias for mplus of the  type class.The 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.algebraic-graphsConnect two graphs.algebraic-graphsFConstruct the graph comprising a single isolated vertex. An alias for .algebraic-graphs!Overlay two graphs. An alias for .algebraic-graphs;Construct the graph comprising a single edge. Complexity: O(1) time, memory and size. edge x y ==  ( x) ( y)  (edge 1 1) == 1  (edge 1 2) == 2 algebraic-graphsOConstruct 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. algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] ==  edges [(x,y)] ==  x y algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. overlays [] == / overlays [x] == x overlays [x,y] ==  x y overlays ==     . overlays ==   algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. connects [] == / connects [x] == x connects [x,y] ==  x y connects ==     . connects ==   algebraic-graphsThe ' function takes two graphs and returns  if the first graph is a subgraph3 of the second. Here is the current implementation: isSubgraphOf x y =  x y == y 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 algebraic-graphs2Check if a graph is empty. A convenient alias for . Complexity: O(s) time. isEmpty ( == True isEmpty (  ) == True isEmpty (' x) == False isEmpty ( x $  x) == True algebraic-graphsACheck if a graph contains a given vertex. A convenient alias for . Complexity: O(s) time.  hasVertex x " == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x .  x == const False algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.  hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (4 x y) == True hasEdge x y ==  (x,y) . edgeList algebraic-graphs0The number of vertices in a graph. Complexity:  O(s * log(n)) time.  vertexCount  == 0 vertexCount (# x) == 1 vertexCount ==  .  algebraic-graphs;The sorted list of vertices of a given graph. Complexity:  O(s * log(n)) time and O(n) memory.  vertexList  == [] vertexList ( x) == [x] vertexList .  == '( . ') algebraic-graphs3The 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. algebraic-graphs+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.w vertexIntSet .  == IntSet.x vertexIntSet .  == IntSet.z vertexIntSet .  == IntSet.z algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] ==  path [x] ==  x path [x,y] ==  x y algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)] algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) ==  (clique xs) (clique ys) algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe starG formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] ==  x starTranspose x [y] ==  y x starTranspose x [y,z] == ) [(y,x), (z,x)] starTranspose x ys ==  ( ys) (( x) starTranspose x ys == transpose ( x ys) algebraic-graphsThe  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)] algebraic-graphsThe  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  algebraic-graphs Construct a  mesh graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists. mesh xs [] ==  mesh [] ys ==  mesh [x] [y] ==  (x, y) mesh xs ys ==  ( xs) ( ys) mesh [1..3] "ab" ==  [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(2,'b')), ((2,'a'),(2,'b')) , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ] algebraic-graphs Construct a  torus graph* from two lists of vertices. Complexity:  O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists. torus xs [] ==  torus [] ys ==  torus [x] [y] == ! (x,y) (x,y) torus xs ys ==  ( xs) ( ys) torus [1,2] "ab" ==  [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b')) , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ] algebraic-graphs Construct a De Bruijn graphV of a given non-negative dimension using symbols from a given alphabet. Complexity:  O(A^(D + 1)) time, memory and size, where A" is the size of the alphabet and D is the dimension of the graph. ) deBruijn 0 xs == 0 [] [] n > 0 ==> deBruijn n [] == * deBruijn 1 [0,1] == Y [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == 4 "00" "00" deBruijn 2 "01" ==  [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ] transpose (deBruijn n xs) ==   $ deBruijn n xs  (deBruijn n xs) == ( $ '( xs)^n n > 0 ==>  edgeCount (deBruijn n xs) == ( $ '( xs)^(n + 1) algebraic-graphsConstruct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s); time, memory and size, assuming that the predicate takes 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 algebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size. removeVertex x ( x) ==  removeVertex 1 ( 2) ==  2 removeVertex x ( x x) ==  removeVertex 1 ( 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs The function  x y replaces vertex x with vertex y in a given . If y already exists, x and y will be merged. Complexity: O(s) time, memory and size. 6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y ==  (== x) y algebraic-graphsNMerge vertices satisfying a given predicate into a given vertex. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated. KmergeVertices (const False) x == id mergeVertices (== x) y == Y x y mergeVertices even 1 (0 * 2) == 1 * 1 mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 algebraic-graphsPSplit 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) algebraic-graphs Compute the Cartesian product of graphs. Complexity:  O(s1 * s2) time, memory and size, where s1 and s2$ are the sizes of the given graphs. box ( [0,1]) ( "ab") ==  [ ((0,'a'), (0,'b')) , ((0,'a'), (1,'a')) , ((0,'b'), (1,'b')) , ((1,'a'), (1,'b')) ] 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-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV Ealgebraic-graphs The class of preorder graphs( that are both reflexive and transitive.algebraic-graphs The class of transitive graphs- that satisfy the following additional axiom.The closure8 axiom: graphs with equal transitive closures are equal. 5y /= empty ==> x * y + x * z + y * z == x * y + y * zpBy repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction.algebraic-graphs The class of reflexive graphs- that satisfy the following additional axiom.Each vertex has a  self-loop: vertex x == vertex x * vertex 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.algebraic-graphs The class of undirected graphs- that satisfy the following additional axiom. is commutative: x * y == y * xalgebraic-graphsThe core type class for constructing algebraic graphs, characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for  and , respectively. is commutative and associative: / x + y == y + x x + (y + z) == (x + y) + z is associative and has  as the identity: < x * empty == x empty * x == x x * (y * z) == (x * y) * z distributes over : 9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed: "x * y * z == x * y + x * z + y * 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.algebraic-graphsThe type of graph vertices.algebraic-graphsConstruct the empty graph.algebraic-graphs)Construct the graph with a single vertex.algebraic-graphsOverlay two graphs.algebraic-graphsConnect two graphs.algebraic-graphs;Construct the graph comprising a single edge. Complexity: O(1) time, memory and size.  edge x y ==  ( x) ( y) algebraic-graphsOConstruct 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 algebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list. edges [] ==  edges [(x,y)] ==  x y algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. overlays [] == ' overlays [x] == x overlays [x,y] ==  x y overlays ==    algebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list. connects [] == ' connects [x] == x connects [x,y] ==  x y connects ==     algebraic-graphsThe  ' function takes two graphs and returns  if the first graph is a subgraph3 of the second. Here is the current implementation: isSubgraphOf x y =  x y == y 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  algebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. path [] ==  path [x] ==  x path [x,y] ==  x y  algebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. circuit [] ==  circuit [x] ==  x x circuit [x,y] ==  [(x,y), (y,x)]  algebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list. clique [] ==  clique [x] ==  x clique [x,y] ==  x y clique [x,y,z] == , [(x,y), (x,z), (y,z)] clique (xs ++ ys) ==  (clique xs) (clique ys)  algebraic-graphsThe biclique( on two lists of vertices. Complexity:  O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists. biclique [] [] ==  biclique [x] [] ==  x biclique [] [y] ==  y biclique [x1,x2] [y1,y2] == B [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==  ( xs) ( ys) algebraic-graphsThe starG formed by a centre vertex connected to a list of leaves. Complexity: O(L) time, memory and size, where L" is the length of the given list. star x [] ==  x star x [y] ==  x y star x [y,z] ==  [(x,y), (x,z)] star x ys ==  ( x) ( ys) algebraic-graphsThe star transposeG formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L" is the length of the given list. starTranspose x [] ==  x starTranspose x [y] ==  y x starTranspose x [y,z] == ) [(y,x), (z,x)] starTranspose x ys ==  ( ys) (( x) starTranspose x ys == transpose ( x ys) algebraic-graphsThe  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)] algebraic-graphsThe  forest graph constructed from a given  data structure. Complexity: O(F) time, memory and size, where FN is the size of the given forest (i.e. the number of vertices in the forest). >forest [] == ? forest [x] == A x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == U [(1,2), (1,3), (4,5)] forest ==  . map            (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone <FKNTV gg0algebraic-graphsThe 0 data type represents a 5binary relation that is both reflexive and transitive$. Preorders satisfy all laws of the $ type class and, in particular, the  self-loop axiom:  x ==  x *  xand the closure axiom: y /= + ==> x * y + x * z + y * z == x * y + y * z!For example, the following holds:   xs == (  xs :: PreorderRelation Int)The sC 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)]"3algebraic-graphsThe 3 data type represents a transitive binary relationF over a set of elements. Transitive relations satisfy all laws of the $ type class and, in particular, the closure axiom: y /= + ==> x * y + x * z + y * z == x * y + y * z!For example, the following holds:   xs == (  xs :: TransitiveRelation Int)The s3 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)]"6algebraic-graphsThe 6 data type represents a symmetric binary relationE over a set of elements. Symmetric relations satisfy all laws of the = type class and, in particular, the commutativity of connect:  x y ==  y xThe s4 instance produces symmetrically closed expressions: rshow (1 :: SymmetricRelation Int) == "vertex 1" show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"9algebraic-graphsThe 9 data type represents a reflexive binary relationE over a set of elements. Reflexive relations satisfy all laws of the $ type class and, in particular, the  self-loop axiom:  x ==  x *  xThe s2 instance produces reflexively closed expressions: xshow (1 :: ReflexiveRelation Int) == "edge 1 1" show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]" 0123456789:; 9:;678345012(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV lhValgebraic-graphs'Construct a transitive relation from a J. Complexity: O(1) time.Walgebraic-graphs.Extract the underlying relation. Complexity: O(n * m * log(m)) time.3VW3VW(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV wXalgebraic-graphs&Construct a symmetric relation from a J. Complexity: O(1) time.Yalgebraic-graphs.Extract the underlying relation. Complexity:  O(m*log(m)) time.Zalgebraic-graphs The set of  neighbours of an element x6 is the set of elements that are related to it, i.e. neighbours x == { a | aRx }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] 6XYZ6XYZ(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV {[algebraic-graphs&Construct a reflexive relation from a J. Complexity: O(1) time.\algebraic-graphs.Extract the underlying relation. Complexity:  O(n*log(m)) time.9[\9[\(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone <FKNTV h]algebraic-graphs%Construct a preorder relation from a J. Complexity: O(1) time.^algebraic-graphs.Extract the underlying relation. Complexity: O(n * m * log(m)) time.0]^0]^(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.com experimentalNone 345<FKNTV _algebraic-graphs%A type synonym for unlabelled graphs.`algebraic-graphs.Edge-labelled graphs, where the type variable e' stands for edge labels. For example,  Graph Bool aE is isomorphic to unlabelled graphs defined in the top-level module Algebra.Graph.Graph, where False and TrueK denote the lack of and the existence of an unlabelled edge, respectively.dalgebraic-graphsConstruct the  empty graph. An alias for the constructor a. Complexity: O(1) time, memory and size.ealgebraic-graphsConstruct the graph comprising a single isolated vertex . An alias for the constructor b. Complexity: O(1) time, memory and size.falgebraic-graphsConstruct the graph comprising  a single edge with the label <. Complexity: O(1) time, memory and size.galgebraic-graphsOverlay two graphs. An alias for c ?Q. This is a commutative, associative and idempotent operation with the identity d. Complexity: O(1) time and memory,  O(s1 + s2) size.halgebraic-graphsConnect two graphs. An alias for c <6. This is an associative operation with the identity d, which distributes over gB and obeys the decomposition axiom. See the full list of laws in  Algebra.Graph. 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).ialgebraic-graphsConnect@ two graphs with edges labelled by a given label. An alias for c. 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).jalgebraic-graphs8The left-hand part of a convenient ternary-ish operator  x -<e>- y9 for connecting graphs with labelled edges. For example: x = e "x" y = e "y" z = x -<2>- y kalgebraic-graphs9The right-hand part of a convenient ternary-ish operator  x -<e>- y9 for connecting graphs with labelled edges. For example: x = e "x" y = e "y" z = x -<2>- y lalgebraic-graphs3Extract the label of a specified edge from a graph._`abcdefghijkl`abc_defghijklj5k5HIJ3? KLMNOP*3> QLRSTUVWXYZZ[\]^__`abcdefghijklmnopqrstuvwxyz{|}~ L,"4-.1!A#2$5  , " 4     - . 1 ! A # 2 $ 5 :  , " 4     - . 1 ! A # 2 $ 5 :   @         , " 4     - . 1 ! > ? A # 2 $   C     - . 1 ! > ? 5 :   4.1 $     ,"4-.1!A#$ !"#$%&@ ,"4-1A'2()#$%&@ ,"4A'2*+,-./0(1)23456789:;<=>?@ABCDEFFGHHIJJKLLMNOPQRSTUVWXYZ[\]^_`abcdefghihijhihik@ lmno)HpqHrstuvwxwyzw{w{zwyGw{Gw|w}zw~w~zw}Gw~GHIHIHIHIHIH8EH8H8H8H89H8H8tH67tHFwwHIHItuHH8   HI        H;H;=w~w~0w~w{HHIHrHHHpHIHI&HHIHIHI+algebraic-graphs-0.2-FKkoIXwzRuzFPludlUk2d8 Algebra.Graph.HigherKinded.Class&Algebra.Graph.AdjacencyIntMap.Internal#Algebra.Graph.AdjacencyMap.InternalAlgebra.Graph.InternalAlgebra.Graph.LabelAlgebra.Graph.Relation.InternalAlgebra.Graph.RelationData.Graph.TypedAlgebra.Graph.AdjacencyMapAlgebra.Graph.AdjacencyIntMap Algebra.GraphAlgebra.Graph.ToGraphAlgebra.Graph.ExportAlgebra.Graph.Export.DotAlgebra.Graph.NonEmptyAlgebra.Graph.FoldAlgebra.Graph.Class&Algebra.Graph.Relation.InternalDerived!Algebra.Graph.Relation.Transitive Algebra.Graph.Relation.Symmetric Algebra.Graph.Relation.ReflexiveAlgebra.Graph.Relation.PreorderAlgebra.Graph.LabelledoverlayconnectemptyedgeisEmpty hasVertex vertexCount edgeCountvertex adjacencyListedgesstars removeEdge Data.Monoid<> Data.Listnubsort AdjacencyMap Data.Graphvertices vertexListedgeList Data.IntSet toAscList vertexIntSetforestAM isSubgraphOf dfsForestFrom Data.Tupleswap Data.Foldablelength reachable Data.EitherrightsRight adjacencyMapadjacencyIntMapGraphcircuitCtoGraphData.List.NonEmptytoListreversefromListbaseGHC.BaseAdjacencyIntMapfromAdjacencyIntSets consistent$fNFDataAdjacencyIntMap$fNumAdjacencyIntMap$fShowAdjacencyIntMap$fEqAdjacencyIntMapfromAdjacencySets$fNFDataAdjacencyMap$fNumAdjacencyMap$fShowAdjacencyMap$fEqAdjacencyMapHitMissTailEdgeFocusokisosvsList emptyFocus vertexFocus overlayFoci connectFoci foldr1Safe $fMonadList$fApplicativeList $fFunctorList$fFoldableList $fIsListList $fOrdList$fEqList $fShowList $fMonoidList$fSemigroupList$fEqHit$fOrdHitDistanceFiniteInfiniteDioidone/\ Semilatticezero\/$fSemilatticeSet$fSemilatticeBool $fDioidBool$fDioidDistance$fSemilatticeDistance $fNumDistance $fEqDistance $fOrdDistance$fShowDistanceRelationdomainrelation setProductreferredToVertexSet $fNumRelation$fNFDataRelation$fShowRelation $fEqRelationoverlaysconnectshasEdge vertexSetedgeSetpreSetpostSetpathcliquebicliquestartree removeVertex replaceVertex mergeVertices transposegmapinducecomposereflexiveClosuresymmetricClosuretransitiveClosurepreorderClosureGraphKL toGraphKL fromVertexKL toVertexKLfromAdjacencyMapfromAdjacencyIntMap dfsForestdfstopSort isAcyclicscc isDfsForestOf isTopSortOf preIntSet postIntSetContextinputsoutputsEmptyVertexOverlayConnectfoldg===sizemeshtorusdeBruijn splitVertexsimplifyboxcontextsparsify$fMonadPlusGraph$fAlternativeGraph $fMonadGraph$fApplicativeGraph $fEqGraph $fNumGraph $fNFDataGraph$fFoldableGraph$fFunctorGraph $fShowGraph$fTraversableGraphToGraphToVertexadjacencyMapTransposeadjacencyIntMapTransposetoAdjacencyMaptoAdjacencyMapTransposetoAdjacencyIntMaptoAdjacencyIntMapTranspose$fToGraphRelation$fToGraphAdjacencyIntMap$fToGraphAdjacencyMap$fToGraphGraphDocliteralrender<+>brackets doubleQuotesindentunlinesexport $fIsStringDoc$fOrdDoc$fEqDoc $fShowDoc $fMonoidDoc$fSemigroupDocStyle graphNamepreamblegraphAttributesdefaultVertexAttributesdefaultEdgeAttributes vertexNamevertexAttributesedgeAttributes Attribute:= defaultStyledefaultStyleViaShow exportAsIs exportViaShow NonEmptyGraphtoNonEmptyGraphoverlay1 vertices1edges1 overlays1 connects1foldg1 vertexList1path1circuit1clique1 biclique1stars1mesh1torus1 removeVertex1 splitVertex1induce1$fMonadNonEmptyGraph$fApplicativeNonEmptyGraph$fEqNonEmptyGraph$fNumNonEmptyGraph$fToGraphNonEmptyGraph$fNFDataNonEmptyGraph$fFoldableNonEmptyGraph$fFunctorNonEmptyGraph$fShowNonEmptyGraph$fTraversableNonEmptyGraphFold $fToGraphFold$fTraversableFold$fFoldableFold $fMonadFold$fMonadPlusFold$fAlternativeFold$fApplicativeFold $fFunctorFold $fNumFold $fNFDataFold$fEqFold $fShowFoldPreorder Transitive Reflexive Undirected starTranspose $fGraphFold $fGraphGraph $fGraph(,,) $fGraph(,) $fGraph(->) $fGraphMaybe $fGraph()$fGraphRelation$fGraphAdjacencyIntMap$fGraphAdjacencyMap$fUndirected(,,)$fUndirected(,)$fUndirected(->)$fUndirectedMaybe$fUndirected()$fReflexive(,,)$fReflexive(,)$fReflexive(->)$fReflexiveMaybe $fReflexive()$fTransitive(,,)$fTransitive(,)$fTransitive(->)$fTransitiveMaybe$fTransitive()$fPreorder(,,) $fPreorder(,)$fPreorder(->)$fPreorderMaybe $fPreorder()PreorderRelation fromPreorderTransitiveRelationfromTransitiveSymmetricRelation fromSymmetricReflexiveRelation fromReflexive$fReflexiveReflexiveRelation$fGraphReflexiveRelation$fShowReflexiveRelation$fEqReflexiveRelation$fUndirectedSymmetricRelation$fGraphSymmetricRelation$fShowSymmetricRelation$fEqSymmetricRelation$fTransitiveTransitiveRelation$fGraphTransitiveRelation$fShowTransitiveRelation$fEqTransitiveRelation$fPreorderPreorderRelation$fTransitivePreorderRelation$fReflexivePreorderRelation$fGraphPreorderRelation$fEqPreorderRelation$fShowPreorderRelation$fNumReflexiveRelation$fNFDataReflexiveRelation$fNumSymmetricRelation$fNFDataSymmetricRelation$fNumTransitiveRelation$fNFDataTransitiveRelation$fNumPreorderRelation$fNFDataPreorderRelation fromRelation toRelation neighboursUnlabelledGraph connectBy-<>- edgeLabelGHC.NumNumGHC.ShowShowghc-prim GHC.ClassesEqcontainers-0.5.11.0Data.IntMap.InternalData.IntMap.Strict singletonData.IntSet.InternalData.Map.InternalData.Map.Strict.InternalData.Set.InternalMonoidmemptymappendpure ApplicativeFoldablefoldr1elemfoldrall GHC.TypesTrueIntGHC.List Data.TreeTreeForestfmapNothingOrd Data.MaybeisJustnullequals equalsIntconcatgmconcatvertexIntCount edgeCountInt vertexIntList edgeIntList edgeIntSetpairs filterContextfocusLeftunion Data.StringIsStringidshow fromStringGHC.Realodd attributessignum:|concatg1vertexIntList1pairs1appendNonEmpty Control.Monad>=> MonadPlus Alternative<|>