Зн! <= WЪ~ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~─│┌┐└┘├┤┬┴┼▀▄█▌▐░▒▓⌠■∙√≈≤≥ ⌡°²·÷═║╒ёє╔ії╗╘╙╚╛ґў╞╟╠╡ЁЄ╣ІЇ╦╧╨╩╪ҐЎ©юабцдефгхийклмнопярстужвьызшэщчъЮАБЦДЕФГХИЙКЛМНОПЯРСТУЖВЬЫЗШЭЩЧЪ !"#$%&'()*+,-./0123456789:;<=>?@ABC D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p qrstuvwxyz{|}~─│┌┐└┘├┤┬┴┼▀▄█▌▐░▒▓⌠■∙√≈≤≥ ⌡°²·÷═║╒ёє╔ії╗╘╙╚╛ґў╞╟╠╡Ё Є ╣ І Ї ╦ ╧ ╨ ╩ ╪ҐЎ©юабцдефгхийклмнопярстужвьызшэщчъЮАБЦДЕФГХИЙКЛМНОПЯРСТУЖВЬЫЗШЭЩЧЪ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~─│┌┐└┘├┤┬┴┼▀▄█▌▐░▒▓⌠■∙√≈≤≥ ⌡°²·÷═║╒ёє╔ії╗╘╙╚╛ґў╞╟╠╡ЁЄ╣ІЇ╦╧╨╩╪ҐЎ©юабцдефгхийклмнопярстужвьызшэщчъЮАБЦДЕФГХИЙКЛМНОПЯРСТУЖВЬЫЗШЭЩЧЪ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone=>?HMPVXhбalgebraic-graphsThe X data type represents a graph by a map of vertices to their adjacency sets. We define a ~; instance as a convenient notation for working with graphs:У0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))Note: the ~7 instance does not satisfy several "customary laws" of ~, which dictate that 0 and 1; should act as additive and multiplicative identities, and ─0 as additive inverse. Nevertheless, overloading , │ and ┌И is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ┐? instance is defined using basic graph construction primitives:Ъ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 └3 instance satisfies all axioms of algebraic graphs: is commutative and associative:/ x + y == y + x x + (y + z) == (x + y) + z! is associative and has " as the identity:< x * empty == x empty * x == x x * (y * z) == (x * y) * z! distributes over :9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z! can be decomposed:"x * y * z == x * y + x * z + y * zIThe following useful theorems can be proved from the above set of axioms. has "# as the identity and is idempotent:2 x + empty == x empty + x == x x + x == xAbsorption and saturation of !:-x * y + x + y == x * y x * x * x == x * xDWhen specifying the time and memory complexity of graph algorithms, n and mI will denote the number of vertices and edges in the graph, respectively.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:# 1 < # 2 # 3 < $ 1 2 # 1 < $ 1 1 $ 1 1 < $ 1 2 $ 1 2 < $ 1 1 + $ 2 2 $ 1 2 < $ 1 3*Note that the resulting order refines the %! relation and is compatible with and ! operations:% x y ==> x <= y"# <= x x <= x + y x + y <= x * yalgebraic-graphsThe adjacency mapY of a graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory.adjacencyIntMap empty == IntMap.┘ adjacencyIntMap (vertex x) == IntMap.├ x IntSet.┤ adjacencyIntMap ($ 1 1) == IntMap.├ 1 (IntSet.┬ 1) adjacencyIntMap ($ 1 2) == IntMap.┴ [(1,IntSet.┬ 2), (2,IntSet.┤)] algebraic-graphsсCheck if the internal graph representation is consistent, i.e. that all edges refer to existing vertices. It should be impossible to create an inconsistent adjacency map, and we use this function in testing. ,Note: this function is for internal use only.consistent " == True consistent (# x) == True consistent ( x y) == True consistent (! x y) == True consistent ($ x y) == True consistent (& xs) == True consistent (' xs) == True algebraic-graphsNote:0 this does not satisfy the usual ring laws; see for more details.(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXH?+ 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-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-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-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.▄ 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) (!C xs) == True isSubgraphOf x y ==> x <= y algebraic-graphs(Check if a graph is empty. Complexity: O(1) time.isEmpty ( == True isEmpty ( ) == True isEmpty (' x) == False isEmpty () x $ x) == True isEmpty (* x y $ x y) == False algebraic-graphs7Check if a graph contains a given vertex. Complexity: O(log(n)) time.hasVertex x " == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x . ) x == ░ False algebraic-graphs5Check if a graph contains a given edge. Complexity: O(log(n)) time.hasEdge x y " == False hasEdge x y ( z) == False hasEdge x y (" x y) == True hasEdge x y . * x y == ░' False hasEdge x y == ┼ (x,y) . algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.vertexCount == 0 vertexCount (3 x) == 1 vertexCount == ▀ . ) vertexCount x < vertexCount y ==> x < y algebraic-graphs-The number of edges in a graph. Complexity: O(n) time. edgeCount == 0 edgeCount ( x) == 0 edgeCount (# x y) == 1 edgeCount == ▀ . algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.vertexList == [] vertexList ( x) == [x] vertexList . == () . (* algebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory. edgeList == [] edgeList ( x) == [] edgeList ( x y) == [(x,y)] edgeList ($' 2 [3,1]) == [(2,1), (2,3)] edgeList . == () . (* edgeList . - == (* . ▒ +, . edgeList algebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory. vertexIntSet == IntSet.┤ vertexIntSet . == IntSet.┬ vertexIntSet . == IntSet.▄ vertexIntSet . " == IntSet.▄ 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-graphsThe 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.┤ postIntSet x ( x) == IntSet.┤ postIntSet x ( x y) == IntSet.▄ [y] postIntSet 2 ( 1 2) == IntSet.┤ 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 == . ▒ (√ $ ) stars . == id + (stars xs) (stars ys) == stars (xs ++ ys) &algebraic-graphs@Construct a graph from a list of adjacency sets; a variation of %. Complexity: O((n + m) * log(n)) time and O(n + m) memory.?fromAdjacencyIntSets [] == " fromAdjacencyIntSets [(x, IntSet.┤)] == $ x fromAdjacencyIntSets [(x, IntSet.┬ y)] == x y fromAdjacencyIntSets . ▒ (≈ IntSet.▄) == % X (fromAdjacencyIntSets xs) (fromAdjacencyIntSets ys) == fromAdjacencyIntSets (xs ++ ys) '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 == . ▒ ' )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.mergeVertices (░7 False) x == id mergeVertices (== x) y == + x y mergeVertices & 1 (0 * 2) == 1 * 1 mergeVertices ⌡ 1 (3 + 4 * 5) == 4 * 1 -algebraic-graphs&Transpose a given graph. Complexity: O(m * log(n)) time, O(n + m) memory. transpose == transpose ( x) == x transpose ( x y) == ! y x transpose . transpose == id . transpose == (* . ▒ +, . .algebraic-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 (░ True ) x == x induce (░ False) x == induce (/= x) == )< x induce p . induce q == induce (\x -> p x && q x) (induce p x) x == True 0algebraic-graphsLeft-to-right relational composition of graphs: vertices x and z< are connected in the resulting graph if there is a vertex y, such that x is connected to y in the first graph, and y is connected to zi in the second graph. There are no isolated vertices in the result. This operation is associative, has and single- graphs as annihilating zeroes, and distributes over . Complexity: O(n * m * log(n)) time and O(n + m) memory.compose x == compose x == compose ( x) y == compose x ( y) == ` compose x (compose y z) == compose (compose x y) z compose x ( y z) == & (compose x y) (compose x z) compose ( x y) z == & (compose x z) (compose y z) compose ( x y) ( y z) == x z compose ( [1..5]) ( [1..5]) == [(1,3), (2,4), (3,5)] compose (! [1..5]) (! [1..5]) == ! [1,3,5,2,4] 1algebraic-graphsCompute the reflexive and transitive closure of a graph. Complexity: O(n * m * log(n)^2) time.closure == closure ( x) == x x closure ( x x) == x x closure ( x y) == [(x,x), (x,y), (y,y)] closure ( $ () xs) == 2 (" $ ()! xs) closure == 2 . 4 closure == 4 . 2% closure . closure == closure x (closure y) == IntSet.▄ (- x y) 2algebraic-graphsCompute the reflexive closureA of a graph by adding a self-loop to every vertex. Complexity: O(n * log(n)) time.reflexiveClosure == reflexiveClosure ( x) == x x reflexiveClosure ( x x) == x x reflexiveClosure ( x y) == O [(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure 3algebraic-graphsCompute the symmetric closureC of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time.symmetricClosure == symmetricClosure ( x) == x symmetricClosure ( x y) == 7 [(x,y), (y,x)] symmetricClosure x == x (-< x) symmetricClosure . symmetricClosure == symmetricClosure 4algebraic-graphsCompute the transitive closure of a graph. Complexity: O(n * m * log(n)^2) time.transitiveClosure == transitiveClosure ( x) == x transitiveClosure ( x y) == x y transitiveClosure ( $ () xs) == " (()@ xs) transitiveClosure . transitiveClosure == transitiveClosure - !"#$%&'()*+,-./01234- !"#$%&'()*+,-./01234(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone=>?HMPVX┤в5algebraic-graphsThe 5X data type represents a graph by a map of vertices to their adjacency sets. We define a ~; instance as a convenient notation for working with graphs:У0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))Note: the ~7 instance does not satisfy several "customary laws" of ~, which dictate that 0 and 1; should act as additive and multiplicative identities, and ─0 as additive inverse. Nevertheless, overloading , │ and ┌И is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ┐? instance is defined using basic graph construction primitives:ЪZshow (empty :: AdjacencyMap Int) == "empty" show (1 :: AdjacencyMap Int) == "vertex 1" show (1 + 2 :: AdjacencyMap Int) == "vertices [1,2]" show (1 * 2 :: AdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyMap Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"The └3 instance satisfies all axioms of algebraic graphs: is commutative and associative:/ x + y == y + x x + (y + z) == (x + y) + z! is associative and has " as the identity:< x * empty == x empty * x == x x * (y * z) == (x * y) * z! distributes over :9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z! can be decomposed:"x * y * z == x * y + x * z + y * zIThe following useful theorems can be proved from the above set of axioms. has "' as the identity and is idempotent:2 x + empty == x empty + x == x x + x == xAbsorption and saturation of !:-x * y + x + y == x * y x * x * x == x * xDWhen specifying the time and memory complexity of graph algorithms, n and mI will denote the number of vertices and edges in the graph, respectively.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:# 1 < # 2 # 3 < $ 1 2 # 1 < $ 1 1 $ 1 1 < $ 1 2 $ 1 2 < $ 1 1 + $ 2 2 $ 1 2 < $ 1 3*Note that the resulting order refines the %! relation and is compatible with and ! operations:% x y ==> x <= y"# <= x x <= x + y x + y <= x * y7algebraic-graphsThe adjacency mapY of a graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory. adjacencyMap " == Map.° adjacencyMap (# x) == Map.² x Set.▓ adjacencyMap ($ 1 1) == Map.² 1 (Set.⌠ 1) adjacencyMap ($ 1 2) == Map.· [(1,Set.⌠ 2), (2,Set.▓)] 8algebraic-graphsсCheck if the internal graph representation is consistent, i.e. that all edges refer to existing vertices. It should be impossible to create an inconsistent adjacency map, and we use this function in testing. ,Note: this function is for internal use only.consistent " == True consistent (# x) == True consistent ( x y) == True consistent (! x y) == True consistent ($ x y) == True consistent (& xs) == True consistent (' xs) == True 9algebraic-graphs(The list of edges of an adjacency map. ,Note: this function is for internal use only.:algebraic-graphsLThe set of vertices that are referred to by the edges of an adjacency map. ,Note: this function is for internal use only.<algebraic-graphsNote:0 this does not satisfy the usual ring laws; see 5 for more details.56789:56789:(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXes+@algebraic-graphsConstruct the empty graph. Complexity: O(1) time and memory.J empty == True K x empty == False M empty == 0 N empty == 0 Aalgebraic-graphsConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.J (vertex x) == False K x (vertex x) == True M (vertex x) == 1 N (vertex x) == 0 Balgebraic-graphsConstruct the graph comprising a single edge. Complexity: O(1) time, memory.edge x y == D (A x) (A y) L x y (edge x y) == True N (edge x y) == 1 M (edge 1 1) == 1 M (edge 1 2) == 2 Calgebraic-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.J (overlay x y) == J x && J y K z (overlay x y) == K z x || K z y M (overlay x y) >= M x M (overlay x y) <= M x + M y N (overlay x y) >= N x N (overlay x y) <= N x + N y M (overlay 1 2) == 2 N (overlay 1 2) == 0 Dalgebraic-graphsConnectA two graphs. This is an associative operation with the identity @, which distributes over C1 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).J (connect x y) == J x && J y K z (connect x y) == K z x || K z y M (connect x y) >= M x M (connect x y) <= M x + M y N (connect x y) >= N x N (connect x y) >= N y N (connect x y) >= M x * M y N (connect x y) <= M x * M y + N x + N y M (connect 1 2) == 2 N (connect 1 2) == 1 Ealgebraic-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] == A x K x . vertices == ┼ x M . vertices == ▀ . () Q . vertices == Set.■ Falgebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory.edges [] == @ edges [(x,y)] == B x y N . edges == ▀ . () P . edges == () . (* Galgebraic-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] == C x y overlays == █ C @ J . overlays == ▌ J Halgebraic-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] == D x y connects == █ D @ J . connects == ▌ J Ialgebraic-graphsThe I' function takes two graphs and returns ▐ if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time. isSubgraphOf @. x == True isSubgraphOf (A x) @/ == False isSubgraphOf x (C x y) == True isSubgraphOf (C x y) (D x y) == True isSubgraphOf (V xs) (WC xs) == True isSubgraphOf x y ==> x <= y Jalgebraic-graphs(Check if a graph is empty. Complexity: O(1) time.isEmpty @( == True isEmpty (C @ @) == True isEmpty (A' x) == False isEmpty (_ x $ A x) == True isEmpty (` x y $ B x y) == False Kalgebraic-graphs7Check if a graph contains a given vertex. Complexity: O(log(n)) time.hasVertex x @" == False hasVertex x (A x) == True hasVertex 1 (A! 2) == False hasVertex x . _ x == ░ False Lalgebraic-graphs5Check if a graph contains a given edge. Complexity: O(log(n)) time.hasEdge x y @" == False hasEdge x y (A z) == False hasEdge x y (B" x y) == True hasEdge x y . ` x y == ░' False hasEdge x y == ┼ (x,y) . P Malgebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.vertexCount @ == 0 vertexCount (A3 x) == 1 vertexCount == ▀ . O) vertexCount x < vertexCount y ==> x < y Nalgebraic-graphs-The number of edges in a graph. Complexity: O(n) time. edgeCount @ == 0 edgeCount (A x) == 0 edgeCount (B# x y) == 1 edgeCount == ▀ . P Oalgebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.vertexList @ == [] vertexList (A x) == [x] vertexList . E == () . (* Palgebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory. edgeList @ == [] edgeList (A x) == [] edgeList (B x y) == [(x,y)] edgeList (Z' 2 [3,1]) == [(2,1), (2,3)] edgeList . F == () . (* edgeList . c == (* . ▒ +, . edgeList Qalgebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory. vertexSet @ == Set.▓ vertexSet . A == Set.⌠ vertexSet . E == Set.■ Ralgebraic-graphs0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory.edgeSet @ == Set.▓ edgeSet (A x) == Set.▓ edgeSet (B x y) == Set.⌠ (x,y) edgeSet . F == Set.■ Salgebraic-graphsThe sorted adjacency list of a graph. Complexity: O(n + m) time and O(m) memory.adjacencyList @ == [] adjacencyList (A$ x) == [(x, [])] adjacencyList (B0 1 2) == [(1, [2]), (2, [])] adjacencyList (Z, 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] [ . adjacencyList == id Talgebraic-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 (A x) == Set.▓ preSet 1 (B 1 2) == Set.▓ preSet y (B x y) == Set.■ [x] Ualgebraic-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 (A x) == Set.▓ postSet x (B x y) == Set.■ [y] postSet 2 (B 1 2) == Set.▓ Valgebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory.path [] == @ path [x] == A x path [x,y] == B x y path . ∙ == c . path Walgebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory.circuit [] == @ circuit [x] == B x x circuit [x,y] == F [(x,y), (y,x)] circuit . ∙ == c . circuit Xalgebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory.clique [] == @ clique [x] == A x clique [x,y] == B x y clique [x,y,z] == F" [(x,y), (x,z), (y,z)] clique (xs ÷ ys) == D" (clique xs) (clique ys) clique . ∙ == c . clique Yalgebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory.biclique [] [] == @ biclique [x] [] == A x biclique [] [y] == A y biclique [x1,x2] [y1,y2] == FB [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == D (E xs) (E ys) Zalgebraic-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 [] == A x star x [y] == B x y star x [y,z] == F [(x,y), (x,z)] star x ys == D (A x) (E ys) [algebraic-graphsThe stars formed by overlaying a list of Zs. An inverse of S. Complexity: O(L * log(n)) time, memory and size, where L! is the total size of the input.!stars [] == @" stars [(x, [])] == A$ x stars [(x, [y])] == B& x y stars [(x, ys)] == Z' x ys stars == G . ▒ (√ Z ) stars . S == id C$ (stars xs) (stars ys) == stars (xs ÷ ys) \algebraic-graphs@Construct a graph from a list of adjacency sets; a variation of [. Complexity: O((n + m) * log(n)) time and O(n + m) memory.9fromAdjacencySets [] == @ fromAdjacencySets [(x, Set.▓)] == A x fromAdjacencySets [(x, Set.⌠ y)] == B x y fromAdjacencySets . ▒ (≈ Set.■) == [ CH (fromAdjacencySets xs) (fromAdjacencySets ys) == fromAdjacencySets (xs ÷ ys) ]algebraic-graphsThe tree graph constructed from a given ≤ data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory.<tree (Node x []) == A? x tree (Node x [Node y [Node z []]]) == VE [x,y,z] tree (Node x [Node y [], Node z []]) == ZE x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == F [(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 []]] == FU [(1,2), (1,3), (4,5)] forest == G . ▒ ] _algebraic-graphs1Remove a vertex from a given graph. Complexity: O(n*log(n)) time.removeVertex x (A x) == @ removeVertex 1 (A 2) == A 2 removeVertex x (B x x) == @ removeVertex 1 (B 1 2) == A5 2 removeVertex x . removeVertex x == removeVertex x `algebraic-graphs0Remove an edge from a given graph. Complexity: O(log(n)) time.removeEdge x y (B x y) == EJ [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 aalgebraic-graphs The function a x y replaces vertex x with vertex y in a given 5. If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time.6replaceVertex x x == id replaceVertex x y (A x) == A# y replaceVertex x y == b (== x) y balgebraic-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.mergeVertices (░7 False) x == id mergeVertices (== x) y == a x y mergeVertices & 1 (0 * 2) == 1 * 1 mergeVertices ⌡ 1 (3 + 4 * 5) == 4 * 1 calgebraic-graphs&Transpose a given graph. Complexity: O(m * log(n)) time, O(n + m) memory. transpose @ == @ transpose (A x) == A x transpose (B x y) == B! y x transpose . transpose == id P . transpose == (* . ▒ +, . P dalgebraic-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 5. Complexity: O((n + m) * log(n)) time.gmap f @ == @ gmap f (A x) == A (f x) gmap f (B x y) == B (f x) (f y) gmap ═ == ═# gmap f . gmap g == gmap (f . g) ealgebraic-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 (░ True ) x == x induce (░ False) x == @ induce (/= x) == _< x induce p . induce q == induce (\x -> p x && q x) I (induce p x) x == True falgebraic-graphsLeft-to-right relational composition of graphs: vertices x and z< are connected in the resulting graph if there is a vertex y, such that x is connected to y in the first graph, and y is connected to zi in the second graph. There are no isolated vertices in the result. This operation is associative, has @ and single-A graphs as annihilating zeroes, and distributes over C. Complexity: O(n * m * log(n)) time and O(n + m) memory.compose @ x == @ compose x @ == @ compose (A x) y == @ compose x (A y) == @` compose x (compose y z) == compose (compose x y) z compose x (C y z) == C& (compose x y) (compose x z) compose (C x y) z == C& (compose x z) (compose y z) compose (B x y) (B y z) == B x z compose (V [1..5]) (V [1..5]) == F [(1,3), (2,4), (3,5)] compose (W [1..5]) (W [1..5]) == W [1,3,5,2,4] galgebraic-graphsCompute the reflexive and transitive closure of a graph. Complexity: O(n * m * log(n)^2) time.closure @ == @ closure (A x) == B x x closure (B x x) == B x x closure (B x y) == F [(x,x), (x,y), (y,y)] closure (V $ () xs) == h (X $ () xs) closure == h . j closure == j . h$ closure . closure == closure U x (closure y) == Set.■ (- x y) halgebraic-graphsCompute the reflexive closureA of a graph by adding a self-loop to every vertex. Complexity: O(n * log(n)) time.reflexiveClosure @ == @ reflexiveClosure (A x) == B x x reflexiveClosure (B x x) == B x x reflexiveClosure (B x y) == FO [(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure ialgebraic-graphsCompute the symmetric closureC of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time.symmetricClosure @ == @ symmetricClosure (A x) == A x symmetricClosure (B x y) == F7 [(x,y), (y,x)] symmetricClosure x == C x (c< x) symmetricClosure . symmetricClosure == symmetricClosure jalgebraic-graphsCompute the transitive closure of a graph. Complexity: O(n * m * log(n)^2) time.transitiveClosure @ == @ transitiveClosure (A x) == A x transitiveClosure (B x y) == B x y transitiveClosure (V $ () xs) == X (()@ xs) transitiveClosure . transitiveClosure == transitiveClosure -57@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghij-57@ABCDEFGHIJKLMNOPSQRTUVWXYZ[\]^_`abcdefghij(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVX├kalgebraic-graphsAn auxiliary data type for hasEdge.: when searching for an edge, we can hit its m$, i.e. the source vertex, the whole n, or l it entirely.oalgebraic-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.palgebraic-graphs.All vertices (leaves) of the graph expression.qalgebraic-graphs4True if focus on the specified subgraph is obtained.ralgebraic-graphs!Inputs into the focused subgraph.salgebraic-graphs$Outputs out of the focused subgraph.ualgebraic-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. u a is a ║: ╒G corresponds to the empty list and two lists can be concatenated with ё (or operator /0:). Singleton lists can be constructed using the function є from the ╔ instance. u a is also an instance of IsList-, therefore you can use list literals, e.g. [1,4] :: u Int is the same as є 1 /0 є 4; note that this requires the OverloadedLists@ GHC extension. To extract plain Haskell lists you can use the і function from the ї instance.walgebraic-graphsFocus on the empty graph.xalgebraic-graphsiFocus on the graph with a single vertex, given a predicate indicating whether the vertex is of interest.yalgebraic-graphsOverlay two foci.zalgebraic-graphsConnect two foci.{algebraic-graphsA safe version of ╗.|algebraic-graphsTragetting ▒ directlyEAuxiliary function that try to apply a function to a base case and a ╘ value and return ╙ the result or ╙ the base case.}algebraic-graphs*Compute the Cartesian product of two sets.~algebraic-graphsWCompute the Cartesian product of two sets, applying a function to each resulting pair.knlmopstrquvwxyz{|}~uvopstrqwxyzknlm{|}~(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPSVXГ2▀algebraic-graphsThe ▀ of a subgraph comprises its █ and ▌й, i.e. all the vertices that are connected to the subgraph's vertices. Note that inputs and outputs can belong to the subgraph itself. In general, there are no guarantees on the order of vertices in █ and ▌); furthermore, there may be repetitions.▐algebraic-graphsThe ▐I data type is a deep embedding of the core graph construction primitives ■, ∙, ≈ and ≤. We define a ~; instance as a convenient notation for working with graphs:У0 == 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: the ~7 instance does not satisfy several "customary laws" of ~, which dictate that 0 and 1; should act as additive and multiplicative identities, and ─0 as additive inverse. Nevertheless, overloading , │ and ┌И is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The └- instance is currently implemented using the 5 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 ║% counts all leaves of the expression:є ■ == 0 ║ ■ == 1 є (∙ x) == 1 ║ (∙ x) == 1 є (■ + ■) == 0 ║ (■ + ■) == 2 Converting a ▐ to the corresponding 5 takes O(s + m * log(m)) time and O(s + m)╨ memory. This is also the complexity of the graph equality test, because it is currently implemented by converting graph expressions to canonical representations based on adjacency maps.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:∙ 1 < ∙ 2 ∙ 3 < √ 1 2 ∙ 1 < √ 1 1 √ 1 1 < √ 1 2 √ 1 2 < √ 1 1 + √ 2 2 √ 1 2 < √ 1 3*Note that the resulting order refines the ·! relation and is compatible with ≈ and ≤ operations:· x y ==> x <= y■# <= x x <= x + y x + y <= x * y■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-graphsGeneralised ▐! 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 ■ ∙ ≈ (╚ ≤) == ╩ foldg 1 (░" 1) (+) (+) == ║ foldg True (░" False) (&&) (&&) == ═5 foldg False (== x) (||) (||) == ╒ x ·algebraic-graphsThe ·' function takes two graphs and returns ▐ if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges 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) (╛C xs) == True isSubgraphOf x y ==> x <= y ÷algebraic-graphs7Structural equality on graph expressions. Complexity: O(s) time.* x === x == True x === x + ■` == False x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False ═algebraic-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-graphs7Check if a graph contains a given vertex. Complexity: O(s) time.hasVertex x ■" == False hasVertex x (∙ x) == True hasVertex 1 (∙! 2) == False hasVertex x . І x == ░ False ёalgebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.hasEdge x y ■" == False hasEdge x y (∙ z) == False hasEdge x y (√" x y) == True hasEdge x y . Ї x y == ░' False hasEdge x y == ┼ (x,y) . ї єalgebraic-graphs0The number of vertices in a graph. Complexity: O(s * log(n)) time.vertexCount ■ == 0 vertexCount (∙3 x) == 1 vertexCount == ▀ . і) vertexCount x < vertexCount y ==> x < y ╔algebraic-graphs-The number of edges in a graph. Complexity: O(s + m * log(m))% time. Note that the number of edges 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 . ╩ == (* . ▒ +, . 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.■ ╘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-graphsThe 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 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 == ⌡ . ▒ (√ ╞ ) 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 == ⌡ . ▒ ╠ Ёalgebraic-graphsConstruct 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-graphsConstruct 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-graphsConstruct 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 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.mergeVertices (░7 False) x == id mergeVertices (== x) y == ╦ x y mergeVertices & 1 (0 * 2) == 1 * 1 mergeVertices ⌡ 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 == (* . ▒ +, . ї ╪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 (░ True ) x == x induce (░ False) x == ■ induce (/= x) == І< x induce p . induce q == induce (\x -> p x && q x) · (induce p x) x == True Ґalgebraic-graphsЪDSimplify a graph expression. Semantically, this is the identity function, but it simplifies a given expression according to the laws of the algebra. The function does not compute the simplest possible expression, but uses heuristics to obtain useful simplifications in reasonable time. Complexity: the function performs O(s)s graph comparisons. It is guaranteed that the size of the result does not exceed the size of the given expression.simplify == id ║ (simplify x) <= ║ x simplify ■ ÷ ■ simplify 1 ÷ 1 simplify (1 + 1) ÷ 1 simplify (1 + 2 + 1) ÷ 1 + 2 simplify (1 * 1 * 1) ÷ 1 * 1 Ўalgebraic-graphsLeft-to-right relational composition of graphs: vertices x and z< are connected in the resulting graph if there is a vertex y, such that x is connected to y in the first graph, and y is connected to zi in the second graph. There are no isolated vertices in the result. This operation is associative, has ■ and single-∙ graphs as annihilating zeroes, and distributes over ≈. Complexity: O(n * m * log(n)) time, O(n + m) memory, and O(m1 + m2) size, where n and mK stand for the number of vertices and edges in the resulting graph, while m1 and m2 are the number of edges in the original graphs. Note that the number of edges in the resulting graph may be quadratic, i.e. m = O(m1 * m2)2, but the algebraic representation requires only O(m1 + m2) operations to list them.compose ■ x == ■ compose x ■ == ■ compose (∙ x) y == ■ compose x (∙ y) == ■` compose x (compose y z) == compose (compose x y) z compose x (≈ y z) == ≈& (compose x y) (compose x z) compose (≈ x y) z == ≈& (compose x z) (compose y z) compose (√ x y) (√ y z) == √ x z compose (╚ [1..5]) (╚ [1..5]) == [(1,3), (2,4), (3,5)] compose (╛ [1..5]) (╛ [1..5]) == ╛ [1,3,5,2,4] ║) (compose x y) <= ╔ x + ╔ y + 1 ©algebraic-graphsCompute 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-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 == (* . 12 . - (13 x) . sparsify є (sparsify x) <= є x + ║ x + 1 ╔ (sparsify x) <= 3 * ║ x ║ (sparsify x) <= 3 * ║ x аalgebraic-graphsExtract the ▀8 of a subgraph specified by a given predicate. Returns Nothing$ if the specified subgraph is empty. context (░> False) x == Nothing context (== 1) (√ 1 2) == Just (▀% [ ] [2 ]) context (== 2) (√ 1 2) == Just (▀ [1 ] [ ]) context (░ True ) (√ 1 2) == Just (▀A [1 ] [2 ]) context (== 4) (3 * 1 * 4 * 1 * 5) == Just (▀ [3,1] [1,5]) хalgebraic-graphsNote:0 this does not satisfy the usual ring laws; see ▐ for more details.7▀▄█▌▐░▒▓⌠■∙√≈≤≥ ⌡°²·÷═║╒ёє╔ії╗╘╙╚╛ґў╞╟╠╡ЁЄ╣ІЇ╦╧╨╩╪ҐЎ©юа7▐░▒▓⌠■∙√≈≤≥ ⌡°²·÷═║╒ёє╔ії╗╘╙╚╛ґў╞╟╠╡ЁЄ╣ІЇ╦╧╨╩╪ҐюЎ©▀▄█▌а÷4(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone 4=>?HMPVX2S!нalgebraic-graphsThe сO semiring specialised to /finding the lexicographically smallest widest path/.оalgebraic-graphsThe с semiring specialised to counting all shortest paths.пalgebraic-graphsThe с semiring specialised to finding all shortest paths.яalgebraic-graphsThe сQ semiring specialised to /finding the lexicographically smallest shortest path/.рalgebraic-graphsA path is a list of edges.сalgebraic-graphsAn optimum semiring" obtained by combining a semiring o that defines an optimisation criterion, and a semiring a that describes the arguments7 of an optimisation problem. For example, by choosing o = щ Int and and a = э (р String), we obtain the shortest path semiring( for computing the shortest path in an Int-labelled graph with String vertices.We assume that the semiring o is selective i.e. for all x and y:x <+> y == x || x <+> y == yIn words, the operation Х? always simply selects one of its arguments. For example, the ъ and щ+ semirings are selective, whereas the the ч semiring is not.вalgebraic-graphsA type synonym for regular expressions, built on top of free labels.ьalgebraic-graphsThe type of free labels$ over the underlying set of symbols a,. This data type is an instance of classes Б and А.ыalgebraic-graphsThe power set% over the underlying set of elements a. If a* is a monoid, then the power set forms a А as follows:Г = PowerSet Set.▓ Е = PowerSet $ Set.⌠ ╒ x Х y = PowerSet $ Set.╟# (getPowerSet x) (getPowerSet y) x Ф y = PowerSet $ ~ ё! (getPowerSet x) (getPowerSet y) эalgebraic-graphsIf a is a monoid, э a forms the following А:Г = є ╒ Е = У (Х) = ╠ ╡ (Ф) = ╠ ё $To create a singleton value of type э a use the є function. For example:getMinimum (є "Hello, " Х є) "World!") == Just "Hello, " getMinimum (є "Hello, " Ф є# "World!") == Just "Hello, World!" щalgebraic-graphsA distance% is a non-negative value that can be И or Л. Distances form a А as follows:Г = Р Л Е = 0 (Х) = ╡ (Ф) = (│) чalgebraic-graphsA count% is a non-negative value that can be И or Л. Counts form a Д as follows:Г = 0 Е = 1 (Х) = (│) (Ф) = (┌) ъalgebraic-graphsA capacity% is a non-negative value that can be И or Л. Capacities form a А as follows:Г = 0 Е = Н Л (Х) = Ё (Ф) = ╡ Юalgebraic-graphs!A non-negative value that can be И or Л+. Note: the current implementation of the ~; instance raises an error on negative literals and on the ─ method.Аalgebraic-graphsA dioid is an idempotent semiring", i.e. it satisfies the following idempotence law in addition to the Д laws:x <+> x == xБalgebraic-graphsA star semiring is a Д# with an additional unary operator Ц# satisfying the following two laws:;star a = one <+> a <.> star a star a = one <+> star a <.> aДalgebraic-graphsA semiring extends a commutative ║ with operation ФU that acts similarly to multiplication over the underlying (additive) monoid and has ЕD as the identity. This module also provides two convenient aliases: Г for ╒, and Х for Є), which makes the interface more uniform.FInstances of this type class must satisfy the following semiring laws:Associativity of Х and Ф:Ex <+> (y <+> z) == (x <+> y) <+> z x <.> (y <.> z) == (x <.> y) <.> zIdentities of Х and Ф::zero <+> x == x == x <+> zero one <.> x == x == x <.> oneCommutativity of Х:x <+> y == y <+> x Annihilating Г:%x <.> zero == zero zero <.> x == zeroDistributivity:Mx <.> (y <+> z) == x <.> y <+> x <.> z (x <+> y) <.> z == x <.> z <+> y <.> zГalgebraic-graphs An alias for ╒.Хalgebraic-graphs An alias for Є.Иalgebraic-graphsA finite non-negative value or Nothing if the argument is negative.Йalgebraic-graphs A finite ╣.Кalgebraic-graphs%A non-negative finite value, created unsafely:: the argument is not checked for being non-negative, so unsafeFinite (-1) compiles just fine.Лalgebraic-graphs"The (non-negative) infinite value.Мalgebraic-graphsGet a finite value or Nothing if the value is infinite.Нalgebraic-graphsA non-negative capacity.Оalgebraic-graphsGet the value of a capacity.Пalgebraic-graphsA non-negative count.Яalgebraic-graphsGet the value of a count.Рalgebraic-graphsA non-negative distance.Сalgebraic-graphsGet the value of a distance.Тalgebraic-graphsExtract the minimum or Nothing if it does not exist.Уalgebraic-graphsSThe value corresponding to the lack of minimum, e.g. the minimum of the empty set.Жalgebraic-graphsCheck if a ь is Г.)нопярстужвьызшэщчъЮАБЦДЕФГХИЙКЛМНОПЯРСТУЖ)ДЕФГХБЦАЮИЙКЛМщРСъНОчПЯызшэТУрьЖвстужяпонІ6Ї7Ф7Х6 (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone=>?HMPVXC╚Calgebraic-graphs.Edge-labelled graphs, where the type variable e' stands for edge labels. For example, C Bool aE is isomorphic to unlabelled graphs defined in the top-level module Algebra.Graph.AdjacencyMap, where False and TrueK denote the lack of and the existence of an unlabelled edge, respectively.Ealgebraic-graphsThe adjacency map of an edge-labelled graph: each vertex is associated with a map from its direct successors to the corresponding edge labels.Falgebraic-graphs|Check if the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and there are no Гz-labelled edges. 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.Galgebraic-graphsNote:0 this does not satisfy the usual ring laws; see C for more details.CDEFCDEF (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXЪj%Lalgebraic-graphsConstruct the empty graph. Complexity: O(1) time and memory.X empty == True Y x empty == False \ empty == 0 ] empty == 0 Malgebraic-graphsConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.X (vertex x) == False Y x (vertex x) == True \ (vertex x) == 1 ] (vertex x) == 0 Nalgebraic-graphsConstruct the graph comprising a single edge. Complexity: O(1) time, memory.edge e x y == R e (M x) (M y) edge Г x y == S [x,y] Z x y (edge e x y) == (e /= Г) [ x y (edge e x y) == e ] (edge e x y) == if e == Г then 0 else 1 \ (edge e 1 1) == 1 \ (edge e 1 2) == 2 Oalgebraic-graphs8The left-hand part of a convenient ternary-ish operator x-<e>-y for creating labelled edges. x -<e>- y == N e x y Palgebraic-graphs9The right-hand part of a convenient ternary-ish operator x-<e>-y for creating labelled edges. x -<e>- y == N e x y Qalgebraic-graphsOverlay\ two graphs. This is a commutative, associative and idempotent operation with the identity L. Complexity: O((n + m) * log(n)) time and O(n + m) memory.X (overlay x y) == X x && X y Y z (overlay x y) == Y z x || Y z y \ (overlay x y) >= \ x \ (overlay x y) <= \ x + \ y ] (overlay x y) >= ] x ] (overlay x y) <= ] x + ] y \ (overlay 1 2) == 2 ] (overlay 1 2) == 0 Note: Q/ composes edges in parallel using the operator Х with Г acting as the identity:[ x y $ overlay (N e x y) (N Г x y) == e [ x y $ overlay (N e x y) (N f x y) == e Х f 0Furthermore, when applied to transitive graphs, Q0 composes edges in sequence using the operator Ф with Е acting as the identity:[ x z $ p (overlay (N e x y) (N Е y z)) == e [ x z $ p (overlay (N e x y) (N f y z)) == e Ф f Ralgebraic-graphsConnect┤ two graphs with edges labelled by a given label. When applied to the same labels, this is an associative operation with the identity L, which distributes over Q1 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).X (connect e x y) == X x && X y Y z (connect e x y) == Y z x || Y z y \ (connect e x y) >= \ x \ (connect e x y) <= \ x + \ y ] (connect e x y) <= \ x * \ y + ] x + ] y \ (connect e 1 2) == 2 ] (connect e 1 2) == if e == Г then 0 else 1 Salgebraic-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 [] == L vertices [x] == M x Y x . vertices == ┼ x \ . vertices == ▀ . () ` . vertices == Set.■ Talgebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory.edges [] == L edges [(e,x,y)] == N e x y edges == U . ▒ (\(e, x, y) -> N e x y) Ualgebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.overlays [] == L/ overlays [x] == x overlays [x,y] == Q x y overlays == █ Q L X . overlays == ▌ X Valgebraic-graphs>Construct a graph from a list of adjacency sets. Complexity: O((n + m) * log(n)) time and O(n + m) memory.9fromAdjacencyMaps [] == L fromAdjacencyMaps [(x, Map.°)] == M x fromAdjacencyMaps [(x, Map.² y e)] == if e == Г then S [x,y] else N e x y QH (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == fromAdjacencyMaps (xs ÷ ys) Walgebraic-graphsThe W' 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 L# x == True isSubgraphOf (M x) L4 == False isSubgraphOf x y ==> x <= y Xalgebraic-graphs(Check if a graph is empty. Complexity: O(1) time.isEmpty L* == True isEmpty (Q L L) == True isEmpty (M) x) == False isEmpty (e x $ M x) == True isEmpty (f x y $ N e x y) == False Yalgebraic-graphs7Check if a graph contains a given vertex. Complexity: O(log(n)) time.hasVertex x L" == False hasVertex x (M x) == True hasVertex 1 (M! 2) == False hasVertex x . e x == ░ False Zalgebraic-graphs5Check if a graph contains a given edge. Complexity: O(log(n)) time.hasEdge x y L" == False hasEdge x y (M z) == False hasEdge x y (N e x y) == (e /= Г) hasEdge x y . f x y == ░' False hasEdge x y == ╦ . ╛ . ╧& (\(_,ex,ey) -> ex == x && ey == y) . _ [algebraic-graphs?Extract the label of a specified edge in a graph. Complexity: O(log(n)) time.edgeLabel x y L == Г edgeLabel x y (M z) == Г edgeLabel x y (N e x y) == e edgeLabel s t (Q x y) == edgeLabel s t x + edgeLabel s t y \algebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.vertexCount L == 0 vertexCount (M3 x) == 1 vertexCount == ▀ . ^) vertexCount x < vertexCount y ==> x < y ]algebraic-graphsThe number of (non-Г!) edges in a graph. Complexity: O(n) time. edgeCount L == 0 edgeCount (M x) == 0 edgeCount (N e x y) == if e == Г) then 0 else 1 edgeCount == ▀ . _ ^algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.vertexList L == [] vertexList (M x) == [x] vertexList . S == () . (* _algebraic-graphs·The list of edges of a graph, sorted lexicographically with respect to pairs of connected vertices (i.e. edge-labels are ignored when sorting). Complexity: O(n + m) time and O(m) memory. edgeList L == [] edgeList (M x) == [] edgeList (N e x y) == if e == Г then [] else [(e,x,y)] `algebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory. vertexSet L == Set.▓ vertexSet . M == Set.⌠ vertexSet . S == Set.■ aalgebraic-graphs0The set of edges of a given graph. Complexity: O(n + m) time and O(m) memory.edgeSet L == Set.▓ edgeSet (M x) == Set.▓ edgeSet (N e x y) == if e == Г then Set.▓ else Set.⌠ (e,x,y) balgebraic-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 L == Set.▓ preSet x (M x) == Set.▓ preSet 1 (N e 1 2) == Set.▓ preSet y (N e x y) == if e == Г then Set.▓ else Set.■ [x] calgebraic-graphsThe postset of a vertex is the set of its direct successors. Complexity: O(log(n)) time and O(1) memory. postSet x L == Set.▓ postSet x (M x) == Set.▓ postSet x (N e x y) == if e == Г then Set.▓ else Set.■ [y] postSet 2 (N e 1 2) == Set.▓ dalgebraic-graphs0Convert a graph to the corresponding unlabelled 5" by forgetting labels on all non-Г edges.Z x y == L x y . skeleton ealgebraic-graphs1Remove a vertex from a given graph. Complexity: O(n*log(n)) time.removeVertex x (M x) == L removeVertex 1 (M 2) == M 2 removeVertex x (N e x x) == L removeVertex 1 (N e 1 2) == M5 2 removeVertex x . removeVertex x == removeVertex x falgebraic-graphs0Remove an edge from a given graph. Complexity: O(log(n)) time.removeEdge x y (N e x y) == SJ [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y . e x == ea x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 galgebraic-graphs The function g x y replaces vertex x with vertex y in a given C. If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time.6replaceVertex x x == id replaceVertex x y (M x) == M# y replaceVertex x y == j! (\v -> if v == x then y else v) halgebraic-graphsZReplace an edge from a given graph. If it doesn't exist, it will be created. Complexity: O(log(n)) time.'replaceEdge e x y z == Q (removeEdge x y z) (N e x y) replaceEdge e x y (N f x y) == N e x y [ x y (replaceEdge e x y z) == e ialgebraic-graphs&Transpose a given graph. Complexity: O(m * log(n)) time, O(n + m) memory. transpose L == L transpose (M x) == M x transpose (N e x y) == N$ e y x transpose . transpose == id jalgebraic-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 C. Complexity: O((n + m) * log(n)) time.gmap f L == L gmap f (M x) == M (f x) gmap f (N e x y) == N e (f x) (f y) gmap ═ == ═% gmap f . gmap g == gmap (f . g) kalgebraic-graphs)Transform a graph by applying a function h* to each of its edge labels. Complexity: O((n + m) * log(n)) time. The function h is required to be a homomorphism# on the underlying type of labels e%. At the very least it must preserve Г and Х:h Г == Г h x Х h y == h (x Х y) If e is also a semiring, then h2 must also preserve the multiplicative structure:h Е == Е h x Ф h y == h (x Ф y) [If the above requirements hold, then the implementation provides the following guarantees.emap h L == L emap h (M x) == M x emap h (N e x y) == N (h e) x y emap h (Q x y) == Q (emap h x) (emap h y) emap h (R e x y) == R" (h e) (emap h x) (emap h y) emap ═ == ═( emap g . emap h == emap (g . h) lalgebraic-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 (░ True ) x == x induce (░ False) x == L induce (/= x) == e< x induce p . induce q == induce (\x -> p x && q x) W (induce p x) x == True malgebraic-graphsCompute the reflexive and transitive closureY of a graph over the underlying star semiring using the Warshall-Floyd-Kleene algorithm.closure L == L closure (M x) == N Е x x closure (N e x x) == N Е x x closure (N e x y) == T [(Е,x,x), (e,x,y), (Е ,y,y)] closure == n . p closure == p . n" closure . closure == closure c x (closure y) == Set.■ (- x y) nalgebraic-graphsCompute the reflexive closureJ of a graph over the underlying semiring by adding a self-loop of weight Е to every vertex. Complexity: O(n * log(n)) time.reflexiveClosure L == L reflexiveClosure (M x) == N Е x x reflexiveClosure (N e x x) == N Е x x reflexiveClosure (N e x y) == T [(Е,x,x), (e,x,y), (Е?,y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure oalgebraic-graphsCompute the symmetric closureC of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time.symmetricClosure L == L symmetricClosure (M x) == M x symmetricClosure (N e x y) == T; [(e,x,y), (e,y,x)] symmetricClosure x == Q x (i< x) symmetricClosure . symmetricClosure == symmetricClosure palgebraic-graphsCompute the transitive closure▓ of a graph over the underlying star semiring using a modified version of the Warshall-Floyd-Kleene algorithm, which omits the reflexivity step.transitiveClosure L == L transitiveClosure (M x) == M x transitiveClosure (N e x y) == NB e x y transitiveClosure . transitiveClosure == transitiveClosure 'CELMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnop'CELMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopO5P5(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone4=>?HMPVXлА.qalgebraic-graphsThe q of a subgraph comprises its s and tЖ, i.e. all the vertices that are connected to the subgraph's vertices (along with the corresponding edge labels). Note that inputs and outputs can belong to the subgraph itself. In general, there are no guarantees on the order of vertices in s and t(; furthermore, there may be repetitions.╨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.ualgebraic-graphsA network4 is a graph whose edges are labelled with distances.valgebraic-graphsA type synonym for automata or labelled transition systems.walgebraic-graphsA type synonym for unlabelled graphs.xalgebraic-graphs.Edge-labelled graphs, where the type variable e' stands for edge labels. For example, x 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.|algebraic-graphsGeneralised x! folding: recursively collapse a x² by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: empty, vertex and connect. Complexity: O(s)D applications of given functions. As an example, the complexity of ┴ is O(s) , since all functions have cost O(1).foldg ~ └ == ═ foldg ~ (≈ ╚ └) == ∙ foldg 1 (░ 1) (░ (+)) == ┴ foldg True (░ False) (░ (&&)) == ┬ foldg False (== x) (░ (||)) == ┼ x foldg Set.▓ Set.⌠ (░ Set.╟) == ▐ }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) (└C x y) == True isSubgraphOf x y ==> x <= y ~algebraic-graphsConstruct the empty graph. An alias for the constructor y. Complexity: O(1) time, memory and size.┬ empty == True ┼ x empty == False 4 empty == 0 5 empty == 0 algebraic-graphsConstruct the graph comprising a single isolated vertex . An alias for the constructor z. Complexity: O(1) time, memory and size.┬ (vertex x) == False ┼ x (vertex x) == True 4 (vertex x) == 1 5 (vertex x) == 0 ─algebraic-graphsConstruct the graph comprising a single labelled edge. Complexity: O(1) time, memory and size.edge e x y == └ e ( x) ( y) edge Г x y == ┘ [x,y] ▀ x y (edge e x y) == (e /= Г) ▄ x y (edge e x y) == e 5 (edge e x y) == if e == Г then 0 else 1 4 (edge e 1 1) == 1 4 (edge e 1 2) == 2 │algebraic-graphs8The left-hand part of a convenient ternary-ish operator x-<e>-y for creating labelled edges. x -<e>- y == ─ e x y ┌algebraic-graphs9The right-hand part of a convenient ternary-ish operator x-<e>-y for creating labelled edges. x -<e>- y == ─ e x y ┐algebraic-graphsOverlay two graphs. An alias for { Г. Complexity: O(1) time and memory, O(s1 + s2) size.┬ (overlay x y) == ┬ x && ┬ y ┼ z (overlay x y) == ┼ z x || ┼ z y 4 (overlay x y) >= 4 x 4 (overlay x y) <= 4 x + 4 y 5 (overlay x y) >= 5 x 5 (overlay x y) <= 5 x + 5 y 4 (overlay 1 2) == 2 5 (overlay 1 2) == 0 Note: ┐/ composes edges in parallel using the operator Х with Г acting as the identity:▄ x y $ overlay (─ e x y) (─ Г x y) == e ▄ x y $ overlay (─ e x y) (─ f x y) == e Х f 0Furthermore, when applied to transitive graphs, ┐0 composes edges in sequence using the operator Ф with Е acting as the identity:▄ x z $ ⌡ (overlay (─ e x y) (─ Е y z)) == e ▄ x z $ ⌡ (overlay (─ e x y) (─ f y z)) == e Ф f └algebraic-graphsConnect@ two graphs with edges labelled by a given label. An alias for {. Complexity: O(1) time and memory, O(s1 + s2)└ size. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).┬ (connect e x y) == ┬ x && ┬ y ┼ z (connect e x y) == ┼ z x || ┼ z y 4 (connect e x y) >= 4 x 4 (connect e x y) <= 4 x + 4 y 5 (connect e x y) <= 4 x * 4 y + 5 x + 5 y 4 (connect e 1 2) == 2 5 (connect e 1 2) == if e == Г then 0 else 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 4 . vertices == ▀ . () 6 . vertices == Set.■ ├algebraic-graphs@Construct the graph from a list of labelled edges. Complexity: O(L) time, memory and size, where L" is the length of the given list.edges [] == ~ edges [(e,x,y)] == ─ e x y edges == ┤ . ▒ (\(e, x, y) -> ─ e x y) ┤algebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list.overlays [] == ~/ overlays [x] == x overlays [x,y] == ┐ x y overlays == █ ┐ ~ ┬ . overlays == ▌ ┬ ┬algebraic-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 $ ─ e 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 >= 4 x ┼algebraic-graphs7Check if a graph contains a given vertex. Complexity: O(s) time.hasVertex x ~" == False hasVertex x ( x) == True hasVertex 1 (! 2) == False hasVertex x . ▒ x == ░ False ▀algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.hasEdge x y ~" == False hasEdge x y ( z) == False hasEdge x y (─ e x y) == (e /= Г) hasEdge x y . ▓ x y == ░' False hasEdge x y == ╦ . ╛ . ╧& (\(_,ex,ey) -> ex == x && ey == y) . ▌ ▄algebraic-graphs3Extract the label of a specified edge from a graph.█algebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(s * log(n)) time and O(n) memory.vertexList ~ == [] vertexList ( x) == [x] vertexList . ┘ == () . (* ▌algebraic-graphs·The list of edges of a graph, sorted lexicographically with respect to pairs of connected vertices (i.e. edge-labels are ignored when sorting). Complexity: O(n + m) time and O(m) memory. edgeList ~ == [] edgeList ( x) == [] edgeList (─ e x y) == if e == Г then [] else [(e,x,y)] ▐algebraic-graphs3The set of vertices of a given graph. Complexity: O(s * log(n)) time and O(n) memory. vertexSet ~ == Set.▓ vertexSet . == Set.⌠ vertexSet . ┘ == Set.■ ░algebraic-graphs0The set of edges of a given graph. Complexity: O(n + m) time and O(m) memory.edgeSet ~ == Set.▓ edgeSet ( x) == Set.▓ edgeSet (─ e x y) == if e == Г then Set.▓ else Set.⌠ (e,x,y) ▒algebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size.removeVertex x ( x) == ~ removeVertex 1 ( 2) == 2 removeVertex x (─ e x x) == ~ removeVertex 1 (─ e 1 2) == 5 2 removeVertex x . removeVertex x == removeVertex x ▓algebraic-graphs0Remove an edge from a given graph. Complexity: O(s) time, memory and size.removeEdge x y (─ e x y) == ┘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 x. If y already exists, x and y will be merged. Complexity: O(s) time, memory and size.6replaceVertex x x == id replaceVertex x y ( x) == # y replaceVertex x y == ≈! (\v -> if v == x then y else v) ■algebraic-graphsZReplace an edge from a given graph. If it doesn't exist, it will be created. Complexity: O(log(n)) time.'replaceEdge e x y z == ┐ (removeEdge x y z) (─ e x y) replaceEdge e x y (─ f x y) == ─ e x y ▄ x y (replaceEdge e x y z) == e ∙algebraic-graphs&Transpose a given graph. Complexity: O(s) time, memory and size. transpose ~ == ~ transpose ( x) == x transpose (─ e x y) == ─$ e y x transpose . transpose == id √algebraic-graphsRTransform a graph by applying a function to each of its edge labels. Complexity: O(s) time, memory and size. The function h is required to be a homomorphism# on the underlying type of labels e%. At the very least it must preserve Г and Х:h Г == Г h x Х h y == h (x Х y) If e is also a semiring, then h2 must also preserve the multiplicative structure:h Е == Е h x Ф h y == h (x Ф y) [If the above requirements hold, then the implementation provides the following guarantees.emap h ~ == ~ emap h ( x) == x emap h (─ e x y) == ─ (h e) x y emap h (┐ x y) == ┐ (emap h x) (emap h y) emap h (└ e x y) == └" (h e) (emap h x) (emap h y) emap ═ == ═( emap g . emap h == emap (g . h) ≈algebraic-graphsConstruct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated.induce (░ True ) x == x induce (░ False) x == ~ induce (/= x) == ▒< x induce p . induce q == induce (\x -> p x && q x) } (induce p x) x == True ≤algebraic-graphsCompute the reflexive and transitive closureY of a graph over the underlying star semiring using the Warshall-Floyd-Kleene algorithm.closure ~ == ~ closure ( x) == ─ Е x x closure (─ e x x) == ─ Е x x closure (─ e x y) == ├ [(Е,x,x), (e,x,y), (Е ,y,y)] closure == ≥ . ⌡ closure == ⌡ . ≥" closure . closure == closure 7 x (closure y) == Set.■ (- x y) ≥algebraic-graphsCompute the reflexive closureJ of a graph over the underlying semiring by adding a self-loop of weight Е to every vertex. Complexity: O(n * log(n)) time.reflexiveClosure ~ == ~ reflexiveClosure ( x) == ─ Е x x reflexiveClosure (─ e x x) == ─ Е x x reflexiveClosure (─ e x y) == ├ [(Е,x,x), (e,x,y), (Е?,y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure algebraic-graphsCompute the symmetric closureC of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time.symmetricClosure ~ == ~ symmetricClosure ( x) == x symmetricClosure (─ e x y) == ├; [(e,x,y), (e,y,x)] symmetricClosure x == ┐ x (∙< x) symmetricClosure . symmetricClosure == symmetricClosure ⌡algebraic-graphsCompute the transitive closure▓ of a graph over the underlying star semiring using a modified version of the Warshall-Floyd-Kleene algorithm, which omits the reflexivity step.transitiveClosure ~ == ~ transitiveClosure ( x) == x transitiveClosure (─ e x y) == ─B e x y transitiveClosure . transitiveClosure == transitiveClosure Ўalgebraic-graphsiFocus on the graph with a single vertex, given a predicate indicating whether the vertex is of interest.©algebraic-graphsConnect two foci.юalgebraic-graphsа on a specified subgraph.°algebraic-graphsExtract the q8 of a subgraph specified by a given predicate. Returns Nothing$ if the specified subgraph is empty. context (░> False) x == Nothing context (== 1) (─ e 1 2) == if e == Г then Just (q [] []) else Just (q) [ ] [(e,2)]) context (== 2) (─ e 1 2) == if e == Г then Just (q [] []) else Just (q [(e,1)] [ ]) context (░ True ) (─ e 1 2) == if e == Г then Just (q [] []) else Just (qE [(e,1)] [(e,2)]) context (== 4) (3 * 1 * 4 * 1 * 5) == Just (q [(Е,3), (Е,1)] [(Е,1), (Е,5)]) ²algebraic-graphsNote:0 this does not satisfy the usual ring laws; see x for more details.,qrstuvwxyz{|}~─│┌┐└┘├┤┬┴┼▀▄█▌▐░▒▓⌠■∙√≈≤≥ ⌡°,xyz{~─│┌┐└┘├┤|}┬┴┼▀▄█▌▐░▒▓⌠■∙√≈≤≥ ⌡wvuqrst°│5┌5(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXы▌єalgebraic-graphsFor simplicity we measure journey times in integer number of minutes.╔algebraic-graphsOur example networks have cities as vertices.╚algebraic-graphs.A part of the EastCoast train network between і and ╘.eastCoast = ┤ [ і │150┌ ї , ї │ 90┌ ╙ , ╙ │170┌ ╘ ] ╛algebraic-graphs-A part of the ScotRail train network between і and ╗.scotRail = ┤ [ і │140┌ ї , ї │ 50┌ ╗ , ї │ 70┌ ╗ ] ґalgebraic-graphsAn example train network. network = ┐ ╛ ╚ є╔╙╘╗їі╚╛ґ ╔╙╘╗їіє╚╛ґ (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXvЁalgebraic-graphsThe ЁX data type represents a graph by a map of vertices to their adjacency sets. We define a ~; instance as a convenient notation for working with graphs:У0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))Note: the б method of the type class ~A cannot be implemented and will throw an error. Furthermore, the ~7 instance does not satisfy several "customary laws" of ~, which dictate that 0 and 1; should act as additive and multiplicative identities, and ─0 as additive inverse. Nevertheless, overloading , │ and ┌И is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ┐? instance is defined using basic graph construction primitives:Ъ,show (1 :: AdjacencyMap Int) == "vertex 1" show (1 + 2 :: AdjacencyMap Int) == "vertices1 [1,2]" show (1 * 2 :: AdjacencyMap Int) == "edge 1 2" show (1 * 2 * 3 :: AdjacencyMap Int) == "edges1 [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: AdjacencyMap Int) == "overlay (vertex 3) (edge 1 2)"The └; instance satisfies the following laws of algebraic graphs: , is commutative, associative and idempotent:@ x + y == y + x x + (y + z) == (x + y) + z x + x == x! is associative:x * (y * z) == (x * y) * z! distributes over :9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z! can be decomposed:"x * y * z == x * y + x * z + y * z!% satisfies absorption and saturation:-x * y + x + y == x * y x * x * x == x * xDWhen specifying the time and memory complexity of graph algorithms, n and mI will denote the number of vertices and edges in the graph, respectively.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:# 1 < # 2 # 3 < $ 1 2 # 1 < $ 1 1 $ 1 1 < $ 1 2 $ 1 2 < $ 1 1 + $ 2 2 $ 1 2 < $ 1 3*Note that the resulting order refines the %! relation and is compatible with and ! operations:% x y ==> x <= yx <= x + y x + y <= x * y╣algebraic-graphsThe adjacency mapY of a graph: each vertex is associated with a set of its direct successors. Complexity: O(1) time and memory.adjacencyMap (vertex x) == Map.² x Set.▓ adjacencyMap ($ 1 1) == Map.² 1 (Set.⌠ 1) adjacencyMap ($ 1 2) == Map.· [(1,Set.⌠ 2), (2,Set.▓)] Іalgebraic-graphsПCheck if the internal graph representation is consistent, i.e. that all edges refer to existing vertices, and the graph is non-empty. It should be impossible to create an inconsistent adjacency map, and we use this function in testing. ,Note: this function is for internal use only.consistent (vertex x) == True consistent (overlay x y) == True consistent (connect x y) == True consistent ($ x y) == True consistent (& xs) == True consistent (' xs) == True ╦algebraic-graphsNote:0 this does not satisfy the usual ring laws; see Ё for more details.ЁЄ╣ІЁЄ╣І(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXЇ&╪algebraic-graphsConvert a possibly empty 5 into NonEmpty.Ё. Returns ц if the argument is @. Complexity: O(1) time, memory and size.toNonEmpty @% == Nothing toNonEmpty (8 x) == Just (x :: Ё a) Ґalgebraic-graphsConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.9: x (vertex x) == True 94 (vertex x) == 1 95 (vertex x) == 0 Ўalgebraic-graphsOverlay\ two graphs. This is a commutative, associative and idempotent operation with the identity empty. Complexity: O((n + m) * log(n)) time and O(n + m) memory.ф z (overlay x y) == ф z x || ф z y х (overlay x y) >= х x х (overlay x y) <= х x + х y и (overlay x y) >= и x и (overlay x y) <= и x + и y х (overlay 1 2) == 2 и (overlay 1 2) == 0 ©algebraic-graphsConnectA two graphs. This is an associative operation with the identity empty, which distributes over Ў1 and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m)├ memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).ф z (connect x y) == ф z x || ф z y х (connect x y) >= х x х (connect x y) <= х x + х y и (connect x y) >= и x и (connect x y) >= и y и (connect x y) >= х x * х y и (connect x y) <= х x * х y + и x + и y х (connect 1 2) == 2 и (connect 1 2) == 1 юalgebraic-graphsConstruct the graph comprising a 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.vertices1 [x] == Ґ x ф x . vertices1 == ┼ x х . vertices1 == ▀ . ;) л . vertices1 == Set.■ . д бalgebraic-graphs7Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory.edges1 [(x,y)] == ю x y и . edges1 == ;< . ;) цalgebraic-graphs-Overlay a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.(overlays1 [x] == x overlays1 [x,y] == Ў x y дalgebraic-graphs-Connect a given list of graphs. Complexity: O((n + m) * log(n)) time and O(n + m) memory.(connects1 [x] == x connects1 [x,y] == © x y еalgebraic-graphsThe е' function takes two graphs and returns ▐ if the first graph is a subgraph of the second. Complexity: O((n + m) * log(n)) time.isSubgraphOf x (Ў x y) == True isSubgraphOf (Ў x y) (© x y) == True isSubgraphOf (п xs) (яB xs) == True isSubgraphOf x y ==> x <= y фalgebraic-graphs7Check if a graph contains a given vertex. Complexity: O(log(n)) time. hasVertex x (Ґ x) == True hasVertex 1 (Ґ 2) == False гalgebraic-graphs5Check if a graph contains a given edge. Complexity: O(log(n)) time. hasEdge x y (Ґ z) == False hasEdge x y (ю" x y) == True hasEdge x y . ь x y == ░' False hasEdge x y == ┼ (x,y) . к хalgebraic-graphs0The number of vertices in a graph. Complexity: O(1) time. vertexCount (Ґ3 x) == 1 vertexCount == ▀ . vertexList) vertexCount x < vertexCount y ==> x < y иalgebraic-graphs-The number of edges in a graph. Complexity: O(n) time.edgeCount (Ґ x) == 0 edgeCount (ю# x y) == 1 edgeCount == ▀ . к йalgebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory. vertexList1 (Ґ x) == [x] vertexList1 . а == ;) . ;* кalgebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory. edgeList (Ґ x) == [] edgeList (ю x y) == [(x,y)] edgeList (т' 2 [3,1]) == [(2,1), (2,3)] edgeList . edges == ;) . (* edgeList . ш == (* . ▒ +, . edgeList лalgebraic-graphs3The set of vertices of a given graph. Complexity: O(n) time and memory.vertexSet . Ґ == Set.⌠ vertexSet . а == Set.■ . д vertexSet . р == Set.■ . д мalgebraic-graphs0The set of edges of a given graph. Complexity: O((n + m) * log(m)) time and O(m) memory. edgeSet (Ґ x) == Set.▓ edgeSet (ю x y) == Set.⌠ (x,y) edgeSet . edges == Set.■ нalgebraic-graphsThe preset of an element x is the set of its direct predecessors. Complexity: O(n * log(n)) time and O(n) memory. preSet x (Ґ x) == Set.▓ preSet 1 (ю 1 2) == Set.▓ preSet y (ю x y) == Set.■ [x] оalgebraic-graphsThe postset of a vertex is the set of its direct successors. Complexity: O(log(n)) time and O(1) memory.postSet x (Ґ x) == Set.▓ postSet x (ю x y) == Set.■ [y] postSet 2 (ю 1 2) == Set.▓ пalgebraic-graphsThe path% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory.path1 [x] == Ґ x path1 [x,y] == ю x y path1 . е == ш . path1 яalgebraic-graphsThe circuit% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory.circuit1 [x] == ю x x circuit1 [x,y] == б [(x,y), (y,x)] circuit1 . е == ш . circuit1 рalgebraic-graphsThe clique% on a list of vertices. Complexity: O((n + m) * log(n)) time and O(n + m) memory.clique1 [x] == Ґ x clique1 [x,y] == ю x y clique1 [x,y,z] == б# [(x,y), (x,z), (y,z)] clique1 (xs Є ys) == ©% (clique1 xs) (clique1 ys) clique1 . е == ш . clique1 сalgebraic-graphsThe biclique( on two lists of vertices. Complexity: O(n * log(n) + m) time and O(n + m) memory.biclique1 [x1,x2] [y1,y2] == бC [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique1 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)] уalgebraic-graphsThe stars formed by overlaying a list of тs. An inverse of adjacencyList. Complexity: O(L * log(n)) time, memory and size, where L! is the total size of the input.#stars1 [(x, [] )] == Ґ& x stars1 [(x, [y])] == ю( x y stars1 [(x, ys )] == т) x ys stars1 == ц . ≈ (√ т) Ў' (stars1 xs) (stars1 ys) == stars1 (xs Є ys) жalgebraic-graphsThe tree graph constructed from a given ≤ data structure. Complexity: O((n + m) * log(n)) time and O(n + m) memory.<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-graphs1Remove a vertex from a given graph. Complexity: O(n*log(n)) time.removeVertex1 x (Ґ) x) == Nothing removeVertex1 1 (Ґ 2) == Just (Ґ 2) removeVertex1 x (ю+ x x) == Nothing removeVertex1 1 (ю 1 2) == Just (Ґ 2) removeVertex1 x =>$ removeVertex1 x == removeVertex1 x ьalgebraic-graphs0Remove an edge from a given graph. Complexity: O(log(n)) time.removeEdge x y (ю x y) == а≈ [x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge 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.mergeVertices (░7 False) x == id mergeVertices (== x) y == ы x y mergeVertices & 1 (0 * 2) == 1 * 1 mergeVertices ⌡ 1 (3 + 4 * 5) == 4 * 1 шalgebraic-graphs&Transpose a given graph. Complexity: O(m * log(n)) time, O(n + m) memory.transpose (Ґ x) == Ґ x transpose (ю x y) == ю! y x transpose . transpose == id к . transpose == (* . ▒ +, . к э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 (Ґ 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. induce1 (░ True ) x == Just x induce1 (░0 False) x == Nothing induce1 (/= x) == в x induce1 p =>) induce1 q == induce1 (\x -> p x && q x) чalgebraic-graphsCompute the reflexive and transitive closure of a graph. Complexity: O(n * m * log(n)^2) time. closure (Ґ x) == ю x x closure (ю x x) == ю x x closure (ю x y) == б [(x,x), (x,y), (y,y)] closure (п $ ;) xs) == ъ (р $ ;)! xs) closure == ъ . А closure == А . ъ% closure . closure == closure о x (closure y) == Set.■ (- x y) ъalgebraic-graphsCompute the reflexive closureA of a graph by adding a self-loop to every vertex. Complexity: O(n * log(n)) time.reflexiveClosure (Ґ x) == ю x x reflexiveClosure (ю x x) == ю x x reflexiveClosure (ю x y) == бO [(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure Юalgebraic-graphsCompute the symmetric closureC of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time.symmetricClosure (Ґ x) == Ґ x symmetricClosure (ю x y) == б7 [(x,y), (y,x)] symmetricClosure x == Ў x (ш< x) symmetricClosure . symmetricClosure == symmetricClosure Аalgebraic-graphsCompute the transitive closure of a graph. Complexity: O(n * m * log(n)^2) time.transitiveClosure (Ґ x) == Ґ x transitiveClosure (ю x y) == ю x y transitiveClosure (п $ ;) xs) == р (;)@ xs) transitiveClosure . transitiveClosure == transitiveClosure 'Ё╪ҐЎ©юабцдефгхийклмнопярстужвьызшэщчъЮА'Ё╪ҐюЎ©абцдефгхийклмнопярстужвьызшэщчъЮА(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone=>?HMPVX ╩ Бalgebraic-graphsThe Б# data type represents a graph as a binary relation. We define a ~; instance as a convenient notation for working with graphs:У0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))Note: the ~7 instance does not satisfy several "customary laws" of ~, which dictate that 0 and 1; should act as additive and multiplicative identities, and ─0 as additive inverse. Nevertheless, overloading , │ and ┌И is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ┐? instance is defined using basic graph construction primitives:ЪBshow (empty :: Relation Int) == "empty" show (1 :: Relation Int) == "vertex 1" show (1 + 2 :: Relation Int) == "vertices [1,2]" show (1 * 2 :: Relation Int) == "edge 1 2" show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"The └3 instance satisfies all axioms of algebraic graphs: is commutative and associative:/ x + y == y + x x + (y + z) == (x + y) + z! is associative and has " as the identity:< x * empty == x empty * x == x x * (y * z) == (x * y) * z! distributes over :9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z! can be decomposed:"x * y * z == x * y + x * z + y * zIThe following useful theorems can be proved from the above set of axioms. has "' as the identity and is idempotent:2 x + empty == x empty + x == x x + x == xAbsorption and saturation of !:-x * y + x + y == x * y x * x * x == x * xDWhen specifying the time and memory complexity of graph algorithms, n and mI will denote the number of vertices and edges in the graph, respectively.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:Г 1 < Г 2 Г 3 < $ 1 2 Г 1 < $ 1 1 $ 1 1 < $ 1 2 $ 1 2 < $ 1 1 + $ 2 2 $ 1 2 < $ 1 3*Note that the resulting order refines the isSubgraphOf! relation and is compatible with Х and И operations:% x y ==> x <= yФ# <= x x <= x + y x + y <= x * yДalgebraic-graphsThe domain of the relation.Еalgebraic-graphs&The set of pairs of elements that are related<. It is guaranteed that each element belongs to the domain.Фalgebraic-graphsConstruct the empty graph. Complexity: O(1) time and memory.? empty == True : x empty == False 4 empty == 0 5 empty == 0 Гalgebraic-graphsConstruct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.? (vertex x) == False : x (vertex x) == True 4 (vertex x) == 1 5 (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 && 'iAlgebra.Graph.Relation.sEmpty' y : z (overlay x y) == : z x || : z y 4 (overlay x y) >= 4 x 4 (overlay x y) <= 4 x + 4 y 5 (overlay x y) >= 5 x 5 (overlay x y) <= 5 x + 5 y 4 (overlay 1 2) == 2 5 (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 4 (connect x y) >= 4 x 4 (connect x y) <= 4 x + 4 y 5 (connect x y) >= 5 x 5 (connect x y) >= 5 y 5 (connect x y) >= 4 x * 4 y 5 (connect x y) <= 4 x * 4 y + 5 x + 5 y 4 (connect 1 2) == 2 5 (connect 1 2) == 1 Йalgebraic-graphshCheck if the internal representation of a relation is consistent, i.e. if all pairs of elements in the Е# refer to existing elements in the Д5. It should be impossible to create an inconsistent Б), and we use this function in testing. ,Note: this function is for internal use only.consistent " == True consistent (# x) == True consistent ( x y) == True consistent (! x y) == True consistent ($ x y) == True consistent (& xs) == True consistent (' xs) == True Кalgebraic-graphs:The set of elements that appear in a given set of pairs. ,Note: this function is for internal use only.Лalgebraic-graphsNote:0 this does not satisfy the usual ring laws; see Б for more details.}БЦДЕФГХИЙКБЦДЕФГХИ}ЙК(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXл²&Я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-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 == ▀ . () Т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) (C xs) == True isSubgraphOf x y ==> x <= y Вalgebraic-graphs+Check if a relation is empty. Complexity: O(1) time.isEmpty Ф( == True isEmpty (Х Ф Ф) == True isEmpty (Г' x) == False isEmpty ( x $ Г x) == True isEmpty ( x y $ Я x y) == False Ьalgebraic-graphs7Check if a graph contains a given vertex. Complexity: O(log(n)) time.hasVertex x Ф" == False hasVertex x (Г x) == True hasVertex 1 (Г! 2) == False hasVertex x . x == ░ False Ыalgebraic-graphs5Check if a graph contains a given edge. Complexity: O(log(n)) time.hasEdge x y Ф" == False hasEdge x y (Г z) == False hasEdge x y (Я" x y) == True hasEdge x y . x y == ░' False hasEdge x y == ┼ (x,y) . Щ Зalgebraic-graphs0The number of vertices in a graph. Complexity: O(1) time.vertexCount Ф == 0 vertexCount (Г3 x) == 1 vertexCount == ▀ . Э) vertexCount x < vertexCount y ==> x < y Шalgebraic-graphs-The number of edges in a graph. Complexity: O(1) time. edgeCount Ф == 0 edgeCount (Г x) == 0 edgeCount (Я# x y) == 1 edgeCount == ▀ . Щ Эalgebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(n) time and memory.vertexList Ф == [] vertexList (Г x) == [x] vertexList . Р == () . (* Щalgebraic-graphs2The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory. edgeList Ф == [] edgeList (Г x) == [] edgeList (Я x y) == [(x,y)] edgeList (' 2 [3,1]) == [(2,1), (2,3)] edgeList . С == () . (* edgeList . == (* . ▒ ф . edgeList Чalgebraic-graphs3The set of vertices of a given graph. Complexity: O(1) time. vertexSet Ф == Set.▓ vertexSet . Г == Set.⌠ vertexSet . Р == Set.■ Ъalgebraic-graphs0The set of edges of a given graph. Complexity: O(1) time.edgeSet Ф == Set.▓ edgeSet (Г x) == Set.▓ edgeSet (Я x y) == Set.⌠ (x,y) edgeSet . С == Set.■ algebraic-graphsThe 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 x7 is the set of elements that are related to it on the left, i.e. preSet x == { a | aRx }E. In the context of directed graphs, this corresponds to the set of direct predecessors of vertex x. Complexity: O(n + m) time and O(n) memory. preSet x Ф == Set.▓ preSet x (Г x) == Set.▓ preSet 1 (Я 1 2) == Set.▓ preSet y (Я x y) == Set.■ [x] algebraic-graphsThe postset of an element x7 is the set of elements that are related to it on the right, i.e. postSet x == { a | xRa }E. In the context of directed graphs, this corresponds to the set of direct successors of vertex x. Complexity: O(n + m) time and O(n) memory. postSet x Ф == Set.▓ postSet x (Г x) == Set.▓ postSet x (Я x y) == Set.■ [y] postSet 2 (Я 1 2) == Set.▓ 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 == Т . ▒ (√ ) 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 == Т . ▒ algebraic-graphs1Remove a vertex from a given graph. Complexity: O(n + m) time.removeVertex x (Г x) == Ф removeVertex 1 (Г 2) == Г 2 removeVertex x (Я x x) == Ф removeVertex 1 (Я 1 2) == Г5 2 removeVertex x . removeVertex x == removeVertex x algebraic-graphs0Remove an edge from a given graph. Complexity: O(log(m)) time.removeEdge x y (9$ 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 AdjacencyMap. If y already exists, x and y will be merged. Complexity: O((n + m) * log(n)) time.6replaceVertex x x == id replaceVertex x y (Г x) == Г# y replaceVertex x y == (== x) y algebraic-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.mergeVertices (░7 False) x == id mergeVertices (== x) y == x y mergeVertices & 1 (0 * 2) == 1 * 1 mergeVertices ⌡ 1 (3 + 4 * 5) == 4 * 1 algebraic-graphs&Transpose a given graph. Complexity: O(m * log(m)) time. transpose Ф == Ф transpose (Г x) == Г x transpose (Я x y) == Я! y x transpose . transpose == id Щ . transpose == (* . ▒ ф . Щ algebraic-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 (░ True ) x == x induce (░ False) x == Ф induce (/= x) == < x induce p . induce q == induce (\x -> p x && q x) Ж (induce p x) x == True algebraic-graphsLeft-to-right relational composition of graphs: vertices x and z< are connected in the resulting graph if there is a vertex y, such that x is connected to y in the first graph, and y is connected to zi in the second graph. There are no isolated vertices in the result. This operation is associative, has Ф and single-Г graphs as annihilating zeroes, and distributes over Х. Complexity: O(n * m * log(m)) time and O(n + m) memory.compose Ф x == Ф compose x Ф == Ф compose (Г x) y == Ф compose x (Г y) == Ф` compose x (compose y z) == compose (compose x y) z compose x (Х y z) == Х& (compose x y) (compose x z) compose (Х x y) z == Х& (compose x z) (compose y z) compose (Я x y) (Я y z) == Я x z compose ( [1..5]) ( [1..5]) == С [(1,3), (2,4), (3,5)] compose ( [1..5]) ( [1..5]) == [1,3,5,2,4] algebraic-graphsCompute the reflexive and transitive closure of a graph. Complexity: O(n * m * log(n) * log(m)) time.closure Ф == Ф closure (Г x) == Я x x closure (Я x x) == Я x x closure (Я x y) == С [(x,x), (x,y), (y,y)] closure ( $ () xs) == ( $ () xs) closure == . closure == . $ closure . closure == closure x (closure y) == Set.■ (- x y) algebraic-graphsCompute the reflexive closure of a graph. Complexity: O(n * log(m)) time.reflexiveClosure Ф == Ф reflexiveClosure (Г x) == Я x x reflexiveClosure (Я x x) == Я x x reflexiveClosure (Я x y) == СO [(x,x), (x,y), (y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure algebraic-graphsCompute the symmetric closure of a graph. Complexity: O(m * log(m)) time.symmetricClosure Ф == Ф symmetricClosure (Г x) == Г x symmetricClosure (Я x y) == С7 [(x,y), (y,x)] symmetricClosure x == Х x (< x) symmetricClosure . symmetricClosure == symmetricClosure algebraic-graphsCompute the transitive closure of a graph. Complexity: O(n * m * log(n) * log(m)) time.transitiveClosure Ф == Ф transitiveClosure (Г x) == Г x transitiveClosure (Я x y) == Я x y transitiveClosure ( $ () xs) == (()@ xs) transitiveClosure . transitiveClosure == transitiveClosure -БЕДФГХИЯРСТУЖВЬЫЗШЭЩЧЪ -БДЕФГЯХИРСТУЖВЬЫЗШЭЩЧЪ +(c) Anton Lorenzen, Andrey Mokhov 2016-2018MIT (see the file LICENSE)*anfelor@posteo.de, andrey.mokhov@gmail.comunstableNone=>?HMPVX" 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 5. If fromAdjacencyMap g == h then the following holds:map ( h) (@A $ % h) == B g map (\(x, y) -> ( h x, h y)) (@& $ h) == C 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) (@A $ % h) == DE (F g) map (\(x, y) -> ( h x, h y)) (@& $ h) == C 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-graphsCompute 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)G (dfsForest % $ 1 1) == H# 1 G (dfsForest % $ 1 2) == $ 1 2 G (dfsForest % $ 2 1) == HA [1, 2] H% (G( $ dfsForest % x) x == True dfsForest % G3 (dfsForest % x) == dfsForest % x dfsForest % HA vs == ▒ (\v -> Node v []) (() $ (* vs) I (BЪ 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-graphsCompute 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.G (dfsForestFrom [1] % $ 1 1) == H# 1 G (dfsForestFrom [1] % $ 1 2) == $ 1 2 G (dfsForestFrom [2] % $ 1 2) == H# 2 G (dfsForestFrom [3] % $ 1 2) == H" G (dfsForestFrom [2, 1] % $ 1 2) == A [1, 2] % (G2 $ dfsForestFrom vs % x) x == True dfsForestFrom (B x) % x == & % x dfsForestFrom vs % A vs == ▒ (\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] % (A $ dfs vs x) x == True !algebraic-graphsCompute 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.comunstableNone=>?HMPVX} "algebraic-graphsCompute the depth-first searchY forest of a graph that corresponds to searching from each of the graph vertices in the г a order. dfsForest @ == [] ^ (dfsForest $ B 1 1) == A 1 ^ (dfsForest $ B 1 2) == B 1 2 ^ (dfsForest $ B 2 1) == E [1,2] I (^ $ dfsForest x) x == True )- (dfsForest x) x == True dfsForest . ^, . dfsForest == dfsForest dfsForest (E vs) == ▒ (\v -> Node v []) (() $ (* vs) # (OЪШ 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-graphsCompute 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] $ B 1 1) == A 1 ^ (dfsForestFrom [1] $ B 1 2) == B 1 2 ^ (dfsForestFrom [2] $ B 1 2) == A 2 ^ (dfsForestFrom [3] $ B 1 2) == @ ^ (dfsForestFrom [2,1] $ B 1 2) == E [1,2] I (^% $ dfsForestFrom vs x) x == True ) (dfsForestFrom (O x) x) x == True dfsForestFrom (O x) x == "! x dfsForestFrom vs (E vs) == ▒ (\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] $ B( 1 1 == [1] dfs [1] $ B* 1 2 == [1,2] dfs [2] $ B( 1 2 == [2] dfs [3] $ B' 1 2 == [] dfs [1,2] $ B* 1 2 == [1,2] dfs [2,1] $ By 1 2 == [2,1] dfs [] $ x == [] dfs [1,4] $ 3 * (1 + 4) * (1 + 5) == [1,5,4] I (E $ 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 $ A+ 1 == [1] reachable 1 $ A* 2 == [] reachable 1 $ B- 1 1 == [1] reachable 1 $ B/ 1 2 == [1,2] reachable 4 $ V0 [1..8] == [4..8] reachable 4 $ W7 [1..8] == [4..8] ++ [1..3] reachable 8 $ X' [8,7..1] == [8] ++ [1..7] I (E $ reachable x y) y == True &algebraic-graphsCompute the topological sort of a graph or return Nothing if the graph is cyclic.mtopSort (1 * 2 + 3 * 1) == Just [3,1,2] topSort (1 * 2 + 2 * 1) == Nothing fmap (╚ * 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 . W == ╛ isAcyclic == х . & (algebraic-graphsCompute the condensation1 of a graph, where each vertex corresponds to a strongly-connected component^ of the original graph. Note that component graphs are non-empty, and are therefore of type #Algebra.Graph.NonEmpty.AdjacencyMap.scc @ == @ scc (A x) == A (NonEmpty.Ґ x) scc (B 1 1) == A (NonEmpty.ю 1 1) scc (B 1 2) == B (NonEmpty.Ґ 1) (NonEmpty.Ґ 2) scc (W (1:xs)) == A (NonEmpty.я (1 ;J! xs)) scc (3 * 1 * 4 * 1 * 5) == F [ (NonEmpty.Ґ 3 , NonEmpty.Ґ9 5 ) , (NonEmpty.Ґ 3 , NonEmpty.р8 [1,4,1]) , (NonEmpty.р [1,4,1], NonEmpty.Ґ 5 ) ] ' . scc == ░ True ' x == (scc x == d NonEmpty.Ґ x) )algebraic-graphs%Check if a given forest is a correct depth-first search┤ forest of a graph. The implementation is based on the paper "Depth-First Search and Strong Connectivity in Coq" by FranГois Pottier..isDfsForestOf [] @C == True isDfsForestOf [] (AB 1) == False isDfsForestOf [Node 1 []] (AA 1) == True isDfsForestOf [Node 1 []] (AB 2) == False isDfsForestOf [Node 1 [], Node 1 []] (AB 1) == False isDfsForestOf [Node 1 []] (BC 1 1) == True isDfsForestOf [Node 1 []] (BD 1 2) == False isDfsForestOf [Node 1 [], Node 2 []] (BD 1 2) == False isDfsForestOf [Node 2 [], Node 1 []] (BC 1 2) == True isDfsForestOf [Node 1 [Node 2 []]] (BC 1 2) == True isDfsForestOf [Node 1 [], Node 2 []] (E? [1,2]) == True isDfsForestOf [Node 2 [], Node 1 []] (E? [1,2]) == True isDfsForestOf [Node 1 [Node 2 []]] (E@ [1,2]) == False isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] (VC [1,2,3]) == True isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] (VD [1,2,3]) == False isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (VC [1,2,3]) == True isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (VC [1,2,3]) == True isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] (V [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] (A& x) == True isTopSortOf [x] (B x x) == False "#$%&'()* "#$%&'()*(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone=>?HMPVXь╠+algebraic-graphsCompute 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 1- (dfsForest x) x == True dfsForest . (, . dfsForest == dfsForest dfsForest ( vs) == ▒ (\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-graphsCompute 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 1 (dfsForestFrom ( x) x) x == True dfsForestFrom ( x) x == +! x dfsForestFrom vs ( vs) == ▒ (\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-graphsCompute the topological sort of a graph or return Nothing if the graph is cyclic.mtopSort (1 * 2 + 3 * 1) == Just [3,1,2] topSort (1 * 2 + 2 * 1) == Nothing fmap (╚ 2 x) (topSort x) /= Just False х# . topSort == 0 0algebraic-graphsCheck if a given graph is acyclic.QisAcyclic (1 * 2 + 3 * 1) == True isAcyclic (1 * 2 + 2 * 1) == False isAcyclic . ! == ╛ isAcyclic == х . / 1algebraic-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 FranГois 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 2algebraic-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 +,-./012+,-./012(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?@HMPVX 8<(3algebraic-graphsThe 3ў type class captures data types that can be converted to algebraic graphs. Instances of this type class should satisfy the laws specified by the default method definitions.4algebraic-graphs,The type of vertices of the resulting graph.5algebraic-graphs:Convert a value to the corresponding algebraic graph, see Algebra.Graph.toGraph == 6 ░ ▒ ▓ ⌠ 6algebraic-graphsThe method 6Ъ 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.² . 5 7algebraic-graphsCheck if a graph is empty.isEmpty == 6 True (░ False) (&&) (&&) 8algebraic-graphsThe sizeD of a graph, i.e. the number of leaves of the expression including empty leaves.Note:b The default implementation of this function violates the requirement that the four arguments of 65 should satisfy the laws of algebraic graphs, since 1 + 1 /= 1. Use this function with care.size == 6 1 (░ 1) (+) (+) 9algebraic-graphs)Check if a graph contains a given vertex.hasVertex x == 6 False (==x) (||) (||) :algebraic-graphs'Check if a graph contains a given edge.hasEdge x y == Algebra.Graph.ё x y . 5 ;algebraic-graphs"The number of vertices in a graph.vertexCount == Set.и . ? <algebraic-graphsThe number of edges in a graph.edgeCount == Set.и . A =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.й . A ?algebraic-graphsThe set of vertices of a graph. vertexSet == 6 Set.▓ Set.⌠ Set.╟ Set.╟ @algebraic-graphs%The set of vertices of a graph. Like ?3 but specialised for graphs with vertices of type к.vertexIntSet == 6 IntSet.┤ IntSet.┬ IntSet.л IntSet.л Aalgebraic-graphsThe set of edges of a graph.&edgeSet == Algebra.Graph.AdjacencyMap.R . Q Balgebraic-graphsThe preset of a vertex is the set of its direct predecessors.'preSet x == Algebra.Graph.AdjacencyMap.T x . Q Calgebraic-graphsThe preset (here preIntSet!) of a vertex is the set of its direct predecessors. Like B3 but specialised for graphs with vertices of type к.-preIntSet x == Algebra.Graph.AdjacencyIntMap. x . S Dalgebraic-graphsThe postset of a vertex is the set of its direct successors.(postSet x == Algebra.Graph.AdjacencyMap.U x . Q Ealgebraic-graphsThe postset (here postIntSet!) of a vertex is the set of its direct successors. Like D3 but specialised for graphs with vertices of type к..postIntSet x == Algebra.Graph.AdjacencyIntMap. x . S Falgebraic-graphsThe sorted adjacency list of a graph.,adjacencyList == Algebra.Graph.AdjacencyMap.S . Q Galgebraic-graphsThe adjacency map: of a graph: each vertex is associated with a set of its direct successors.+adjacencyMap == Algebra.Graph.AdjacencyMap.K . Q Halgebraic-graphsThe adjacency map: of a graph: each vertex is associated with a set of its direct successors. Like G3 but specialised for graphs with vertices of type к.1adjacencyIntMap == Algebra.Graph.AdjacencyIntMap.L . S Ialgebraic-graphsThe transposed adjacency map: of a graph: each vertex is associated with a set of its direct predecessors.4adjacencyMapTranspose == Algebra.Graph.AdjacencyMap.K . R Jalgebraic-graphsThe transposed adjacency map: of a graph: each vertex is associated with a set of its direct predecessors. Like I3 but specialised for graphs with vertices of type к.:adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap.L . T Kalgebraic-graphsCompute 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 Lalgebraic-graphsCompute 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 Malgebraic-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 Nalgebraic-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 Oalgebraic-graphsCompute the topological sort of a graph or return Nothing if the graph is cyclic.&topSort == Algebra.Graph.AdjacencyMap.& . toAdjacencyMap Palgebraic-graphsCheck if a given graph is acyclic.(isAcyclic == Algebra.Graph.AdjacencyMap.' . toAdjacencyMap Qalgebraic-graphs%Convert a value to the corresponding 5.toAdjacencyMap == 6 @ A C D Ralgebraic-graphs%Convert a value to the corresponding 5 and transpose the result.toAdjacencyMapTranspose == 6 @ A C (╚ D) Salgebraic-graphs%Convert a value to the corresponding .toAdjacencyIntMap == 6 Talgebraic-graphs%Convert a value to the corresponding and transpose the result.toAdjacencyIntMapTranspose == 6 (╚ ) Ualgebraic-graphs#Check if a given forest is a valid depth-first search forest of a graph..isDfsForestOf f == Algebra.Graph.AdjacencyMap.) f . toAdjacencyMap Valgebraic-graphs-Check if a given list of vertices is a valid topological sort of a graph.-isTopSortOf vs == Algebra.Graph.AdjacencyMap.* vs . toAdjacencyMap Xalgebraic-graphsSee #Algebra.Graph.NonEmpty.AdjacencyMap.Yalgebraic-graphsSee #Algebra.Graph.Labelled.AdjacencyMap.Zalgebraic-graphsSee Algebra.Graph.Labelled.\algebraic-graphsSee Algebra.Graph.AdjacencyMap.$348MON679:;<=>?AFH@CEKLPUVGBDQ5SRTIJ$348MON679:;<=>?AFH@CEKLPUVGBDQ5SRTIJ(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone 4=>?HMPVX M■-^algebraic-graphsJNon-empty algebraic graphs, which are constructed using three primitives: c, e and g . See module Algebra.Graph( for algebraic graphs that can be empty.We define a ~; instance as a convenient notation for working with graphs:У0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))Note: the б method of the type class ~A cannot be implemented and will throw an error. Furthermore, the ~7 instance does not satisfy several "customary laws" of ~, which dictate that 0 and 1; should act as additive and multiplicative identities, and ─0 as additive inverse. Nevertheless, overloading , │ and ┌И is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The └E instance satisfies the following laws of non-empty algebraic graphs.e, is commutative, associative and idempotent:@ x + y == y + x x + (y + z) == (x + y) + z x + x == xg is associative:x * (y * z) == (x * y) * zg distributes over e:9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * zg can be decomposed:"x * y * z == x * y + x * z + y * zg% 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 ^? expression, defined as the number of vertex leaves (note that n <= s). If g is a ^, the corresponding n, m and s can be computed as follows:n == r g m == s g s == o g Converting a ^ to the corresponding 9 takes O(s + m * log(m)) time and O(s + m)╨ memory. This is also the complexity of the graph equality test, because it is currently implemented by converting graph expressions to canonical representations based on adjacency maps.The total order г on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:c 1 < c 2 c 3 < d 1 2 c 1 < d 1 1 d 1 1 < d 1 2 d 1 2 < d 1 1 + d 2 2 d 1 2 < d 1 3*Note that the resulting order refines the m! relation and is compatible with e and g operations:m x y ==> x <= yx <= x + y x + y <= x * yмalgebraic-graphsICheck if two graphs are equal by converting them to their adjacency maps.balgebraic-graphs!Convert an algebraic graph (from Algebra.Graph-) into a non-empty algebraic graph. Returns ц if the argument is ■. Complexity: O(s) time, memory and size.toNonEmpty ■ == Nothing toNonEmpty (5 x) == Just (x :: ^ a) calgebraic-graphsConstruct the graph comprising a single isolated vertex . An alias for the constructor _. Complexity: O(1) time, memory and size.p x (vertex x) == True r (vertex x) == 1 s (vertex x) == 0 o (vertex x) == 1 dalgebraic-graphsConstruct the graph comprising a single edge. Complexity: O(1) time, memory and size.edge x y == g (c x) (c y) q x y (edge x y) == True s (edge x y) == 1 r (edge 1 1) == 1 r (edge 1 2) == 2 ealgebraic-graphsOverlay* two graphs. An alias for the constructor `M. This is a commutative, associative and idempotent operation. Complexity: O(1) time and memory, O(s1 + s2) size.p z (overlay x y) == p z x || p z y r (overlay x y) >= r x r (overlay x y) <= r x + r y s (overlay x y) >= s x s (overlay x y) <= s x + s y o (overlay x y) == o x + o y r (overlay 1 2) == 2 s (overlay 1 2) == 0 falgebraic-graphs%Overlay a possibly empty graph (from Algebra.Graph4) with a non-empty graph. If the first argument is ■V, the function returns the second argument; otherwise it is semantically the same as e. Complexity: O(s1) time and memory, and O(s1 + s2) size. overlay1 ■ x == x x /= ■= ==> overlay1 x y == overlay (fromJust $ toNonEmpty x) y galgebraic-graphsConnect* two graphs. An alias for the constructor a<. This is an associative operation, which distributes over e2 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).p z (connect x y) == p z x || p z y r (connect x y) >= r x r (connect x y) <= r x + r y s (connect x y) >= s x s (connect x y) >= s y s (connect x y) >= r x * r y s (connect x y) <= r x * r y + s x + s y o (connect x y) == o x + o y r (connect 1 2) == 2 s (connect 1 2) == 1 halgebraic-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] == c x p x . vertices1 == ┼ x r . vertices1 == ▀ . ;) v . vertices1 == Set.■ . ;M ialgebraic-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)] == d x y s . edges1 == ;< . ;) jalgebraic-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] == e x y kalgebraic-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] == g x y lalgebraic-graphs2Generalised graph folding: recursively collapse a ^÷ by applying the provided functions to the leaves and internal nodes of the expression. The order of arguments is: vertex, overlay and connect. Complexity: O(s)D applications of given functions. As an example, the complexity of o is O(s) , since all functions have cost O(1).foldg1 c e g == id foldg1 c e (╚ g) == ├ foldg1 (░ 1) (+) (+) == o, foldg1 (== x) (||) (||) == p x malgebraic-graphsThe m' 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 (e x y) == True isSubgraphOf (e x y) (g x y) == True isSubgraphOf (x xs) (yB xs) == True isSubgraphOf x y ==> x <= y nalgebraic-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 oalgebraic-graphsThe sizeG of a graph, i.e. the number of leaves of the expression. Complexity: O(s) time.size (c x) == 1 size (e x y) == size x + size y size (gG x y) == size x + size y size x >= 1 size x >= r x palgebraic-graphs7Check if a graph contains a given vertex. Complexity: O(s) time. hasVertex x (c x) == True hasVertex 1 (c 2) == False qalgebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time. hasEdge x y (c z) == False hasEdge x y (d" x y) == True hasEdge x y . ┌ x y == ░' False hasEdge x y == ┼ (x,y) . u ralgebraic-graphs0The number of vertices in a graph. Complexity: O(s * log(n)) time. vertexCount (c3 x) == 1 vertexCount == ▀ . vertexList) vertexCount x < vertexCount y ==> x < y salgebraic-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 (c x) == 0 edgeCount (d# x y) == 1 edgeCount == ▀ . u talgebraic-graphs;The sorted list of vertices of a given graph. Complexity: O(s * log(n)) time and O(n) memory. vertexList1 (c x) == [x] vertexList1 . h == ;) . ;* нalgebraic-graphsLike t1 but specialised for Graph with vertices of type к.ualgebraic-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 (c x) == [] edgeList (d x y) == [(x,y)] edgeList (|' 2 [3,1]) == [(2,1), (2,3)] edgeList . i == () . (* . ;M edgeList . ├ == (* . ▒ +, . edgeList valgebraic-graphs3The set of vertices of a given graph. Complexity: O(s * log(n)) time and O(n) memory.vertexSet . c == Set.⌠ vertexSet . h == Set.■ . ;M vertexSet . z == Set.■ . ;M walgebraic-graphs0The set of edges of a given graph. Complexity: O(s * log(m)) time and O(m) memory. edgeSet (c x) == Set.▓ edgeSet (d x y) == Set.⌠ (x,y) edgeSet . i == Set.■ . ;M xalgebraic-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] == c x path1 [x,y] == d x y path1 . ;N == ├ . path1 yalgebraic-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] == d x x circuit1 [x,y] == i [(x,y), (y,x)] circuit1 . ;N == ├ . circuit1 zalgebraic-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] == c x clique1 [x,y] == d x y clique1 [x,y,z] == i# [(x,y), (x,z), (y,z)] clique1 (xs Є ys) == g% (clique1 xs) (clique1 ys) clique1 . ;N == ├ . 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] == iC [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique1 xs ys == g (h xs) (h 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 [] == c x star x [y] == d x y star x [y,z] == i [(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, [] )] == c& x stars1 [(x, [y])] == d( x y stars1 [(x, ys )] == |) x ys stars1 == j . ≈ (√ |) e' (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 []) == c? x tree (Node x [Node y [Node z []]]) == xE [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 []]]) == i [(1,2), (1,3), (3,4), (3,5)] algebraic-graphsConstruct 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] == c$ (x, y) mesh1 xs ys == ┴ (x xs) (x! ys) mesh1 [1,2,3] ['a', 'b'] == iУ [ ((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-graphsConstruct 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] == d( (x,y) (x,y) torus1 xs ys == ┴ (y xs) (y ys) torus1 [1,2] ['a', 'b'] == iЪ [ ((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,Remove a vertex from a given graph. Returns Nothing0 if the resulting graph is empty. Complexity: O(s) time, memory and size.removeVertex1 x (c) x) == Nothing removeVertex1 1 (c 2) == Just (c 2) removeVertex1 x (d+ x x) == Nothing removeVertex1 1 (d 1 2) == Just (c 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 (d x y) == h≈ [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 o# (removeEdge x y z) <= 3 * o z ┐algebraic-graphs The function ┐ x y replaces vertex x with vertex y in a given ^. If y already exists, x and y will be merged. Complexity: O(s) time, memory and size.6replaceVertex x x == id replaceVertex x y (c x) == c# 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.mergeVertices (░7 False) x == id mergeVertices (== x) y == ┐ x y mergeVertices & 1 (0 * 2) == 1 * 1 mergeVertices ⌡ 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.OsplitVertex1 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 (c x) == c x transpose (d x y) == d, y x transpose . transpose == id transpose (┴ x y) == ┴ (transpose x) (transpose y) u . transpose == (* . ▒ +, . u ┤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 (░ True ) x == Just x induce1 (░0 False) x == Nothing induce1 (/= x) == │ x induce1 p о) induce1 q == induce1 (\x -> p x && q x) ┬algebraic-graphsЪDSimplify a graph expression. Semantically, this is the identity function, but it simplifies a given expression according to the laws of the algebra. The function does not compute the simplest possible expression, but uses heuristics to obtain useful simplifications in reasonable time. Complexity: the function performs O(s)s graph comparisons. It is guaranteed that the size of the result does not exceed the size of the given expression.simplify == id o (simplify x) <= o x simplify 1 n 1 simplify (1 + 1) n 1 simplify (1 + 2 + 1) n 1 + 2 simplify (1 * 1 * 1) n 1 * 1 ┴algebraic-graphsCompute 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 (x [0,1]) (x ['a','b']) == iА [ ((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 e, 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 (e y z) == e (box x y) (box x z) box x (c ()) ~~ x ├ (box x y) == box (├ x) (├ y) r (box x y) == r x * r y s (box x y) <= r x * s y + s x * r 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 == (* . 12 . - (13 x) . sparsify r (sparsify x) <= r x + o x + 1 s (sparsify x) <= 3 * o x o (sparsify x) <= 3 * o x ▐algebraic-graphsNote:0 this does not satisfy the usual ring laws; see ^ for more details.-^_`abcdefghijklmnopqrstuvwxyz{|}~─│┌┐└┘├┤┬┴┼-^_`abcdefghijklmnopqrstuvwxyz{|}~─│┌┐└┘├┤┬┼┴n4(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone =>?HMPVX ^Ц■algebraic-graphsThe state of the order.∙algebraic-graphsChoosing what to order√algebraic-graphsMaking the payment≈algebraic-graphsThe order is complete≤algebraic-graphs3The alphabet of actions for ordering coffee or tea.≥algebraic-graphsOrder coffee algebraic-graphs Order tea⌡algebraic-graphsCancel payment or order°algebraic-graphsPay for the order²algebraic-graphs0An example automaton for ordering coffee or tea.order = ┤ [ ∙ │[≥, ]┌ √ , ∙ │[⌡ ]┌ ≈ , √ │[⌡ ]┌ ∙ , √ │[° ]┌ ≈ ] ·algebraic-graphsThe map of ■ reachability.reachability = Map.п $ map (s -> (s, N s order)) [∙ ..] Or, when evaluated:reachability = Map.п [ (∙ , [∙ , √, ≈"]) , (√ , [√ , ∙ , ≈"]) , (≈, [≈ ]) ] ■≈√∙≤°⌡ ≥²·≤°⌡ ≥■≈√∙²·(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPSVXH#╘algebraic-graphsThe ╘V data type is the Boehm-Berarducci encoding of the core graph construction primitives ╙, ╚, ґ and ў. We define a ~; instance as a convenient notation for working with graphs:У0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))Note: the ~7 instance does not satisfy several "customary laws" of ~, which dictate that 0 and 1; should act as additive and multiplicative identities, and ─0 as additive inverse. Nevertheless, overloading , │ and ┌И is very convenient when working with algebraic graphs; we hope that in future Haskell's Prelude will provide a more fine-grained class hierarchy for algebraic structures, which we would be able to utilise without violating any laws.The ┐? instance is defined using basic graph construction primitives:Ъ*show (empty :: Fold Int) == "empty" show (1 :: Fold Int) == "vertex 1" show (1 + 2 :: Fold Int) == "vertices [1,2]" show (1 * 2 :: Fold Int) == "edge 1 2" show (1 * 2 * 3 :: Fold Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Fold Int) == "overlay (vertex 3) (edge 1 2)"The └- instance is currently implemented using the 5 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 І% counts all leaves of the expression:╧ ╙ == 0 І ╙ == 1 ╧ (╚ x) == 1 І (╚ x) == 1 ╧ (╙ + ╙) == 0 І (╙ + ╙) == 2 Converting a ╘ to the corresponding 5 takes O(s + m * log(m)) time and O(s + m)╨ memory. This is also the complexity of the graph equality test, because it is currently implemented by converting graph expressions to canonical representations based on adjacency maps.+The total order on graphs is defined using size-lexicographic comparison:;Compare the number of vertices. In case of a tie, continue.9Compare the sets of vertices. In case of a tie, continue.8Compare the number of edges. In case of a tie, continue.Compare the sets of edges.Here are a few examples:╚ 1 < ╚ 2 ╚ 3 < ╛ 1 2 ╚ 1 < ╛ 1 1 ╛ 1 1 < ╛ 1 2 ╛ 1 2 < ╛ 1 1 + ╛ 2 2 ╛ 1 2 < ╛ 1 3*Note that the resulting order refines the Є! relation and is compatible with ґ and ў operations:Є x y ==> x <= y╙# <= x x <= x + y x + y <= x * y╙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-graphsGeneralised 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 ╙ ╚ ґ (╚ ў) == х foldg 1 (░" 1) (+) (+) == І foldg True (░" False) (&&) (&&) == ╣5 foldg False (== x) (||) (||) == Ї x Єalgebraic-graphsThe Є' function takes two graphs and returns ▐ if the first graph is a subgraph of the second. Complexity: O(s + m * log(m))% time. Note that the number of edges 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) (аC xs) == True isSubgraphOf x y ==> x <= y ╣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-graphs7Check if a graph contains a given vertex. Complexity: O(s) time.hasVertex x ╙" == False hasVertex x (╚ x) == True hasVertex 1 (╚! 2) == False hasVertex x . ф x == ░ False ╦algebraic-graphs5Check if a graph contains a given edge. Complexity: O(s) time.hasEdge x y ╙" == False hasEdge x y (╚ z) == False hasEdge x y (╛" x y) == True hasEdge x y . г x y == ░' False hasEdge x y == ┼ (x,y) . ╪ ╧algebraic-graphs0The number of vertices in a graph. Complexity: O(s * log(n)) time.vertexCount ╙ == 0 vertexCount (╚3 x) == 1 vertexCount == ▀ . ╩) vertexCount x < vertexCount y ==> x < y ╨algebraic-graphs-The number of edges in a graph. Complexity: O(s + m * log(m))% time. Note that the number of edges 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 . х == (* . ▒ +, . 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.■ Ў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-graphsThe 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 == ╠ . ▒ (√ д ) 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&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 == (* . ▒ +, . ╪ и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 (░ True ) x == x induce (░ False) x == ╙ induce (/= x) == ф< x induce p . induce q == induce (\x -> p x && q x) Є (induce p x) x == True йalgebraic-graphsЪVSimplify 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 яalgebraic-graphsNote:0 this does not satisfy the usual ring laws; see ╘ for more details."╘╙╚╛ґў╞╟╠╡ЁЄ╣ІЇ╦╧╨╩╪ҐЎ©юабцдефгхий"╘╙╚╛ґў╞╟╠╡ЁЄ╣ІЇ╦╧╨╩╪ҐЎ©юабцдефгхий(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXЧэ ж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 * xзalgebraic-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) vertexCount (edge 1 1) == 1 vertexCount (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 hasVertex x . vertices == ┼ x vertexCount . vertices == ▀ . () vertexSet . vertices == Set.OP Юalgebraic-graphs7Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L" is the length of the given list.edges [] == edges [(x,y)] == ч x y Аalgebraic-graphs-Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list.overlays [] == / overlays [x] == x overlays [x,y] == щ x y overlays == █ щ isEmpty . overlays == ▌ isEmpty Бalgebraic-graphs-Connect a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L' is the length of the given list, and S/ is the sum of sizes of the graphs in the list.connects [] == / connects [x] == x connects [x,y] == ш x y connects == █ ш isEmpty . connects == ▌ isEmpty Цalgebraic-graphsThe Ц' function takes two graphs and returns ▐ if the first graph is a subgraph3 of the second. Here is the current implementation:isSubgraphOf x y = щ x y == y 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-graphs5Check if a graph contains a given edge. Complexity: O(s) time.hasEdge x y " == False hasEdge x y (э z) == False hasEdge x y (ч4 x y) == True hasEdge x y == ┼ (x,y) . edgeList Еalgebraic-graphsThe path% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.path [] == path [x] == э x path [x,y] == ч x y Фalgebraic-graphsThe circuit% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.circuit [] == circuit [x] == ч x x circuit [x,y] == Ю [(x,y), (y,x)] Гalgebraic-graphsThe clique% on a list of vertices. Complexity: O(L) time, memory and size, where L" is the length of the given list.clique [] == clique [x] == э x clique [x,y] == ч x y clique [x,y,z] == Ю, [(x,y), (x,z), (y,z)] clique (xs ++ ys) == ш (clique xs) (clique ys) Хalgebraic-graphsThe biclique( on two lists of vertices. Complexity: O(L1 + L2) time, memory and size, where L1 and L2% are the lengths of the given lists.biclique [] [] == biclique [x] [] == э x biclique [] [y] == э y biclique [x1,x2] [y1,y2] == Ю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 adjacencyList. Complexity: O(L) time, memory and size, where L! is the total size of the input.!stars [] == " stars [(x, [])] == э$ x stars [(x, [y])] == ч& x y stars [(x, ys)] == И' x ys stars == А . ▒ (√ И ) stars . adjacencyList == id щ+ (stars xs) (stars ys) == stars (xs ++ ys) Кalgebraic-graphsThe tree graph constructed from a given ≤ data structure. Complexity: O(T) time, memory and size, where 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 == А . ▒ К Мalgebraic-graphsConstruct a mesh graph* from two lists of vertices. Complexity: O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists.mesh xs [] == mesh [] ys == mesh [x] [y] == э (x, y) mesh xs ys == box (Е xs) (Е ys) mesh [1..3] "ab" == Ює [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(2,'b')), ((2,'a'),(2,'b')) , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ] Нalgebraic-graphsConstruct a torus graph* from two lists of vertices. Complexity: O(L1 * L2) time, memory and size, where L1 and L2% are the lengths of the given lists.torus xs [] == torus [] ys == torus [x] [y] == ч! (x,y) (x,y) torus xs ys == box (Ф xs) (Ф ys) torus [1,2] "ab" == ЮЇ [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b')) , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ] тalgebraic-graphsAuxiliary function for М and НОalgebraic-graphsConstruct 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 vertexCount (deBruijn n xs) == (▀ $ () xs)^n n > 0 ==> edgeCount (deBruijn n xs) == (▀ $ () xs)^(n + 1) Пalgebraic-graphsConstruct the induced subgraph` of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s); time, memory and size, assuming that the predicate takes O(1) to be evaluated.induce (░ True ) x == x induce (░ False) x == induce (/= x) == Я< x induce p . induce q == induce (\x -> p x && q x) Ц (induce p x) x == True Яalgebraic-graphs1Remove a vertex from a given graph. Complexity: O(s) time, memory and size.removeVertex x (э x) == removeVertex 1 (э 2) == э 2 removeVertex x (ч x x) == removeVertex 1 (ч 1 2) == э5 2 removeVertex x . removeVertex x == removeVertex x Рalgebraic-graphs The function Р x y replaces vertex x with vertex y in a given з. If y already exists, x and y will be merged. Complexity: O(s) time, memory and size.6replaceVertex x x == id replaceVertex x y (э x) == э# y replaceVertex x y == С (== x) y Сalgebraic-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.mergeVertices (░7 False) x == id mergeVertices (== x) y == Р x y mergeVertices & 1 (0 * 2) == 1 * 1 mergeVertices ⌡ 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) жвьызшэщчъЮАБЦДЕФГХИЙКЛМНОПЯРСТ зшэщыьвжчъЮАБЦДЕФГХИЙКЛМНОЯРСТП(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXeEВ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 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 * xШalgebraic-graphs│The core type class for constructing algebraic graphs, characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for Ъ and , respectively.Ъ is commutative and associative:/ x + y == y + x x + (y + z) == (x + y) + z is associative and has Щ as the identity:< x * empty == x empty * x == x x * (y * z) == (x * y) * z distributes over Ъ:9x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z can be decomposed:"x * y * z == x * y + x * z + y * zIThe following useful theorems can be proved from the above set of axioms.Ъ has Щ# as the identity and is idempotent:2 x + empty == x empty + x == x x + x == xAbsorption and saturation of :-x * y + x + y == x * y x * x * x == x * xThe core type class Ш, corresponds to unlabelled directed graphs. З, Ы, Ь and В? graphs can be obtained by extending the minimal set of axioms.DWhen specifying the time and memory complexity of graph algorithms, n2 will denote the number of vertices in the graph, m3 will denote the number of edges in the graph, and s will denote the size of the corresponding Ш expression.Э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 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 == . ▒ ВЬЫЗШЭЩЧЪ ШЭЩЧЪЗЫЬВ (c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comunstableNone=>?HMPVX┤.algebraic-graphsThe . data type represents a 5binary relation that is both reflexive and transitive$. Preorders satisfy all laws of the В$ type class and, in particular, the self-loop axiom:Ч x == Ч x * Ч xand the closure axiom:y /= Щ+ ==> x * y + x * z + y * z == x * y + y * z!For example, the following holds: xs == ( xs :: PreorderRelation Int)The ┐C instance produces reflexively and transitively closed expressions:Дshow (1 :: PreorderRelation Int) == "edge 1 1" show (1 * 2 :: PreorderRelation Int) == "edges [(1,1),(1,2),(2,2)]" show (1 * 2 + 2 * 3 :: PreorderRelation Int) == "edges [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"1algebraic-graphsThe 1 data type represents a transitive binary relationF over a set of elements. Transitive relations satisfy all laws of the Ь$ type class and, in particular, the closure axiom:y /= Щ+ ==> x * y + x * z + y * z == x * y + y * z!For example, the following holds: xs == ( xs :: TransitiveRelation Int)The ┐3 instance produces transitively closed expressions:┼show (1 * 2 :: TransitiveRelation Int) == "edge 1 2" show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"4algebraic-graphsThe 4 data type represents a symmetric binary relationE over a set of elements. Symmetric relations satisfy all laws of the З= type class and, in particular, the commutativity of connect: x y == y xThe ┐4 instance produces symmetrically closed expressions:rshow (1 :: SymmetricRelation Int) == "vertex 1" show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"7algebraic-graphsThe 7 data type represents a reflexive binary relationE over a set of elements. Reflexive relations satisfy all laws of the Ы$ type class and, in particular, the self-loop axiom:Ч x == Ч x * Ч xThe ┐2 instance produces reflexively closed expressions:xshow (1 :: ReflexiveRelation Int) == "edge 1 1" show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"./0123456789789456123./0(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVX▄Talgebraic-graphs'Construct a transitive relation from a Б. Complexity: O(1) time.Ualgebraic-graphs.Extract the underlying relation. Complexity: O(n * m * log(m)) time.1TU1TU(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVX√мValgebraic-graphs&Construct a symmetric relation from a Б. Complexity: O(1) time.Walgebraic-graphs.Extract the underlying relation. Complexity: O(m*log(m)) time.Xalgebraic-graphsThe 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] 4VWX4VWX(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVX⌡┌Yalgebraic-graphs&Construct a reflexive relation from a Б. Complexity: O(1) time.Zalgebraic-graphs.Extract the underlying relation. Complexity: O(n*log(m)) time.7YZ7YZ(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVX═C[algebraic-graphs%Construct a preorder relation from a Б. Complexity: O(1) time.\algebraic-graphs.Extract the underlying relation. Complexity: O(n * m * log(m)) time..[\.[\(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone=>?HMPVXвg]algebraic-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). ] s is a ║ , therefore ╒ corresponds to the empty document- and two documents can be concatenated with ё (or operator /0Z). Documents comprising a single symbol or string can be constructed using the function _Q. Alternatively, you can construct documents as string literals, e.g. simply as "alga", by using the OverloadedStringsC GHC extension. To extract the document contents use the function `.ЇNote that the document comprising a single empty string is considered to be different from the empty document. This design choice is motivated by the desire to support string types s that have no └ instance, such as Data.ByteString.Builder^, for which there is no way to check whether a string is empty or not. As a consequence, the └ and г# instances are defined as follows:╒ /= _ "" ╒ < _ "" ^algebraic-graphs^Check if a document is empty. The result is the same as when comparing the given document to ╒), but this function does not require the └ s} constraint. Note that the document comprising a single empty string is considered to be different from the empty document.isEmpty ╒ == True isEmpty (_, "") == False isEmpty x == (x == ╒) _algebraic-graphs>Construct a document comprising a single symbol or string. If s is an instance of class у, then documents of type ] sR can be constructed directly from string literals (see the second example below).literal "Hello, " /0s literal "World!" == literal "Hello, World!" literal "I am just a string literal" == "I am just a string literal" `# . literal == ═ `algebraic-graphsCRender the document as a single string. An inverse of the function _.render (_ "al" /0 _ "ga") :: (у s, ║ s) => s render (_ "al" /0 _ "ga") == "alga" render ╒ == ╒ render . _ == ═ aalgebraic-graphs█Concatenate 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" balgebraic-graphs#Wrap a document in square brackets."brackets "i" == "[i]" brackets ╒ == "[]" calgebraic-graphs#Wrap a document into double quotes.YdoubleQuotes "/path/with spaces" == "\"/path/with spaces\"" doubleQuotes (doubleQuotes ╒) == "\"\"\"\"" dalgebraic-graphs/Prepend a given number of spaces to a document.indent 0 == ═ indent 1 ╒ == " " ealgebraic-graphsKConcatenate documents after appending a terminating newline symbol to each.!unlines [] == ╒ unlines [╒L] == "\n" unlines ["title", "subtitle"] == "title\nsubtitle\n" falgebraic-graphs²Export a graph into a document given two functions that construct documents for individual vertices and edges. The order of export is: vertices, sorted by г a, and then edges, sorted by г (a, a).For example:vDoc x = _ (ж x) <> "\n" eDoc x y = _ (ж x) <> " -> " <> _ (ж y) <> "\n" > putStrLn $ `( $ export vDoc eDoc (1 + 2 * (3 + 4) :: Q Int) 1 2 3 4 2 -> 3 2 -> 4 halgebraic-graphsThe empty document is smallest. ]^_`abcdef ]^_`abcdefa7(c) Andrey Mokhov 2016-2018MIT (see the file LICENSE)andrey.mokhov@gmail.comexperimentalNone"#=>?HMPVX кmalgebraic-graphsThe record m 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 t!, which holds a function of type a -> s< to compute vertex names. See the example for the function {.oalgebraic-graphsName of the graph.palgebraic-graphsJPreamble (a list of lines) is added at the beginning of the DOT file body.qalgebraic-graphsGraph style, e.g. ["bgcolor" := "azure"].ralgebraic-graphsDefault vertex style, e.g. ["shape" := "diamond"].salgebraic-graphsDefault edge style, e.g. ["style" := "dashed"].talgebraic-graphsCompute a vertex name.ualgebraic-graphs Attributes of a specific vertex.valgebraic-graphsAttributes of a specific edge.walgebraic-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.yalgebraic-graphsMDefault style for exporting graphs. All style settings are empty except for t), which is provided as the only argument.zalgebraic-graphs6Default style for exporting graphs whose vertices are ┐0-able. All style settings are empty except for t, which is computed from ж.defaultStyleViaShow = y (в . ж) {algebraic-graphs"Export a graph with a given style.For example: style :: m Int String style = m { o! = "Example" , p8 = [" // This is an example", ""] , q= = ["label" := "Example", "labelloc" := "top"] , r = ["shape" := "circle"] , s = ╒ , t = \x -> "v" ++ ж x , u) = \x -> ["color" := "blue" | ⌡ x ] , v+ = \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"].|algebraic-graphsDExport a graph whose vertices are represented simply by their names.For example:> Text.putStrLn $ exportAsIs (R ["a", "b", "c"] :: 9M Text) digraph { "a" "b" "c" "a" -> "b" "b" -> "c" "c" -> "a" } }algebraic-graphsExport a graph using the z.For example:/> putStrLn $ exportViaShow (1 + 2 * (3 + 4) :: QE Int) digraph { "1" "2" "3" "4" "2" -> "3" "2" -> "4" } mnopqrstuvwxyz{|}wxmnopqrstuvyz{|}ыST"UHLVWXYZ["#$ !A&\]%?:^45BCF_`abcRdef'ghGi.jklmnopqrs9HKVtuvwxyz"#$ !A&\]%?:^45BC6_`{7cRdef'|hGi.jklmnopqrs}~─││┌┐└┘├├┤┬┴┼▀▄█▌▐░▒▓⌠■∙√≈≤≥ ⌡⌡°²Q·÷═║"#$ !A&\]╒%ё?є:^45BC6_`cRdef'hG╔іїi.jk╗ln╘o╙╚╛ґў╞╟╠╡ЁЄ╣ІЇ╦╧╨╩╪ҐЎЎ©юабццдефгхийкfлмнопярстужвьызшэщчъЮАБЦДЕФГХИЙКЛМНОПЯРСТУЖВЬЫЗШЭЩЧЪ !"#$%&'()* 9 H K V w y x z v " # $ + , ! A & \ - % ? : ^ . 4 5 B C 6 _ { 7 / i . j 0 l m 1 n p q r s⌡⌡°²234Q·÷║╒%"#$+, !A&\?є:^.BC6_i.j0l1npqrs╛Ё╠╡╣ІЇ╦56789:;<=>?@ABC 9 D E V x w z v yF# !$GHIJ%:^45KC6_{7LMNOfPhQ.jklmRpqrsSSTU"# !VuVWXYZ$A&\]%?:^45BC6_`{7cRdef'hGi.jklmnopqrs[[\]^_`aIbcaIb-cdefgaIb-cdfghij╒?є:^45BC6F_{a7b`KLklaIb-cd8mnofgpqrstuvQ÷═║F#$ w!GHIJx%ёє:^45KC6_LMNOfPhyzQ.jk{lR╘╙╚╞╟╠╡ЁsЄ╣І|}~─│┌┐└┘├┤┬┴┼▀▄█▌▐░▒"#$ !A&\]╒%?є:^45BC6_`cRdef'i.ln╘▓⌠■∙√≈≤≥ ⌡°²·÷═Q!# $A&\]%^cRdef'hG╔іїnijk╗║╒²·÷═Q÷"# !$A&\]%cRdefhGёє╔ії╗╘╒╙║╚╛ґў╞╟╠╡ЁЄ╣ІЇ╦╧╨╩╪ҐЎ©юаабццдеефггхийклмнопярстужвьызшэщчъЮАБЦДЦДЕЦДЦДФ?ГХпИЙКЛМНОПЯРСТТУЖВЬЫЗШЭЩЧЪМSSSSSS ""PSS<PSSSTST"PSNS+ST !S"#S"$%"&&PST'ST(ST)ST*ST+ST,ST-SMS.S/S01S02ST3S45S16S137ST89:ST0;<=>S?│┌┐└┬┼@│SAS0BS;MS;NS+,CSDEєEF7GHS=>%PSTISTJSTK5SLMS NSLOPQ+algebraic-graphs-0.3-9iXAmdS5Ckb8ByYBrd2dwP Algebra.Graph.HigherKinded.Class&Algebra.Graph.AdjacencyIntMap.InternalAlgebra.Graph.AdjacencyIntMap#Algebra.Graph.AdjacencyMap.InternalAlgebra.Graph.AdjacencyMapAlgebra.Graph.Internal Algebra.GraphAlgebra.Graph.Label,Algebra.Graph.Labelled.AdjacencyMap.Internal#Algebra.Graph.Labelled.AdjacencyMapAlgebra.Graph.Labelled&Algebra.Graph.Labelled.Example.Network,Algebra.Graph.NonEmpty.AdjacencyMap.Internal#Algebra.Graph.NonEmpty.AdjacencyMapAlgebra.Graph.Relation.InternalAlgebra.Graph.RelationData.Graph.Typed$Algebra.Graph.AdjacencyMap.Algorithm'Algebra.Graph.AdjacencyIntMap.AlgorithmAlgebra.Graph.ToGraphAlgebra.Graph.NonEmpty(Algebra.Graph.Labelled.Example.AutomatonAlgebra.Graph.FoldAlgebra.Graph.Class&Algebra.Graph.Relation.InternalDerived!Algebra.Graph.Relation.Transitive Algebra.Graph.Relation.Symmetric Algebra.Graph.Relation.ReflexiveAlgebra.Graph.Relation.PreorderAlgebra.Graph.ExportAlgebra.Graph.Export.DotoverlayconnectemptyvertexedgeisSubgraphOfedgesstars Data.Listnubsort Data.Tupleswap reachable removeEdgeData.Monoid<>Data.EitherrightsRightvertexCount edgeCount vertexSetpostSettoAdjacencyMapAdjacencyMap hasVertexData.List.NonEmptylength Control.Monad>=>isEmpty Data.Graphvertices vertexListedgeListData.IntSet toAscListvertexIntSetforestAM dfsForestFrom:|adjacencyMapadjacencyIntMaptoListreverseSetfromListGraphcircuitbaseGHC.BaseAdjacencyIntMap consistent$fNFDataAdjacencyIntMap$fNumAdjacencyIntMap$fOrdAdjacencyIntMap$fShowAdjacencyIntMap$fEqAdjacencyIntMapoverlaysconnectshasEdgeedgeSet adjacencyList preIntSet postIntSetpathcliquebicliquestarfromAdjacencyIntSetstreeremoveVertex replaceVertex mergeVertices transposegmapinducecomposeclosurereflexiveClosuresymmetricClosuretransitiveClosureinternalEdgeListreferredToVertexSet$fNFDataAdjacencyMap$fNumAdjacencyMap$fShowAdjacencyMap$fOrdAdjacencyMap$fEqAdjacencyMappreSetfromAdjacencySetsHitMissTailEdgeFocusokisosvsList emptyFocusvertexFocusoverlayFociconnectFoci foldr1SafemaybeF setProductsetProductWith$fMonadList$fApplicativeList $fFunctorList$fFoldableList$fIsListList $fOrdList$fEqList $fShowList$fMonoidList$fSemigroupList$fEqHit$fOrdHitContextinputsoutputsEmptyVertexOverlayConnectfoldg===sizemeshtorusdeBruijnsplitVertexsimplifyboxsparsifycontext$fMonadPlusGraph$fAlternativeGraph$fMonadGraph$fApplicativeGraph $fOrdGraph $fEqGraph $fNumGraph $fNFDataGraph$fFunctorGraph$fShowGraph$fEqContext $fShowContext WidestPathCountShortestPathsAllShortestPathsShortestPathPathOptimum getOptimumgetArgumentRegularExpressionLabelPowerSetgetPowerSetMinimumDistanceCountCapacityNonNegativeDioidStarSemiringSemiringone<.>zero<+>finite finiteWordunsafeFiniteinfinite getFinitecapacitygetCapacitycountgetCountdistancegetDistance getMinimum noMinimumisZero $fSemiringAny$fStarSemiringAny $fDioidAny $fNumExtended$fMonadExtended$fApplicativeExtended$fNumNonNegative$fBoundedNonNegative$fShowNonNegative$fDioidDistance$fStarSemiringDistance$fSemiringDistance$fShowDistance$fStarSemiringCount$fSemiringCount$fShowCount$fDioidCapacity$fStarSemiringCapacity$fSemiringCapacity$fShowCapacity$fIsListMinimum $fShowMinimum$fDioidPowerSet$fStarSemiringPowerSet$fSemiringPowerSet$fStarSemiringLabel$fSemiringLabel $fMonoidLabel$fSemigroupLabel$fShowLabel $fIsListLabel$fDioidOptimum$fStarSemiringOptimum$fSemiringOptimum$fMonoidOptimum$fSemigroupOptimum$fEqExtended$fFunctorExtended $fOrdExtended$fShowExtended$fApplicativeNonNegative$fEqNonNegative$fFunctorNonNegative$fOrdNonNegative$fMonadNonNegative$fBoundedDistance$fEqDistance$fMonoidDistance $fNumDistance $fOrdDistance$fSemigroupDistance$fBoundedCount $fEqCount $fMonoidCount $fNumCount $fOrdCount$fSemigroupCount$fBoundedCapacity$fEqCapacity$fMonoidCapacity $fNumCapacity $fOrdCapacity$fSemigroupCapacity$fApplicativeMinimum$fEqMinimum$fFunctorMinimum$fOrdMinimum$fMonadMinimum$fEqPowerSet$fMonoidPowerSet $fOrdPowerSet$fSemigroupPowerSet$fFunctorLabel$fEqOptimum$fOrdOptimum $fShowOptimum-<>-fromAdjacencyMaps edgeLabelskeletonreplaceEdgeemapNetwork AutomatonUnlabelledGraphJourneyTimeCityAberdeen EdinburghGlasgowLondon Newcastle eastCoastscotRailnetwork $fBoundedCity $fEnumCity$fEqCity $fOrdCity $fShowCityNAMam toNonEmpty vertices1edges1 overlays1 connects1vertexList1path1circuit1clique1 biclique1stars1 removeVertex1induce1Relationdomainrelation $fNumRelation$fNFDataRelation $fOrdRelation$fShowRelation$fEqRelationGraphKL toGraphKLfromVertexKL toVertexKLfromAdjacencyMapfromAdjacencyIntMap dfsForestdfstopSort isAcyclicscc isDfsForestOfisTopSortOfToGraphToVertextoGraphadjacencyMapTransposeadjacencyIntMapTransposetoAdjacencyMapTransposetoAdjacencyIntMaptoAdjacencyIntMapTranspose$fToGraphRelation$fToGraphAdjacencyMap$fToGraphAdjacencyMap0$fToGraphGraph$fToGraphAdjacencyIntMap$fToGraphAdjacencyMap1$fToGraphGraph0overlay1foldg1mesh1torus1splitVertex1StateChoicePaymentCompleteAlphabetCoffeeTeaCancelPaycoffeeTeaAutomatonreachability$fBoundedAlphabet$fEnumAlphabet$fEqAlphabet $fOrdAlphabet$fShowAlphabet$fBoundedState$fEnumState $fEqState $fOrdState$fShowStateFold $fToGraphFold$fMonadFold$fMonadPlusFold$fAlternativeFold$fApplicativeFold $fFunctorFold $fNumFold$fNFDataFold $fOrdFold$fEqFold $fShowFoldPreorder Transitive Reflexive Undirected$fGraphFold$fGraphGraph$fGraph(,,) $fGraph(,) $fGraph->$fGraphMaybe $fGraph()$fGraphRelation$fGraphAdjacencyMap$fGraphAdjacencyIntMap$fGraphAdjacencyMap0 $fGraphGraph0$fUndirected(,,)$fUndirected(,)$fUndirected->$fUndirectedMaybe$fUndirected()$fReflexive(,,)$fReflexive(,) $fReflexive->$fReflexiveMaybe $fReflexive()$fTransitive(,,)$fTransitive(,)$fTransitive->$fTransitiveMaybe$fTransitive()$fPreorder(,,) $fPreorder(,)$fPreorder->$fPreorderMaybe$fPreorder()PreorderRelationfromPreorderTransitiveRelationfromTransitiveSymmetricRelation 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$fNFDataPreorderRelationfromRelation toRelation neighboursDocliteralrenderbracketsdoubleQuotesindentunlinesexport $fIsStringDoc$fOrdDoc$fEqDoc $fShowDoc$fMonoidDoc$fSemigroupDocStyle graphNamepreamblegraphAttributesdefaultVertexAttributesdefaultEdgeAttributes vertexNamevertexAttributesedgeAttributes Attribute:=defaultStyledefaultStyleViaShow exportAsIs exportViaShowGHC.NumNumfromIntegernegate+*GHC.ShowShowghc-primGHC.ClassesEqcontainers-0.6.0.1Data.IntMap.InternalData.IntMap.Strict singletonData.IntSet.Internal Data.Foldableelemfoldrall GHC.TypesTrueconstmapData.Set.InternalGHC.Listuncurryfmap Data.TreeTreeForestGHC.RealevenoddData.Map.InternalData.Map.Strict.Internal++idMonoidmemptymappendpureApplicativeFoldablefoldr1 GHC.MaybeMaybeJustflipnullpairsLeftunionliftA2minmaxWord:+::*:notfilterfocussignumNothingOrd Data.MaybeisJustInteqvertexIntList1 MonadPlusAlternative<|>Data.StringIsStringshow fromString attributes