-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | A library for algebraic graph construction and transformation -- -- Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory and implementation details. -- -- The top-level module Algebra.Graph defines the main data type -- for algebraic graphs Graph, as well as associated -- algorithms. For type-safe representation and manipulation of -- non-empty algebraic graphs, see Algebra.Graph.NonEmpty. -- Furthermore, algebraic graphs with edge labels are implemented -- in Algebra.Graph.Labelled. -- -- The library also provides conventional graph data structures, such as -- Algebra.Graph.AdjacencyMap along with its various flavours: -- adjacency maps specialised to graphs with vertices of type Int -- (Algebra.Graph.AdjacencyIntMap), non-empty adjacency maps -- (Algebra.Graph.NonEmpty.AdjacencyMap), and adjacency maps with -- edge labels (Algebra.Graph.Labelled.AdjacencyMap). A large part -- of the API of algebraic graphs and adjacency maps is available through -- the Foldable-like type class Algebra.Graph.ToGraph. -- -- The type classes defined in Algebra.Graph.Class and -- Algebra.Graph.HigherKinded.Class can be used for polymorphic -- construction and manipulation of graphs. Also see -- Algebra.Graph.Fold that defines the Boehm-Berarducci encoding -- of algebraic graphs. -- -- This is an experimental library and the API is expected to remain -- unstable until version 1.0.0. Please consider contributing to the -- on-going discussions on the library API. @package algebraic-graphs @version 0.3 -- | This module exposes the implementation of adjacency maps. The API is -- unstable and unsafe, and is exposed only for documentation. You should -- use the non-internal module Algebra.Graph.AdjacencyIntMap -- instead. module Algebra.Graph.AdjacencyIntMap.Internal -- | The AdjacencyIntMap data type represents a graph by a map of -- vertices to their adjacency sets. We define a Num 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 Num instance does not satisfy several -- "customary laws" of Num, which dictate that fromInteger -- 0 and fromInteger 1 should act as additive -- and multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show instance is defined using basic graph construction -- primitives: -- --
-- show (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 Eq instance satisfies all axioms of algebraic graphs: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- empty <= x -- x <= x + y -- x + y <= x * y --newtype AdjacencyIntMap AM :: IntMap IntSet -> AdjacencyIntMap -- | The adjacency map of a graph: each vertex is associated with a -- set of its direct successors. Complexity: O(1) time and memory. -- --
-- adjacencyIntMap empty == IntMap.empty -- adjacencyIntMap (vertex x) == IntMap.singleton x IntSet.empty -- adjacencyIntMap (edge 1 1) == IntMap.singleton 1 (IntSet.singleton 1) -- adjacencyIntMap (edge 1 2) == IntMap.fromList [(1,IntSet.singleton 2), (2,IntSet.empty)] --[adjacencyIntMap] :: AdjacencyIntMap -> IntMap IntSet -- | 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 empty == True -- consistent (vertex x) == True -- consistent (overlay x y) == True -- consistent (connect x y) == True -- consistent (edge x y) == True -- consistent (edges xs) == True -- consistent (stars xs) == True --consistent :: AdjacencyIntMap -> Bool instance GHC.Classes.Eq Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap instance GHC.Show.Show Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap instance GHC.Classes.Ord Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap instance GHC.Num.Num Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap instance Control.DeepSeq.NFData Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the AdjacencyIntMap data type and -- associated functions. See -- Algebra.Graph.AdjacencyIntMap.Algorithm for implementations of -- basic graph algorithms. AdjacencyIntMap is an instance of the -- Graph type class, which can be used for polymorphic graph -- construction and manipulation. See Algebra.Graph.AdjacencyMap -- for graphs with non-Int vertices. module Algebra.Graph.AdjacencyIntMap -- | The AdjacencyIntMap data type represents a graph by a map of -- vertices to their adjacency sets. We define a Num 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 Num instance does not satisfy several -- "customary laws" of Num, which dictate that fromInteger -- 0 and fromInteger 1 should act as additive -- and multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show instance is defined using basic graph construction -- primitives: -- --
-- show (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 Eq instance satisfies all axioms of algebraic graphs: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- empty <= x -- x <= x + y -- x + y <= x * y --data AdjacencyIntMap -- | The adjacency map of a graph: each vertex is associated with a -- set of its direct successors. Complexity: O(1) time and memory. -- --
-- adjacencyIntMap empty == IntMap.empty -- adjacencyIntMap (vertex x) == IntMap.singleton x IntSet.empty -- adjacencyIntMap (edge 1 1) == IntMap.singleton 1 (IntSet.singleton 1) -- adjacencyIntMap (edge 1 2) == IntMap.fromList [(1,IntSet.singleton 2), (2,IntSet.empty)] --adjacencyIntMap :: AdjacencyIntMap -> IntMap IntSet -- | Construct the empty graph. Complexity: O(1) time and -- memory. -- --
-- isEmpty empty == True -- hasVertex x empty == False -- vertexCount empty == 0 -- edgeCount empty == 0 --empty :: AdjacencyIntMap -- | Construct the graph comprising a single isolated vertex. -- Complexity: O(1) time and memory. -- --
-- isEmpty (vertex x) == False -- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 --vertex :: Int -> AdjacencyIntMap -- | Construct the graph comprising a single edge. Complexity: -- O(1) time, memory. -- --
-- edge x y == connect (vertex x) (vertex y) -- hasEdge x y (edge x y) == True -- edgeCount (edge x y) == 1 -- vertexCount (edge 1 1) == 1 -- vertexCount (edge 1 2) == 2 --edge :: Int -> Int -> AdjacencyIntMap -- | Overlay 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. -- --
-- isEmpty (overlay x y) == isEmpty x && isEmpty y -- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 --overlay :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap -- | Connect two graphs. This is an associative operation with the -- identity empty, which distributes over overlay and obeys -- the decomposition axiom. Complexity: O((n + m) * log(n)) time -- and O(n + m) memory. Note that the number of edges in the -- resulting graph is quadratic with respect to the number of vertices of -- the arguments: m = O(m1 + m2 + n1 * n2). -- --
-- isEmpty (connect x y) == isEmpty x && isEmpty y -- hasVertex z (connect x y) == hasVertex z x || hasVertex z y -- vertexCount (connect x y) >= vertexCount x -- vertexCount (connect x y) <= vertexCount x + vertexCount y -- edgeCount (connect x y) >= edgeCount x -- edgeCount (connect x y) >= edgeCount y -- edgeCount (connect x y) >= vertexCount x * vertexCount y -- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- vertexCount (connect 1 2) == 2 -- edgeCount (connect 1 2) == 1 --connect :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap -- | Construct 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 [] == empty -- vertices [x] == vertex x -- hasVertex x . vertices == elem x -- vertexCount . vertices == length . nub -- vertexIntSet . vertices == IntSet.fromList --vertices :: [Int] -> AdjacencyIntMap -- | Construct the graph from a list of edges. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- edges [] == empty -- edges [(x,y)] == edge x y -- edgeCount . edges == length . nub -- edgeList . edges == nub . sort --edges :: [(Int, Int)] -> AdjacencyIntMap -- | Overlay a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- overlays [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty -- isEmpty . overlays == all isEmpty --overlays :: [AdjacencyIntMap] -> AdjacencyIntMap -- | Connect a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- connects [] == empty -- connects [x] == x -- connects [x,y] == connect x y -- connects == foldr connect empty -- isEmpty . connects == all isEmpty --connects :: [AdjacencyIntMap] -> AdjacencyIntMap -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O((n + m) * log(n)) time. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path xs) (circuit xs) == True -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: AdjacencyIntMap -> AdjacencyIntMap -> Bool -- | Check if a graph is empty. Complexity: O(1) time. -- --
-- isEmpty empty == True -- isEmpty (overlay empty empty) == True -- isEmpty (vertex x) == False -- isEmpty (removeVertex x $ vertex x) == True -- isEmpty (removeEdge x y $ edge x y) == False --isEmpty :: AdjacencyIntMap -> Bool -- | Check if a graph contains a given vertex. Complexity: O(log(n)) -- time. -- --
-- hasVertex x empty == False -- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False -- hasVertex x . removeVertex x == const False --hasVertex :: Int -> AdjacencyIntMap -> Bool -- | Check if a graph contains a given edge. Complexity: O(log(n)) -- time. -- --
-- hasEdge x y empty == False -- hasEdge x y (vertex z) == False -- hasEdge x y (edge x y) == True -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == elem (x,y) . edgeList --hasEdge :: Int -> Int -> AdjacencyIntMap -> Bool -- | The number of vertices in a graph. Complexity: O(1) time. -- --
-- vertexCount empty == 0 -- vertexCount (vertex x) == 1 -- vertexCount == length . vertexList -- vertexCount x < vertexCount y ==> x < y --vertexCount :: AdjacencyIntMap -> Int -- | The number of edges in a graph. Complexity: O(n) time. -- --
-- edgeCount empty == 0 -- edgeCount (vertex x) == 0 -- edgeCount (edge x y) == 1 -- edgeCount == length . edgeList --edgeCount :: AdjacencyIntMap -> Int -- | The sorted list of vertices of a given graph. Complexity: O(n) -- time and memory. -- --
-- vertexList empty == [] -- vertexList (vertex x) == [x] -- vertexList . vertices == nub . sort --vertexList :: AdjacencyIntMap -> [Int] -- | The sorted list of edges of a graph. Complexity: O(n + m) time -- and O(m) memory. -- --
-- edgeList empty == [] -- edgeList (vertex x) == [] -- edgeList (edge x y) == [(x,y)] -- edgeList (star 2 [3,1]) == [(2,1), (2,3)] -- edgeList . edges == nub . sort -- edgeList . transpose == sort . map swap . edgeList --edgeList :: AdjacencyIntMap -> [(Int, Int)] -- | The sorted adjacency list of a graph. Complexity: O(n + -- m) time and O(m) memory. -- --
-- adjacencyList empty == [] -- adjacencyList (vertex x) == [(x, [])] -- adjacencyList (edge 1 2) == [(1, [2]), (2, [])] -- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] -- stars . adjacencyList == id --adjacencyList :: AdjacencyIntMap -> [(Int, [Int])] -- | The set of vertices of a given graph. Complexity: O(n) time and -- memory. -- --
-- vertexIntSet empty == IntSet.empty -- vertexIntSet . vertex == IntSet.singleton -- vertexIntSet . vertices == IntSet.fromList -- vertexIntSet . clique == IntSet.fromList --vertexIntSet :: AdjacencyIntMap -> IntSet -- | The set of edges of a given graph. Complexity: O((n + m) * -- log(m)) time and O(m) memory. -- --
-- edgeSet empty == Set.empty -- edgeSet (vertex x) == Set.empty -- edgeSet (edge x y) == Set.singleton (x,y) -- edgeSet . edges == Set.fromList --edgeSet :: AdjacencyIntMap -> Set (Int, Int) -- | The 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 empty == Set.empty -- preIntSet x (vertex x) == Set.empty -- preIntSet 1 (edge 1 2) == Set.empty -- preIntSet y (edge x y) == Set.fromList [x] --preIntSet :: Int -> AdjacencyIntMap -> IntSet -- | The postset (here postIntSet) of a vertex is the set -- of its direct successors. -- --
-- postIntSet x empty == IntSet.empty -- postIntSet x (vertex x) == IntSet.empty -- postIntSet x (edge x y) == IntSet.fromList [y] -- postIntSet 2 (edge 1 2) == IntSet.empty --postIntSet :: Int -> AdjacencyIntMap -> IntSet -- | The path on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- path [] == empty -- path [x] == vertex x -- path [x,y] == edge x y -- path . reverse == transpose . path --path :: [Int] -> AdjacencyIntMap -- | The circuit on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- circuit [] == empty -- circuit [x] == edge x x -- circuit [x,y] == edges [(x,y), (y,x)] -- circuit . reverse == transpose . circuit --circuit :: [Int] -> AdjacencyIntMap -- | The clique on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- clique [] == empty -- clique [x] == vertex x -- clique [x,y] == edge x y -- clique [x,y,z] == edges [(x,y), (x,z), (y,z)] -- clique (xs ++ ys) == connect (clique xs) (clique ys) -- clique . reverse == transpose . clique --clique :: [Int] -> AdjacencyIntMap -- | The biclique on two lists of vertices. Complexity: O(n * -- log(n) + m) time and O(n + m) memory. -- --
-- biclique [] [] == empty -- biclique [x] [] == vertex x -- biclique [] [y] == vertex y -- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique xs ys == connect (vertices xs) (vertices ys) --biclique :: [Int] -> [Int] -> AdjacencyIntMap -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges [(x,y), (x,z)] -- star x ys == connect (vertex x) (vertices ys) --star :: Int -> [Int] -> AdjacencyIntMap -- | The stars formed by overlaying a list of stars. An -- inverse of adjacencyList. Complexity: O(L * log(n)) -- time, memory and size, where L is the total size of the input. -- --
-- stars [] == empty -- stars [(x, [])] == vertex x -- stars [(x, [y])] == edge x y -- stars [(x, ys)] == star x ys -- stars == overlays . map (uncurry star) -- stars . adjacencyList == id -- overlay (stars xs) (stars ys) == stars (xs ++ ys) --stars :: [(Int, [Int])] -> AdjacencyIntMap -- | Construct a graph from a list of adjacency sets; a variation of -- stars. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- fromAdjacencyIntSets [] == empty -- fromAdjacencyIntSets [(x, IntSet.empty)] == vertex x -- fromAdjacencyIntSets [(x, IntSet.singleton y)] == edge x y -- fromAdjacencyIntSets . map (fmap IntSet.fromList) == stars -- overlay (fromAdjacencyIntSets xs) (fromAdjacencyIntSets ys) == fromAdjacencyIntSets (xs ++ ys) --fromAdjacencyIntSets :: [(Int, IntSet)] -> AdjacencyIntMap -- | The tree graph constructed from a given Tree data -- structure. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- tree (Node x []) == vertex x -- tree (Node x [Node y [Node z []]]) == path [x,y,z] -- tree (Node x [Node y [], Node z []]) == star x [y,z] -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges [(1,2), (1,3), (3,4), (3,5)] --tree :: Tree Int -> AdjacencyIntMap -- | The forest graph constructed from a given Forest data -- structure. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- forest [] == empty -- forest [x] == tree x -- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == edges [(1,2), (1,3), (4,5)] -- forest == overlays . map tree --forest :: Forest Int -> AdjacencyIntMap -- | Remove a vertex from a given graph. Complexity: O(n*log(n)) -- time. -- --
-- removeVertex x (vertex x) == empty -- removeVertex 1 (vertex 2) == vertex 2 -- removeVertex x (edge x x) == empty -- removeVertex 1 (edge 1 2) == vertex 2 -- removeVertex x . removeVertex x == removeVertex x --removeVertex :: Int -> AdjacencyIntMap -> AdjacencyIntMap -- | Remove an edge from a given graph. Complexity: O(log(n)) time. -- --
-- removeEdge x y (edge x y) == vertices [x,y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . removeVertex x == removeVertex x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 -- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 --removeEdge :: Int -> Int -> AdjacencyIntMap -> AdjacencyIntMap -- | The function replaceVertex x y replaces vertex -- x with vertex y in a given AdjacencyIntMap. -- If y already exists, x and y will be -- merged. Complexity: O((n + m) * log(n)) time. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == mergeVertices (== x) y --replaceVertex :: Int -> Int -> AdjacencyIntMap -> AdjacencyIntMap -- | Merge 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 (const False) x == id -- mergeVertices (== x) y == replaceVertex x y -- mergeVertices even 1 (0 * 2) == 1 * 1 -- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 --mergeVertices :: (Int -> Bool) -> Int -> AdjacencyIntMap -> AdjacencyIntMap -- | Transpose a given graph. Complexity: O(m * log(n)) time, O(n -- + m) memory. -- --
-- transpose empty == empty -- transpose (vertex x) == vertex x -- transpose (edge x y) == edge y x -- transpose . transpose == id -- edgeList . transpose == sort . map swap . edgeList --transpose :: AdjacencyIntMap -> AdjacencyIntMap -- | Transform a graph by applying a function to each of its vertices. This -- is similar to Functor's fmap but can be used with -- non-fully-parametric AdjacencyIntMap. Complexity: O((n + m) -- * log(n)) time. -- --
-- gmap f empty == empty -- gmap f (vertex x) == vertex (f x) -- gmap f (edge x y) == edge (f x) (f y) -- gmap id == id -- gmap f . gmap g == gmap (f . g) --gmap :: (Int -> Int) -> AdjacencyIntMap -> AdjacencyIntMap -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(m) time, assuming that the predicate takes O(1) to be -- evaluated. -- --
-- induce (const True ) x == x -- induce (const False) x == empty -- induce (/= x) == removeVertex x -- induce p . induce q == induce (\x -> p x && q x) -- isSubgraphOf (induce p x) x == True --induce :: (Int -> Bool) -> AdjacencyIntMap -> AdjacencyIntMap -- | Left-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 -- z in the second graph. There are no isolated vertices in the -- result. This operation is associative, has empty and -- single-vertex graphs as annihilating zeroes, and -- distributes over overlay. Complexity: O(n * m * log(n)) -- time and O(n + m) memory. -- --
-- compose empty x == empty -- compose x empty == empty -- compose (vertex x) y == empty -- compose x (vertex y) == empty -- compose x (compose y z) == compose (compose x y) z -- compose x (overlay y z) == overlay (compose x y) (compose x z) -- compose (overlay x y) z == overlay (compose x z) (compose y z) -- compose (edge x y) (edge y z) == edge x z -- compose (path [1..5]) (path [1..5]) == edges [(1,3), (2,4), (3,5)] -- compose (circuit [1..5]) (circuit [1..5]) == circuit [1,3,5,2,4] --compose :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap -- | Compute the reflexive and transitive closure of a graph. -- Complexity: O(n * m * log(n)^2) time. -- --
-- closure empty == empty -- closure (vertex x) == edge x x -- closure (edge x x) == edge x x -- closure (edge x y) == edges [(x,x), (x,y), (y,y)] -- closure (path $ nub xs) == reflexiveClosure (clique $ nub xs) -- closure == reflexiveClosure . transitiveClosure -- closure == transitiveClosure . reflexiveClosure -- closure . closure == closure -- postIntSet x (closure y) == IntSet.fromList (reachable x y) --closure :: AdjacencyIntMap -> AdjacencyIntMap -- | Compute the reflexive closure of a graph by adding a self-loop -- to every vertex. Complexity: O(n * log(n)) time. -- --
-- reflexiveClosure empty == empty -- reflexiveClosure (vertex x) == edge x x -- reflexiveClosure (edge x x) == edge x x -- reflexiveClosure (edge x y) == edges [(x,x), (x,y), (y,y)] -- reflexiveClosure . reflexiveClosure == reflexiveClosure --reflexiveClosure :: AdjacencyIntMap -> AdjacencyIntMap -- | Compute the symmetric closure of a graph by overlaying it with -- its own transpose. Complexity: O((n + m) * log(n)) time. -- --
-- symmetricClosure empty == empty -- symmetricClosure (vertex x) == vertex x -- symmetricClosure (edge x y) == edges [(x,y), (y,x)] -- symmetricClosure x == overlay x (transpose x) -- symmetricClosure . symmetricClosure == symmetricClosure --symmetricClosure :: AdjacencyIntMap -> AdjacencyIntMap -- | Compute the transitive closure of a graph. Complexity: O(n * -- m * log(n)^2) time. -- --
-- transitiveClosure empty == empty -- transitiveClosure (vertex x) == vertex x -- transitiveClosure (edge x y) == edge x y -- transitiveClosure (path $ nub xs) == clique (nub xs) -- transitiveClosure . transitiveClosure == transitiveClosure --transitiveClosure :: AdjacencyIntMap -> AdjacencyIntMap -- | This module exposes the implementation of adjacency maps. The API is -- unstable and unsafe, and is exposed only for documentation. You should -- use the non-internal module Algebra.Graph.AdjacencyMap instead. module Algebra.Graph.AdjacencyMap.Internal -- | The AdjacencyMap data type represents a graph by a map of -- vertices to their adjacency sets. We define a Num 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 Num instance does not satisfy several -- "customary laws" of Num, which dictate that fromInteger -- 0 and fromInteger 1 should act as additive -- and multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show instance is defined using basic graph construction -- primitives: -- --
-- show (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 Eq instance satisfies all axioms of algebraic graphs: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- empty <= x -- x <= x + y -- x + y <= x * y --newtype AdjacencyMap a AM :: Map a (Set a) -> AdjacencyMap a -- | The adjacency map of a graph: each vertex is associated with a -- set of its direct successors. Complexity: O(1) time and memory. -- --
-- adjacencyMap empty == Map.empty -- adjacencyMap (vertex x) == Map.singleton x Set.empty -- adjacencyMap (edge 1 1) == Map.singleton 1 (Set.singleton 1) -- adjacencyMap (edge 1 2) == Map.fromList [(1,Set.singleton 2), (2,Set.empty)] --[adjacencyMap] :: AdjacencyMap a -> Map a (Set a) -- | 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 empty == True -- consistent (vertex x) == True -- consistent (overlay x y) == True -- consistent (connect x y) == True -- consistent (edge x y) == True -- consistent (edges xs) == True -- consistent (stars xs) == True --consistent :: Ord a => AdjacencyMap a -> Bool -- | The list of edges of an adjacency map. Note: this function is for -- internal use only. internalEdgeList :: Map a (Set a) -> [(a, a)] -- | The set of vertices that are referred to by the edges of an adjacency -- map. Note: this function is for internal use only. referredToVertexSet :: Ord a => Map a (Set a) -> Set a instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a) instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a) -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the AdjacencyMap data type and associated -- functions. See Algebra.Graph.AdjacencyMap.Algorithm for -- implementations of basic graph algorithms. AdjacencyMap is an -- instance of the Graph type class, which can be used for -- polymorphic graph construction and manipulation. -- Algebra.Graph.AdjacencyIntMap defines adjacency maps -- specialised to graphs with Int vertices. module Algebra.Graph.AdjacencyMap -- | The AdjacencyMap data type represents a graph by a map of -- vertices to their adjacency sets. We define a Num 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 Num instance does not satisfy several -- "customary laws" of Num, which dictate that fromInteger -- 0 and fromInteger 1 should act as additive -- and multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show instance is defined using basic graph construction -- primitives: -- --
-- show (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 Eq instance satisfies all axioms of algebraic graphs: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- empty <= x -- x <= x + y -- x + y <= x * y --data AdjacencyMap a -- | The adjacency map of a graph: each vertex is associated with a -- set of its direct successors. Complexity: O(1) time and memory. -- --
-- adjacencyMap empty == Map.empty -- adjacencyMap (vertex x) == Map.singleton x Set.empty -- adjacencyMap (edge 1 1) == Map.singleton 1 (Set.singleton 1) -- adjacencyMap (edge 1 2) == Map.fromList [(1,Set.singleton 2), (2,Set.empty)] --adjacencyMap :: AdjacencyMap a -> Map a (Set a) -- | Construct the empty graph. Complexity: O(1) time and -- memory. -- --
-- isEmpty empty == True -- hasVertex x empty == False -- vertexCount empty == 0 -- edgeCount empty == 0 --empty :: AdjacencyMap a -- | Construct the graph comprising a single isolated vertex. -- Complexity: O(1) time and memory. -- --
-- isEmpty (vertex x) == False -- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 --vertex :: a -> AdjacencyMap a -- | Construct the graph comprising a single edge. Complexity: -- O(1) time, memory. -- --
-- edge x y == connect (vertex x) (vertex y) -- hasEdge x y (edge x y) == True -- edgeCount (edge x y) == 1 -- vertexCount (edge 1 1) == 1 -- vertexCount (edge 1 2) == 2 --edge :: Ord a => a -> a -> AdjacencyMap a -- | Overlay 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. -- --
-- isEmpty (overlay x y) == isEmpty x && isEmpty y -- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 --overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a -- | Connect two graphs. This is an associative operation with the -- identity empty, which distributes over overlay and obeys -- the decomposition axiom. Complexity: O((n + m) * log(n)) time -- and O(n + m) memory. Note that the number of edges in the -- resulting graph is quadratic with respect to the number of vertices of -- the arguments: m = O(m1 + m2 + n1 * n2). -- --
-- isEmpty (connect x y) == isEmpty x && isEmpty y -- hasVertex z (connect x y) == hasVertex z x || hasVertex z y -- vertexCount (connect x y) >= vertexCount x -- vertexCount (connect x y) <= vertexCount x + vertexCount y -- edgeCount (connect x y) >= edgeCount x -- edgeCount (connect x y) >= edgeCount y -- edgeCount (connect x y) >= vertexCount x * vertexCount y -- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- vertexCount (connect 1 2) == 2 -- edgeCount (connect 1 2) == 1 --connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a -- | Construct 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 [] == empty -- vertices [x] == vertex x -- hasVertex x . vertices == elem x -- vertexCount . vertices == length . nub -- vertexSet . vertices == Set.fromList --vertices :: Ord a => [a] -> AdjacencyMap a -- | Construct the graph from a list of edges. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- edges [] == empty -- edges [(x,y)] == edge x y -- edgeCount . edges == length . nub -- edgeList . edges == nub . sort --edges :: Ord a => [(a, a)] -> AdjacencyMap a -- | Overlay a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- overlays [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty -- isEmpty . overlays == all isEmpty --overlays :: Ord a => [AdjacencyMap a] -> AdjacencyMap a -- | Connect a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- connects [] == empty -- connects [x] == x -- connects [x,y] == connect x y -- connects == foldr connect empty -- isEmpty . connects == all isEmpty --connects :: Ord a => [AdjacencyMap a] -> AdjacencyMap a -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O((n + m) * log(n)) time. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path xs) (circuit xs) == True -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool -- | Check if a graph is empty. Complexity: O(1) time. -- --
-- isEmpty empty == True -- isEmpty (overlay empty empty) == True -- isEmpty (vertex x) == False -- isEmpty (removeVertex x $ vertex x) == True -- isEmpty (removeEdge x y $ edge x y) == False --isEmpty :: AdjacencyMap a -> Bool -- | Check if a graph contains a given vertex. Complexity: O(log(n)) -- time. -- --
-- hasVertex x empty == False -- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False -- hasVertex x . removeVertex x == const False --hasVertex :: Ord a => a -> AdjacencyMap a -> Bool -- | Check if a graph contains a given edge. Complexity: O(log(n)) -- time. -- --
-- hasEdge x y empty == False -- hasEdge x y (vertex z) == False -- hasEdge x y (edge x y) == True -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == elem (x,y) . edgeList --hasEdge :: Ord a => a -> a -> AdjacencyMap a -> Bool -- | The number of vertices in a graph. Complexity: O(1) time. -- --
-- vertexCount empty == 0 -- vertexCount (vertex x) == 1 -- vertexCount == length . vertexList -- vertexCount x < vertexCount y ==> x < y --vertexCount :: AdjacencyMap a -> Int -- | The number of edges in a graph. Complexity: O(n) time. -- --
-- edgeCount empty == 0 -- edgeCount (vertex x) == 0 -- edgeCount (edge x y) == 1 -- edgeCount == length . edgeList --edgeCount :: AdjacencyMap a -> Int -- | The sorted list of vertices of a given graph. Complexity: O(n) -- time and memory. -- --
-- vertexList empty == [] -- vertexList (vertex x) == [x] -- vertexList . vertices == nub . sort --vertexList :: AdjacencyMap a -> [a] -- | The sorted list of edges of a graph. Complexity: O(n + m) time -- and O(m) memory. -- --
-- edgeList empty == [] -- edgeList (vertex x) == [] -- edgeList (edge x y) == [(x,y)] -- edgeList (star 2 [3,1]) == [(2,1), (2,3)] -- edgeList . edges == nub . sort -- edgeList . transpose == sort . map swap . edgeList --edgeList :: AdjacencyMap a -> [(a, a)] -- | The sorted adjacency list of a graph. Complexity: O(n + -- m) time and O(m) memory. -- --
-- adjacencyList empty == [] -- adjacencyList (vertex x) == [(x, [])] -- adjacencyList (edge 1 2) == [(1, [2]), (2, [])] -- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] -- stars . adjacencyList == id --adjacencyList :: AdjacencyMap a -> [(a, [a])] -- | The set of vertices of a given graph. Complexity: O(n) time and -- memory. -- --
-- vertexSet empty == Set.empty -- vertexSet . vertex == Set.singleton -- vertexSet . vertices == Set.fromList --vertexSet :: AdjacencyMap a -> Set a -- | The set of edges of a given graph. Complexity: O((n + m) * -- log(m)) time and O(m) memory. -- --
-- edgeSet empty == Set.empty -- edgeSet (vertex x) == Set.empty -- edgeSet (edge x y) == Set.singleton (x,y) -- edgeSet . edges == Set.fromList --edgeSet :: Eq a => AdjacencyMap a -> Set (a, a) -- | The preset of an element x is the set of its direct -- predecessors. Complexity: O(n * log(n)) time and -- O(n) memory. -- --
-- preSet x empty == Set.empty -- preSet x (vertex x) == Set.empty -- preSet 1 (edge 1 2) == Set.empty -- preSet y (edge x y) == Set.fromList [x] --preSet :: Ord a => a -> AdjacencyMap a -> Set a -- | The postset of a vertex is the set of its direct -- successors. Complexity: O(log(n)) time and O(1) -- memory. -- --
-- postSet x empty == Set.empty -- postSet x (vertex x) == Set.empty -- postSet x (edge x y) == Set.fromList [y] -- postSet 2 (edge 1 2) == Set.empty --postSet :: Ord a => a -> AdjacencyMap a -> Set a -- | The path on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- path [] == empty -- path [x] == vertex x -- path [x,y] == edge x y -- path . reverse == transpose . path --path :: Ord a => [a] -> AdjacencyMap a -- | The circuit on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- circuit [] == empty -- circuit [x] == edge x x -- circuit [x,y] == edges [(x,y), (y,x)] -- circuit . reverse == transpose . circuit --circuit :: Ord a => [a] -> AdjacencyMap a -- | The clique on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- clique [] == empty -- clique [x] == vertex x -- clique [x,y] == edge x y -- clique [x,y,z] == edges [(x,y), (x,z), (y,z)] -- clique (xs ++ ys) == connect (clique xs) (clique ys) -- clique . reverse == transpose . clique --clique :: Ord a => [a] -> AdjacencyMap a -- | The biclique on two lists of vertices. Complexity: O(n * -- log(n) + m) time and O(n + m) memory. -- --
-- biclique [] [] == empty -- biclique [x] [] == vertex x -- biclique [] [y] == vertex y -- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique xs ys == connect (vertices xs) (vertices ys) --biclique :: Ord a => [a] -> [a] -> AdjacencyMap a -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges [(x,y), (x,z)] -- star x ys == connect (vertex x) (vertices ys) --star :: Ord a => a -> [a] -> AdjacencyMap a -- | The stars formed by overlaying a list of stars. An -- inverse of adjacencyList. Complexity: O(L * log(n)) -- time, memory and size, where L is the total size of the input. -- --
-- stars [] == empty -- stars [(x, [])] == vertex x -- stars [(x, [y])] == edge x y -- stars [(x, ys)] == star x ys -- stars == overlays . map (uncurry star) -- stars . adjacencyList == id -- overlay (stars xs) (stars ys) == stars (xs ++ ys) --stars :: Ord a => [(a, [a])] -> AdjacencyMap a -- | Construct a graph from a list of adjacency sets; a variation of -- stars. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- fromAdjacencySets [] == empty -- fromAdjacencySets [(x, Set.empty)] == vertex x -- fromAdjacencySets [(x, Set.singleton y)] == edge x y -- fromAdjacencySets . map (fmap Set.fromList) == stars -- overlay (fromAdjacencySets xs) (fromAdjacencySets ys) == fromAdjacencySets (xs ++ ys) --fromAdjacencySets :: Ord a => [(a, Set a)] -> AdjacencyMap a -- | The tree graph constructed from a given Tree data -- structure. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- tree (Node x []) == vertex x -- tree (Node x [Node y [Node z []]]) == path [x,y,z] -- tree (Node x [Node y [], Node z []]) == star x [y,z] -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges [(1,2), (1,3), (3,4), (3,5)] --tree :: Ord a => Tree a -> AdjacencyMap a -- | The forest graph constructed from a given Forest data -- structure. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- forest [] == empty -- forest [x] == tree x -- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == edges [(1,2), (1,3), (4,5)] -- forest == overlays . map tree --forest :: Ord a => Forest a -> AdjacencyMap a -- | Remove a vertex from a given graph. Complexity: O(n*log(n)) -- time. -- --
-- removeVertex x (vertex x) == empty -- removeVertex 1 (vertex 2) == vertex 2 -- removeVertex x (edge x x) == empty -- removeVertex 1 (edge 1 2) == vertex 2 -- removeVertex x . removeVertex x == removeVertex x --removeVertex :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a -- | Remove an edge from a given graph. Complexity: O(log(n)) time. -- --
-- removeEdge x y (edge x y) == vertices [x,y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . removeVertex x == removeVertex x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 -- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 --removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a -- | The function replaceVertex 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. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == mergeVertices (== x) y --replaceVertex :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a -- | Merge 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 (const False) x == id -- mergeVertices (== x) y == replaceVertex x y -- mergeVertices even 1 (0 * 2) == 1 * 1 -- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 --mergeVertices :: Ord a => (a -> Bool) -> a -> AdjacencyMap a -> AdjacencyMap a -- | Transpose a given graph. Complexity: O(m * log(n)) time, O(n -- + m) memory. -- --
-- transpose empty == empty -- transpose (vertex x) == vertex x -- transpose (edge x y) == edge y x -- transpose . transpose == id -- edgeList . transpose == sort . map swap . edgeList --transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Transform a graph by applying a function to each of its vertices. This -- is similar to Functor's fmap but can be used with -- non-fully-parametric AdjacencyMap. Complexity: O((n + m) * -- log(n)) time. -- --
-- gmap f empty == empty -- gmap f (vertex x) == vertex (f x) -- gmap f (edge x y) == edge (f x) (f y) -- gmap id == id -- gmap f . gmap g == gmap (f . g) --gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap b -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(m) time, assuming that the predicate takes O(1) to be -- evaluated. -- --
-- induce (const True ) x == x -- induce (const False) x == empty -- induce (/= x) == removeVertex x -- induce p . induce q == induce (\x -> p x && q x) -- isSubgraphOf (induce p x) x == True --induce :: (a -> Bool) -> AdjacencyMap a -> AdjacencyMap a -- | Left-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 -- z in the second graph. There are no isolated vertices in the -- result. This operation is associative, has empty and -- single-vertex graphs as annihilating zeroes, and -- distributes over overlay. Complexity: O(n * m * log(n)) -- time and O(n + m) memory. -- --
-- compose empty x == empty -- compose x empty == empty -- compose (vertex x) y == empty -- compose x (vertex y) == empty -- compose x (compose y z) == compose (compose x y) z -- compose x (overlay y z) == overlay (compose x y) (compose x z) -- compose (overlay x y) z == overlay (compose x z) (compose y z) -- compose (edge x y) (edge y z) == edge x z -- compose (path [1..5]) (path [1..5]) == edges [(1,3), (2,4), (3,5)] -- compose (circuit [1..5]) (circuit [1..5]) == circuit [1,3,5,2,4] --compose :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a -- | Compute the reflexive and transitive closure of a graph. -- Complexity: O(n * m * log(n)^2) time. -- --
-- closure empty == empty -- closure (vertex x) == edge x x -- closure (edge x x) == edge x x -- closure (edge x y) == edges [(x,x), (x,y), (y,y)] -- closure (path $ nub xs) == reflexiveClosure (clique $ nub xs) -- closure == reflexiveClosure . transitiveClosure -- closure == transitiveClosure . reflexiveClosure -- closure . closure == closure -- postSet x (closure y) == Set.fromList (reachable x y) --closure :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Compute the reflexive closure of a graph by adding a self-loop -- to every vertex. Complexity: O(n * log(n)) time. -- --
-- reflexiveClosure empty == empty -- reflexiveClosure (vertex x) == edge x x -- reflexiveClosure (edge x x) == edge x x -- reflexiveClosure (edge x y) == edges [(x,x), (x,y), (y,y)] -- reflexiveClosure . reflexiveClosure == reflexiveClosure --reflexiveClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Compute the symmetric closure of a graph by overlaying it with -- its own transpose. Complexity: O((n + m) * log(n)) time. -- --
-- symmetricClosure empty == empty -- symmetricClosure (vertex x) == vertex x -- symmetricClosure (edge x y) == edges [(x,y), (y,x)] -- symmetricClosure x == overlay x (transpose x) -- symmetricClosure . symmetricClosure == symmetricClosure --symmetricClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Compute the transitive closure of a graph. Complexity: O(n * -- m * log(n)^2) time. -- --
-- transitiveClosure empty == empty -- transitiveClosure (vertex x) == vertex x -- transitiveClosure (edge x y) == edge x y -- transitiveClosure (path $ nub xs) == clique (nub xs) -- transitiveClosure . transitiveClosure == transitiveClosure --transitiveClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines various internal utilities and data structures -- used throughout the library, such as lists with fast concatenation. -- The API is unstable and unsafe, and is exposed only for documentation. module Algebra.Graph.Internal -- | An abstract list data type with O(1) time concatenation (the -- current implementation uses difference lists). Here a is the -- type of list elements. List a is a Monoid: -- mempty corresponds to the empty list and two lists can be -- concatenated with mappend (or operator <>). -- Singleton lists can be constructed using the function pure from -- the Applicative instance. List a is also an -- instance of IsList, therefore you can use list literals, e.g. -- [1,4] :: List Int is the same as -- pure 1 <> pure 4; note -- that this requires the OverloadedLists GHC extension. To -- extract plain Haskell lists you can use the toList function -- from the Foldable instance. newtype List a List :: Endo [a] -> List a -- | The focus of a graph expression is a flattened represenentation -- of the subgraph under focus, its context, as well as the list of all -- encountered vertices. See removeEdge for a use-case example. data Focus a -- | All vertices (leaves) of the graph expression. Focus :: Bool -> List a -> List a -> List a -> Focus a -- | True if focus on the specified subgraph is obtained. [ok] :: Focus a -> Bool -- | Inputs into the focused subgraph. [is] :: Focus a -> List a -- | Outputs out of the focused subgraph. [os] :: Focus a -> List a [vs] :: Focus a -> List a -- | Focus on the empty graph. emptyFocus :: Focus a -- | Focus on the graph with a single vertex, given a predicate indicating -- whether the vertex is of interest. vertexFocus :: (a -> Bool) -> a -> Focus a -- | Overlay two foci. overlayFoci :: Focus a -> Focus a -> Focus a -- | Connect two foci. connectFoci :: Focus a -> Focus a -> Focus a -- | An auxiliary data type for hasEdge: when searching for an -- edge, we can hit its Tail, i.e. the source vertex, the whole -- Edge, or Miss it entirely. data Hit Miss :: Hit Tail :: Hit Edge :: Hit -- | A safe version of foldr1. foldr1Safe :: (a -> a -> a) -> [a] -> Maybe a -- | Tragetting map directly -- -- Auxiliary function that try to apply a function to a base case and a -- Maybe value and return Just the result or Just -- the base case. maybeF :: (a -> b -> a) -> a -> Maybe b -> Maybe a -- | Compute the Cartesian product of two sets. setProduct :: Set a -> Set b -> Set (a, b) -- | Compute the Cartesian product of two sets, applying a function to each -- resulting pair. setProductWith :: Ord c => (a -> b -> c) -> Set a -> Set b -> Set c instance GHC.Classes.Ord Algebra.Graph.Internal.Hit instance GHC.Classes.Eq Algebra.Graph.Internal.Hit instance GHC.Base.Semigroup (Algebra.Graph.Internal.List a) instance GHC.Base.Monoid (Algebra.Graph.Internal.List a) instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Internal.List a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Internal.List a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Internal.List a) instance GHC.Exts.IsList (Algebra.Graph.Internal.List a) instance Data.Foldable.Foldable Algebra.Graph.Internal.List instance GHC.Base.Functor Algebra.Graph.Internal.List instance GHC.Base.Applicative Algebra.Graph.Internal.List instance GHC.Base.Monad Algebra.Graph.Internal.List -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the core data type Graph and associated -- algorithms. For graphs that are known to be non-empty at -- compile time, see Algebra.Graph.NonEmpty. Graph is an -- instance of type classes defined in modules Algebra.Graph.Class -- and Algebra.Graph.HigherKinded.Class, which can be used for -- polymorphic graph construction and manipulation. module Algebra.Graph -- | The Graph data type is a deep embedding of the core graph -- construction primitives empty, vertex, overlay -- and connect. We define a Num 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 Num instance does not satisfy several -- "customary laws" of Num, which dictate that fromInteger -- 0 and fromInteger 1 should act as additive -- and multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Eq instance is currently implemented using the -- AdjacencyMap as the canonical graph representation and -- satisfies all axioms of algebraic graphs: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
-- n == vertexCount g -- m == edgeCount g -- s == size g ---- -- Note that size counts all leaves of the expression: -- --
-- vertexCount empty == 0 -- size empty == 1 -- vertexCount (vertex x) == 1 -- size (vertex x) == 1 -- vertexCount (empty + empty) == 0 -- size (empty + empty) == 2 ---- -- Converting a Graph to the corresponding AdjacencyMap -- 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: -- --
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- empty <= x -- x <= x + y -- x + y <= x * y --data Graph a Empty :: Graph a Vertex :: a -> Graph a Overlay :: Graph a -> Graph a -> Graph a Connect :: Graph a -> Graph a -> Graph a -- | Construct the empty graph. An alias for the constructor -- Empty. Complexity: O(1) time, memory and size. -- --
-- isEmpty empty == True -- hasVertex x empty == False -- vertexCount empty == 0 -- edgeCount empty == 0 -- size empty == 1 --empty :: Graph a -- | Construct the graph comprising a single isolated vertex. An -- alias for the constructor Vertex. Complexity: O(1) time, -- memory and size. -- --
-- isEmpty (vertex x) == False -- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 -- size (vertex x) == 1 --vertex :: a -> Graph a -- | Construct the graph comprising a single edge. Complexity: -- O(1) time, memory and size. -- --
-- edge x y == connect (vertex x) (vertex y) -- hasEdge x y (edge x y) == True -- edgeCount (edge x y) == 1 -- vertexCount (edge 1 1) == 1 -- vertexCount (edge 1 2) == 2 --edge :: a -> a -> Graph a -- | Overlay two graphs. An alias for the constructor -- Overlay. This is a commutative, associative and idempotent -- operation with the identity empty. Complexity: O(1) time -- and memory, O(s1 + s2) size. -- --
-- isEmpty (overlay x y) == isEmpty x && isEmpty y -- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- size (overlay x y) == size x + size y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 --overlay :: Graph a -> Graph a -> Graph a -- | Connect two graphs. An alias for the constructor -- Connect. This is an associative operation with the identity -- empty, which distributes over overlay and obeys the -- decomposition axiom. Complexity: O(1) time and memory, O(s1 -- + s2) size. Note that the number of edges in the resulting graph -- is quadratic with respect to the number of vertices of the arguments: -- m = O(m1 + m2 + n1 * n2). -- --
-- isEmpty (connect x y) == isEmpty x && isEmpty y -- hasVertex z (connect x y) == hasVertex z x || hasVertex z y -- vertexCount (connect x y) >= vertexCount x -- vertexCount (connect x y) <= vertexCount x + vertexCount y -- edgeCount (connect x y) >= edgeCount x -- edgeCount (connect x y) >= edgeCount y -- edgeCount (connect x y) >= vertexCount x * vertexCount y -- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- size (connect x y) == size x + size y -- vertexCount (connect 1 2) == 2 -- edgeCount (connect 1 2) == 1 --connect :: Graph a -> Graph a -> Graph a -- | Construct 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 [] == empty -- vertices [x] == vertex x -- hasVertex x . vertices == elem x -- vertexCount . vertices == length . nub -- vertexSet . vertices == Set.fromList --vertices :: [a] -> Graph a -- | Construct the graph from a list of edges. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- edges [] == empty -- edges [(x,y)] == edge x y -- edgeCount . edges == length . nub --edges :: [(a, a)] -> Graph a -- | Overlay a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- overlays [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty -- isEmpty . overlays == all isEmpty --overlays :: [Graph a] -> Graph a -- | Connect a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- connects [] == empty -- connects [x] == x -- connects [x,y] == connect x y -- connects == foldr connect empty -- isEmpty . connects == all isEmpty --connects :: [Graph a] -> Graph a -- | Generalised Graph folding: recursively collapse a Graph -- by applying the provided functions to the leaves and internal nodes of -- the expression. The order of arguments is: empty, vertex, overlay and -- connect. Complexity: O(s) applications of given functions. As -- an example, the complexity of size is O(s), since all -- functions have cost O(1). -- --
-- foldg empty vertex overlay connect == id -- foldg empty vertex overlay (flip connect) == transpose -- foldg 1 (const 1) (+) (+) == size -- foldg True (const False) (&&) (&&) == isEmpty -- foldg False (== x) (||) (||) == hasVertex x --foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O(s + m * log(m)) time. Note that the number of -- edges m of a graph can be quadratic with respect to the -- expression size s. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path xs) (circuit xs) == True -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool -- | Structural equality on graph expressions. Complexity: O(s) -- time. -- --
-- x === x == True -- x === x + empty == False -- x + y === x + y == True -- 1 + 2 === 2 + 1 == False -- x + y === x * y == False --(===) :: Eq a => Graph a -> Graph a -> Bool infix 4 === -- | Check if a graph is empty. A convenient alias for null. -- Complexity: O(s) time. -- --
-- isEmpty empty == True -- isEmpty (overlay empty empty) == True -- isEmpty (vertex x) == False -- isEmpty (removeVertex x $ vertex x) == True -- isEmpty (removeEdge x y $ edge x y) == False --isEmpty :: Graph a -> Bool -- | The size of a graph, i.e. the number of leaves of the -- expression including empty leaves. Complexity: O(s) -- time. -- --
-- size empty == 1 -- size (vertex x) == 1 -- size (overlay x y) == size x + size y -- size (connect x y) == size x + size y -- size x >= 1 -- size x >= vertexCount x --size :: Graph a -> Int -- | Check if a graph contains a given vertex. Complexity: O(s) -- time. -- --
-- hasVertex x empty == False -- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False -- hasVertex x . removeVertex x == const False --hasVertex :: Eq a => a -> Graph a -> Bool -- | Check if a graph contains a given edge. Complexity: O(s) time. -- --
-- hasEdge x y empty == False -- hasEdge x y (vertex z) == False -- hasEdge x y (edge x y) == True -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == elem (x,y) . edgeList --hasEdge :: Eq a => a -> a -> Graph a -> Bool -- | The number of vertices in a graph. Complexity: O(s * log(n)) -- time. -- --
-- vertexCount empty == 0 -- vertexCount (vertex x) == 1 -- vertexCount == length . vertexList -- vertexCount x < vertexCount y ==> x < y --vertexCount :: Ord a => Graph a -> Int -- | The number of edges in a graph. Complexity: O(s + m * log(m)) -- time. Note that the number of edges m of a graph can be -- quadratic with respect to the expression size s. -- --
-- edgeCount empty == 0 -- edgeCount (vertex x) == 0 -- edgeCount (edge x y) == 1 -- edgeCount == length . edgeList --edgeCount :: Ord a => Graph a -> Int -- | The sorted list of vertices of a given graph. Complexity: O(s * -- log(n)) time and O(n) memory. -- --
-- vertexList empty == [] -- vertexList (vertex x) == [x] -- vertexList . vertices == nub . sort --vertexList :: Ord a => Graph a -> [a] -- | The sorted list of edges of a graph. Complexity: O(s + m * -- log(m)) time and O(m) memory. Note that the number of edges -- m of a graph can be quadratic with respect to the expression -- size s. -- --
-- edgeList empty == [] -- edgeList (vertex x) == [] -- edgeList (edge x y) == [(x,y)] -- edgeList (star 2 [3,1]) == [(2,1), (2,3)] -- edgeList . edges == nub . sort -- edgeList . transpose == sort . map swap . edgeList --edgeList :: Ord a => Graph a -> [(a, a)] -- | The set of vertices of a given graph. Complexity: O(s * log(n)) -- time and O(n) memory. -- --
-- vertexSet empty == Set.empty -- vertexSet . vertex == Set.singleton -- vertexSet . vertices == Set.fromList --vertexSet :: Ord a => Graph a -> Set a -- | The set of edges of a given graph. Complexity: O(s * log(m)) -- time and O(m) memory. -- --
-- edgeSet empty == Set.empty -- edgeSet (vertex x) == Set.empty -- edgeSet (edge x y) == Set.singleton (x,y) -- edgeSet . edges == Set.fromList --edgeSet :: Ord a => Graph a -> Set (a, a) -- | The sorted adjacency list of a graph. Complexity: O(n + -- m) time and O(m) memory. -- --
-- adjacencyList empty == [] -- adjacencyList (vertex x) == [(x, [])] -- adjacencyList (edge 1 2) == [(1, [2]), (2, [])] -- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] -- stars . adjacencyList == id --adjacencyList :: Ord a => Graph a -> [(a, [a])] -- | The path on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- path [] == empty -- path [x] == vertex x -- path [x,y] == edge x y -- path . reverse == transpose . path --path :: [a] -> Graph a -- | The circuit on a list of vertices. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- circuit [] == empty -- circuit [x] == edge x x -- circuit [x,y] == edges [(x,y), (y,x)] -- circuit . reverse == transpose . circuit --circuit :: [a] -> Graph a -- | The clique on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- clique [] == empty -- clique [x] == vertex x -- clique [x,y] == edge x y -- clique [x,y,z] == edges [(x,y), (x,z), (y,z)] -- clique (xs ++ ys) == connect (clique xs) (clique ys) -- clique . reverse == transpose . clique --clique :: [a] -> Graph a -- | The biclique on two lists of vertices. Complexity: O(L1 + -- L2) time, memory and size, where L1 and L2 are the -- lengths of the given lists. -- --
-- biclique [] [] == empty -- biclique [x] [] == vertex x -- biclique [] [y] == vertex y -- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique xs ys == connect (vertices xs) (vertices ys) --biclique :: [a] -> [a] -> Graph a -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges [(x,y), (x,z)] -- star x ys == connect (vertex x) (vertices ys) --star :: a -> [a] -> Graph a -- | The stars formed by overlaying a list of stars. An -- inverse of adjacencyList. Complexity: O(L) time, memory -- and size, where L is the total size of the input. -- --
-- stars [] == empty -- stars [(x, [])] == vertex x -- stars [(x, [y])] == edge x y -- stars [(x, ys)] == star x ys -- stars == overlays . map (uncurry star) -- stars . adjacencyList == id -- overlay (stars xs) (stars ys) == stars (xs ++ ys) --stars :: [(a, [a])] -> Graph a -- | The tree graph constructed from a given Tree data -- structure. Complexity: O(T) time, memory and size, where -- T is the size of the given tree (i.e. the number of vertices in -- the tree). -- --
-- tree (Node x []) == vertex x -- tree (Node x [Node y [Node z []]]) == path [x,y,z] -- tree (Node x [Node y [], Node z []]) == star x [y,z] -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges [(1,2), (1,3), (3,4), (3,5)] --tree :: Tree a -> Graph a -- | The forest graph constructed from a given Forest data -- structure. Complexity: O(F) time, memory and size, where -- F is the size of the given forest (i.e. the number of vertices -- in the forest). -- --
-- forest [] == empty -- forest [x] == tree x -- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == edges [(1,2), (1,3), (4,5)] -- forest == overlays . map tree --forest :: Forest a -> Graph a -- | Construct a mesh graph from two lists of vertices. Complexity: -- O(L1 * L2) time, memory and size, where L1 and L2 -- are the lengths of the given lists. -- --
-- mesh xs [] == empty -- mesh [] ys == empty -- mesh [x] [y] == vertex (x, y) -- mesh xs ys == box (path xs) (path ys) -- mesh [1..3] "ab" == edges [ ((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')) ] --mesh :: [a] -> [b] -> Graph (a, b) -- | Construct a torus graph from two lists of vertices. Complexity: -- O(L1 * L2) time, memory and size, where L1 and L2 -- are the lengths of the given lists. -- --
-- torus xs [] == empty -- torus [] ys == empty -- torus [x] [y] == edge (x,y) (x,y) -- torus xs ys == box (circuit xs) (circuit ys) -- torus [1,2] "ab" == edges [ ((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')) ] --torus :: [a] -> [b] -> Graph (a, b) -- | Construct a De Bruijn graph 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 == edge [] []
-- n > 0 ==> deBruijn n [] == empty
-- deBruijn 1 [0,1] == edges [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ]
-- deBruijn 2 "0" == edge "00" "00"
-- deBruijn 2 "01" == edges [ ("00","00"), ("00","01"), ("01","10"), ("01","11")
-- , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]
-- transpose (deBruijn n xs) == fmap reverse $ deBruijn n xs
-- vertexCount (deBruijn n xs) == (length $ nub xs)^n
-- n > 0 ==> edgeCount (deBruijn n xs) == (length $ nub xs)^(n + 1)
--
deBruijn :: Int -> [a] -> Graph [a]
-- | Remove a vertex from a given graph. Complexity: O(s) time,
-- memory and size.
--
-- -- removeVertex x (vertex x) == empty -- removeVertex 1 (vertex 2) == vertex 2 -- removeVertex x (edge x x) == empty -- removeVertex 1 (edge 1 2) == vertex 2 -- removeVertex x . removeVertex x == removeVertex x --removeVertex :: Eq a => a -> Graph a -> Graph a -- | Remove an edge from a given graph. Complexity: O(s) time, -- memory and size. -- --
-- removeEdge x y (edge x y) == vertices [x,y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . removeVertex x == removeVertex x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 -- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 -- size (removeEdge x y z) <= 3 * size z --removeEdge :: Eq a => a -> a -> Graph a -> Graph a -- | The function replaceVertex x y replaces vertex -- x with vertex y in a given Graph. If -- y already exists, x and y will be merged. -- Complexity: O(s) time, memory and size. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == mergeVertices (== x) y --replaceVertex :: Eq a => a -> a -> Graph a -> Graph a -- | Merge 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 (const False) x == id -- mergeVertices (== x) y == replaceVertex x y -- mergeVertices even 1 (0 * 2) == 1 * 1 -- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 --mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a -- | Split a vertex into a list of vertices with the same connectivity. -- Complexity: O(s + k * L) time, memory and size, where k -- is the number of occurrences of the vertex in the expression and -- L is the length of the given list. -- --
-- splitVertex x [] == removeVertex x -- splitVertex x [x] == id -- splitVertex x [y] == replaceVertex x y -- splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3) --splitVertex :: Eq a => a -> [a] -> Graph a -> Graph a -- | Transpose a given graph. Complexity: O(s) time, memory and -- size. -- --
-- transpose empty == empty -- transpose (vertex x) == vertex x -- transpose (edge x y) == edge y x -- transpose . transpose == id -- transpose (box x y) == box (transpose x) (transpose y) -- edgeList . transpose == sort . map swap . edgeList --transpose :: Graph a -> Graph a -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(s) time, memory and size, assuming that the predicate takes -- O(1) to be evaluated. -- --
-- induce (const True ) x == x -- induce (const False) x == empty -- induce (/= x) == removeVertex x -- induce p . induce q == induce (\x -> p x && q x) -- isSubgraphOf (induce p x) x == True --induce :: (a -> Bool) -> Graph a -> Graph a -- | Simplify 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) graph -- comparisons. It is guaranteed that the size of the result does not -- exceed the size of the given expression. -- --
-- simplify == id -- size (simplify x) <= size x -- simplify empty === empty -- simplify 1 === 1 -- simplify (1 + 1) === 1 -- simplify (1 + 2 + 1) === 1 + 2 -- simplify (1 * 1 * 1) === 1 * 1 --simplify :: Ord a => Graph a -> Graph a -- | Sparsify a graph by adding intermediate Left -- Int vertices between the original vertices (wrapping the -- latter in Right) 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. -- --
-- sort . reachable x == sort . rights . reachable (Right x) . sparsify -- vertexCount (sparsify x) <= vertexCount x + size x + 1 -- edgeCount (sparsify x) <= 3 * size x -- size (sparsify x) <= 3 * size x --sparsify :: Graph a -> Graph (Either Int a) -- | Left-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 -- z in the second graph. There are no isolated vertices in the -- result. This operation is associative, has empty and -- single-vertex graphs as annihilating zeroes, and -- distributes over overlay. Complexity: O(n * m * log(n)) -- time, O(n + m) memory, and O(m1 + m2) size, where -- n and m 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), but the -- algebraic representation requires only O(m1 + m2) operations to -- list them. -- --
-- compose empty x == empty -- compose x empty == empty -- compose (vertex x) y == empty -- compose x (vertex y) == empty -- compose x (compose y z) == compose (compose x y) z -- compose x (overlay y z) == overlay (compose x y) (compose x z) -- compose (overlay x y) z == overlay (compose x z) (compose y z) -- compose (edge x y) (edge y z) == edge x z -- compose (path [1..5]) (path [1..5]) == edges [(1,3), (2,4), (3,5)] -- compose (circuit [1..5]) (circuit [1..5]) == circuit [1,3,5,2,4] -- size (compose x y) <= edgeCount x + edgeCount y + 1 --compose :: Ord a => Graph a -> Graph a -> Graph a -- | Compute the Cartesian product of graphs. Complexity: O(s1 * -- s2) time, memory and size, where s1 and s2 are the -- sizes of the given graphs. -- --
-- box (path [0,1]) (path "ab") == edges [ ((0,'a'), (0,'b')) -- , ((0,'a'), (1,'a')) -- , ((0,'b'), (1,'b')) -- , ((1,'a'), (1,'b')) ] ---- -- Up to an isomorphism between the resulting vertex types, this -- operation is commutative, associative, -- distributes over overlay, has singleton graphs as -- identities and empty as the annihilating zero. -- Below ~~ stands for the equality up to an isomorphism, e.g. -- (x, ()) ~~ x. -- --
-- box x y ~~ box y x -- box x (box y z) ~~ box (box x y) z -- box x (overlay y z) == overlay (box x y) (box x z) -- box x (vertex ()) ~~ x -- box x empty ~~ empty -- transpose (box x y) == box (transpose x) (transpose y) -- vertexCount (box x y) == vertexCount x * vertexCount y -- edgeCount (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y --box :: Graph a -> Graph b -> Graph (a, b) -- | The Context of a subgraph comprises its inputs and -- outputs, 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 inputs and outputs; furthermore, there may -- be repetitions. data Context a Context :: [a] -> [a] -> Context a [inputs] :: Context a -> [a] [outputs] :: Context a -> [a] -- | Extract the Context of a subgraph specified by a given -- predicate. Returns Nothing if the specified subgraph is -- empty. -- --
-- context (const False) x == Nothing -- context (== 1) (edge 1 2) == Just (Context [ ] [2 ]) -- context (== 2) (edge 1 2) == Just (Context [1 ] [ ]) -- context (const True ) (edge 1 2) == Just (Context [1 ] [2 ]) -- context (== 4) (3 * 1 * 4 * 1 * 5) == Just (Context [3,1] [1,5]) --context :: (a -> Bool) -> Graph a -> Maybe (Context a) instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Context a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Context a) instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Graph a) instance GHC.Base.Functor Algebra.Graph.Graph instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Graph a) instance GHC.Num.Num a => GHC.Num.Num (Algebra.Graph.Graph a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Graph a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Graph a) instance GHC.Base.Applicative Algebra.Graph.Graph instance GHC.Base.Monad Algebra.Graph.Graph instance GHC.Base.Alternative Algebra.Graph.Graph instance GHC.Base.MonadPlus Algebra.Graph.Graph -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module provides basic data types and type classes for -- representing edge labels in edge-labelled graphs, e.g. see -- Algebra.Graph.Labelled. module Algebra.Graph.Label -- | A semiring extends a commutative Monoid with operation -- <.> that acts similarly to multiplication over the -- underlying (additive) monoid and has one as the identity. This -- module also provides two convenient aliases: zero for -- mempty, and <+> for <>, which makes -- the interface more uniform. -- -- Instances of this type class must satisfy the following semiring laws: -- --
x -- <+> (y <+> z) == (x <+> y) <+> z x <.> -- (y <.> z) == (x <.> y) <.> z
zero -- <+> x == x == x <+> zero one <.> x == x == x -- <.> one
x <+> y == y -- <+> x
x <.> zero == zero zero -- <.> x == zero
x <.> (y <+> z) == x <.> y -- <+> x <.> z (x <+> y) <.> z == x <.> z -- <+> y <.> z
-- star a = one <+> a <.> star a -- star a = one <+> star a <.> a --class Semiring a => StarSemiring a star :: StarSemiring a => a -> a -- | A dioid is an idempotent semiring, i.e. it satisfies the -- following idempotence law in addition to the Semiring -- laws: -- --
-- x <+> x == x --class Semiring a => Dioid a -- | A non-negative value that can be finite or infinite. -- Note: the current implementation of the Num instance raises an -- error on negative literals and on the negate method. data NonNegative a -- | A finite non-negative value or Nothing if the argument is -- negative. finite :: (Num a, Ord a) => a -> Maybe (NonNegative a) -- | A finite Word. finiteWord :: Word -> NonNegative Word -- | A non-negative finite value, created unsafely: the argument is -- not checked for being non-negative, so unsafeFinite (-1) -- compiles just fine. unsafeFinite :: a -> NonNegative a -- | The (non-negative) infinite value. infinite :: NonNegative a -- | Get a finite value or Nothing if the value is infinite. getFinite :: NonNegative a -> Maybe a -- | A distance is a non-negative value that can be finite or -- infinite. Distances form a Dioid as follows: -- --
-- zero = distance infinite -- one = 0 -- (<+>) = min -- (<.>) = (+) --data Distance a -- | A non-negative distance. distance :: NonNegative a -> Distance a -- | Get the value of a distance. getDistance :: Distance a -> NonNegative a -- | A capacity is a non-negative value that can be finite or -- infinite. Capacities form a Dioid as follows: -- --
-- zero = 0 -- one = capacity infinite -- (<+>) = max -- (<.>) = min --data Capacity a -- | A non-negative capacity. capacity :: NonNegative a -> Capacity a -- | Get the value of a capacity. getCapacity :: Capacity a -> NonNegative a -- | A count is a non-negative value that can be finite or -- infinite. Counts form a Semiring as follows: -- --
-- zero = 0 -- one = 1 -- (<+>) = (+) -- (<.>) = (*) --data Count a -- | A non-negative count. count :: NonNegative a -> Count a -- | Get the value of a count. getCount :: Count a -> NonNegative a -- | The power set over the underlying set of elements a. -- If a is a monoid, then the power set forms a Dioid as -- follows: -- --
-- zero = PowerSet Set.empty -- one = PowerSet $ Set.singleton mempty -- x <+> y = PowerSet $ Set.union (getPowerSet x) (getPowerSet y) -- x <.> y = PowerSet $ setProductWith mappend (getPowerSet x) (getPowerSet y) --newtype PowerSet a PowerSet :: Set a -> PowerSet a [getPowerSet] :: PowerSet a -> Set a -- | If a is a monoid, Minimum a forms the -- following Dioid: -- --
-- zero = pure mempty -- one = noMinimum -- (<+>) = liftA2 min -- (<.>) = liftA2 mappend ---- -- To create a singleton value of type Minimum a use the -- pure function. For example: -- --
-- getMinimum (pure "Hello, " <+> pure "World!") == Just "Hello, " -- getMinimum (pure "Hello, " <.> pure "World!") == Just "Hello, World!" --data Minimum a -- | Extract the minimum or Nothing if it does not exist. getMinimum :: Minimum a -> Maybe a -- | The value corresponding to the lack of minimum, e.g. the minimum of -- the empty set. noMinimum :: Minimum a -- | A path is a list of edges. type Path a = [(a, a)] -- | The type of free labels over the underlying set of symbols -- a. This data type is an instance of classes -- StarSemiring and Dioid. data Label a -- | Check if a Label is zero. isZero :: Label a -> Bool -- | A type synonym for regular expressions, built on top of free -- labels. type RegularExpression a = Label a -- | An optimum semiring obtained by combining a semiring o -- that defines an optimisation criterion, and a semiring -- a that describes the arguments of an optimisation -- problem. For example, by choosing o = Distance Int and -- and a = Minimum (Path 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 == y ---- -- In words, the operation <+> always simply selects one of -- its arguments. For example, the Capacity and Distance -- semirings are selective, whereas the the Count semiring is not. data Optimum o a Optimum :: o -> a -> Optimum o a [getOptimum] :: Optimum o a -> o [getArgument] :: Optimum o a -> a -- | The Optimum semiring specialised to /finding the -- lexicographically smallest shortest path/. type ShortestPath e a = Optimum (Distance e) (Minimum (Path a)) -- | The Optimum semiring specialised to finding all shortest -- paths. type AllShortestPaths e a = Optimum (Distance e) (PowerSet (Path a)) -- | The Optimum semiring specialised to counting all shortest -- paths. type CountShortestPaths e a = Optimum (Distance e) (Count Integer) -- | The Optimum semiring specialised to /finding the -- lexicographically smallest widest path/. type WidestPath e a = Optimum (Capacity e) (Minimum (Path a)) instance (GHC.Show.Show o, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Label.Optimum o a) instance (GHC.Classes.Ord o, GHC.Classes.Ord a) => GHC.Classes.Ord (Algebra.Graph.Label.Optimum o a) instance (GHC.Classes.Eq o, GHC.Classes.Eq a) => GHC.Classes.Eq (Algebra.Graph.Label.Optimum o a) instance GHC.Base.Functor Algebra.Graph.Label.Label instance GHC.Classes.Ord a => GHC.Base.Semigroup (Algebra.Graph.Label.PowerSet a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Label.PowerSet a) instance GHC.Classes.Ord a => GHC.Base.Monoid (Algebra.Graph.Label.PowerSet a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Label.PowerSet a) instance GHC.Base.Monad Algebra.Graph.Label.Minimum instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Label.Minimum a) instance GHC.Base.Functor Algebra.Graph.Label.Minimum instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Label.Minimum a) instance GHC.Base.Applicative Algebra.Graph.Label.Minimum instance GHC.Classes.Ord a => GHC.Base.Semigroup (Algebra.Graph.Label.Capacity a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Label.Capacity a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Label.Capacity a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Base.Monoid (Algebra.Graph.Label.Capacity a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Label.Capacity a) instance GHC.Num.Num a => GHC.Enum.Bounded (Algebra.Graph.Label.Capacity a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Base.Semigroup (Algebra.Graph.Label.Count a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Label.Count a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Label.Count a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Base.Monoid (Algebra.Graph.Label.Count a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Label.Count a) instance GHC.Num.Num a => GHC.Enum.Bounded (Algebra.Graph.Label.Count a) instance GHC.Classes.Ord a => GHC.Base.Semigroup (Algebra.Graph.Label.Distance a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Label.Distance a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Label.Distance a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Base.Monoid (Algebra.Graph.Label.Distance a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Label.Distance a) instance GHC.Num.Num a => GHC.Enum.Bounded (Algebra.Graph.Label.Distance a) instance GHC.Base.Monad Algebra.Graph.Label.NonNegative instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Label.NonNegative a) instance GHC.Base.Functor Algebra.Graph.Label.NonNegative instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Label.NonNegative a) instance GHC.Base.Applicative Algebra.Graph.Label.NonNegative instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Label.Extended a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Label.Extended a) instance GHC.Base.Functor Algebra.Graph.Label.Extended instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Label.Extended a) instance (GHC.Classes.Eq o, GHC.Base.Monoid a, GHC.Base.Monoid o) => GHC.Base.Semigroup (Algebra.Graph.Label.Optimum o a) instance (GHC.Classes.Eq o, GHC.Base.Monoid a, GHC.Base.Monoid o) => GHC.Base.Monoid (Algebra.Graph.Label.Optimum o a) instance (GHC.Classes.Eq o, Algebra.Graph.Label.Semiring a, Algebra.Graph.Label.Semiring o) => Algebra.Graph.Label.Semiring (Algebra.Graph.Label.Optimum o a) instance (GHC.Classes.Eq o, Algebra.Graph.Label.StarSemiring a, Algebra.Graph.Label.StarSemiring o) => Algebra.Graph.Label.StarSemiring (Algebra.Graph.Label.Optimum o a) instance (GHC.Classes.Eq o, Algebra.Graph.Label.Dioid a, Algebra.Graph.Label.Dioid o) => Algebra.Graph.Label.Dioid (Algebra.Graph.Label.Optimum o a) instance GHC.Exts.IsList (Algebra.Graph.Label.Label a) instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Label.Label a) instance GHC.Base.Semigroup (Algebra.Graph.Label.Label a) instance GHC.Base.Monoid (Algebra.Graph.Label.Label a) instance Algebra.Graph.Label.Semiring (Algebra.Graph.Label.Label a) instance Algebra.Graph.Label.StarSemiring (Algebra.Graph.Label.Label a) instance (GHC.Base.Monoid a, GHC.Classes.Ord a) => Algebra.Graph.Label.Semiring (Algebra.Graph.Label.PowerSet a) instance (GHC.Base.Monoid a, GHC.Classes.Ord a) => Algebra.Graph.Label.StarSemiring (Algebra.Graph.Label.PowerSet a) instance (GHC.Base.Monoid a, GHC.Classes.Ord a) => Algebra.Graph.Label.Dioid (Algebra.Graph.Label.PowerSet a) instance (GHC.Num.Num a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Label.Minimum a) instance GHC.Exts.IsList a => GHC.Exts.IsList (Algebra.Graph.Label.Minimum a) instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Label.Capacity a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.Semiring (Algebra.Graph.Label.Capacity a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.StarSemiring (Algebra.Graph.Label.Capacity a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.Dioid (Algebra.Graph.Label.Capacity a) instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Label.Count a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.Semiring (Algebra.Graph.Label.Count a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.StarSemiring (Algebra.Graph.Label.Count a) instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.Label.Distance a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.Semiring (Algebra.Graph.Label.Distance a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.StarSemiring (Algebra.Graph.Label.Distance a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => Algebra.Graph.Label.Dioid (Algebra.Graph.Label.Distance a) instance (GHC.Num.Num a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Label.NonNegative a) instance GHC.Num.Num a => GHC.Enum.Bounded (Algebra.Graph.Label.NonNegative a) instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Label.NonNegative a) instance GHC.Base.Applicative Algebra.Graph.Label.Extended instance GHC.Base.Monad Algebra.Graph.Label.Extended instance GHC.Num.Num a => GHC.Num.Num (Algebra.Graph.Label.Extended a) instance Algebra.Graph.Label.Dioid Data.Semigroup.Internal.Any instance Algebra.Graph.Label.StarSemiring Data.Semigroup.Internal.Any instance Algebra.Graph.Label.Semiring Data.Semigroup.Internal.Any -- | This module exposes the implementation of edge-labelled adjacency -- maps. The API is unstable and unsafe, and is exposed only for -- documentation. You should use the non-internal module -- Algebra.Graph.Labelled.AdjdacencyMap instead. module Algebra.Graph.Labelled.AdjacencyMap.Internal -- | Edge-labelled graphs, where the type variable e stands for -- edge labels. For example, AdjacencyMap Bool a -- is isomorphic to unlabelled graphs defined in the top-level module -- Algebra.Graph.AdjacencyMap, where False and -- True denote the lack of and the existence of an unlabelled -- edge, respectively. newtype AdjacencyMap e a AM :: Map a (Map a e) -> AdjacencyMap e a -- | The adjacency map of an edge-labelled graph: each vertex is -- associated with a map from its direct successors to the corresponding -- edge labels. [adjacencyMap] :: AdjacencyMap e a -> Map a (Map a e) -- | Check if the internal graph representation is consistent, i.e. that -- all edges refer to existing vertices, and there are no -- zero-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. consistent :: (Ord a, Eq e, Monoid e) => AdjacencyMap e a -> Bool instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData e) => Control.DeepSeq.NFData (Algebra.Graph.Labelled.AdjacencyMap.Internal.AdjacencyMap e a) instance (GHC.Classes.Eq a, GHC.Classes.Eq e) => GHC.Classes.Eq (Algebra.Graph.Labelled.AdjacencyMap.Internal.AdjacencyMap e a) instance (GHC.Classes.Ord a, GHC.Show.Show a, GHC.Classes.Ord e, GHC.Show.Show e) => GHC.Show.Show (Algebra.Graph.Labelled.AdjacencyMap.Internal.AdjacencyMap e a) instance (GHC.Classes.Ord e, GHC.Base.Monoid e, GHC.Classes.Ord a) => GHC.Classes.Ord (Algebra.Graph.Labelled.AdjacencyMap.Internal.AdjacencyMap e a) instance (GHC.Classes.Eq e, Algebra.Graph.Label.Dioid e, GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (Algebra.Graph.Labelled.AdjacencyMap.Internal.AdjacencyMap e a) -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the AdjacencyMap data type for -- edge-labelled graphs, as well as associated operations and algorithms. -- AdjacencyMap is an instance of the Graph type class, -- which can be used for polymorphic graph construction and manipulation. module Algebra.Graph.Labelled.AdjacencyMap -- | Edge-labelled graphs, where the type variable e stands for -- edge labels. For example, AdjacencyMap Bool a -- is isomorphic to unlabelled graphs defined in the top-level module -- Algebra.Graph.AdjacencyMap, where False and -- True denote the lack of and the existence of an unlabelled -- edge, respectively. data AdjacencyMap e a -- | The adjacency map of an edge-labelled graph: each vertex is -- associated with a map from its direct successors to the corresponding -- edge labels. adjacencyMap :: AdjacencyMap e a -> Map a (Map a e) -- | Construct the empty graph. Complexity: O(1) time and -- memory. -- --
-- isEmpty empty == True -- hasVertex x empty == False -- vertexCount empty == 0 -- edgeCount empty == 0 --empty :: AdjacencyMap e a -- | Construct the graph comprising a single isolated vertex. -- Complexity: O(1) time and memory. -- --
-- isEmpty (vertex x) == False -- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 --vertex :: a -> AdjacencyMap e a -- | Construct the graph comprising a single edge. Complexity: -- O(1) time, memory. -- --
-- edge e x y == connect e (vertex x) (vertex y) -- edge zero x y == vertices [x,y] -- hasEdge x y (edge e x y) == (e /= zero) -- edgeLabel x y (edge e x y) == e -- edgeCount (edge e x y) == if e == zero then 0 else 1 -- vertexCount (edge e 1 1) == 1 -- vertexCount (edge e 1 2) == 2 --edge :: (Eq e, Monoid e, Ord a) => e -> a -> a -> AdjacencyMap e a -- | The left-hand part of a convenient ternary-ish operator -- x-<e>-y for creating labelled edges. -- --
-- x -<e>- y == edge e x y --(-<) :: a -> e -> (a, e) infixl 5 -< -- | The right-hand part of a convenient ternary-ish operator -- x-<e>-y for creating labelled edges. -- --
-- x -<e>- y == edge e x y --(>-) :: (Eq e, Monoid e, Ord a) => (a, e) -> a -> AdjacencyMap e a infixl 5 >- -- | Overlay 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. -- --
-- isEmpty (overlay x y) == isEmpty x && isEmpty y -- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 ---- -- Note: overlay composes edges in parallel using the operator -- <+> with zero acting as the identity: -- --
-- edgeLabel x y $ overlay (edge e x y) (edge zero x y) == e -- edgeLabel x y $ overlay (edge e x y) (edge f x y) == e <+> f ---- -- Furthermore, when applied to transitive graphs, overlay -- composes edges in sequence using the operator <.> with -- one acting as the identity: -- --
-- edgeLabel x z $ transitiveClosure (overlay (edge e x y) (edge one y z)) == e -- edgeLabel x z $ transitiveClosure (overlay (edge e x y) (edge f y z)) == e <.> f --overlay :: (Eq e, Monoid e, Ord a) => AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a -- | Connect two graphs with edges labelled by a given label. When -- applied to the same labels, this is an associative operation with the -- identity empty, which distributes over overlay and obeys -- the decomposition axiom. Complexity: O((n + m) * log(n)) time -- and O(n + m) memory. Note that the number of edges in the -- resulting graph is quadratic with respect to the number of vertices of -- the arguments: m = O(m1 + m2 + n1 * n2). -- --
-- isEmpty (connect e x y) == isEmpty x && isEmpty y -- hasVertex z (connect e x y) == hasVertex z x || hasVertex z y -- vertexCount (connect e x y) >= vertexCount x -- vertexCount (connect e x y) <= vertexCount x + vertexCount y -- edgeCount (connect e x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- vertexCount (connect e 1 2) == 2 -- edgeCount (connect e 1 2) == if e == zero then 0 else 1 --connect :: (Eq e, Monoid e, Ord a) => e -> AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a -- | Construct 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 [] == empty -- vertices [x] == vertex x -- hasVertex x . vertices == elem x -- vertexCount . vertices == length . nub -- vertexSet . vertices == Set.fromList --vertices :: Ord a => [a] -> AdjacencyMap e a -- | Construct the graph from a list of edges. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- edges [] == empty -- edges [(e,x,y)] == edge e x y -- edges == overlays . map (\(e, x, y) -> edge e x y) --edges :: (Eq e, Monoid e, Ord a) => [(e, a, a)] -> AdjacencyMap e a -- | Overlay a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- overlays [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty -- isEmpty . overlays == all isEmpty --overlays :: (Eq e, Monoid e, Ord a) => [AdjacencyMap e a] -> AdjacencyMap e a -- | Construct a graph from a list of adjacency sets. Complexity: O((n + -- m) * log(n)) time and O(n + m) memory. -- --
-- fromAdjacencyMaps [] == empty -- fromAdjacencyMaps [(x, Map.empty)] == vertex x -- fromAdjacencyMaps [(x, Map.singleton y e)] == if e == zero then vertices [x,y] else edge e x y -- overlay (fromAdjacencyMaps xs) (fromAdjacencyMaps ys) == fromAdjacencyMaps (xs ++ ys) --fromAdjacencyMaps :: (Eq e, Monoid e, Ord a) => [(a, Map a e)] -> AdjacencyMap e a -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O(s + m * log(m)) time. Note that the number of -- edges m of a graph can be quadratic with respect to the -- expression size s. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: (Eq e, Monoid e, Ord a) => AdjacencyMap e a -> AdjacencyMap e a -> Bool -- | Check if a graph is empty. Complexity: O(1) time. -- --
-- isEmpty empty == True -- isEmpty (overlay empty empty) == True -- isEmpty (vertex x) == False -- isEmpty (removeVertex x $ vertex x) == True -- isEmpty (removeEdge x y $ edge e x y) == False --isEmpty :: AdjacencyMap e a -> Bool -- | Check if a graph contains a given vertex. Complexity: O(log(n)) -- time. -- --
-- hasVertex x empty == False -- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False -- hasVertex x . removeVertex x == const False --hasVertex :: Ord a => a -> AdjacencyMap e a -> Bool -- | Check if a graph contains a given edge. Complexity: O(log(n)) -- time. -- --
-- hasEdge x y empty == False -- hasEdge x y (vertex z) == False -- hasEdge x y (edge e x y) == (e /= zero) -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == not . null . filter (\(_,ex,ey) -> ex == x && ey == y) . edgeList --hasEdge :: Ord a => a -> a -> AdjacencyMap e a -> Bool -- | Extract the label of a specified edge in a graph. Complexity: -- O(log(n)) time. -- --
-- edgeLabel x y empty == zero -- edgeLabel x y (vertex z) == zero -- edgeLabel x y (edge e x y) == e -- edgeLabel s t (overlay x y) == edgeLabel s t x + edgeLabel s t y --edgeLabel :: (Monoid e, Ord a) => a -> a -> AdjacencyMap e a -> e -- | The number of vertices in a graph. Complexity: O(1) time. -- --
-- vertexCount empty == 0 -- vertexCount (vertex x) == 1 -- vertexCount == length . vertexList -- vertexCount x < vertexCount y ==> x < y --vertexCount :: AdjacencyMap e a -> Int -- | The number of (non-zero) edges in a graph. Complexity: -- O(n) time. -- --
-- edgeCount empty == 0 -- edgeCount (vertex x) == 0 -- edgeCount (edge e x y) == if e == zero then 0 else 1 -- edgeCount == length . edgeList --edgeCount :: AdjacencyMap e a -> Int -- | The sorted list of vertices of a given graph. Complexity: O(n) -- time and memory. -- --
-- vertexList empty == [] -- vertexList (vertex x) == [x] -- vertexList . vertices == nub . sort --vertexList :: AdjacencyMap e a -> [a] -- | 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 empty == [] -- edgeList (vertex x) == [] -- edgeList (edge e x y) == if e == zero then [] else [(e,x,y)] --edgeList :: AdjacencyMap e a -> [(e, a, a)] -- | The set of vertices of a given graph. Complexity: O(n) time and -- memory. -- --
-- vertexSet empty == Set.empty -- vertexSet . vertex == Set.singleton -- vertexSet . vertices == Set.fromList --vertexSet :: AdjacencyMap e a -> Set a -- | The set of edges of a given graph. Complexity: O(n + m) time -- and O(m) memory. -- --
-- edgeSet empty == Set.empty -- edgeSet (vertex x) == Set.empty -- edgeSet (edge e x y) == if e == zero then Set.empty else Set.singleton (e,x,y) --edgeSet :: (Eq a, Eq e) => AdjacencyMap e a -> Set (e, a, a) -- | The preset of an element x is the set of its direct -- predecessors. Complexity: O(n * log(n)) time and -- O(n) memory. -- --
-- preSet x empty == Set.empty -- preSet x (vertex x) == Set.empty -- preSet 1 (edge e 1 2) == Set.empty -- preSet y (edge e x y) == if e == zero then Set.empty else Set.fromList [x] --preSet :: Ord a => a -> AdjacencyMap e a -> Set a -- | The postset of a vertex is the set of its direct -- successors. Complexity: O(log(n)) time and O(1) -- memory. -- --
-- postSet x empty == Set.empty -- postSet x (vertex x) == Set.empty -- postSet x (edge e x y) == if e == zero then Set.empty else Set.fromList [y] -- postSet 2 (edge e 1 2) == Set.empty --postSet :: Ord a => a -> AdjacencyMap e a -> Set a -- | Convert a graph to the corresponding unlabelled AdjacencyMap by -- forgetting labels on all non-zero edges. -- --
-- hasEdge x y == hasEdge x y . skeleton --skeleton :: AdjacencyMap e a -> AdjacencyMap a -- | Remove a vertex from a given graph. Complexity: O(n*log(n)) -- time. -- --
-- removeVertex x (vertex x) == empty -- removeVertex 1 (vertex 2) == vertex 2 -- removeVertex x (edge e x x) == empty -- removeVertex 1 (edge e 1 2) == vertex 2 -- removeVertex x . removeVertex x == removeVertex x --removeVertex :: Ord a => a -> AdjacencyMap e a -> AdjacencyMap e a -- | Remove an edge from a given graph. Complexity: O(log(n)) time. -- --
-- removeEdge x y (edge e x y) == vertices [x,y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . removeVertex x == removeVertex x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 -- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 --removeEdge :: Ord a => a -> a -> AdjacencyMap e a -> AdjacencyMap e a -- | The function replaceVertex 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. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == gmap (\v -> if v == x then y else v) --replaceVertex :: (Eq e, Monoid e, Ord a) => a -> a -> AdjacencyMap e a -> AdjacencyMap e a -- | Replace 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 == overlay (removeEdge x y z) (edge e x y) -- replaceEdge e x y (edge f x y) == edge e x y -- edgeLabel x y (replaceEdge e x y z) == e --replaceEdge :: (Eq e, Monoid e, Ord a) => e -> a -> a -> AdjacencyMap e a -> AdjacencyMap e a -- | Transpose a given graph. Complexity: O(m * log(n)) time, O(n -- + m) memory. -- --
-- transpose empty == empty -- transpose (vertex x) == vertex x -- transpose (edge e x y) == edge e y x -- transpose . transpose == id --transpose :: (Monoid e, Ord a) => AdjacencyMap e a -> AdjacencyMap e a -- | Transform a graph by applying a function to each of its vertices. This -- is similar to Functor's fmap but can be used with -- non-fully-parametric AdjacencyMap. Complexity: O((n + m) * -- log(n)) time. -- --
-- gmap f empty == empty -- gmap f (vertex x) == vertex (f x) -- gmap f (edge e x y) == edge e (f x) (f y) -- gmap id == id -- gmap f . gmap g == gmap (f . g) --gmap :: (Eq e, Monoid e, Ord a, Ord b) => (a -> b) -> AdjacencyMap e a -> AdjacencyMap e b -- | 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 zero and <+>: -- --
-- h zero == zero -- h x <+> h y == h (x <+> y) ---- -- If e is also a semiring, then h must also preserve -- the multiplicative structure: -- --
-- h one == one -- h x <.> h y == h (x <.> y) ---- -- If the above requirements hold, then the implementation provides the -- following guarantees. -- --
-- emap h empty == empty -- emap h (vertex x) == vertex x -- emap h (edge e x y) == edge (h e) x y -- emap h (overlay x y) == overlay (emap h x) (emap h y) -- emap h (connect e x y) == connect (h e) (emap h x) (emap h y) -- emap id == id -- emap g . emap h == emap (g . h) --emap :: (Eq f, Monoid f) => (e -> f) -> AdjacencyMap e a -> AdjacencyMap f a -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(m) time, assuming that the predicate takes O(1) to be -- evaluated. -- --
-- induce (const True ) x == x -- induce (const False) x == empty -- induce (/= x) == removeVertex x -- induce p . induce q == induce (\x -> p x && q x) -- isSubgraphOf (induce p x) x == True --induce :: (a -> Bool) -> AdjacencyMap e a -> AdjacencyMap e a -- | Compute the reflexive and transitive closure of a graph over -- the underlying star semiring using the Warshall-Floyd-Kleene -- algorithm. -- --
-- closure empty == empty -- closure (vertex x) == edge one x x -- closure (edge e x x) == edge one x x -- closure (edge e x y) == edges [(one,x,x), (e,x,y), (one,y,y)] -- closure == reflexiveClosure . transitiveClosure -- closure == transitiveClosure . reflexiveClosure -- closure . closure == closure -- postSet x (closure y) == Set.fromList (reachable x y) --closure :: (Eq e, Ord a, StarSemiring e) => AdjacencyMap e a -> AdjacencyMap e a -- | Compute the reflexive closure of a graph over the underlying -- semiring by adding a self-loop of weight one to every vertex. -- Complexity: O(n * log(n)) time. -- --
-- reflexiveClosure empty == empty -- reflexiveClosure (vertex x) == edge one x x -- reflexiveClosure (edge e x x) == edge one x x -- reflexiveClosure (edge e x y) == edges [(one,x,x), (e,x,y), (one,y,y)] -- reflexiveClosure . reflexiveClosure == reflexiveClosure --reflexiveClosure :: (Ord a, Semiring e) => AdjacencyMap e a -> AdjacencyMap e a -- | Compute the symmetric closure of a graph by overlaying it with -- its own transpose. Complexity: O((n + m) * log(n)) time. -- --
-- symmetricClosure empty == empty -- symmetricClosure (vertex x) == vertex x -- symmetricClosure (edge e x y) == edges [(e,x,y), (e,y,x)] -- symmetricClosure x == overlay x (transpose x) -- symmetricClosure . symmetricClosure == symmetricClosure --symmetricClosure :: (Eq e, Monoid e, Ord a) => AdjacencyMap e a -> AdjacencyMap e a -- | Compute 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 empty == empty -- transitiveClosure (vertex x) == vertex x -- transitiveClosure (edge e x y) == edge e x y -- transitiveClosure . transitiveClosure == transitiveClosure --transitiveClosure :: (Eq e, Ord a, StarSemiring e) => AdjacencyMap e a -> AdjacencyMap e a -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module provides a minimal and experimental implementation of -- algebraic graphs with edge labels. The API will be expanded in the -- next release. module Algebra.Graph.Labelled -- | Edge-labelled graphs, where the type variable e stands for -- edge labels. For example, Graph Bool a is -- isomorphic to unlabelled graphs defined in the top-level module -- Algebra.Graph.Graph, where False and True -- denote the lack of and the existence of an unlabelled edge, -- respectively. data Graph e a Empty :: Graph e a Vertex :: a -> Graph e a Connect :: e -> Graph e a -> Graph e a -> Graph e a -- | Construct the empty graph. An alias for the constructor -- Empty. Complexity: O(1) time, memory and size. -- --
-- isEmpty empty == True -- hasVertex x empty == False -- vertexCount empty == 0 -- edgeCount empty == 0 --empty :: Graph e a -- | Construct the graph comprising a single isolated vertex. An -- alias for the constructor Vertex. Complexity: O(1) time, -- memory and size. -- --
-- isEmpty (vertex x) == False -- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 --vertex :: a -> Graph e a -- | Construct the graph comprising a single labelled edge. -- Complexity: O(1) time, memory and size. -- --
-- edge e x y == connect e (vertex x) (vertex y) -- edge zero x y == vertices [x,y] -- hasEdge x y (edge e x y) == (e /= zero) -- edgeLabel x y (edge e x y) == e -- edgeCount (edge e x y) == if e == zero then 0 else 1 -- vertexCount (edge e 1 1) == 1 -- vertexCount (edge e 1 2) == 2 --edge :: e -> a -> a -> Graph e a -- | The left-hand part of a convenient ternary-ish operator -- x-<e>-y for creating labelled edges. -- --
-- x -<e>- y == edge e x y --(-<) :: a -> e -> (a, e) infixl 5 -< -- | The right-hand part of a convenient ternary-ish operator -- x-<e>-y for creating labelled edges. -- --
-- x -<e>- y == edge e x y --(>-) :: (a, e) -> a -> Graph e a infixl 5 >- -- | Overlay two graphs. An alias for Connect zero. -- Complexity: O(1) time and memory, O(s1 + s2) size. -- --
-- isEmpty (overlay x y) == isEmpty x && isEmpty y -- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 ---- -- Note: overlay composes edges in parallel using the operator -- <+> with zero acting as the identity: -- --
-- edgeLabel x y $ overlay (edge e x y) (edge zero x y) == e -- edgeLabel x y $ overlay (edge e x y) (edge f x y) == e <+> f ---- -- Furthermore, when applied to transitive graphs, overlay -- composes edges in sequence using the operator <.> with -- one acting as the identity: -- --
-- edgeLabel x z $ transitiveClosure (overlay (edge e x y) (edge one y z)) == e -- edgeLabel x z $ transitiveClosure (overlay (edge e x y) (edge f y z)) == e <.> f --overlay :: Monoid e => Graph e a -> Graph e a -> Graph e a -- | Connect two graphs with edges labelled by a given label. An -- alias for Connect. 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). -- --
-- isEmpty (connect e x y) == isEmpty x && isEmpty y -- hasVertex z (connect e x y) == hasVertex z x || hasVertex z y -- vertexCount (connect e x y) >= vertexCount x -- vertexCount (connect e x y) <= vertexCount x + vertexCount y -- edgeCount (connect e x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- vertexCount (connect e 1 2) == 2 -- edgeCount (connect e 1 2) == if e == zero then 0 else 1 --connect :: e -> Graph e a -> Graph e a -> Graph e a -- | Construct 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 [] == empty -- vertices [x] == vertex x -- hasVertex x . vertices == elem x -- vertexCount . vertices == length . nub -- vertexSet . vertices == Set.fromList --vertices :: Monoid e => [a] -> Graph e a -- | 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 [] == empty -- edges [(e,x,y)] == edge e x y -- edges == overlays . map (\(e, x, y) -> edge e x y) --edges :: Monoid e => [(e, a, a)] -> Graph e a -- | Overlay a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- overlays [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty -- isEmpty . overlays == all isEmpty --overlays :: Monoid e => [Graph e a] -> Graph e a -- | Generalised Graph folding: recursively collapse a Graph -- by applying the provided functions to the leaves and internal nodes of -- the expression. The order of arguments is: empty, vertex and connect. -- Complexity: O(s) applications of given functions. As an -- example, the complexity of size is O(s), since all -- functions have cost O(1). -- --
-- foldg empty vertex connect == id -- foldg empty vertex (fmap flip connect) == transpose -- foldg 1 (const 1) (const (+)) == size -- foldg True (const False) (const (&&)) == isEmpty -- foldg False (== x) (const (||)) == hasVertex x -- foldg Set.empty Set.singleton (const Set.union) == vertexSet --foldg :: b -> (a -> b) -> (e -> b -> b -> b) -> Graph e a -> b -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O(s + m * log(m)) time. Note that the number of -- edges m of a graph can be quadratic with respect to the -- expression size s. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: (Eq e, Monoid e, Ord a) => Graph e a -> Graph e a -> Bool -- | Check if a graph is empty. A convenient alias for null. -- Complexity: O(s) time. -- --
-- isEmpty empty == True -- isEmpty (overlay empty empty) == True -- isEmpty (vertex x) == False -- isEmpty (removeVertex x $ vertex x) == True -- isEmpty (removeEdge x y $ edge e x y) == False --isEmpty :: Graph e a -> Bool -- | The size of a graph, i.e. the number of leaves of the -- expression including empty leaves. Complexity: O(s) -- time. -- --
-- size empty == 1 -- size (vertex x) == 1 -- size (overlay x y) == size x + size y -- size (connect x y) == size x + size y -- size x >= 1 -- size x >= vertexCount x --size :: Graph e a -> Int -- | Check if a graph contains a given vertex. Complexity: O(s) -- time. -- --
-- hasVertex x empty == False -- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False -- hasVertex x . removeVertex x == const False --hasVertex :: Eq a => a -> Graph e a -> Bool -- | Check if a graph contains a given edge. Complexity: O(s) time. -- --
-- hasEdge x y empty == False -- hasEdge x y (vertex z) == False -- hasEdge x y (edge e x y) == (e /= zero) -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == not . null . filter (\(_,ex,ey) -> ex == x && ey == y) . edgeList --hasEdge :: (Eq e, Monoid e, Ord a) => a -> a -> Graph e a -> Bool -- | Extract the label of a specified edge from a graph. edgeLabel :: (Eq a, Monoid e) => a -> a -> Graph e a -> e -- | The sorted list of vertices of a given graph. Complexity: O(s * -- log(n)) time and O(n) memory. -- --
-- vertexList empty == [] -- vertexList (vertex x) == [x] -- vertexList . vertices == nub . sort --vertexList :: Ord a => Graph e a -> [a] -- | 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 empty == [] -- edgeList (vertex x) == [] -- edgeList (edge e x y) == if e == zero then [] else [(e,x,y)] --edgeList :: (Eq e, Monoid e, Ord a) => Graph e a -> [(e, a, a)] -- | The set of vertices of a given graph. Complexity: O(s * log(n)) -- time and O(n) memory. -- --
-- vertexSet empty == Set.empty -- vertexSet . vertex == Set.singleton -- vertexSet . vertices == Set.fromList --vertexSet :: Ord a => Graph e a -> Set a -- | The set of edges of a given graph. Complexity: O(n + m) time -- and O(m) memory. -- --
-- edgeSet empty == Set.empty -- edgeSet (vertex x) == Set.empty -- edgeSet (edge e x y) == if e == zero then Set.empty else Set.singleton (e,x,y) --edgeSet :: (Eq e, Monoid e, Ord a) => Graph e a -> Set (e, a, a) -- | Remove a vertex from a given graph. Complexity: O(s) time, -- memory and size. -- --
-- removeVertex x (vertex x) == empty -- removeVertex 1 (vertex 2) == vertex 2 -- removeVertex x (edge e x x) == empty -- removeVertex 1 (edge e 1 2) == vertex 2 -- removeVertex x . removeVertex x == removeVertex x --removeVertex :: Eq a => a -> Graph e a -> Graph e a -- | Remove an edge from a given graph. Complexity: O(s) time, -- memory and size. -- --
-- removeEdge x y (edge e x y) == vertices [x,y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . removeVertex x == removeVertex x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 -- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 --removeEdge :: (Eq a, Eq e, Monoid e) => a -> a -> Graph e a -> Graph e a -- | The function replaceVertex x y replaces vertex -- x with vertex y in a given Graph. If -- y already exists, x and y will be merged. -- Complexity: O(s) time, memory and size. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == fmap (\v -> if v == x then y else v) --replaceVertex :: Eq a => a -> a -> Graph e a -> Graph e a -- | Replace 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 == overlay (removeEdge x y z) (edge e x y) -- replaceEdge e x y (edge f x y) == edge e x y -- edgeLabel x y (replaceEdge e x y z) == e --replaceEdge :: (Eq e, Monoid e, Ord a) => e -> a -> a -> Graph e a -> Graph e a -- | Transpose a given graph. Complexity: O(s) time, memory and -- size. -- --
-- transpose empty == empty -- transpose (vertex x) == vertex x -- transpose (edge e x y) == edge e y x -- transpose . transpose == id --transpose :: Graph e a -> Graph e a -- | Transform 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 zero and <+>: -- --
-- h zero == zero -- h x <+> h y == h (x <+> y) ---- -- If e is also a semiring, then h must also preserve -- the multiplicative structure: -- --
-- h one == one -- h x <.> h y == h (x <.> y) ---- -- If the above requirements hold, then the implementation provides the -- following guarantees. -- --
-- emap h empty == empty -- emap h (vertex x) == vertex x -- emap h (edge e x y) == edge (h e) x y -- emap h (overlay x y) == overlay (emap h x) (emap h y) -- emap h (connect e x y) == connect (h e) (emap h x) (emap h y) -- emap id == id -- emap g . emap h == emap (g . h) --emap :: (e -> f) -> Graph e a -> Graph f a -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(s) time, memory and size, assuming that the predicate takes -- O(1) to be evaluated. -- --
-- induce (const True ) x == x -- induce (const False) x == empty -- induce (/= x) == removeVertex x -- induce p . induce q == induce (\x -> p x && q x) -- isSubgraphOf (induce p x) x == True --induce :: (a -> Bool) -> Graph e a -> Graph e a -- | Compute the reflexive and transitive closure of a graph over -- the underlying star semiring using the Warshall-Floyd-Kleene -- algorithm. -- --
-- closure empty == empty -- closure (vertex x) == edge one x x -- closure (edge e x x) == edge one x x -- closure (edge e x y) == edges [(one,x,x), (e,x,y), (one,y,y)] -- closure == reflexiveClosure . transitiveClosure -- closure == transitiveClosure . reflexiveClosure -- closure . closure == closure -- postSet x (closure y) == Set.fromList (reachable x y) --closure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a -- | Compute the reflexive closure of a graph over the underlying -- semiring by adding a self-loop of weight one to every vertex. -- Complexity: O(n * log(n)) time. -- --
-- reflexiveClosure empty == empty -- reflexiveClosure (vertex x) == edge one x x -- reflexiveClosure (edge e x x) == edge one x x -- reflexiveClosure (edge e x y) == edges [(one,x,x), (e,x,y), (one,y,y)] -- reflexiveClosure . reflexiveClosure == reflexiveClosure --reflexiveClosure :: (Ord a, Semiring e) => Graph e a -> Graph e a -- | Compute the symmetric closure of a graph by overlaying it with -- its own transpose. Complexity: O((n + m) * log(n)) time. -- --
-- symmetricClosure empty == empty -- symmetricClosure (vertex x) == vertex x -- symmetricClosure (edge e x y) == edges [(e,x,y), (e,y,x)] -- symmetricClosure x == overlay x (transpose x) -- symmetricClosure . symmetricClosure == symmetricClosure --symmetricClosure :: Monoid e => Graph e a -> Graph e a -- | Compute 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 empty == empty -- transitiveClosure (vertex x) == vertex x -- transitiveClosure (edge e x y) == edge e x y -- transitiveClosure . transitiveClosure == transitiveClosure --transitiveClosure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a -- | A type synonym for unlabelled graphs. type UnlabelledGraph a = Graph Any a -- | A type synonym for automata or labelled transition -- systems. type Automaton a s = Graph (RegularExpression a) s -- | A network is a graph whose edges are labelled with distances. type Network e a = Graph (Distance e) a -- | The Context of a subgraph comprises its inputs and -- outputs, 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 inputs and -- outputs; furthermore, there may be repetitions. data Context e a Context :: [(e, a)] -> [(e, a)] -> Context e a [inputs] :: Context e a -> [(e, a)] [outputs] :: Context e a -> [(e, a)] -- | Extract the Context of a subgraph specified by a given -- predicate. Returns Nothing if the specified subgraph is -- empty. -- --
-- context (const False) x == Nothing -- context (== 1) (edge e 1 2) == if e == zero then Just (Context [] []) else Just (Context [ ] [(e,2)]) -- context (== 2) (edge e 1 2) == if e == zero then Just (Context [] []) else Just (Context [(e,1)] [ ]) -- context (const True ) (edge e 1 2) == if e == zero then Just (Context [] []) else Just (Context [(e,1)] [(e,2)]) -- context (== 4) (3 * 1 * 4 * 1 * 5) == Just (Context [(one,3), (one,1)] [(one,1), (one,5)]) --context :: (Eq e, Monoid e) => (a -> Bool) -> Graph e a -> Maybe (Context e a) instance (GHC.Show.Show e, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Labelled.Context e a) instance (GHC.Classes.Eq e, GHC.Classes.Eq a) => GHC.Classes.Eq (Algebra.Graph.Labelled.Context e a) instance (GHC.Show.Show a, GHC.Show.Show e) => GHC.Show.Show (Algebra.Graph.Labelled.Graph e a) instance GHC.Base.Functor (Algebra.Graph.Labelled.Graph e) instance (GHC.Classes.Eq e, GHC.Base.Monoid e, GHC.Classes.Ord a) => GHC.Classes.Eq (Algebra.Graph.Labelled.Graph e a) instance (GHC.Classes.Eq e, GHC.Base.Monoid e, GHC.Classes.Ord a, GHC.Classes.Ord e) => GHC.Classes.Ord (Algebra.Graph.Labelled.Graph e a) instance (GHC.Classes.Ord a, GHC.Num.Num a, Algebra.Graph.Label.Dioid e) => GHC.Num.Num (Algebra.Graph.Labelled.Graph e a) -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module contains a simple example of using edge-labelled graphs -- defined in the module Algebra.Graph.Labelled for working with -- networks, i.e. graphs whose edges are labelled with distances. module Algebra.Graph.Labelled.Example.Network -- | Our example networks have cities as vertices. data City Aberdeen :: City Edinburgh :: City Glasgow :: City London :: City Newcastle :: City -- | For simplicity we measure journey times in integer number of -- minutes. type JourneyTime = Int -- | A part of the EastCoast train network between Aberdeen and -- London. -- --
-- eastCoast = overlays [ Aberdeen -<150>- Edinburgh -- , Edinburgh -< 90>- Newcastle -- , Newcastle -<170>- London ] --eastCoast :: Network JourneyTime City -- | A part of the ScotRail train network between Aberdeen and -- Glasgow. -- --
-- scotRail = overlays [ Aberdeen -<140>- Edinburgh -- , Edinburgh -< 50>- Glasgow -- , Edinburgh -< 70>- Glasgow ] --scotRail :: Network JourneyTime City -- | An example train network. -- --
-- network = overlay scotRail eastCoast --network :: Network JourneyTime City instance GHC.Show.Show Algebra.Graph.Labelled.Example.Network.City instance GHC.Classes.Ord Algebra.Graph.Labelled.Example.Network.City instance GHC.Classes.Eq Algebra.Graph.Labelled.Example.Network.City instance GHC.Enum.Enum Algebra.Graph.Labelled.Example.Network.City instance GHC.Enum.Bounded Algebra.Graph.Labelled.Example.Network.City -- | This module exposes the implementation of non-empty adjacency maps. -- The API is unstable and unsafe, and is exposed only for documentation. -- You should use the non-internal module -- Algebra.Graph.NonEmpty.AdjacencyMap instead. module Algebra.Graph.NonEmpty.AdjacencyMap.Internal -- | The AdjacencyMap data type represents a graph by a map of -- vertices to their adjacency sets. We define a Num 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 signum method of the type class Num -- cannot be implemented and will throw an error. Furthermore, the -- Num instance does not satisfy several "customary laws" of -- Num, which dictate that fromInteger 0 and -- fromInteger 1 should act as additive and -- multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show 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 Eq instance satisfies the following laws of algebraic -- graphs: -- --
x -- + y == y + x x + (y + z) == (x + y) + z x + x == x
x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x * y + x -- + y == x * y x * x * x == x * x
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- x <= x + y -- x + y <= x * y --newtype AdjacencyMap a NAM :: AdjacencyMap a -> AdjacencyMap a -- | The adjacency map of a graph: each vertex is associated with a -- set of its direct successors. Complexity: O(1) time and memory. -- --
-- adjacencyMap (vertex x) == Map.singleton x Set.empty -- adjacencyMap (edge 1 1) == Map.singleton 1 (Set.singleton 1) -- adjacencyMap (edge 1 2) == Map.fromList [(1,Set.singleton 2), (2,Set.empty)] --[am] :: AdjacencyMap a -> AdjacencyMap a -- | 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 (edge x y) == True -- consistent (edges xs) == True -- consistent (stars xs) == True --consistent :: Ord a => AdjacencyMap a -> Bool instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.NonEmpty.AdjacencyMap.Internal.AdjacencyMap a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.NonEmpty.AdjacencyMap.Internal.AdjacencyMap a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.NonEmpty.AdjacencyMap.Internal.AdjacencyMap a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.NonEmpty.AdjacencyMap.Internal.AdjacencyMap a) instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.NonEmpty.AdjacencyMap.Internal.AdjacencyMap a) -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the data type AdjacencyMap for graphs that -- are known to be non-empty at compile time. To avoid name clashes with -- Algebra.Graph.AdjacencyMap, this module can be imported -- qualified: -- --
-- import qualified Algebra.Graph.NonEmpty.AdjacencyMap as NonEmpty ---- -- The naming convention generally follows that of -- Data.List.NonEmpty: we use suffix 1 to indicate the -- functions whose interface must be changed compared to -- Algebra.Graph.AdjacencyMap, e.g. vertices1. module Algebra.Graph.NonEmpty.AdjacencyMap -- | The AdjacencyMap data type represents a graph by a map of -- vertices to their adjacency sets. We define a Num 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 signum method of the type class Num -- cannot be implemented and will throw an error. Furthermore, the -- Num instance does not satisfy several "customary laws" of -- Num, which dictate that fromInteger 0 and -- fromInteger 1 should act as additive and -- multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show 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 Eq instance satisfies the following laws of algebraic -- graphs: -- --
x -- + y == y + x x + (y + z) == (x + y) + z x + x == x
x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x * y + x -- + y == x * y x * x * x == x * x
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- x <= x + y -- x + y <= x * y --data AdjacencyMap a -- | Convert a possibly empty AdjacencyMap into -- NonEmpty.AdjacencyMap. Returns Nothing if the argument -- is empty. Complexity: O(1) time, memory and size. -- --
-- toNonEmpty empty == Nothing -- toNonEmpty (toAdjacencyMap x) == Just (x :: AdjacencyMap a) --toNonEmpty :: AdjacencyMap a -> Maybe (AdjacencyMap a) -- | Construct the graph comprising a single isolated vertex. -- Complexity: O(1) time and memory. -- --
-- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 --vertex :: a -> AdjacencyMap a -- | Construct the graph comprising a single edge. Complexity: -- O(1) time, memory. -- --
-- edge x y == connect (vertex x) (vertex y) -- hasEdge x y (edge x y) == True -- edgeCount (edge x y) == 1 -- vertexCount (edge 1 1) == 1 -- vertexCount (edge 1 2) == 2 --edge :: Ord a => a -> a -> AdjacencyMap a -- | Overlay 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. -- --
-- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 --overlay :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a -- | Connect two graphs. This is an associative operation with the -- identity empty, which distributes over overlay and -- obeys the decomposition axiom. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. Note that the number of edges in the -- resulting graph is quadratic with respect to the number of vertices of -- the arguments: m = O(m1 + m2 + n1 * n2). -- --
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y -- vertexCount (connect x y) >= vertexCount x -- vertexCount (connect x y) <= vertexCount x + vertexCount y -- edgeCount (connect x y) >= edgeCount x -- edgeCount (connect x y) >= edgeCount y -- edgeCount (connect x y) >= vertexCount x * vertexCount y -- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- vertexCount (connect 1 2) == 2 -- edgeCount (connect 1 2) == 1 --connect :: Ord a => AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a -- | Construct 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] == vertex x -- hasVertex x . vertices1 == elem x -- vertexCount . vertices1 == length . nub -- vertexSet . vertices1 == Set.fromList . toList --vertices1 :: Ord a => NonEmpty a -> AdjacencyMap a -- | Construct the graph from a list of edges. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- edges1 [(x,y)] == edge x y -- edgeCount . edges1 == length . nub --edges1 :: Ord a => NonEmpty (a, a) -> AdjacencyMap a -- | Overlay a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- overlays1 [x] == x -- overlays1 [x,y] == overlay x y --overlays1 :: Ord a => NonEmpty (AdjacencyMap a) -> AdjacencyMap a -- | Connect a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- connects1 [x] == x -- connects1 [x,y] == connect x y --connects1 :: Ord a => NonEmpty (AdjacencyMap a) -> AdjacencyMap a -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O((n + m) * log(n)) time. -- --
-- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path1 xs) (circuit1 xs) == True -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: Ord a => AdjacencyMap a -> AdjacencyMap a -> Bool -- | Check if a graph contains a given vertex. Complexity: O(log(n)) -- time. -- --
-- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False --hasVertex :: Ord a => a -> AdjacencyMap a -> Bool -- | Check if a graph contains a given edge. Complexity: O(log(n)) -- time. -- --
-- hasEdge x y (vertex z) == False -- hasEdge x y (edge x y) == True -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == elem (x,y) . edgeList --hasEdge :: Ord a => a -> a -> AdjacencyMap a -> Bool -- | The number of vertices in a graph. Complexity: O(1) time. -- --
-- vertexCount (vertex x) == 1 -- vertexCount == length . vertexList -- vertexCount x < vertexCount y ==> x < y --vertexCount :: AdjacencyMap a -> Int -- | The number of edges in a graph. Complexity: O(n) time. -- --
-- edgeCount (vertex x) == 0 -- edgeCount (edge x y) == 1 -- edgeCount == length . edgeList --edgeCount :: AdjacencyMap a -> Int -- | The sorted list of vertices of a given graph. Complexity: O(n) -- time and memory. -- --
-- vertexList1 (vertex x) == [x] -- vertexList1 . vertices1 == nub . sort --vertexList1 :: AdjacencyMap a -> NonEmpty a -- | The sorted list of edges of a graph. Complexity: O(n + m) time -- and O(m) memory. -- --
-- edgeList (vertex x) == [] -- edgeList (edge x y) == [(x,y)] -- edgeList (star 2 [3,1]) == [(2,1), (2,3)] -- edgeList . edges == nub . sort -- edgeList . transpose == sort . map swap . edgeList --edgeList :: AdjacencyMap a -> [(a, a)] -- | The set of vertices of a given graph. Complexity: O(n) time and -- memory. -- --
-- vertexSet . vertex == Set.singleton -- vertexSet . vertices1 == Set.fromList . toList -- vertexSet . clique1 == Set.fromList . toList --vertexSet :: AdjacencyMap a -> Set a -- | The set of edges of a given graph. Complexity: O((n + m) * -- log(m)) time and O(m) memory. -- --
-- edgeSet (vertex x) == Set.empty -- edgeSet (edge x y) == Set.singleton (x,y) -- edgeSet . edges == Set.fromList --edgeSet :: Ord a => AdjacencyMap a -> Set (a, a) -- | The preset of an element x is the set of its direct -- predecessors. Complexity: O(n * log(n)) time and -- O(n) memory. -- --
-- preSet x (vertex x) == Set.empty -- preSet 1 (edge 1 2) == Set.empty -- preSet y (edge x y) == Set.fromList [x] --preSet :: Ord a => a -> AdjacencyMap a -> Set a -- | The postset of a vertex is the set of its direct -- successors. Complexity: O(log(n)) time and O(1) -- memory. -- --
-- postSet x (vertex x) == Set.empty -- postSet x (edge x y) == Set.fromList [y] -- postSet 2 (edge 1 2) == Set.empty --postSet :: Ord a => a -> AdjacencyMap a -> Set a -- | The path on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- path1 [x] == vertex x -- path1 [x,y] == edge x y -- path1 . reverse == transpose . path1 --path1 :: Ord a => NonEmpty a -> AdjacencyMap a -- | The circuit on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- circuit1 [x] == edge x x -- circuit1 [x,y] == edges1 [(x,y), (y,x)] -- circuit1 . reverse == transpose . circuit1 --circuit1 :: Ord a => NonEmpty a -> AdjacencyMap a -- | The clique on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- clique1 [x] == vertex x -- clique1 [x,y] == edge x y -- clique1 [x,y,z] == edges1 [(x,y), (x,z), (y,z)] -- clique1 (xs <> ys) == connect (clique1 xs) (clique1 ys) -- clique1 . reverse == transpose . clique1 --clique1 :: Ord a => NonEmpty a -> AdjacencyMap a -- | The biclique on two lists of vertices. Complexity: O(n * -- log(n) + m) time and O(n + m) memory. -- --
-- biclique1 [x1,x2] [y1,y2] == edges1 [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique1 xs ys == connect (vertices1 xs) (vertices1 ys) --biclique1 :: Ord a => NonEmpty a -> NonEmpty a -> AdjacencyMap a -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges1 [(x,y), (x,z)] --star :: Ord a => a -> [a] -> AdjacencyMap a -- | The stars formed by overlaying a list of stars. An -- inverse of adjacencyList. Complexity: O(L * log(n)) -- time, memory and size, where L is the total size of the input. -- --
-- stars1 [(x, [] )] == vertex x -- stars1 [(x, [y])] == edge x y -- stars1 [(x, ys )] == star x ys -- stars1 == overlays1 . fmap (uncurry star) -- overlay (stars1 xs) (stars1 ys) == stars1 (xs <> ys) --stars1 :: Ord a => NonEmpty (a, [a]) -> AdjacencyMap a -- | The tree graph constructed from a given Tree data -- structure. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- tree (Node x []) == vertex x -- tree (Node x [Node y [Node z []]]) == path1 [x,y,z] -- tree (Node x [Node y [], Node z []]) == star x [y,z] -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges1 [(1,2), (1,3), (3,4), (3,5)] --tree :: Ord a => Tree a -> AdjacencyMap a -- | Remove a vertex from a given graph. Complexity: O(n*log(n)) -- time. -- --
-- removeVertex1 x (vertex x) == Nothing -- removeVertex1 1 (vertex 2) == Just (vertex 2) -- removeVertex1 x (edge x x) == Nothing -- removeVertex1 1 (edge 1 2) == Just (vertex 2) -- removeVertex1 x >=> removeVertex1 x == removeVertex1 x --removeVertex1 :: Ord a => a -> AdjacencyMap a -> Maybe (AdjacencyMap a) -- | Remove an edge from a given graph. Complexity: O(log(n)) time. -- --
-- removeEdge x y (edge x y) == vertices1 [x,y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 -- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 --removeEdge :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a -- | The function replaceVertex 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. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == mergeVertices (== x) y --replaceVertex :: Ord a => a -> a -> AdjacencyMap a -> AdjacencyMap a -- | Merge 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 (const False) x == id -- mergeVertices (== x) y == replaceVertex x y -- mergeVertices even 1 (0 * 2) == 1 * 1 -- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 --mergeVertices :: Ord a => (a -> Bool) -> a -> AdjacencyMap a -> AdjacencyMap a -- | Transpose a given graph. Complexity: O(m * log(n)) time, O(n -- + m) memory. -- --
-- transpose (vertex x) == vertex x -- transpose (edge x y) == edge y x -- transpose . transpose == id -- edgeList . transpose == sort . map swap . edgeList --transpose :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Transform a graph by applying a function to each of its vertices. This -- is similar to Functor's fmap but can be used with -- non-fully-parametric AdjacencyMap. Complexity: O((n + m) * -- log(n)) time. -- --
-- gmap f (vertex x) == vertex (f x) -- gmap f (edge x y) == edge (f x) (f y) -- gmap id == id -- gmap f . gmap g == gmap (f . g) --gmap :: (Ord a, Ord b) => (a -> b) -> AdjacencyMap a -> AdjacencyMap b -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(m) time, assuming that the predicate takes O(1) to be -- evaluated. -- --
-- induce1 (const True ) x == Just x -- induce1 (const False) x == Nothing -- induce1 (/= x) == removeVertex1 x -- induce1 p >=> induce1 q == induce1 (\x -> p x && q x) --induce1 :: (a -> Bool) -> AdjacencyMap a -> Maybe (AdjacencyMap a) -- | Compute the reflexive and transitive closure of a graph. -- Complexity: O(n * m * log(n)^2) time. -- --
-- closure (vertex x) == edge x x -- closure (edge x x) == edge x x -- closure (edge x y) == edges1 [(x,x), (x,y), (y,y)] -- closure (path1 $ nub xs) == reflexiveClosure (clique1 $ nub xs) -- closure == reflexiveClosure . transitiveClosure -- closure == transitiveClosure . reflexiveClosure -- closure . closure == closure -- postSet x (closure y) == Set.fromList (reachable x y) --closure :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Compute the reflexive closure of a graph by adding a self-loop -- to every vertex. Complexity: O(n * log(n)) time. -- --
-- reflexiveClosure (vertex x) == edge x x -- reflexiveClosure (edge x x) == edge x x -- reflexiveClosure (edge x y) == edges1 [(x,x), (x,y), (y,y)] -- reflexiveClosure . reflexiveClosure == reflexiveClosure --reflexiveClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Compute the symmetric closure of a graph by overlaying it with -- its own transpose. Complexity: O((n + m) * log(n)) time. -- --
-- symmetricClosure (vertex x) == vertex x -- symmetricClosure (edge x y) == edges1 [(x,y), (y,x)] -- symmetricClosure x == overlay x (transpose x) -- symmetricClosure . symmetricClosure == symmetricClosure --symmetricClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | Compute the transitive closure of a graph. Complexity: O(n * -- m * log(n)^2) time. -- --
-- transitiveClosure (vertex x) == vertex x -- transitiveClosure (edge x y) == edge x y -- transitiveClosure (path1 $ nub xs) == clique1 (nub xs) -- transitiveClosure . transitiveClosure == transitiveClosure --transitiveClosure :: Ord a => AdjacencyMap a -> AdjacencyMap a -- | This module exposes the implementation of the Relation data -- type. The API is unstable and unsafe, and is exposed only for -- documentation. You should use the non-internal module -- Algebra.Graph.Relation instead. module Algebra.Graph.Relation.Internal -- | The Relation data type represents a graph as a binary -- relation. We define a Num 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 Num instance does not satisfy several -- "customary laws" of Num, which dictate that fromInteger -- 0 and fromInteger 1 should act as additive -- and multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show instance is defined using basic graph construction -- primitives: -- --
-- show (empty :: Relation Int) == "empty" -- show (1 :: Relation Int) == "vertex 1" -- show (1 + 2 :: Relation Int) == "vertices [1,2]" -- show (1 * 2 :: Relation Int) == "edge 1 2" -- show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]" -- show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)" ---- -- The Eq instance satisfies all axioms of algebraic graphs: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf -- relation and is compatible with overlay and connect -- operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- empty <= x -- x <= x + y -- x + y <= x * y --data Relation a Relation :: Set a -> Set (a, a) -> Relation a -- | The domain of the relation. [domain] :: Relation a -> Set a -- | The set of pairs of elements that are related. It is guaranteed -- that each element belongs to the domain. [relation] :: Relation a -> Set (a, a) -- | Construct the empty graph. Complexity: O(1) time and -- memory. -- --
-- isEmpty empty == True -- hasVertex x empty == False -- vertexCount empty == 0 -- edgeCount empty == 0 --empty :: Relation a -- | Construct the graph comprising a single isolated vertex. -- Complexity: O(1) time and memory. -- --
-- isEmpty (vertex x) == False -- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 --vertex :: a -> Relation a -- | Overlay 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. -- --
-- isEmpty (overlay x y) == isEmpty x && 'iAlgebra.Graph.Relation.sEmpty' y -- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 --overlay :: Ord a => Relation a -> Relation a -> Relation a -- | Connect two graphs. This is an associative operation with the -- identity empty, which distributes over overlay and obeys -- the decomposition axiom. Complexity: O((n + m) * log(n)) time -- and O(n + m) memory. Note that the number of edges in the -- resulting graph is quadratic with respect to the number of vertices of -- the arguments: m = O(m1 + m2 + n1 * n2). -- --
-- isEmpty (connect x y) == isEmpty x && isEmpty y -- hasVertex z (connect x y) == hasVertex z x || hasVertex z y -- vertexCount (connect x y) >= vertexCount x -- vertexCount (connect x y) <= vertexCount x + vertexCount y -- edgeCount (connect x y) >= edgeCount x -- edgeCount (connect x y) >= edgeCount y -- edgeCount (connect x y) >= vertexCount x * vertexCount y -- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- vertexCount (connect 1 2) == 2 -- edgeCount (connect 1 2) == 1 --connect :: Ord a => Relation a -> Relation a -> Relation a -- | Compute the Cartesian product of two sets. setProduct :: Set a -> Set b -> Set (a, b) -- | Check if the internal representation of a relation is consistent, i.e. -- if all pairs of elements in the relation refer to existing -- elements in the domain. It should be impossible to create an -- inconsistent Relation, and we use this function in testing. -- Note: this function is for internal use only. -- --
-- consistent empty == True -- consistent (vertex x) == True -- consistent (overlay x y) == True -- consistent (connect x y) == True -- consistent (edge x y) == True -- consistent (edges xs) == True -- consistent (stars xs) == True --consistent :: Ord a => Relation a -> Bool -- | The set of elements that appear in a given set of pairs. Note: this -- function is for internal use only. referredToVertexSet :: Ord a => Set (a, a) -> Set a instance GHC.Classes.Eq a => GHC.Classes.Eq (Algebra.Graph.Relation.Internal.Relation a) instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.Internal.Relation a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Relation.Internal.Relation a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.Internal.Relation a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.Internal.Relation a) -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the Relation data type, as well as -- associated operations and algorithms. Relation is an instance -- of the Graph type class, which can be used for polymorphic -- graph construction and manipulation. module Algebra.Graph.Relation -- | The Relation data type represents a graph as a binary -- relation. We define a Num 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 Num instance does not satisfy several -- "customary laws" of Num, which dictate that fromInteger -- 0 and fromInteger 1 should act as additive -- and multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show instance is defined using basic graph construction -- primitives: -- --
-- show (empty :: Relation Int) == "empty" -- show (1 :: Relation Int) == "vertex 1" -- show (1 + 2 :: Relation Int) == "vertices [1,2]" -- show (1 * 2 :: Relation Int) == "edge 1 2" -- show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]" -- show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)" ---- -- The Eq instance satisfies all axioms of algebraic graphs: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf -- relation and is compatible with overlay and connect -- operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- empty <= x -- x <= x + y -- x + y <= x * y --data Relation a -- | The domain of the relation. domain :: Relation a -> Set a -- | The set of pairs of elements that are related. It is guaranteed -- that each element belongs to the domain. relation :: Relation a -> Set (a, a) -- | Construct the empty graph. Complexity: O(1) time and -- memory. -- --
-- isEmpty empty == True -- hasVertex x empty == False -- vertexCount empty == 0 -- edgeCount empty == 0 --empty :: Relation a -- | Construct the graph comprising a single isolated vertex. -- Complexity: O(1) time and memory. -- --
-- isEmpty (vertex x) == False -- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 --vertex :: a -> Relation a -- | Construct the graph comprising a single edge. Complexity: -- O(1) time, memory and size. -- --
-- edge x y == connect (vertex x) (vertex y) -- hasEdge x y (edge x y) == True -- edgeCount (edge x y) == 1 -- vertexCount (edge 1 1) == 1 -- vertexCount (edge 1 2) == 2 --edge :: Ord a => a -> a -> Relation a -- | Overlay 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. -- --
-- isEmpty (overlay x y) == isEmpty x && 'iAlgebra.Graph.Relation.sEmpty' y -- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 --overlay :: Ord a => Relation a -> Relation a -> Relation a -- | Connect two graphs. This is an associative operation with the -- identity empty, which distributes over overlay and obeys -- the decomposition axiom. Complexity: O((n + m) * log(n)) time -- and O(n + m) memory. Note that the number of edges in the -- resulting graph is quadratic with respect to the number of vertices of -- the arguments: m = O(m1 + m2 + n1 * n2). -- --
-- isEmpty (connect x y) == isEmpty x && isEmpty y -- hasVertex z (connect x y) == hasVertex z x || hasVertex z y -- vertexCount (connect x y) >= vertexCount x -- vertexCount (connect x y) <= vertexCount x + vertexCount y -- edgeCount (connect x y) >= edgeCount x -- edgeCount (connect x y) >= edgeCount y -- edgeCount (connect x y) >= vertexCount x * vertexCount y -- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- vertexCount (connect 1 2) == 2 -- edgeCount (connect 1 2) == 1 --connect :: Ord a => Relation a -> Relation a -> Relation a -- | Construct 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 [] == empty -- vertices [x] == vertex x -- hasVertex x . vertices == elem x -- vertexCount . vertices == length . nub -- vertexSet . vertices == Set.fromList --vertices :: Ord a => [a] -> Relation a -- | Construct the graph from a list of edges. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- edges [] == empty -- edges [(x,y)] == edge x y -- edgeCount . edges == length . nub --edges :: Ord a => [(a, a)] -> Relation a -- | Overlay a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- overlays [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty -- isEmpty . overlays == all isEmpty --overlays :: Ord a => [Relation a] -> Relation a -- | Connect a given list of graphs. Complexity: O((n + m) * log(n)) -- time and O(n + m) memory. -- --
-- connects [] == empty -- connects [x] == x -- connects [x,y] == connect x y -- connects == foldr connect empty -- isEmpty . connects == all isEmpty --connects :: Ord a => [Relation a] -> Relation a -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O((n + m) * log(n)) time. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path xs) (circuit xs) == True -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: Ord a => Relation a -> Relation a -> Bool -- | Check if a relation is empty. Complexity: O(1) time. -- --
-- isEmpty empty == True -- isEmpty (overlay empty empty) == True -- isEmpty (vertex x) == False -- isEmpty (removeVertex x $ vertex x) == True -- isEmpty (removeEdge x y $ edge x y) == False --isEmpty :: Relation a -> Bool -- | Check if a graph contains a given vertex. Complexity: O(log(n)) -- time. -- --
-- hasVertex x empty == False -- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False -- hasVertex x . removeVertex x == const False --hasVertex :: Ord a => a -> Relation a -> Bool -- | Check if a graph contains a given edge. Complexity: O(log(n)) -- time. -- --
-- hasEdge x y empty == False -- hasEdge x y (vertex z) == False -- hasEdge x y (edge x y) == True -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == elem (x,y) . edgeList --hasEdge :: Ord a => a -> a -> Relation a -> Bool -- | The number of vertices in a graph. Complexity: O(1) time. -- --
-- vertexCount empty == 0 -- vertexCount (vertex x) == 1 -- vertexCount == length . vertexList -- vertexCount x < vertexCount y ==> x < y --vertexCount :: Relation a -> Int -- | The number of edges in a graph. Complexity: O(1) time. -- --
-- edgeCount empty == 0 -- edgeCount (vertex x) == 0 -- edgeCount (edge x y) == 1 -- edgeCount == length . edgeList --edgeCount :: Relation a -> Int -- | The sorted list of vertices of a given graph. Complexity: O(n) -- time and memory. -- --
-- vertexList empty == [] -- vertexList (vertex x) == [x] -- vertexList . vertices == nub . sort --vertexList :: Relation a -> [a] -- | The sorted list of edges of a graph. Complexity: O(n + m) time -- and O(m) memory. -- --
-- edgeList empty == [] -- edgeList (vertex x) == [] -- edgeList (edge x y) == [(x,y)] -- edgeList (star 2 [3,1]) == [(2,1), (2,3)] -- edgeList . edges == nub . sort -- edgeList . transpose == sort . map swap . edgeList --edgeList :: Relation a -> [(a, a)] -- | The sorted adjacency list of a graph. Complexity: O(n + -- m) time and O(m) memory. -- --
-- adjacencyList empty == [] -- adjacencyList (vertex x) == [(x, [])] -- adjacencyList (edge 1 2) == [(1, [2]), (2, [])] -- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] -- stars . adjacencyList == id --adjacencyList :: Eq a => Relation a -> [(a, [a])] -- | The set of vertices of a given graph. Complexity: O(1) time. -- --
-- vertexSet empty == Set.empty -- vertexSet . vertex == Set.singleton -- vertexSet . vertices == Set.fromList --vertexSet :: Relation a -> Set a -- | The set of edges of a given graph. Complexity: O(1) time. -- --
-- edgeSet empty == Set.empty -- edgeSet (vertex x) == Set.empty -- edgeSet (edge x y) == Set.singleton (x,y) -- edgeSet . edges == Set.fromList --edgeSet :: Relation a -> Set (a, a) -- | The preset of an element x is the set of elements that -- are related to it on the left, i.e. preSet x == { a | aRx -- }. 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 empty == Set.empty -- preSet x (vertex x) == Set.empty -- preSet 1 (edge 1 2) == Set.empty -- preSet y (edge x y) == Set.fromList [x] --preSet :: Ord a => a -> Relation a -> Set a -- | The postset of an element x is the set of elements -- that are related to it on the right, i.e. postSet x == { a -- | xRa }. 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 empty == Set.empty -- postSet x (vertex x) == Set.empty -- postSet x (edge x y) == Set.fromList [y] -- postSet 2 (edge 1 2) == Set.empty --postSet :: Ord a => a -> Relation a -> Set a -- | The path on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- path [] == empty -- path [x] == vertex x -- path [x,y] == edge x y -- path . reverse == transpose . path --path :: Ord a => [a] -> Relation a -- | The circuit on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- circuit [] == empty -- circuit [x] == edge x x -- circuit [x,y] == edges [(x,y), (y,x)] -- circuit . reverse == transpose . circuit --circuit :: Ord a => [a] -> Relation a -- | The clique on a list of vertices. Complexity: O((n + m) * -- log(n)) time and O(n + m) memory. -- --
-- clique [] == empty -- clique [x] == vertex x -- clique [x,y] == edge x y -- clique [x,y,z] == edges [(x,y), (x,z), (y,z)] -- clique (xs ++ ys) == connect (clique xs) (clique ys) -- clique . reverse == transpose . clique --clique :: Ord a => [a] -> Relation a -- | The biclique on two lists of vertices. Complexity: O(n * -- log(n) + m) time and O(n + m) memory. -- --
-- biclique [] [] == empty -- biclique [x] [] == vertex x -- biclique [] [y] == vertex y -- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique xs ys == connect (vertices xs) (vertices ys) --biclique :: Ord a => [a] -> [a] -> Relation a -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges [(x,y), (x,z)] -- star x ys == connect (vertex x) (vertices ys) --star :: Ord a => a -> [a] -> Relation a -- | The stars formed by overlaying a list of stars. An -- inverse of adjacencyList. Complexity: O(L * log(n)) -- time, memory and size, where L is the total size of the input. -- --
-- stars [] == empty -- stars [(x, [])] == vertex x -- stars [(x, [y])] == edge x y -- stars [(x, ys)] == star x ys -- stars == overlays . map (uncurry star) -- stars . adjacencyList == id -- overlay (stars xs) (stars ys) == stars (xs ++ ys) --stars :: Ord a => [(a, [a])] -> Relation a -- | The tree graph constructed from a given Tree data -- structure. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- tree (Node x []) == vertex x -- tree (Node x [Node y [Node z []]]) == path [x,y,z] -- tree (Node x [Node y [], Node z []]) == star x [y,z] -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges [(1,2), (1,3), (3,4), (3,5)] --tree :: Ord a => Tree a -> Relation a -- | The forest graph constructed from a given Forest data -- structure. Complexity: O((n + m) * log(n)) time and O(n + -- m) memory. -- --
-- forest [] == empty -- forest [x] == tree x -- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == edges [(1,2), (1,3), (4,5)] -- forest == overlays . map tree --forest :: Ord a => Forest a -> Relation a -- | Remove a vertex from a given graph. Complexity: O(n + m) time. -- --
-- removeVertex x (vertex x) == empty -- removeVertex 1 (vertex 2) == vertex 2 -- removeVertex x (edge x x) == empty -- removeVertex 1 (edge 1 2) == vertex 2 -- removeVertex x . removeVertex x == removeVertex x --removeVertex :: Ord a => a -> Relation a -> Relation a -- | Remove an edge from a given graph. Complexity: O(log(m)) time. -- --
-- removeEdge x y (edge x y) == vertices [x,y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . removeVertex x == removeVertex x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 -- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 --removeEdge :: Ord a => a -> a -> Relation a -> Relation a -- | The function replaceVertex 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. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == mergeVertices (== x) y --replaceVertex :: Ord a => a -> a -> Relation a -> Relation a -- | Merge 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 (const False) x == id -- mergeVertices (== x) y == replaceVertex x y -- mergeVertices even 1 (0 * 2) == 1 * 1 -- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 --mergeVertices :: Ord a => (a -> Bool) -> a -> Relation a -> Relation a -- | Transpose a given graph. Complexity: O(m * log(m)) time. -- --
-- transpose empty == empty -- transpose (vertex x) == vertex x -- transpose (edge x y) == edge y x -- transpose . transpose == id -- edgeList . transpose == sort . map swap . edgeList --transpose :: Ord a => Relation a -> Relation a -- | Transform a graph by applying a function to each of its vertices. This -- is similar to Functor's fmap but can be used with -- non-fully-parametric Relation. Complexity: O((n + m) * -- log(n)) time. -- --
-- gmap f empty == empty -- gmap f (vertex x) == vertex (f x) -- gmap f (edge x y) == edge (f x) (f y) -- gmap id == id -- gmap f . gmap g == gmap (f . g) --gmap :: Ord b => (a -> b) -> Relation a -> Relation b -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(m) time, assuming that the predicate takes O(1) to be -- evaluated. -- --
-- induce (const True ) x == x -- induce (const False) x == empty -- induce (/= x) == removeVertex x -- induce p . induce q == induce (\x -> p x && q x) -- isSubgraphOf (induce p x) x == True --induce :: (a -> Bool) -> Relation a -> Relation a -- | Left-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 -- z in the second graph. There are no isolated vertices in the -- result. This operation is associative, has empty and -- single-vertex graphs as annihilating zeroes, and -- distributes over overlay. Complexity: O(n * m * log(m)) -- time and O(n + m) memory. -- --
-- compose empty x == empty -- compose x empty == empty -- compose (vertex x) y == empty -- compose x (vertex y) == empty -- compose x (compose y z) == compose (compose x y) z -- compose x (overlay y z) == overlay (compose x y) (compose x z) -- compose (overlay x y) z == overlay (compose x z) (compose y z) -- compose (edge x y) (edge y z) == edge x z -- compose (path [1..5]) (path [1..5]) == edges [(1,3), (2,4), (3,5)] -- compose (circuit [1..5]) (circuit [1..5]) == circuit [1,3,5,2,4] --compose :: Ord a => Relation a -> Relation a -> Relation a -- | Compute the reflexive and transitive closure of a graph. -- Complexity: O(n * m * log(n) * log(m)) time. -- --
-- closure empty == empty -- closure (vertex x) == edge x x -- closure (edge x x) == edge x x -- closure (edge x y) == edges [(x,x), (x,y), (y,y)] -- closure (path $ nub xs) == reflexiveClosure (clique $ nub xs) -- closure == reflexiveClosure . transitiveClosure -- closure == transitiveClosure . reflexiveClosure -- closure . closure == closure -- postSet x (closure y) == Set.fromList (reachable x y) --closure :: Ord a => Relation a -> Relation a -- | Compute the reflexive closure of a graph. Complexity: O(n * -- log(m)) time. -- --
-- reflexiveClosure empty == empty -- reflexiveClosure (vertex x) == edge x x -- reflexiveClosure (edge x x) == edge x x -- reflexiveClosure (edge x y) == edges [(x,x), (x,y), (y,y)] -- reflexiveClosure . reflexiveClosure == reflexiveClosure --reflexiveClosure :: Ord a => Relation a -> Relation a -- | Compute the symmetric closure of a graph. Complexity: O(m * -- log(m)) time. -- --
-- symmetricClosure empty == empty -- symmetricClosure (vertex x) == vertex x -- symmetricClosure (edge x y) == edges [(x,y), (y,x)] -- symmetricClosure x == overlay x (transpose x) -- symmetricClosure . symmetricClosure == symmetricClosure --symmetricClosure :: Ord a => Relation a -> Relation a -- | Compute the transitive closure of a graph. Complexity: O(n * -- m * log(n) * log(m)) time. -- --
-- transitiveClosure empty == empty -- transitiveClosure (vertex x) == vertex x -- transitiveClosure (edge x y) == edge x y -- transitiveClosure (path $ nub xs) == clique (nub xs) -- transitiveClosure . transitiveClosure == transitiveClosure --transitiveClosure :: Ord a => Relation a -> Relation a -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module provides primitives for interoperability between this -- library and the Data.Graph module of the containers library. It -- is for internal use only and may be removed without notice at any -- point. module Data.Graph.Typed -- | GraphKL encapsulates King-Launchbury graphs, which are -- implemented in the Data.Graph module of the containers -- library. data GraphKL a GraphKL :: Graph -> (Vertex -> a) -> (a -> Maybe Vertex) -> GraphKL a -- | Array-based graph representation (King and Launchbury, 1995). [toGraphKL] :: GraphKL a -> Graph -- | A mapping of Data.Graph.Vertex to vertices of type a. -- This is partial and may fail if the vertex is out of bounds. [fromVertexKL] :: GraphKL a -> Vertex -> a -- | A mapping from vertices of type a to -- Data.Graph.Vertex. Returns Nothing if the argument is -- not in the graph. [toVertexKL] :: GraphKL a -> a -> Maybe Vertex -- | Build GraphKL from an AdjacencyMap. If -- fromAdjacencyMap g == h then the following holds: -- --
-- map (fromVertexKL h) (vertices $ toGraphKL h) == vertexList g -- map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g -- toGraphKL (fromAdjacencyMap (1 * 2 + 3 * 1)) == array (0,2) [(0,[1]), (1,[]), (2,[0])] -- toGraphKL (fromAdjacencyMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])] --fromAdjacencyMap :: Ord a => AdjacencyMap a -> GraphKL a -- | Build GraphKL from an AdjacencyIntMap. If -- fromAdjacencyIntMap g == h then the following holds: -- --
-- map (fromVertexKL h) (vertices $ toGraphKL h) == toAscList (vertexIntSet g) -- map (\(x, y) -> (fromVertexKL h x, fromVertexKL h y)) (edges $ toGraphKL h) == edgeList g -- toGraphKL (fromAdjacencyIntMap (1 * 2 + 3 * 1)) == array (0,2) [(0,[1]), (1,[]), (2,[0])] -- toGraphKL (fromAdjacencyIntMap (1 * 2 + 2 * 1)) == array (0,1) [(0,[1]), (1,[0])] --fromAdjacencyIntMap :: AdjacencyIntMap -> GraphKL Int -- | Compute the depth-first search forest of a graph. -- -- In the following we will use the helper function: -- --
-- (%) :: (GraphKL Int -> a) -> AM.AdjacencyMap Int -> a -- a % g = a $ fromAdjacencyMap g ---- -- for greater clarity. (One could use an AdjacencyIntMap just as well) -- --
-- forest (dfsForest % edge 1 1) == vertex 1
-- forest (dfsForest % edge 1 2) == edge 1 2
-- forest (dfsForest % edge 2 1) == vertices [1, 2]
-- isSubgraphOf (forest $ dfsForest % x) x == True
-- dfsForest % forest (dfsForest % x) == dfsForest % x
-- dfsForest % vertices vs == map (\v -> Node v []) (nub $ sort vs)
-- dfsForestFrom (vertexList 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 = [] }]}]
--
dfsForest :: GraphKL a -> Forest a
-- | Compute the depth-first search forest of a graph, searching
-- from each of the given vertices in order. Note that the resulting
-- forest does not necessarily span the whole graph, as some vertices may
-- be unreachable.
--
--
-- forest (dfsForestFrom [1] % edge 1 1) == vertex 1
-- forest (dfsForestFrom [1] % edge 1 2) == edge 1 2
-- forest (dfsForestFrom [2] % edge 1 2) == vertex 2
-- forest (dfsForestFrom [3] % edge 1 2) == empty
-- forest (dfsForestFrom [2, 1] % edge 1 2) == vertices [1, 2]
-- isSubgraphOf (forest $ dfsForestFrom vs % x) x == True
-- dfsForestFrom (vertexList x) % x == dfsForest % x
-- dfsForestFrom vs % vertices vs == map (\v -> Node v []) (nub vs)
-- dfsForestFrom [] % x == []
-- dfsForestFrom [1, 4] % (3 * (1 + 4) * (1 + 5)) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }
-- , Node { rootLabel = 4
-- , subForest = [] }]
--
dfsForestFrom :: [a] -> GraphKL a -> Forest a
-- | Compute the list of vertices visited by the depth-first search
-- in a graph, when searching from each of the given vertices in order.
--
-- -- dfs [1] % edge 1 1 == [1] -- dfs [1] % edge 1 2 == [1,2] -- dfs [2] % edge 1 2 == [2] -- dfs [3] % edge 1 2 == [] -- dfs [1,2] % edge 1 2 == [1,2] -- dfs [2,1] % edge 1 2 == [2,1] -- dfs [] % x == [] -- dfs [1,4] % (3 * (1 + 4) * (1 + 5)) == [1, 5, 4] -- isSubgraphOf (vertices $ dfs vs x) x == True --dfs :: [a] -> GraphKL a -> [a] -- | Compute the topological sort of a graph. Unlike the -- (Int)AdjacencyMap algorithm this returns a result even if the graph is -- cyclic. -- --
-- topSort % (1 * 2 + 3 * 1) == [3,1,2] -- topSort % (1 * 2 + 2 * 1) == [1,2] --topSort :: GraphKL a -> [a] -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module provides basic graph algorithms, such as depth-first -- search, implemented for the Algebra.Graph.AdjacencyMap data -- type. module Algebra.Graph.AdjacencyMap.Algorithm -- | Compute the depth-first search forest of a graph that -- corresponds to searching from each of the graph vertices in the -- Ord a order. -- --
-- dfsForest empty == []
-- forest (dfsForest $ edge 1 1) == vertex 1
-- forest (dfsForest $ edge 1 2) == edge 1 2
-- forest (dfsForest $ edge 2 1) == vertices [1,2]
-- isSubgraphOf (forest $ dfsForest x) x == True
-- isDfsForestOf (dfsForest x) x == True
-- dfsForest . forest . dfsForest == dfsForest
-- dfsForest (vertices vs) == map (\v -> Node v []) (nub $ sort vs)
-- dfsForestFrom (vertexList 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 = [] }]}]
--
dfsForest :: Ord a => AdjacencyMap a -> Forest a
-- | Compute the depth-first search forest of a graph, searching
-- from each of the given vertices in order. Note that the resulting
-- forest does not necessarily span the whole graph, as some vertices may
-- be unreachable.
--
--
-- dfsForestFrom vs empty == []
-- forest (dfsForestFrom [1] $ edge 1 1) == vertex 1
-- forest (dfsForestFrom [1] $ edge 1 2) == edge 1 2
-- forest (dfsForestFrom [2] $ edge 1 2) == vertex 2
-- forest (dfsForestFrom [3] $ edge 1 2) == empty
-- forest (dfsForestFrom [2,1] $ edge 1 2) == vertices [1,2]
-- isSubgraphOf (forest $ dfsForestFrom vs x) x == True
-- isDfsForestOf (dfsForestFrom (vertexList x) x) x == True
-- dfsForestFrom (vertexList x) x == dfsForest x
-- dfsForestFrom vs (vertices vs) == map (\v -> Node v []) (nub vs)
-- dfsForestFrom [] x == []
-- dfsForestFrom [1,4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }
-- , Node { rootLabel = 4
-- , subForest = [] }]
--
dfsForestFrom :: Ord a => [a] -> AdjacencyMap a -> Forest a
-- | Compute the list of vertices visited by the depth-first search
-- in a graph, when searching from each of the given vertices in order.
--
-- -- dfs vs $ empty == [] -- dfs [1] $ edge 1 1 == [1] -- dfs [1] $ edge 1 2 == [1,2] -- dfs [2] $ edge 1 2 == [2] -- dfs [3] $ edge 1 2 == [] -- dfs [1,2] $ edge 1 2 == [1,2] -- dfs [2,1] $ edge 1 2 == [2,1] -- dfs [] $ x == [] -- dfs [1,4] $ 3 * (1 + 4) * (1 + 5) == [1,5,4] -- isSubgraphOf (vertices $ dfs vs x) x == True --dfs :: Ord a => [a] -> AdjacencyMap a -> [a] -- | 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 $ empty == [] -- reachable 1 $ vertex 1 == [1] -- reachable 1 $ vertex 2 == [] -- reachable 1 $ edge 1 1 == [1] -- reachable 1 $ edge 1 2 == [1,2] -- reachable 4 $ path [1..8] == [4..8] -- reachable 4 $ circuit [1..8] == [4..8] ++ [1..3] -- reachable 8 $ clique [8,7..1] == [8] ++ [1..7] -- isSubgraphOf (vertices $ reachable x y) y == True --reachable :: Ord a => a -> AdjacencyMap a -> [a] -- | Compute the topological sort of a graph or return -- Nothing if the graph is cyclic. -- --
-- topSort (1 * 2 + 3 * 1) == Just [3,1,2] -- topSort (1 * 2 + 2 * 1) == Nothing -- fmap (flip isTopSortOf x) (topSort x) /= Just False -- isJust . topSort == isAcyclic --topSort :: Ord a => AdjacencyMap a -> Maybe [a] -- | Check if a given graph is acyclic. -- --
-- isAcyclic (1 * 2 + 3 * 1) == True -- isAcyclic (1 * 2 + 2 * 1) == False -- isAcyclic . circuit == null -- isAcyclic == isJust . topSort --isAcyclic :: Ord a => AdjacencyMap a -> Bool -- | Compute the condensation 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 empty == empty -- scc (vertex x) == vertex (NonEmpty.vertex x) -- scc (edge 1 1) == vertex (NonEmpty.edge 1 1) -- scc (edge 1 2) == edge (NonEmpty.vertex 1) (NonEmpty.vertex 2) -- scc (circuit (1:xs)) == vertex (NonEmpty.circuit1 (1 :| xs)) -- scc (3 * 1 * 4 * 1 * 5) == edges [ (NonEmpty.vertex 3 , NonEmpty.vertex 5 ) -- , (NonEmpty.vertex 3 , NonEmpty.clique1 [1,4,1]) -- , (NonEmpty.clique1 [1,4,1], NonEmpty.vertex 5 ) ] -- isAcyclic . scc == const True -- isAcyclic x == (scc x == gmap NonEmpty.vertex x) --scc :: Ord a => AdjacencyMap a -> AdjacencyMap (AdjacencyMap a) -- | 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 [] empty == True -- isDfsForestOf [] (vertex 1) == False -- isDfsForestOf [Node 1 []] (vertex 1) == True -- isDfsForestOf [Node 1 []] (vertex 2) == False -- isDfsForestOf [Node 1 [], Node 1 []] (vertex 1) == False -- isDfsForestOf [Node 1 []] (edge 1 1) == True -- isDfsForestOf [Node 1 []] (edge 1 2) == False -- isDfsForestOf [Node 1 [], Node 2 []] (edge 1 2) == False -- isDfsForestOf [Node 2 [], Node 1 []] (edge 1 2) == True -- isDfsForestOf [Node 1 [Node 2 []]] (edge 1 2) == True -- isDfsForestOf [Node 1 [], Node 2 []] (vertices [1,2]) == True -- isDfsForestOf [Node 2 [], Node 1 []] (vertices [1,2]) == True -- isDfsForestOf [Node 1 [Node 2 []]] (vertices [1,2]) == False -- isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] (path [1,2,3]) == True -- isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] (path [1,2,3]) == False -- isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (path [1,2,3]) == True -- isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (path [1,2,3]) == True -- isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] (path [1,2,3]) == False --isDfsForestOf :: Ord a => Forest a -> AdjacencyMap a -> Bool -- | 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 [] empty == True -- isTopSortOf [x] (vertex x) == True -- isTopSortOf [x] (edge x x) == False --isTopSortOf :: Ord a => [a] -> AdjacencyMap a -> Bool -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module provides basic graph algorithms, such as depth-first -- search, implemented for the Algebra.Graph.AdjacencyIntMap -- data type. module Algebra.Graph.AdjacencyIntMap.Algorithm -- | Compute the depth-first search forest of a graph that -- corresponds to searching from each of the graph vertices in the -- Ord a order. -- --
-- dfsForest empty == []
-- forest (dfsForest $ edge 1 1) == vertex 1
-- forest (dfsForest $ edge 1 2) == edge 1 2
-- forest (dfsForest $ edge 2 1) == vertices [1,2]
-- isSubgraphOf (forest $ dfsForest x) x == True
-- isDfsForestOf (dfsForest x) x == True
-- dfsForest . forest . dfsForest == dfsForest
-- dfsForest (vertices vs) == map (\v -> Node v []) (nub $ sort vs)
-- dfsForestFrom (vertexList 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 = [] }]}]
--
dfsForest :: AdjacencyIntMap -> Forest Int
-- | Compute the depth-first search forest of a graph, searching
-- from each of the given vertices in order. Note that the resulting
-- forest does not necessarily span the whole graph, as some vertices may
-- be unreachable.
--
--
-- dfsForestFrom vs empty == []
-- forest (dfsForestFrom [1] $ edge 1 1) == vertex 1
-- forest (dfsForestFrom [1] $ edge 1 2) == edge 1 2
-- forest (dfsForestFrom [2] $ edge 1 2) == vertex 2
-- forest (dfsForestFrom [3] $ edge 1 2) == empty
-- forest (dfsForestFrom [2,1] $ edge 1 2) == vertices [1,2]
-- isSubgraphOf (forest $ dfsForestFrom vs x) x == True
-- isDfsForestOf (dfsForestFrom (vertexList x) x) x == True
-- dfsForestFrom (vertexList x) x == dfsForest x
-- dfsForestFrom vs (vertices vs) == map (\v -> Node v []) (nub vs)
-- dfsForestFrom [] x == []
-- dfsForestFrom [1,4] $ 3 * (1 + 4) * (1 + 5) == [ Node { rootLabel = 1
-- , subForest = [ Node { rootLabel = 5
-- , subForest = [] }
-- , Node { rootLabel = 4
-- , subForest = [] }]
--
dfsForestFrom :: [Int] -> AdjacencyIntMap -> Forest Int
-- | Compute the list of vertices visited by the depth-first search
-- in a graph, when searching from each of the given vertices in order.
--
-- -- dfs vs $ empty == [] -- dfs [1] $ edge 1 1 == [1] -- dfs [1] $ edge 1 2 == [1,2] -- dfs [2] $ edge 1 2 == [2] -- dfs [3] $ edge 1 2 == [] -- dfs [1,2] $ edge 1 2 == [1,2] -- dfs [2,1] $ edge 1 2 == [2,1] -- dfs [] $ x == [] -- dfs [1,4] $ 3 * (1 + 4) * (1 + 5) == [1,5,4] -- isSubgraphOf (vertices $ dfs vs x) x == True --dfs :: [Int] -> AdjacencyIntMap -> [Int] -- | 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 $ empty == [] -- reachable 1 $ vertex 1 == [1] -- reachable 1 $ vertex 2 == [] -- reachable 1 $ edge 1 1 == [1] -- reachable 1 $ edge 1 2 == [1,2] -- reachable 4 $ path [1..8] == [4..8] -- reachable 4 $ circuit [1..8] == [4..8] ++ [1..3] -- reachable 8 $ clique [8,7..1] == [8] ++ [1..7] -- isSubgraphOf (vertices $ reachable x y) y == True --reachable :: Int -> AdjacencyIntMap -> [Int] -- | Compute the topological sort of a graph or return -- Nothing if the graph is cyclic. -- --
-- topSort (1 * 2 + 3 * 1) == Just [3,1,2] -- topSort (1 * 2 + 2 * 1) == Nothing -- fmap (flip isTopSortOf x) (topSort x) /= Just False -- isJust . topSort == isAcyclic --topSort :: AdjacencyIntMap -> Maybe [Int] -- | Check if a given graph is acyclic. -- --
-- isAcyclic (1 * 2 + 3 * 1) == True -- isAcyclic (1 * 2 + 2 * 1) == False -- isAcyclic . circuit == null -- isAcyclic == isJust . topSort --isAcyclic :: AdjacencyIntMap -> Bool -- | 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 [] empty == True -- isDfsForestOf [] (vertex 1) == False -- isDfsForestOf [Node 1 []] (vertex 1) == True -- isDfsForestOf [Node 1 []] (vertex 2) == False -- isDfsForestOf [Node 1 [], Node 1 []] (vertex 1) == False -- isDfsForestOf [Node 1 []] (edge 1 1) == True -- isDfsForestOf [Node 1 []] (edge 1 2) == False -- isDfsForestOf [Node 1 [], Node 2 []] (edge 1 2) == False -- isDfsForestOf [Node 2 [], Node 1 []] (edge 1 2) == True -- isDfsForestOf [Node 1 [Node 2 []]] (edge 1 2) == True -- isDfsForestOf [Node 1 [], Node 2 []] (vertices [1,2]) == True -- isDfsForestOf [Node 2 [], Node 1 []] (vertices [1,2]) == True -- isDfsForestOf [Node 1 [Node 2 []]] (vertices [1,2]) == False -- isDfsForestOf [Node 1 [Node 2 [Node 3 []]]] (path [1,2,3]) == True -- isDfsForestOf [Node 1 [Node 3 [Node 2 []]]] (path [1,2,3]) == False -- isDfsForestOf [Node 3 [], Node 1 [Node 2 []]] (path [1,2,3]) == True -- isDfsForestOf [Node 2 [Node 3 []], Node 1 []] (path [1,2,3]) == True -- isDfsForestOf [Node 1 [], Node 2 [Node 3 []]] (path [1,2,3]) == False --isDfsForestOf :: Forest Int -> AdjacencyIntMap -> Bool -- | 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 [] empty == True -- isTopSortOf [x] (vertex x) == True -- isTopSortOf [x] (edge x x) == False --isTopSortOf :: [Int] -> AdjacencyIntMap -> Bool -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the type class ToGraph for capturing data -- types that can be converted to algebraic graphs. To make an instance -- of this class you need to define just a single method (toGraph -- or foldg), which gives you access to many other useful methods -- for free (although note that the default implementations may be -- suboptimal performance-wise). -- -- This type class is similar to the standard type class Foldable -- defined for lists. Furthermore, one can define Foldable methods -- foldMap and toList using ToGraph.foldg: -- --
-- foldMap f = foldg mempty f (<>) (<>) -- toList = foldg [] pure (++) (++) ---- -- However, the resulting Foldable instance is problematic. For -- example, folding equivalent algebraic graphs 1 and 1 -- + 1 leads to different results: -- --
-- toList (1 ) == [1] -- toList (1 + 1) == [1, 1] ---- -- To avoid such cases, we do not provide Foldable instances for -- algebraic graph datatypes. Furthermore, we require that the four -- arguments passed to foldg satisfy the laws of the algebra of -- graphs. The above definitions of foldMap and toList -- violate this requirement, for example [1] ++ [1] /= [1], and -- are therefore disallowed. module Algebra.Graph.ToGraph -- | The ToGraph 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. class ToGraph t where { -- | The type of vertices of the resulting graph. type family ToVertex t; } -- | Convert a value to the corresponding algebraic graph, see -- Algebra.Graph. -- --
-- toGraph == foldg Empty Vertex Overlay Connect --toGraph :: ToGraph t => t -> Graph (ToVertex t) -- | The method foldg 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.foldg . toGraph --foldg :: ToGraph t => r -> (ToVertex t -> r) -> (r -> r -> r) -> (r -> r -> r) -> t -> r -- | Check if a graph is empty. -- --
-- isEmpty == foldg True (const False) (&&) (&&) --isEmpty :: ToGraph t => t -> Bool -- | The size of a graph, i.e. the number of leaves of the -- expression including empty leaves. -- -- Note: The default implementation of this function violates the -- requirement that the four arguments of foldg should satisfy the -- laws of algebraic graphs, since 1 + 1 /= 1. Use this function -- with care. -- --
-- size == foldg 1 (const 1) (+) (+) --size :: ToGraph t => t -> Int -- | Check if a graph contains a given vertex. -- --
-- hasVertex x == foldg False (==x) (||) (||) --hasVertex :: (ToGraph t, Eq (ToVertex t)) => ToVertex t -> t -> Bool -- | Check if a graph contains a given edge. -- --
-- hasEdge x y == Algebra.Graph.hasEdge x y . toGraph --hasEdge :: (ToGraph t, Eq (ToVertex t)) => ToVertex t -> ToVertex t -> t -> Bool -- | The number of vertices in a graph. -- --
-- vertexCount == Set.size . vertexSet --vertexCount :: (ToGraph t, Ord (ToVertex t)) => t -> Int -- | The number of edges in a graph. -- --
-- edgeCount == Set.size . edgeSet --edgeCount :: (ToGraph t, Ord (ToVertex t)) => t -> Int -- | The sorted list of vertices of a given graph. -- --
-- vertexList == Set.toAscList . vertexSet --vertexList :: (ToGraph t, Ord (ToVertex t)) => t -> [ToVertex t] -- | The sorted list of edges of a graph. -- --
-- edgeList == Set.toAscList . edgeSet --edgeList :: (ToGraph t, Ord (ToVertex t)) => t -> [(ToVertex t, ToVertex t)] -- | The set of vertices of a graph. -- --
-- vertexSet == foldg Set.empty Set.singleton Set.union Set.union --vertexSet :: (ToGraph t, Ord (ToVertex t)) => t -> Set (ToVertex t) -- | The set of vertices of a graph. Like vertexSet but specialised -- for graphs with vertices of type Int. -- --
-- vertexIntSet == foldg IntSet.empty IntSet.singleton IntSet.union IntSet.union --vertexIntSet :: (ToGraph t, ToVertex t ~ Int) => t -> IntSet -- | The set of edges of a graph. -- --
-- edgeSet == Algebra.Graph.AdjacencyMap.edgeSet . toAdjacencyMap --edgeSet :: (ToGraph t, Ord (ToVertex t)) => t -> Set (ToVertex t, ToVertex t) -- | The preset of a vertex is the set of its direct -- predecessors. -- --
-- preSet x == Algebra.Graph.AdjacencyMap.preSet x . toAdjacencyMap --preSet :: (ToGraph t, Ord (ToVertex t)) => ToVertex t -> t -> Set (ToVertex t) -- | The preset (here preIntSet) of a vertex is the set of -- its direct predecessors. Like preSet but specialised for -- graphs with vertices of type Int. -- --
-- preIntSet x == Algebra.Graph.AdjacencyIntMap.preIntSet x . toAdjacencyIntMap --preIntSet :: (ToGraph t, ToVertex t ~ Int) => Int -> t -> IntSet -- | The postset of a vertex is the set of its direct -- successors. -- --
-- postSet x == Algebra.Graph.AdjacencyMap.postSet x . toAdjacencyMap --postSet :: (ToGraph t, Ord (ToVertex t)) => ToVertex t -> t -> Set (ToVertex t) -- | The postset (here postIntSet) of a vertex is the set -- of its direct successors. Like postSet but specialised -- for graphs with vertices of type Int. -- --
-- postIntSet x == Algebra.Graph.AdjacencyIntMap.postIntSet x . toAdjacencyIntMap --postIntSet :: (ToGraph t, ToVertex t ~ Int) => Int -> t -> IntSet -- | The sorted adjacency list of a graph. -- --
-- adjacencyList == Algebra.Graph.AdjacencyMap.adjacencyList . toAdjacencyMap --adjacencyList :: (ToGraph t, Ord (ToVertex t)) => t -> [(ToVertex t, [ToVertex t])] -- | The adjacency map of a graph: each vertex is associated with a -- set of its direct successors. -- --
-- adjacencyMap == Algebra.Graph.AdjacencyMap.adjacencyMap . toAdjacencyMap --adjacencyMap :: (ToGraph t, Ord (ToVertex t)) => t -> Map (ToVertex t) (Set (ToVertex t)) -- | The adjacency map of a graph: each vertex is associated with a -- set of its direct successors. Like adjacencyMap but -- specialised for graphs with vertices of type Int. -- --
-- adjacencyIntMap == Algebra.Graph.AdjacencyIntMap.adjacencyIntMap . toAdjacencyIntMap --adjacencyIntMap :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet -- | The transposed adjacency map of a graph: each vertex is -- associated with a set of its direct predecessors. -- --
-- adjacencyMapTranspose == Algebra.Graph.AdjacencyMap.adjacencyMap . toAdjacencyMapTranspose --adjacencyMapTranspose :: (ToGraph t, Ord (ToVertex t)) => t -> Map (ToVertex t) (Set (ToVertex t)) -- | The transposed adjacency map of a graph: each vertex is -- associated with a set of its direct predecessors. Like -- adjacencyMapTranspose but specialised for graphs with vertices -- of type Int. -- --
-- adjacencyIntMapTranspose == Algebra.Graph.AdjacencyIntMap.adjacencyIntMap . toAdjacencyIntMapTranspose --adjacencyIntMapTranspose :: (ToGraph t, ToVertex t ~ Int) => t -> IntMap IntSet -- | Compute the depth-first search forest of a graph that -- corresponds to searching from each of the graph vertices in the -- Ord a order. -- --
-- dfsForest == Algebra.Graph.AdjacencyMap.dfsForest . toAdjacencyMap --dfsForest :: (ToGraph t, Ord (ToVertex t)) => t -> Forest (ToVertex t) -- | Compute the depth-first search forest of a graph, searching -- from each of the given vertices in order. Note that the resulting -- forest does not necessarily span the whole graph, as some vertices may -- be unreachable. -- --
-- dfsForestFrom vs == Algebra.Graph.AdjacencyMap.dfsForestFrom vs . toAdjacencyMap --dfsForestFrom :: (ToGraph t, Ord (ToVertex t)) => [ToVertex t] -> t -> Forest (ToVertex t) -- | Compute the list of vertices visited by the depth-first search -- in a graph, when searching from each of the given vertices in order. -- --
-- dfs vs == Algebra.Graph.AdjacencyMap.dfs vs . toAdjacencyMap --dfs :: (ToGraph t, Ord (ToVertex t)) => [ToVertex t] -> t -> [ToVertex t] -- | 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.reachable x . toAdjacencyMap --reachable :: (ToGraph t, Ord (ToVertex t)) => ToVertex t -> t -> [ToVertex t] -- | Compute the topological sort of a graph or return -- Nothing if the graph is cyclic. -- --
-- topSort == Algebra.Graph.AdjacencyMap.topSort . toAdjacencyMap --topSort :: (ToGraph t, Ord (ToVertex t)) => t -> Maybe [ToVertex t] -- | Check if a given graph is acyclic. -- --
-- isAcyclic == Algebra.Graph.AdjacencyMap.isAcyclic . toAdjacencyMap --isAcyclic :: (ToGraph t, Ord (ToVertex t)) => t -> Bool -- | Convert a value to the corresponding AdjacencyMap. -- --
-- toAdjacencyMap == foldg empty vertex overlay connect --toAdjacencyMap :: (ToGraph t, Ord (ToVertex t)) => t -> AdjacencyMap (ToVertex t) -- | Convert a value to the corresponding AdjacencyMap and transpose -- the result. -- --
-- toAdjacencyMapTranspose == foldg empty vertex overlay (flip connect) --toAdjacencyMapTranspose :: (ToGraph t, Ord (ToVertex t)) => t -> AdjacencyMap (ToVertex t) -- | Convert a value to the corresponding AdjacencyIntMap. -- --
-- toAdjacencyIntMap == foldg empty vertex overlay connect --toAdjacencyIntMap :: (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap -- | Convert a value to the corresponding AdjacencyIntMap and -- transpose the result. -- --
-- toAdjacencyIntMapTranspose == foldg empty vertex overlay (flip connect) --toAdjacencyIntMapTranspose :: (ToGraph t, ToVertex t ~ Int) => t -> AdjacencyIntMap -- | Check if a given forest is a valid depth-first search forest of -- a graph. -- --
-- isDfsForestOf f == Algebra.Graph.AdjacencyMap.isDfsForestOf f . toAdjacencyMap --isDfsForestOf :: (ToGraph t, Ord (ToVertex t)) => Forest (ToVertex t) -> t -> Bool -- | Check if a given list of vertices is a valid topological sort -- of a graph. -- --
-- isTopSortOf vs == Algebra.Graph.AdjacencyMap.isTopSortOf vs . toAdjacencyMap --isTopSortOf :: (ToGraph t, Ord (ToVertex t)) => [ToVertex t] -> t -> Bool instance GHC.Classes.Ord a => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.Graph a) instance GHC.Classes.Ord a => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a) instance Algebra.Graph.ToGraph.ToGraph Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap instance (GHC.Classes.Eq e, GHC.Base.Monoid e, GHC.Classes.Ord a) => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.Labelled.Graph e a) instance (GHC.Classes.Eq e, GHC.Base.Monoid e, GHC.Classes.Ord a) => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.Labelled.AdjacencyMap.Internal.AdjacencyMap e a) instance GHC.Classes.Ord a => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.NonEmpty.AdjacencyMap.Internal.AdjacencyMap a) instance GHC.Classes.Ord a => Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.Relation.Internal.Relation a) -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the data type Graph for algebraic graphs -- that are known to be non-empty at compile time. To avoid name clashes -- with Algebra.Graph, this module can be imported qualified: -- --
-- import qualified Algebra.Graph.NonEmpty as NonEmpty ---- -- The naming convention generally follows that of -- Data.List.NonEmpty: we use suffix 1 to indicate the -- functions whose interface must be changed compared to -- Algebra.Graph, e.g. vertices1. module Algebra.Graph.NonEmpty -- | Non-empty algebraic graphs, which are constructed using three -- primitives: vertex, overlay and connect. See -- module Algebra.Graph for algebraic graphs that can be empty. -- -- We define a Num 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 signum method of the type class Num -- cannot be implemented and will throw an error. Furthermore, the -- Num instance does not satisfy several "customary laws" of -- Num, which dictate that fromInteger 0 and -- fromInteger 1 should act as additive and -- multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Eq instance satisfies the following laws of non-empty -- algebraic graphs. -- --
x -- + y == y + x x + (y + z) == (x + y) + z x + x == x
x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x * y + x -- + y == x * y x * x * x == x * x
-- n == vertexCount g -- m == edgeCount g -- s == size g ---- -- Converting a Graph to the corresponding AdjacencyMap -- 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 Ord on graphs is defined using -- size-lexicographic comparison: -- --
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- x <= x + y -- x + y <= x * y --data Graph a Vertex :: a -> Graph a Overlay :: Graph a -> Graph a -> Graph a Connect :: Graph a -> Graph a -> Graph a -- | Convert an algebraic graph (from Algebra.Graph) into a -- non-empty algebraic graph. Returns Nothing if the argument is -- empty. Complexity: O(s) time, memory and size. -- --
-- toNonEmpty empty == Nothing -- toNonEmpty (toGraph x) == Just (x :: Graph a) --toNonEmpty :: Graph a -> Maybe (Graph a) -- | Construct the graph comprising a single isolated vertex. An -- alias for the constructor Vertex. Complexity: O(1) time, -- memory and size. -- --
-- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 -- size (vertex x) == 1 --vertex :: a -> Graph a -- | Construct the graph comprising a single edge. Complexity: -- O(1) time, memory and size. -- --
-- edge x y == connect (vertex x) (vertex y) -- hasEdge x y (edge x y) == True -- edgeCount (edge x y) == 1 -- vertexCount (edge 1 1) == 1 -- vertexCount (edge 1 2) == 2 --edge :: a -> a -> Graph a -- | Overlay two graphs. An alias for the constructor -- Overlay. This is a commutative, associative and idempotent -- operation. Complexity: O(1) time and memory, O(s1 + s2) -- size. -- --
-- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- size (overlay x y) == size x + size y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 --overlay :: Graph a -> Graph a -> Graph a -- | Overlay a possibly empty graph (from Algebra.Graph) with a -- non-empty graph. If the first argument is empty, the function -- returns the second argument; otherwise it is semantically the same as -- overlay. Complexity: O(s1) time and memory, and O(s1 -- + s2) size. -- --
-- overlay1 empty x == x -- x /= empty ==> overlay1 x y == overlay (fromJust $ toNonEmpty x) y --overlay1 :: Graph a -> Graph a -> Graph a -- | Connect two graphs. An alias for the constructor -- Connect. This is an associative operation, which distributes -- over overlay and obeys the decomposition axiom. Complexity: -- O(1) time and memory, O(s1 + s2) size. Note that the -- number of edges in the resulting graph is quadratic with respect to -- the number of vertices of the arguments: m = O(m1 + m2 + n1 * -- n2). -- --
-- hasVertex z (connect x y) == hasVertex z x || hasVertex z y -- vertexCount (connect x y) >= vertexCount x -- vertexCount (connect x y) <= vertexCount x + vertexCount y -- edgeCount (connect x y) >= edgeCount x -- edgeCount (connect x y) >= edgeCount y -- edgeCount (connect x y) >= vertexCount x * vertexCount y -- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- size (connect x y) == size x + size y -- vertexCount (connect 1 2) == 2 -- edgeCount (connect 1 2) == 1 --connect :: Graph a -> Graph a -> Graph a -- | Construct 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] == vertex x -- hasVertex x . vertices1 == elem x -- vertexCount . vertices1 == length . nub -- vertexSet . vertices1 == Set.fromList . toList --vertices1 :: NonEmpty a -> Graph a -- | Construct 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)] == edge x y -- edgeCount . edges1 == length . nub --edges1 :: NonEmpty (a, a) -> Graph a -- | Overlay a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- overlays1 [x] == x -- overlays1 [x,y] == overlay x y --overlays1 :: NonEmpty (Graph a) -> Graph a -- | Connect a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- connects1 [x] == x -- connects1 [x,y] == connect x y --connects1 :: NonEmpty (Graph a) -> Graph a -- | Generalised graph folding: recursively collapse a Graph by -- applying the provided functions to the leaves and internal nodes of -- the expression. The order of arguments is: vertex, overlay and -- connect. Complexity: O(s) applications of given functions. As -- an example, the complexity of size is O(s), since all -- functions have cost O(1). -- --
-- foldg1 vertex overlay connect == id -- foldg1 vertex overlay (flip connect) == transpose -- foldg1 (const 1) (+) (+) == size -- foldg1 (== x) (||) (||) == hasVertex x --foldg1 :: (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O(s + m * log(m)) time. Note that the number of -- edges m of a graph can be quadratic with respect to the -- expression size s. -- --
-- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path1 xs) (circuit1 xs) == True -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool -- | Structural equality on graph expressions. Complexity: O(s) -- time. -- --
-- x === x == True -- x + y === x + y == True -- 1 + 2 === 2 + 1 == False -- x + y === x * y == False --(===) :: Eq a => Graph a -> Graph a -> Bool infix 4 === -- | The size of a graph, i.e. the number of leaves of the -- expression. Complexity: O(s) time. -- --
-- size (vertex x) == 1 -- size (overlay x y) == size x + size y -- size (connect x y) == size x + size y -- size x >= 1 -- size x >= vertexCount x --size :: Graph a -> Int -- | Check if a graph contains a given vertex. Complexity: O(s) -- time. -- --
-- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False --hasVertex :: Eq a => a -> Graph a -> Bool -- | Check if a graph contains a given edge. Complexity: O(s) time. -- --
-- hasEdge x y (vertex z) == False -- hasEdge x y (edge x y) == True -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == elem (x,y) . edgeList --hasEdge :: Eq a => a -> a -> Graph a -> Bool -- | The number of vertices in a graph. Complexity: O(s * log(n)) -- time. -- --
-- vertexCount (vertex x) == 1 -- vertexCount == length . vertexList -- vertexCount x < vertexCount y ==> x < y --vertexCount :: Ord a => Graph a -> Int -- | The number of edges in a graph. Complexity: O(s + m * log(m)) -- time. Note that the number of edges m of a graph can be -- quadratic with respect to the expression size s. -- --
-- edgeCount (vertex x) == 0 -- edgeCount (edge x y) == 1 -- edgeCount == length . edgeList --edgeCount :: Ord a => Graph a -> Int -- | The sorted list of vertices of a given graph. Complexity: O(s * -- log(n)) time and O(n) memory. -- --
-- vertexList1 (vertex x) == [x] -- vertexList1 . vertices1 == nub . sort --vertexList1 :: Ord a => Graph a -> NonEmpty a -- | The sorted list of edges of a graph. Complexity: O(s + m * -- log(m)) time and O(m) memory. Note that the number of edges -- m of a graph can be quadratic with respect to the expression -- size s. -- --
-- edgeList (vertex x) == [] -- edgeList (edge x y) == [(x,y)] -- edgeList (star 2 [3,1]) == [(2,1), (2,3)] -- edgeList . edges1 == nub . sort . toList -- edgeList . transpose == sort . map swap . edgeList --edgeList :: Ord a => Graph a -> [(a, a)] -- | The set of vertices of a given graph. Complexity: O(s * log(n)) -- time and O(n) memory. -- --
-- vertexSet . vertex == Set.singleton -- vertexSet . vertices1 == Set.fromList . toList -- vertexSet . clique1 == Set.fromList . toList --vertexSet :: Ord a => Graph a -> Set a -- | The set of edges of a given graph. Complexity: O(s * log(m)) -- time and O(m) memory. -- --
-- edgeSet (vertex x) == Set.empty -- edgeSet (edge x y) == Set.singleton (x,y) -- edgeSet . edges1 == Set.fromList . toList --edgeSet :: Ord a => Graph a -> Set (a, a) -- | The path on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- path1 [x] == vertex x -- path1 [x,y] == edge x y -- path1 . reverse == transpose . path1 --path1 :: NonEmpty a -> Graph a -- | The circuit on a list of vertices. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- circuit1 [x] == edge x x -- circuit1 [x,y] == edges1 [(x,y), (y,x)] -- circuit1 . reverse == transpose . circuit1 --circuit1 :: NonEmpty a -> Graph a -- | The clique on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- clique1 [x] == vertex x -- clique1 [x,y] == edge x y -- clique1 [x,y,z] == edges1 [(x,y), (x,z), (y,z)] -- clique1 (xs <> ys) == connect (clique1 xs) (clique1 ys) -- clique1 . reverse == transpose . clique1 --clique1 :: NonEmpty a -> Graph a -- | The biclique on two lists of vertices. Complexity: O(L1 + -- L2) time, memory and size, where L1 and L2 are the -- lengths of the given lists. -- --
-- biclique1 [x1,x2] [y1,y2] == edges1 [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique1 xs ys == connect (vertices1 xs) (vertices1 ys) --biclique1 :: NonEmpty a -> NonEmpty a -> Graph a -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges1 [(x,y), (x,z)] --star :: a -> [a] -> Graph a -- | The stars formed by overlaying a non-empty list of -- stars. Complexity: O(L) time, memory and size, where -- L is the total size of the input. -- --
-- stars1 [(x, [] )] == vertex x -- stars1 [(x, [y])] == edge x y -- stars1 [(x, ys )] == star x ys -- stars1 == overlays1 . fmap (uncurry star) -- overlay (stars1 xs) (stars1 ys) == stars1 (xs <> ys) --stars1 :: NonEmpty (a, [a]) -> Graph a -- | The tree graph constructed from a given Tree data -- structure. Complexity: O(T) time, memory and size, where -- T is the size of the given tree (i.e. the number of vertices in -- the tree). -- --
-- tree (Node x []) == vertex x -- tree (Node x [Node y [Node z []]]) == path1 [x,y,z] -- tree (Node x [Node y [], Node z []]) == star x [y,z] -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges1 [(1,2), (1,3), (3,4), (3,5)] --tree :: Tree a -> Graph a -- | Construct a mesh graph from two lists of vertices. Complexity: -- O(L1 * L2) time, memory and size, where L1 and L2 -- are the lengths of the given lists. -- --
-- mesh1 [x] [y] == vertex (x, y) -- mesh1 xs ys == box (path1 xs) (path1 ys) -- mesh1 [1,2,3] ['a', 'b'] == edges1 [ ((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')) ] --mesh1 :: NonEmpty a -> NonEmpty b -> Graph (a, b) -- | Construct a torus graph from two lists of vertices. Complexity: -- O(L1 * L2) time, memory and size, where L1 and L2 -- are the lengths of the given lists. -- --
-- torus1 [x] [y] == edge (x,y) (x,y) -- torus1 xs ys == box (circuit1 xs) (circuit1 ys) -- torus1 [1,2] ['a', 'b'] == edges1 [ ((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')) ] --torus1 :: NonEmpty a -> NonEmpty b -> Graph (a, b) -- | Remove a vertex from a given graph. Returns Nothing if the -- resulting graph is empty. Complexity: O(s) time, memory and -- size. -- --
-- removeVertex1 x (vertex x) == Nothing -- removeVertex1 1 (vertex 2) == Just (vertex 2) -- removeVertex1 x (edge x x) == Nothing -- removeVertex1 1 (edge 1 2) == Just (vertex 2) -- removeVertex1 x >=> removeVertex1 x == removeVertex1 x --removeVertex1 :: Eq a => a -> Graph a -> Maybe (Graph a) -- | Remove an edge from a given graph. Complexity: O(s) time, -- memory and size. -- --
-- removeEdge x y (edge x y) == vertices1 [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 -- size (removeEdge x y z) <= 3 * size z --removeEdge :: Eq a => a -> a -> Graph a -> Graph a -- | The function replaceVertex x y replaces vertex -- x with vertex y in a given Graph. If -- y already exists, x and y will be merged. -- Complexity: O(s) time, memory and size. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == mergeVertices (== x) y --replaceVertex :: Eq a => a -> a -> Graph a -> Graph a -- | Merge 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 (const False) x == id -- mergeVertices (== x) y == replaceVertex x y -- mergeVertices even 1 (0 * 2) == 1 * 1 -- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 --mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a -- | Split a vertex into a list of vertices with the same connectivity. -- Complexity: O(s + k * L) time, memory and size, where k -- is the number of occurrences of the vertex in the expression and -- L is the length of the given list. -- --
-- splitVertex1 x [x] == id -- splitVertex1 x [y] == replaceVertex x y -- splitVertex1 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3) --splitVertex1 :: Eq a => a -> NonEmpty a -> Graph a -> Graph a -- | Transpose a given graph. Complexity: O(s) time, memory and -- size. -- --
-- transpose (vertex x) == vertex x -- transpose (edge x y) == edge y x -- transpose . transpose == id -- transpose (box x y) == box (transpose x) (transpose y) -- edgeList . transpose == sort . map swap . edgeList --transpose :: Graph a -> Graph a -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Returns -- Nothing if the resulting graph is empty. Complexity: -- O(s) time, memory and size, assuming that the predicate takes -- O(1) to be evaluated. -- --
-- induce1 (const True ) x == Just x -- induce1 (const False) x == Nothing -- induce1 (/= x) == removeVertex1 x -- induce1 p >=> induce1 q == induce1 (\x -> p x && q x) --induce1 :: (a -> Bool) -> Graph a -> Maybe (Graph a) -- | Simplify 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) graph -- comparisons. It is guaranteed that the size of the result does not -- exceed the size of the given expression. -- --
-- simplify == id -- size (simplify x) <= size x -- simplify 1 === 1 -- simplify (1 + 1) === 1 -- simplify (1 + 2 + 1) === 1 + 2 -- simplify (1 * 1 * 1) === 1 * 1 --simplify :: Ord a => Graph a -> Graph a -- | Sparsify a graph by adding intermediate Left -- Int vertices between the original vertices (wrapping the -- latter in Right) 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. -- --
-- sort . reachable x == sort . rights . reachable (Right x) . sparsify -- vertexCount (sparsify x) <= vertexCount x + size x + 1 -- edgeCount (sparsify x) <= 3 * size x -- size (sparsify x) <= 3 * size x --sparsify :: Graph a -> Graph (Either Int a) -- | Compute the Cartesian product of graphs. Complexity: O(s1 * -- s2) time, memory and size, where s1 and s2 are the -- sizes of the given graphs. -- --
-- box (path1 [0,1]) (path1 ['a','b']) == edges1 [ ((0,'a'), (0,'b')) -- , ((0,'a'), (1,'a')) -- , ((0,'b'), (1,'b')) -- , ((1,'a'), (1,'b')) ] ---- -- Up to an isomorphism between the resulting vertex types, this -- operation is commutative, associative, -- distributes over overlay, and has singleton graphs as -- identities. Below ~~ stands for the equality up to an -- isomorphism, e.g. (x, ()) ~~ x. -- --
-- box x y ~~ box y x -- box x (box y z) ~~ box (box x y) z -- box x (overlay y z) == overlay (box x y) (box x z) -- box x (vertex ()) ~~ x -- transpose (box x y) == box (transpose x) (transpose y) -- vertexCount (box x y) == vertexCount x * vertexCount y -- edgeCount (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y --box :: Graph a -> Graph b -> Graph (a, b) instance GHC.Show.Show a => GHC.Show.Show (Algebra.Graph.NonEmpty.Graph a) instance GHC.Base.Functor Algebra.Graph.NonEmpty.Graph instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.NonEmpty.Graph a) instance Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.NonEmpty.Graph a) instance GHC.Num.Num a => GHC.Num.Num (Algebra.Graph.NonEmpty.Graph a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.NonEmpty.Graph a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.NonEmpty.Graph a) instance GHC.Base.Applicative Algebra.Graph.NonEmpty.Graph instance GHC.Base.Monad Algebra.Graph.NonEmpty.Graph -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module contains a simple example of using edge-labelled graphs -- defined in the module Algebra.Graph.Labelled for working with -- finite automata. module Algebra.Graph.Labelled.Example.Automaton -- | The alphabet of actions for ordering coffee or tea. data Alphabet -- | Order coffee Coffee :: Alphabet -- | Order tea Tea :: Alphabet -- | Cancel payment or order Cancel :: Alphabet -- | Pay for the order Pay :: Alphabet -- | The state of the order. data State -- | Choosing what to order Choice :: State -- | Making the payment Payment :: State -- | The order is complete Complete :: State -- | An example automaton for ordering coffee or tea. -- --
-- order = overlays [ Choice -<[Coffee, Tea]>- Payment -- , Choice -<[Cancel ]>- Complete -- , Payment -<[Cancel ]>- Choice -- , Payment -<[Pay ]>- Complete ] --coffeeTeaAutomaton :: Automaton Alphabet State -- | The map of State reachability. -- --
-- reachability = Map.fromList $ map (s -> (s, reachable s order)) [Choice ..] ---- -- Or, when evaluated: -- --
-- reachability = Map.fromList [ (Choice , [Choice , Payment, Complete]) -- , (Payment , [Payment , Choice , Complete]) -- , (Complete, [Complete ]) ] --reachability :: Map State [State] instance GHC.Show.Show Algebra.Graph.Labelled.Example.Automaton.State instance GHC.Classes.Ord Algebra.Graph.Labelled.Example.Automaton.State instance GHC.Classes.Eq Algebra.Graph.Labelled.Example.Automaton.State instance GHC.Enum.Enum Algebra.Graph.Labelled.Example.Automaton.State instance GHC.Enum.Bounded Algebra.Graph.Labelled.Example.Automaton.State instance GHC.Show.Show Algebra.Graph.Labelled.Example.Automaton.Alphabet instance GHC.Classes.Ord Algebra.Graph.Labelled.Example.Automaton.Alphabet instance GHC.Classes.Eq Algebra.Graph.Labelled.Example.Automaton.Alphabet instance GHC.Enum.Enum Algebra.Graph.Labelled.Example.Automaton.Alphabet instance GHC.Enum.Bounded Algebra.Graph.Labelled.Example.Automaton.Alphabet -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the Fold data type -- the Boehm-Berarducci -- encoding of algebraic graphs, which is used for generalised graph -- folding and for the implementation of polymorphic graph construction -- and transformation algorithms. Fold is an instance of type -- classes defined in modules Algebra.Graph.Class and -- Algebra.Graph.HigherKinded.Class, which can be used for -- polymorphic graph construction and manipulation. module Algebra.Graph.Fold -- | The Fold data type is the Boehm-Berarducci encoding of the core -- graph construction primitives empty, vertex, -- overlay and connect. We define a Num 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 Num instance does not satisfy several -- "customary laws" of Num, which dictate that fromInteger -- 0 and fromInteger 1 should act as additive -- and multiplicative identities, and negate as additive inverse. -- Nevertheless, overloading fromInteger, + 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 Show 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 Eq instance is currently implemented using the -- AdjacencyMap as the canonical graph representation and -- satisfies all axioms of algebraic graphs: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
-- n == vertexCount g -- m == edgeCount g -- s == size g ---- -- Note that size counts all leaves of the expression: -- --
-- vertexCount empty == 0 -- size empty == 1 -- vertexCount (vertex x) == 1 -- size (vertex x) == 1 -- vertexCount (empty + empty) == 0 -- size (empty + empty) == 2 ---- -- Converting a Fold to the corresponding AdjacencyMap -- 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: -- --
-- vertex 1 < vertex 2 -- vertex 3 < edge 1 2 -- vertex 1 < edge 1 1 -- edge 1 1 < edge 1 2 -- edge 1 2 < edge 1 1 + edge 2 2 -- edge 1 2 < edge 1 3 ---- -- Note that the resulting order refines the isSubgraphOf relation -- and is compatible with overlay and connect operations: -- --
-- isSubgraphOf x y ==> x <= y ---- --
-- empty <= x -- x <= x + y -- x + y <= x * y --data Fold a -- | Construct the empty graph. Complexity: O(1) time, memory -- and size. -- --
-- isEmpty empty == True -- hasVertex x empty == False -- vertexCount empty == 0 -- edgeCount empty == 0 -- size empty == 1 --empty :: Fold a -- | Construct the graph comprising a single isolated vertex. -- Complexity: O(1) time, memory and size. -- --
-- isEmpty (vertex x) == False -- hasVertex x (vertex x) == True -- vertexCount (vertex x) == 1 -- edgeCount (vertex x) == 0 -- size (vertex x) == 1 --vertex :: a -> Fold a -- | Construct the graph comprising a single edge. Complexity: -- O(1) time, memory and size. -- --
-- edge x y == connect (vertex x) (vertex y) -- hasEdge x y (edge x y) == True -- edgeCount (edge x y) == 1 -- vertexCount (edge 1 1) == 1 -- vertexCount (edge 1 2) == 2 --edge :: a -> a -> Fold a -- | Overlay two graphs. This is a commutative, associative and -- idempotent operation with the identity empty. Complexity: -- O(1) time and memory, O(s1 + s2) size. -- --
-- isEmpty (overlay x y) == isEmpty x && isEmpty y -- hasVertex z (overlay x y) == hasVertex z x || hasVertex z y -- vertexCount (overlay x y) >= vertexCount x -- vertexCount (overlay x y) <= vertexCount x + vertexCount y -- edgeCount (overlay x y) >= edgeCount x -- edgeCount (overlay x y) <= edgeCount x + edgeCount y -- size (overlay x y) == size x + size y -- vertexCount (overlay 1 2) == 2 -- edgeCount (overlay 1 2) == 0 --overlay :: Fold a -> Fold a -> Fold a -- | Connect two graphs. This is an associative operation with the -- identity empty, which distributes over overlay and obeys -- the decomposition axiom. Complexity: O(1) time and memory, -- O(s1 + s2) size. Note that the number of edges in the resulting -- graph is quadratic with respect to the number of vertices of the -- arguments: m = O(m1 + m2 + n1 * n2). -- --
-- isEmpty (connect x y) == isEmpty x && isEmpty y -- hasVertex z (connect x y) == hasVertex z x || hasVertex z y -- vertexCount (connect x y) >= vertexCount x -- vertexCount (connect x y) <= vertexCount x + vertexCount y -- edgeCount (connect x y) >= edgeCount x -- edgeCount (connect x y) >= edgeCount y -- edgeCount (connect x y) >= vertexCount x * vertexCount y -- edgeCount (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y -- size (connect x y) == size x + size y -- vertexCount (connect 1 2) == 2 -- edgeCount (connect 1 2) == 1 --connect :: Fold a -> Fold a -> Fold a -- | Construct 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 [] == empty -- vertices [x] == vertex x -- hasVertex x . vertices == elem x -- vertexCount . vertices == length . nub -- vertexSet . vertices == Set.fromList --vertices :: [a] -> Fold a -- | Construct the graph from a list of edges. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- edges [] == empty -- edges [(x,y)] == edge x y -- edgeCount . edges == length . nub --edges :: [(a, a)] -> Fold a -- | Overlay a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- overlays [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty -- isEmpty . overlays == all isEmpty --overlays :: [Fold a] -> Fold a -- | Connect a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- connects [] == empty -- connects [x] == x -- connects [x,y] == connect x y -- connects == foldr connect empty -- isEmpty . connects == all isEmpty --connects :: [Fold a] -> Fold a -- | Generalised Graph folding: recursively collapse a -- Graph by applying the provided functions to the leaves and -- internal nodes of the expression. The order of arguments is: empty, -- vertex, overlay and connect. Complexity: O(s) applications of -- given functions. As an example, the complexity of size is -- O(s), since all functions have cost O(1). -- --
-- foldg empty vertex overlay connect == id -- foldg empty vertex overlay (flip connect) == transpose -- foldg 1 (const 1) (+) (+) == size -- foldg True (const False) (&&) (&&) == isEmpty -- foldg False (== x) (||) (||) == hasVertex x --foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Fold a -> b -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Complexity: O(s + m * log(m)) time. Note that the number of -- edges m of a graph can be quadratic with respect to the -- expression size s. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path xs) (circuit xs) == True -- isSubgraphOf x y ==> x <= y --isSubgraphOf :: Ord a => Fold a -> Fold a -> Bool -- | Check if a graph is empty. A convenient alias for null. -- Complexity: O(s) time. -- --
-- isEmpty empty == True -- isEmpty (overlay empty empty) == True -- isEmpty (vertex x) == False -- isEmpty (removeVertex x $ vertex x) == True -- isEmpty (removeEdge x y $ edge x y) == False --isEmpty :: Fold a -> Bool -- | The size of a graph, i.e. the number of leaves of the -- expression including empty leaves. Complexity: O(s) -- time. -- --
-- size empty == 1 -- size (vertex x) == 1 -- size (overlay x y) == size x + size y -- size (connect x y) == size x + size y -- size x >= 1 -- size x >= vertexCount x --size :: Fold a -> Int -- | Check if a graph contains a given vertex. Complexity: O(s) -- time. -- --
-- hasVertex x empty == False -- hasVertex x (vertex x) == True -- hasVertex 1 (vertex 2) == False -- hasVertex x . removeVertex x == const False --hasVertex :: Eq a => a -> Fold a -> Bool -- | Check if a graph contains a given edge. Complexity: O(s) time. -- --
-- hasEdge x y empty == False -- hasEdge x y (vertex z) == False -- hasEdge x y (edge x y) == True -- hasEdge x y . removeEdge x y == const False -- hasEdge x y == elem (x,y) . edgeList --hasEdge :: Eq a => a -> a -> Fold a -> Bool -- | The number of vertices in a graph. Complexity: O(s * log(n)) -- time. -- --
-- vertexCount empty == 0 -- vertexCount (vertex x) == 1 -- vertexCount == length . vertexList -- vertexCount x < vertexCount y ==> x < y --vertexCount :: Ord a => Fold a -> Int -- | The number of edges in a graph. Complexity: O(s + m * log(m)) -- time. Note that the number of edges m of a graph can be -- quadratic with respect to the expression size s. -- --
-- edgeCount empty == 0 -- edgeCount (vertex x) == 0 -- edgeCount (edge x y) == 1 -- edgeCount == length . edgeList --edgeCount :: Ord a => Fold a -> Int -- | The sorted list of vertices of a given graph. Complexity: O(s * -- log(n)) time and O(n) memory. -- --
-- vertexList empty == [] -- vertexList (vertex x) == [x] -- vertexList . vertices == nub . sort --vertexList :: Ord a => Fold a -> [a] -- | The sorted list of edges of a graph. Complexity: O(s + m * -- log(m)) time and O(m) memory. Note that the number of edges -- m of a graph can be quadratic with respect to the expression -- size s. -- --
-- edgeList empty == [] -- edgeList (vertex x) == [] -- edgeList (edge x y) == [(x,y)] -- edgeList (star 2 [3,1]) == [(2,1), (2,3)] -- edgeList . edges == nub . sort -- edgeList . transpose == sort . map swap . edgeList --edgeList :: Ord a => Fold a -> [(a, a)] -- | The set of vertices of a given graph. Complexity: O(s * log(n)) -- time and O(n) memory. -- --
-- vertexSet empty == Set.empty -- vertexSet . vertex == Set.singleton -- vertexSet . vertices == Set.fromList --vertexSet :: Ord a => Fold a -> Set a -- | The set of edges of a given graph. Complexity: O(s * log(m)) -- time and O(m) memory. -- --
-- edgeSet empty == Set.empty -- edgeSet (vertex x) == Set.empty -- edgeSet (edge x y) == Set.singleton (x,y) -- edgeSet . edges == Set.fromList --edgeSet :: Ord a => Fold a -> Set (a, a) -- | The sorted adjacency list of a graph. Complexity: O(s + m * -- log(m)) time. Note that the number of edges m of a graph -- can be quadratic with respect to the expression size s. -- --
-- adjacencyList empty == [] -- adjacencyList (vertex x) == [(x, [])] -- adjacencyList (edge 1 2) == [(1, [2]), (2, [])] -- adjacencyList (star 2 [3,1]) == [(1, []), (2, [1,3]), (3, [])] -- stars . adjacencyList == id --adjacencyList :: Ord a => Fold a -> [(a, [a])] -- | The path on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- path [] == empty -- path [x] == vertex x -- path [x,y] == edge x y -- path . reverse == transpose . path --path :: [a] -> Fold a -- | The circuit on a list of vertices. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- circuit [] == empty -- circuit [x] == edge x x -- circuit [x,y] == edges [(x,y), (y,x)] -- circuit . reverse == transpose . circuit --circuit :: [a] -> Fold a -- | The clique on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- clique [] == empty -- clique [x] == vertex x -- clique [x,y] == edge x y -- clique [x,y,z] == edges [(x,y), (x,z), (y,z)] -- clique (xs ++ ys) == connect (clique xs) (clique ys) -- clique . reverse == transpose . clique --clique :: [a] -> Fold a -- | The biclique on two lists of vertices. Complexity: O(L1 + -- L2) time, memory and size, where L1 and L2 are the -- lengths of the given lists. -- --
-- biclique [] [] == empty -- biclique [x] [] == vertex x -- biclique [] [y] == vertex y -- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique xs ys == connect (vertices xs) (vertices ys) --biclique :: [a] -> [a] -> Fold a -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges [(x,y), (x,z)] -- star x ys == connect (vertex x) (vertices ys) --star :: a -> [a] -> Fold a -- | The stars formed by overlaying a list of stars. An -- inverse of adjacencyList. Complexity: O(L) time, memory -- and size, where L is the total size of the input. -- --
-- stars [] == empty -- stars [(x, [])] == vertex x -- stars [(x, [y])] == edge x y -- stars [(x, ys)] == star x ys -- stars == overlays . map (uncurry star) -- stars . adjacencyList == id -- overlay (stars xs) (stars ys) == stars (xs ++ ys) --stars :: [(a, [a])] -> Fold a -- | Remove a vertex from a given graph. Complexity: O(s) time, -- memory and size. -- --
-- removeVertex x (vertex x) == empty -- removeVertex 1 (vertex 2) == vertex 2 -- removeVertex x (edge x x) == empty -- removeVertex 1 (edge 1 2) == vertex 2 -- removeVertex x . removeVertex x == removeVertex x --removeVertex :: Eq a => a -> Fold a -> Fold a -- | Remove an edge from a given graph. Complexity: O(s) time, -- memory and size. -- --
-- removeEdge x y (edge x y) == vertices [x,y] -- removeEdge x y . removeEdge x y == removeEdge x y -- removeEdge x y . removeVertex x == removeVertex x -- removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 -- removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2 -- size (removeEdge x y z) <= 3 * size z --removeEdge :: Eq a => a -> a -> Fold a -> Fold a -- | Transpose a given graph. Complexity: O(s) time, memory and -- size. -- --
-- transpose empty == empty -- transpose (vertex x) == vertex x -- transpose (edge x y) == edge y x -- transpose . transpose == id -- transpose (box x y) == box (transpose x) (transpose y) -- edgeList . transpose == sort . map swap . edgeList --transpose :: Fold a -> Fold a -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(s) time, memory and size, assuming that the predicate takes -- O(1) to be evaluated. -- --
-- induce (const True ) x == x -- induce (const False) x == empty -- induce (/= x) == removeVertex x -- induce p . induce q == induce (\x -> p x && q x) -- isSubgraphOf (induce p x) x == True --induce :: (a -> Bool) -> Fold a -> Fold a -- | Simplify 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 -- size (simplify x) <= size x -- simplify empty ~> empty -- simplify 1 ~> 1 -- simplify (1 + 1) ~> 1 -- simplify (1 + 2 + 1) ~> 1 + 2 -- simplify (1 * 1 * 1) ~> 1 * 1 --simplify :: Ord a => Fold a -> Fold a instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Fold.Fold a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Fold.Fold a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Algebra.Graph.Fold.Fold a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Fold.Fold a) instance GHC.Num.Num a => GHC.Num.Num (Algebra.Graph.Fold.Fold a) instance GHC.Base.Functor Algebra.Graph.Fold.Fold instance GHC.Base.Applicative Algebra.Graph.Fold.Fold instance GHC.Base.Alternative Algebra.Graph.Fold.Fold instance GHC.Base.MonadPlus Algebra.Graph.Fold.Fold instance GHC.Base.Monad Algebra.Graph.Fold.Fold instance Algebra.Graph.ToGraph.ToGraph (Algebra.Graph.Fold.Fold a) -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the core type class Graph, a few graph -- subclasses, and basic polymorphic graph construction primitives. -- Functions that cannot be implemented fully polymorphically and require -- the use of an intermediate data type are not included. For example, to -- compute the size of a Graph expression you will need to use a -- concrete data type, such as Algebra.Graph. -- -- See Algebra.Graph.Class for alternative definitions where the -- core type class is not higher-kinded and permits more instances. module Algebra.Graph.HigherKinded.Class -- | The core type class for constructing algebraic graphs is defined by -- introducing the connect method to the standard MonadPlus -- class and reusing the following existing methods: -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
x * y == y * x
vertex x == vertex x * -- vertex x
-- pure x == pure x * pure x ---- -- Note that by applying the axiom in the reverse direction, one can -- always remove all self-loops resulting in an irreflexive graph. -- This type class can therefore be also used in the context of -- irreflexive graphs. class Graph g => Reflexive g -- | The class of transitive graphs that satisfy the following -- additional axiom. -- --
y /= empty ==> x * y + x * z + y * z == x * y + y * -- z
-- edge x y == connect (vertex x) (vertex y) -- vertexCount (edge 1 1) == 1 -- vertexCount (edge 1 2) == 2 --edge :: Graph g => a -> a -> g a -- | Construct 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 [] == empty -- vertices [x] == vertex x -- hasVertex x . vertices == elem x -- vertexCount . vertices == length . nub -- vertexSet . vertices == Set.fromList --vertices :: Graph g => [a] -> g a -- | Construct the graph from a list of edges. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- edges [] == empty -- edges [(x,y)] == edge x y --edges :: Graph g => [(a, a)] -> g a -- | Overlay a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- overlays [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty -- isEmpty . overlays == all isEmpty --overlays :: Graph g => [g a] -> g a -- | Connect a given list of graphs. Complexity: O(L) time and -- memory, and O(S) size, where L is the length of the -- given list, and S is the sum of sizes of the graphs in the -- list. -- --
-- connects [] == empty -- connects [x] == x -- connects [x,y] == connect x y -- connects == foldr connect empty -- isEmpty . connects == all isEmpty --connects :: Graph g => [g a] -> g a -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Here is the current implementation: -- --
-- isSubgraphOf x y = overlay x y == y ---- -- The complexity therefore depends on the complexity of equality testing -- of the specific graph instance. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path xs) (circuit xs) == True --isSubgraphOf :: (Graph g, Eq (g a)) => g a -> g a -> Bool -- | Check if a graph contains a given edge. Complexity: O(s) time. -- --
-- hasEdge x y empty == False -- hasEdge x y (vertex z) == False -- hasEdge x y (edge x y) == True -- hasEdge x y == elem (x,y) . edgeList --hasEdge :: (Eq (g a), Graph g, Ord a) => a -> a -> g a -> Bool -- | The path on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- path [] == empty -- path [x] == vertex x -- path [x,y] == edge x y --path :: Graph g => [a] -> g a -- | The circuit on a list of vertices. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- circuit [] == empty -- circuit [x] == edge x x -- circuit [x,y] == edges [(x,y), (y,x)] --circuit :: Graph g => [a] -> g a -- | The clique on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- clique [] == empty -- clique [x] == vertex x -- clique [x,y] == edge x y -- clique [x,y,z] == edges [(x,y), (x,z), (y,z)] -- clique (xs ++ ys) == connect (clique xs) (clique ys) --clique :: Graph g => [a] -> g a -- | The biclique on two lists of vertices. Complexity: O(L1 + -- L2) time, memory and size, where L1 and L2 are the -- lengths of the given lists. -- --
-- biclique [] [] == empty -- biclique [x] [] == vertex x -- biclique [] [y] == vertex y -- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique xs ys == connect (vertices xs) (vertices ys) --biclique :: Graph g => [a] -> [a] -> g a -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges [(x,y), (x,z)] -- star x ys == connect (vertex x) (vertices ys) --star :: Graph g => a -> [a] -> g a -- | The stars formed by overlaying a list of stars. An -- inverse of adjacencyList. Complexity: O(L) time, -- memory and size, where L is the total size of the input. -- --
-- stars [] == empty -- stars [(x, [])] == vertex x -- stars [(x, [y])] == edge x y -- stars [(x, ys)] == star x ys -- stars == overlays . map (uncurry star) -- stars . adjacencyList == id -- overlay (stars xs) (stars ys) == stars (xs ++ ys) --stars :: Graph g => [(a, [a])] -> g a -- | The tree graph constructed from a given Tree data -- structure. Complexity: O(T) time, memory and size, where -- T is the size of the given tree (i.e. the number of vertices in -- the tree). -- --
-- tree (Node x []) == vertex x -- tree (Node x [Node y [Node z []]]) == path [x,y,z] -- tree (Node x [Node y [], Node z []]) == star x [y,z] -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges [(1,2), (1,3), (3,4), (3,5)] --tree :: Graph g => Tree a -> g a -- | The forest graph constructed from a given Forest data -- structure. Complexity: O(F) time, memory and size, where -- F is the size of the given forest (i.e. the number of vertices -- in the forest). -- --
-- forest [] == empty -- forest [x] == tree x -- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == edges [(1,2), (1,3), (4,5)] -- forest == overlays . map tree --forest :: Graph g => Forest a -> g a -- | Construct a mesh graph from two lists of vertices. Complexity: -- O(L1 * L2) time, memory and size, where L1 and L2 -- are the lengths of the given lists. -- --
-- mesh xs [] == empty -- mesh [] ys == empty -- mesh [x] [y] == vertex (x, y) -- mesh xs ys == box (path xs) (path ys) -- mesh [1..3] "ab" == edges [ ((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')) ] --mesh :: Graph g => [a] -> [b] -> g (a, b) -- | Construct a torus graph from two lists of vertices. Complexity: -- O(L1 * L2) time, memory and size, where L1 and L2 -- are the lengths of the given lists. -- --
-- torus xs [] == empty -- torus [] ys == empty -- torus [x] [y] == edge (x,y) (x,y) -- torus xs ys == box (circuit xs) (circuit ys) -- torus [1,2] "ab" == edges [ ((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')) ] --torus :: Graph g => [a] -> [b] -> g (a, b) -- | Construct a De Bruijn graph 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 == edge [] []
-- n > 0 ==> deBruijn n [] == empty
-- deBruijn 1 [0,1] == edges [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ]
-- deBruijn 2 "0" == edge "00" "00"
-- deBruijn 2 "01" == edges [ ("00","00"), ("00","01"), ("01","10"), ("01","11")
-- , ("10","00"), ("10","01"), ("11","10"), ("11","11") ]
-- transpose (deBruijn n xs) == fmap reverse $ deBruijn n xs
-- vertexCount (deBruijn n xs) == (length $ nub xs)^n
-- n > 0 ==> edgeCount (deBruijn n xs) == (length $ nub xs)^(n + 1)
--
deBruijn :: Graph g => Int -> [a] -> g [a]
-- | Remove a vertex from a given graph. Complexity: O(s) time,
-- memory and size.
--
-- -- removeVertex x (vertex x) == empty -- removeVertex 1 (vertex 2) == vertex 2 -- removeVertex x (edge x x) == empty -- removeVertex 1 (edge 1 2) == vertex 2 -- removeVertex x . removeVertex x == removeVertex x --removeVertex :: (Eq a, Graph g) => a -> g a -> g a -- | The function replaceVertex x y replaces vertex -- x with vertex y in a given Graph. If -- y already exists, x and y will be merged. -- Complexity: O(s) time, memory and size. -- --
-- replaceVertex x x == id -- replaceVertex x y (vertex x) == vertex y -- replaceVertex x y == mergeVertices (== x) y --replaceVertex :: (Eq a, Graph g) => a -> a -> g a -> g a -- | Merge 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 (const False) x == id -- mergeVertices (== x) y == replaceVertex x y -- mergeVertices even 1 (0 * 2) == 1 * 1 -- mergeVertices odd 1 (3 + 4 * 5) == 4 * 1 --mergeVertices :: Graph g => (a -> Bool) -> a -> g a -> g a -- | Split a vertex into a list of vertices with the same connectivity. -- Complexity: O(s + k * L) time, memory and size, where k -- is the number of occurrences of the vertex in the expression and -- L is the length of the given list. -- --
-- splitVertex x [] == removeVertex x -- splitVertex x [x] == id -- splitVertex x [y] == replaceVertex x y -- splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3) --splitVertex :: (Eq a, Graph g) => a -> [a] -> g a -> g a -- | Construct the induced subgraph of a given graph by removing the -- vertices that do not satisfy a given predicate. Complexity: -- O(s) time, memory and size, assuming that the predicate takes -- O(1) to be evaluated. -- --
-- induce (const True ) x == x -- induce (const False) x == empty -- induce (/= x) == removeVertex x -- induce p . induce q == induce (\x -> p x && q x) -- isSubgraphOf (induce p x) x == True --induce :: Graph g => (a -> Bool) -> g a -> g a instance Algebra.Graph.HigherKinded.Class.Graph Algebra.Graph.Graph instance Algebra.Graph.HigherKinded.Class.Graph Algebra.Graph.Fold.Fold -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines the core type class Graph, a few graph -- subclasses, and basic polymorphic graph construction primitives. -- Functions that cannot be implemented fully polymorphically and require -- the use of an intermediate data type are not included. For example, to -- compute the number of vertices in a Graph expression you will -- need to use a concrete data type, such as Algebra.Graph.Fold. -- Other useful Graph instances are defined in -- Algebra.Graph, Algebra.Graph.AdjacencyMap and -- Algebra.Graph.Relation. -- -- See Algebra.Graph.HigherKinded.Class for the higher-kinded -- version of the core graph type class. module Algebra.Graph.Class -- | 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 overlay and -- connect, respectively. -- --
x + y == y + x -- x + (y + z) == (x + y) + z
x * empty == x empty * x == x x * (y * z) == (x * y) * -- z
x * (y + z) == -- x * y + x * z (x + y) * z == x * z + y * z
x * y * z == x * y + x * z + -- y * z
x + empty == x empty + x == x x + x == x
x * y + x + y == -- x * y x * x * x == x * x
x * y == y * x
vertex x == vertex x * -- vertex x
y /= empty ==> x * y + x * z + y * z == x * y + y * -- z
-- edge x y == connect (vertex x) (vertex y) --edge :: Graph g => Vertex g -> Vertex g -> g -- | Construct 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 [] == empty -- vertices [x] == vertex x --vertices :: Graph g => [Vertex g] -> g -- | 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 [] == empty -- overlays [x] == x -- overlays [x,y] == overlay x y -- overlays == foldr overlay empty --overlays :: Graph g => [g] -> g -- | 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 [] == empty -- connects [x] == x -- connects [x,y] == connect x y -- connects == foldr connect empty --connects :: Graph g => [g] -> g -- | Construct the graph from a list of edges. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- edges [] == empty -- edges [(x,y)] == edge x y --edges :: Graph g => [(Vertex g, Vertex g)] -> g -- | The isSubgraphOf function takes two graphs and returns -- True if the first graph is a subgraph of the second. -- Here is the current implementation: -- --
-- isSubgraphOf x y = overlay x y == y ---- -- The complexity therefore depends on the complexity of equality testing -- of the specific graph instance. -- --
-- isSubgraphOf empty x == True -- isSubgraphOf (vertex x) empty == False -- isSubgraphOf x (overlay x y) == True -- isSubgraphOf (overlay x y) (connect x y) == True -- isSubgraphOf (path xs) (circuit xs) == True --isSubgraphOf :: (Graph g, Eq g) => g -> g -> Bool -- | The path on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- path [] == empty -- path [x] == vertex x -- path [x,y] == edge x y --path :: Graph g => [Vertex g] -> g -- | The circuit on a list of vertices. Complexity: O(L) -- time, memory and size, where L is the length of the given list. -- --
-- circuit [] == empty -- circuit [x] == edge x x -- circuit [x,y] == edges [(x,y), (y,x)] --circuit :: Graph g => [Vertex g] -> g -- | The clique on a list of vertices. Complexity: O(L) time, -- memory and size, where L is the length of the given list. -- --
-- clique [] == empty -- clique [x] == vertex x -- clique [x,y] == edge x y -- clique [x,y,z] == edges [(x,y), (x,z), (y,z)] -- clique (xs ++ ys) == connect (clique xs) (clique ys) --clique :: Graph g => [Vertex g] -> g -- | The biclique on two lists of vertices. Complexity: O(L1 + -- L2) time, memory and size, where L1 and L2 are the -- lengths of the given lists. -- --
-- biclique [] [] == empty -- biclique [x] [] == vertex x -- biclique [] [y] == vertex y -- biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] -- biclique xs ys == connect (vertices xs) (vertices ys) --biclique :: Graph g => [Vertex g] -> [Vertex g] -> g -- | The star 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 [] == vertex x -- star x [y] == edge x y -- star x [y,z] == edges [(x,y), (x,z)] -- star x ys == connect (vertex x) (vertices ys) --star :: Graph g => Vertex g -> [Vertex g] -> g -- | The tree graph constructed from a given Tree data -- structure. Complexity: O(T) time, memory and size, where -- T is the size of the given tree (i.e. the number of vertices in -- the tree). -- --
-- tree (Node x []) == vertex x -- tree (Node x [Node y [Node z []]]) == path [x,y,z] -- tree (Node x [Node y [], Node z []]) == star x [y,z] -- tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges [(1,2), (1,3), (3,4), (3,5)] --tree :: Graph g => Tree (Vertex g) -> g -- | The forest graph constructed from a given Forest data -- structure. Complexity: O(F) time, memory and size, where -- F is the size of the given forest (i.e. the number of vertices -- in the forest). -- --
-- forest [] == empty -- forest [x] == tree x -- forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == edges [(1,2), (1,3), (4,5)] -- forest == overlays . map tree --forest :: Graph g => Forest (Vertex g) -> g instance Algebra.Graph.Class.Preorder () instance Algebra.Graph.Class.Preorder g => Algebra.Graph.Class.Preorder (GHC.Maybe.Maybe g) instance Algebra.Graph.Class.Preorder g => Algebra.Graph.Class.Preorder (a -> g) instance (Algebra.Graph.Class.Preorder g, Algebra.Graph.Class.Preorder h) => Algebra.Graph.Class.Preorder (g, h) instance (Algebra.Graph.Class.Preorder g, Algebra.Graph.Class.Preorder h, Algebra.Graph.Class.Preorder i) => Algebra.Graph.Class.Preorder (g, h, i) instance Algebra.Graph.Class.Transitive () instance Algebra.Graph.Class.Transitive g => Algebra.Graph.Class.Transitive (GHC.Maybe.Maybe g) instance Algebra.Graph.Class.Transitive g => Algebra.Graph.Class.Transitive (a -> g) instance (Algebra.Graph.Class.Transitive g, Algebra.Graph.Class.Transitive h) => Algebra.Graph.Class.Transitive (g, h) instance (Algebra.Graph.Class.Transitive g, Algebra.Graph.Class.Transitive h, Algebra.Graph.Class.Transitive i) => Algebra.Graph.Class.Transitive (g, h, i) instance Algebra.Graph.Class.Reflexive () instance Algebra.Graph.Class.Reflexive g => Algebra.Graph.Class.Reflexive (GHC.Maybe.Maybe g) instance Algebra.Graph.Class.Reflexive g => Algebra.Graph.Class.Reflexive (a -> g) instance (Algebra.Graph.Class.Reflexive g, Algebra.Graph.Class.Reflexive h) => Algebra.Graph.Class.Reflexive (g, h) instance (Algebra.Graph.Class.Reflexive g, Algebra.Graph.Class.Reflexive h, Algebra.Graph.Class.Reflexive i) => Algebra.Graph.Class.Reflexive (g, h, i) instance Algebra.Graph.Class.Undirected () instance Algebra.Graph.Class.Undirected g => Algebra.Graph.Class.Undirected (GHC.Maybe.Maybe g) instance Algebra.Graph.Class.Undirected g => Algebra.Graph.Class.Undirected (a -> g) instance (Algebra.Graph.Class.Undirected g, Algebra.Graph.Class.Undirected h) => Algebra.Graph.Class.Undirected (g, h) instance (Algebra.Graph.Class.Undirected g, Algebra.Graph.Class.Undirected h, Algebra.Graph.Class.Undirected i) => Algebra.Graph.Class.Undirected (g, h, i) instance Algebra.Graph.Class.Graph (Algebra.Graph.Graph a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.AdjacencyMap.Internal.AdjacencyMap a) instance Algebra.Graph.Class.Graph (Algebra.Graph.Fold.Fold a) instance Algebra.Graph.Class.Graph Algebra.Graph.AdjacencyIntMap.Internal.AdjacencyIntMap instance Algebra.Graph.Label.Dioid e => Algebra.Graph.Class.Graph (Algebra.Graph.Labelled.Graph e a) instance (Algebra.Graph.Label.Dioid e, GHC.Classes.Eq e, GHC.Classes.Ord a) => Algebra.Graph.Class.Graph (Algebra.Graph.Labelled.AdjacencyMap.Internal.AdjacencyMap e a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.Internal.Relation a) instance Algebra.Graph.Class.Graph () instance Algebra.Graph.Class.Graph g => Algebra.Graph.Class.Graph (GHC.Maybe.Maybe g) instance Algebra.Graph.Class.Graph g => Algebra.Graph.Class.Graph (a -> g) instance (Algebra.Graph.Class.Graph g, Algebra.Graph.Class.Graph h) => Algebra.Graph.Class.Graph (g, h) instance (Algebra.Graph.Class.Graph g, Algebra.Graph.Class.Graph h, Algebra.Graph.Class.Graph i) => Algebra.Graph.Class.Graph (g, h, i) -- | This module exposes the implementation of derived binary relation data -- types. The API is unstable and unsafe, and is exposed only for -- documentation. You should use the non-internal modules -- Algebra.Graph.Relation.Reflexive, -- Algebra.Graph.Relation.Symmetric, -- Algebra.Graph.Relation.Transitive and -- Algebra.Graph.Relation.Preorder instead. module Algebra.Graph.Relation.InternalDerived -- | The ReflexiveRelation data type represents a reflexive -- binary relation over a set of elements. Reflexive relations -- satisfy all laws of the Reflexive type class and, in -- particular, the self-loop axiom: -- --
-- vertex x == vertex x * vertex x ---- -- The Show instance produces reflexively closed expressions: -- --
-- show (1 :: ReflexiveRelation Int) == "edge 1 1" -- show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]" --newtype ReflexiveRelation a ReflexiveRelation :: Relation a -> ReflexiveRelation a [fromReflexive] :: ReflexiveRelation a -> Relation a -- | The SymmetricRelation data type represents a symmetric -- binary relation over a set of elements. Symmetric relations -- satisfy all laws of the Undirected type class and, in -- particular, the commutativity of connect: -- --
-- connect x y == connect y x ---- -- The Show instance produces symmetrically closed expressions: -- --
-- show (1 :: SymmetricRelation Int) == "vertex 1" -- show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]" --newtype SymmetricRelation a SymmetricRelation :: Relation a -> SymmetricRelation a [fromSymmetric] :: SymmetricRelation a -> Relation a -- | The TransitiveRelation data type represents a transitive -- binary relation over a set of elements. Transitive relations -- satisfy all laws of the Transitive type class and, in -- particular, the closure axiom: -- --
-- y /= empty ==> x * y + x * z + y * z == x * y + y * z ---- -- For example, the following holds: -- --
-- path xs == (clique xs :: TransitiveRelation Int) ---- -- The Show 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)]" --newtype TransitiveRelation a TransitiveRelation :: Relation a -> TransitiveRelation a [fromTransitive] :: TransitiveRelation a -> Relation a -- | The PreorderRelation data type represents a binary relation -- that is both reflexive and transitive. Preorders satisfy all laws -- of the Preorder type class and, in particular, the -- self-loop axiom: -- --
-- vertex x == vertex x * vertex x ---- -- and the closure axiom: -- --
-- y /= empty ==> x * y + x * z + y * z == x * y + y * z ---- -- For example, the following holds: -- --
-- path xs == (clique xs :: PreorderRelation Int) ---- -- The Show 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)]" --newtype PreorderRelation a PreorderRelation :: Relation a -> PreorderRelation a [fromPreorder] :: PreorderRelation a -> Relation a instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.InternalDerived.PreorderRelation a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.PreorderRelation a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a) instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a) instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.InternalDerived.PreorderRelation a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Relation.InternalDerived.PreorderRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.InternalDerived.PreorderRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Reflexive (Algebra.Graph.Relation.InternalDerived.PreorderRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Transitive (Algebra.Graph.Relation.InternalDerived.PreorderRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Preorder (Algebra.Graph.Relation.InternalDerived.PreorderRelation a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a) instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Transitive (Algebra.Graph.Relation.InternalDerived.TransitiveRelation a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a) instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Undirected (Algebra.Graph.Relation.InternalDerived.SymmetricRelation a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a) instance (GHC.Classes.Ord a, GHC.Show.Show a) => GHC.Show.Show (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Graph (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a) instance GHC.Classes.Ord a => Algebra.Graph.Class.Reflexive (Algebra.Graph.Relation.InternalDerived.ReflexiveRelation a) -- | An abstract implementation of transitive binary relations. Use -- Algebra.Graph.Class for polymorphic construction and -- manipulation. module Algebra.Graph.Relation.Transitive -- | The TransitiveRelation data type represents a transitive -- binary relation over a set of elements. Transitive relations -- satisfy all laws of the Transitive type class and, in -- particular, the closure axiom: -- --
-- y /= empty ==> x * y + x * z + y * z == x * y + y * z ---- -- For example, the following holds: -- --
-- path xs == (clique xs :: TransitiveRelation Int) ---- -- The Show 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)]" --data TransitiveRelation a -- | Construct a transitive relation from a Relation. Complexity: -- O(1) time. fromRelation :: Relation a -> TransitiveRelation a -- | Extract the underlying relation. Complexity: O(n * m * log(m)) -- time. toRelation :: Ord a => TransitiveRelation a -> Relation a -- | An abstract implementation of symmetric binary relations. Use -- Algebra.Graph.Class for polymorphic construction and -- manipulation. module Algebra.Graph.Relation.Symmetric -- | The SymmetricRelation data type represents a symmetric -- binary relation over a set of elements. Symmetric relations -- satisfy all laws of the Undirected type class and, in -- particular, the commutativity of connect: -- --
-- connect x y == connect y x ---- -- The Show instance produces symmetrically closed expressions: -- --
-- show (1 :: SymmetricRelation Int) == "vertex 1" -- show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]" --data SymmetricRelation a -- | Construct a symmetric relation from a Relation. Complexity: -- O(1) time. fromRelation :: Relation a -> SymmetricRelation a -- | Extract the underlying relation. Complexity: O(m*log(m)) time. toRelation :: Ord a => SymmetricRelation a -> Relation a -- | The set of neighbours of an element x is the set of -- elements that are related to it, i.e. neighbours x == { a | aRx -- }. In the context of undirected graphs, this corresponds to the -- set of adjacent vertices of vertex x. -- --
-- neighbours x empty == Set.empty -- neighbours x (vertex x) == Set.empty -- neighbours x (edge x y) == Set.fromList [y] -- neighbours y (edge x y) == Set.fromList [x] --neighbours :: Ord a => a -> SymmetricRelation a -> Set a -- | An abstract implementation of reflexive binary relations. Use -- Algebra.Graph.Class for polymorphic construction and -- manipulation. module Algebra.Graph.Relation.Reflexive -- | The ReflexiveRelation data type represents a reflexive -- binary relation over a set of elements. Reflexive relations -- satisfy all laws of the Reflexive type class and, in -- particular, the self-loop axiom: -- --
-- vertex x == vertex x * vertex x ---- -- The Show instance produces reflexively closed expressions: -- --
-- show (1 :: ReflexiveRelation Int) == "edge 1 1" -- show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]" --data ReflexiveRelation a -- | Construct a reflexive relation from a Relation. Complexity: -- O(1) time. fromRelation :: Relation a -> ReflexiveRelation a -- | Extract the underlying relation. Complexity: O(n*log(m)) time. toRelation :: Ord a => ReflexiveRelation a -> Relation a -- | An abstract implementation of preorder relations. Use -- Algebra.Graph.Class for polymorphic construction and -- manipulation. module Algebra.Graph.Relation.Preorder -- | The PreorderRelation data type represents a binary relation -- that is both reflexive and transitive. Preorders satisfy all laws -- of the Preorder type class and, in particular, the -- self-loop axiom: -- --
-- vertex x == vertex x * vertex x ---- -- and the closure axiom: -- --
-- y /= empty ==> x * y + x * z + y * z == x * y + y * z ---- -- For example, the following holds: -- --
-- path xs == (clique xs :: PreorderRelation Int) ---- -- The Show 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)]" --data PreorderRelation a -- | Construct a preorder relation from a Relation. Complexity: -- O(1) time. fromRelation :: Relation a -> PreorderRelation a -- | Extract the underlying relation. Complexity: O(n * m * log(m)) -- time. toRelation :: Ord a => PreorderRelation a -> Relation a -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines basic functionality for exporting graphs in -- textual and binary formats. Algebra.Graph.Export.Dot provides -- DOT-specific functions. module Algebra.Graph.Export -- | An abstract document data type with O(1) time concatenation -- (the current implementation uses difference lists). Here s is -- the type of abstract symbols or strings (text or binary). Doc -- s is a Monoid, therefore mempty corresponds to -- the empty document and two documents can be concatenated with -- mappend (or operator <>). Documents comprising a -- single symbol or string can be constructed using the function -- literal. Alternatively, you can construct documents as string -- literals, e.g. simply as "alga", by using the -- OverloadedStrings GHC extension. To extract the document -- contents use the function render. -- -- 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 Eq 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 Eq and Ord instances are defined as -- follows: -- --
-- mempty /= literal "" -- mempty < literal "" --data Doc s -- | Check if a document is empty. The result is the same as when comparing -- the given document to mempty, but this function does not -- require the Eq s constraint. Note that the document -- comprising a single empty string is considered to be different from -- the empty document. -- --
-- isEmpty mempty == True -- isEmpty (literal "") == False -- isEmpty x == (x == mempty) --isEmpty :: Doc s -> Bool -- | Construct a document comprising a single symbol or string. If -- s is an instance of class IsString, then documents of -- type Doc s can be constructed directly from string -- literals (see the second example below). -- --
-- literal "Hello, " <> literal "World!" == literal "Hello, World!" -- literal "I am just a string literal" == "I am just a string literal" -- render . literal == id --literal :: s -> Doc s -- | Render the document as a single string. An inverse of the function -- literal. -- --
-- render (literal "al" <> literal "ga") :: (IsString s, Monoid s) => s -- render (literal "al" <> literal "ga") == "alga" -- render mempty == mempty -- render . literal == id --render :: Monoid s => Doc s -> s -- | Concatenate two documents, separated by a single space, unless one of -- the documents is empty. The operator <+> is associative with -- identity mempty. -- --
-- x <+> mempty == x -- mempty <+> x == x -- x <+> (y <+> z) == (x <+> y) <+> z -- "name" <+> "surname" == "name surname" --(<+>) :: IsString s => Doc s -> Doc s -> Doc s infixl 7 <+> -- | Wrap a document in square brackets. -- --
-- brackets "i" == "[i]" -- brackets mempty == "[]" --brackets :: IsString s => Doc s -> Doc s -- | Wrap a document into double quotes. -- --
-- doubleQuotes "/path/with spaces" == "\"/path/with spaces\"" -- doubleQuotes (doubleQuotes mempty) == "\"\"\"\"" --doubleQuotes :: IsString s => Doc s -> Doc s -- | Prepend a given number of spaces to a document. -- --
-- indent 0 == id -- indent 1 mempty == " " --indent :: IsString s => Int -> Doc s -> Doc s -- | Concatenate documents after appending a terminating newline symbol to -- each. -- --
-- unlines [] == mempty -- unlines [mempty] == "\n" -- unlines ["title", "subtitle"] == "title\nsubtitle\n" --unlines :: IsString s => [Doc s] -> Doc s -- | 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 Ord a, and then edges, sorted by -- Ord (a, a). -- -- For example: -- --
-- vDoc x = literal (show x) <> "\n" -- eDoc x y = literal (show x) <> " -> " <> literal (show y) <> "\n" -- > putStrLn $ render $ export vDoc eDoc (1 + 2 * (3 + 4) :: Graph Int) -- -- 1 -- 2 -- 3 -- 4 -- 2 -> 3 -- 2 -> 4 --export :: (Ord a, ToGraph g, ToVertex g ~ a) => (a -> Doc s) -> (a -> a -> Doc s) -> g -> Doc s instance GHC.Base.Semigroup (Algebra.Graph.Export.Doc s) instance GHC.Base.Monoid (Algebra.Graph.Export.Doc s) instance (GHC.Base.Monoid s, GHC.Show.Show s) => GHC.Show.Show (Algebra.Graph.Export.Doc s) instance (GHC.Base.Monoid s, GHC.Classes.Eq s) => GHC.Classes.Eq (Algebra.Graph.Export.Doc s) instance (GHC.Base.Monoid s, GHC.Classes.Ord s) => GHC.Classes.Ord (Algebra.Graph.Export.Doc s) instance Data.String.IsString s => Data.String.IsString (Algebra.Graph.Export.Doc s) -- | Alga is a library for algebraic construction and manipulation -- of graphs in Haskell. See this paper for the motivation behind -- the library, the underlying theory, and implementation details. -- -- This module defines functions for exporting graphs in the DOT file -- format. module Algebra.Graph.Export.Dot -- | An attribute is just a key-value pair, for example "shape" := -- "box". Attributes are used to specify the style of graph elements -- during export. data Attribute s (:=) :: s -> s -> Attribute s -- | The record Style a s 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 vertexName, which holds a function of type a -> -- s to compute vertex names. See the example for the function -- export. data Style a s Style :: s -> [s] -> [Attribute s] -> [Attribute s] -> [Attribute s] -> (a -> s) -> (a -> [Attribute s]) -> (a -> a -> [Attribute s]) -> Style a s -- | Name of the graph. [graphName] :: Style a s -> s -- | Preamble (a list of lines) is added at the beginning of the DOT file -- body. [preamble] :: Style a s -> [s] -- | Graph style, e.g. ["bgcolor" := "azure"]. [graphAttributes] :: Style a s -> [Attribute s] -- | Default vertex style, e.g. ["shape" := "diamond"]. [defaultVertexAttributes] :: Style a s -> [Attribute s] -- | Default edge style, e.g. ["style" := "dashed"]. [defaultEdgeAttributes] :: Style a s -> [Attribute s] -- | Compute a vertex name. [vertexName] :: Style a s -> a -> s -- | Attributes of a specific vertex. [vertexAttributes] :: Style a s -> a -> [Attribute s] -- | Attributes of a specific edge. [edgeAttributes] :: Style a s -> a -> a -> [Attribute s] -- | Default style for exporting graphs. All style settings are empty -- except for vertexName, which is provided as the only argument. defaultStyle :: Monoid s => (a -> s) -> Style a s -- | Default style for exporting graphs whose vertices are -- Show-able. All style settings are empty except for -- vertexName, which is computed from show. -- --
-- defaultStyleViaShow = defaultStyle (fromString . show) --defaultStyleViaShow :: (Show a, IsString s, Monoid s) => Style a s -- | Export a graph with a given style. -- -- For example: -- --
-- style :: Style Int String
-- style = Style
-- { graphName = "Example"
-- , preamble = [" // This is an example", ""]
-- , graphAttributes = ["label" := "Example", "labelloc" := "top"]
-- , defaultVertexAttributes = ["shape" := "circle"]
-- , defaultEdgeAttributes = mempty
-- , vertexName = \x -> "v" ++ show x
-- , vertexAttributes = \x -> ["color" := "blue" | odd x ]
-- , edgeAttributes = \x y -> ["style" := "dashed" | odd (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"
-- }
--
export :: (IsString s, Monoid s, Ord a, ToGraph g, ToVertex g ~ a) => Style a s -> g -> s
-- | Export a graph whose vertices are represented simply by their names.
--
-- For example:
--
--
-- > Text.putStrLn $ exportAsIs (circuit ["a", "b", "c"] :: AdjacencyMap Text)
--
-- digraph
-- {
-- "a"
-- "b"
-- "c"
-- "a" -> "b"
-- "b" -> "c"
-- "c" -> "a"
-- }
--
exportAsIs :: (IsString s, Monoid s, Ord (ToVertex g), ToGraph g, ToVertex g ~ s) => g -> s
-- | Export a graph using the defaultStyleViaShow.
--
-- For example:
--
--
-- > putStrLn $ exportViaShow (1 + 2 * (3 + 4) :: Graph Int)
--
-- digraph
-- {
-- "1"
-- "2"
-- "3"
-- "4"
-- "2" -> "3"
-- "2" -> "4"
-- }
--
exportViaShow :: (IsString s, Monoid s, Ord (ToVertex g), Show (ToVertex g), ToGraph g) => g -> s