| Copyright | (c) Andrey Mokhov 2016-2021 |
|---|---|
| License | MIT (see the file LICENSE) |
| Maintainer | andrey.mokhov@gmail.com |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell2010 |
Algebra.Graph
Description
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.
Synopsis
- data Graph a
- empty :: Graph a
- vertex :: a -> Graph a
- edge :: a -> a -> Graph a
- overlay :: Graph a -> Graph a -> Graph a
- connect :: Graph a -> Graph a -> Graph a
- vertices :: [a] -> Graph a
- edges :: [(a, a)] -> Graph a
- overlays :: [Graph a] -> Graph a
- connects :: [Graph a] -> Graph a
- foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
- buildg :: (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r) -> Graph a
- isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool
- (===) :: Eq a => Graph a -> Graph a -> Bool
- isEmpty :: Graph a -> Bool
- size :: Graph a -> Int
- hasVertex :: Eq a => a -> Graph a -> Bool
- hasEdge :: Eq a => a -> a -> Graph a -> Bool
- vertexCount :: Ord a => Graph a -> Int
- edgeCount :: Ord a => Graph a -> Int
- vertexList :: Ord a => Graph a -> [a]
- edgeList :: Ord a => Graph a -> [(a, a)]
- vertexSet :: Ord a => Graph a -> Set a
- edgeSet :: Ord a => Graph a -> Set (a, a)
- adjacencyList :: Ord a => Graph a -> [(a, [a])]
- path :: [a] -> Graph a
- circuit :: [a] -> Graph a
- clique :: [a] -> Graph a
- biclique :: [a] -> [a] -> Graph a
- star :: a -> [a] -> Graph a
- stars :: [(a, [a])] -> Graph a
- tree :: Tree a -> Graph a
- forest :: Forest a -> Graph a
- mesh :: [a] -> [b] -> Graph (a, b)
- torus :: [a] -> [b] -> Graph (a, b)
- deBruijn :: Int -> [a] -> Graph [a]
- removeVertex :: Eq a => a -> Graph a -> Graph a
- removeEdge :: Eq a => a -> a -> Graph a -> Graph a
- replaceVertex :: Eq a => a -> a -> Graph a -> Graph a
- mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a
- splitVertex :: Eq a => a -> [a] -> Graph a -> Graph a
- transpose :: Graph a -> Graph a
- induce :: (a -> Bool) -> Graph a -> Graph a
- induceJust :: Graph (Maybe a) -> Graph a
- simplify :: Ord a => Graph a -> Graph a
- sparsify :: Graph a -> Graph (Either Int a)
- sparsifyKL :: Int -> Graph Int -> Graph
- compose :: Ord a => Graph a -> Graph a -> Graph a
- box :: Graph a -> Graph b -> Graph (a, b)
- data Context a = Context {}
- context :: (a -> Bool) -> Graph a -> Maybe (Context a)
Algebraic data type for graphs
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 ==vertex0 1 + 2 ==overlay(vertex1) (vertex2) 1 * 2 ==connect(vertex1) (vertex2) 1 + 2 * 3 ==overlay(vertex1) (connect(vertex2) (vertex3)) 1 * (2 + 3) ==connect(vertex1) (overlay(vertex2) (vertex3))
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:
overlayis commutative and associative:x + y == y + x x + (y + z) == (x + y) + z
connectis associative and hasemptyas the identity:x * empty == x empty * x == x x * (y * z) == (x * y) * z
connectdistributes overoverlay:x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z
connectcan be decomposed:x * y * z == x * y + x * z + y * z
The following useful theorems can be proved from the above set of axioms.
overlayhasemptyas the identity and is idempotent:x + empty == x empty + x == x x + x == xAbsorption and saturation of
connect:x * y + x + y == x * y x * x * x == x * x
When specifying the time and memory complexity of graph algorithms, n will
denote the number of vertices in the graph, m will denote the number of
edges in the graph, and s will denote the size of the corresponding
Graph expression. For example, if g is a Graph then n, m and s can
be computed as follows:
n ==vertexCountg m ==edgeCountg s ==sizeg
Note that size counts all leaves of the expression:
vertexCountempty== 0sizeempty== 1vertexCount(vertexx) == 1size(vertexx) == 1vertexCount(empty+empty) == 0size(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:
- Compare the number of vertices. In case of a tie, continue.
- Compare the sets of vertices. In case of a tie, continue.
- Compare the number of edges. In case of a tie, continue.
- Compare the sets of edges.
Here are a few examples:
vertex1 <vertex2vertex3 <edge1 2vertex1 <edge1 1edge1 1 <edge1 2edge1 2 <edge1 1 +edge2 2edge1 2 <edge1 3
Note that the resulting order refines the isSubgraphOf relation and is
compatible with overlay and connect operations:
isSubgraphOf x y ==> x <= yempty <= x
x <= x + y
x + y <= x * yDeforestation (fusion) is implemented for some functions in this module. This means that when a function tagged as a "good producer" is composed with a function tagged as a "good consumer", the intermediate structure will not be built.
Instances
Basic graph construction primitives
edge :: a -> a -> Graph a Source #
Construct the graph comprising a single edge.
edge x y ==connect(vertexx) (vertexy)hasEdgex y (edge x y) == TrueedgeCount(edge x y) == 1vertexCount(edge 1 1) == 1vertexCount(edge 1 2) == 2
overlay :: Graph a -> Graph a -> Graph a Source #
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) ==isEmptyx &&isEmptyyhasVertexz (overlay x y) ==hasVertexz x ||hasVertexz yvertexCount(overlay x y) >=vertexCountxvertexCount(overlay x y) <=vertexCountx +vertexCountyedgeCount(overlay x y) >=edgeCountxedgeCount(overlay x y) <=edgeCountx +edgeCountysize(overlay x y) ==sizex +sizeyvertexCount(overlay 1 2) == 2edgeCount(overlay 1 2) == 0
connect :: Graph a -> Graph a -> Graph a Source #
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) ==isEmptyx &&isEmptyyhasVertexz (connect x y) ==hasVertexz x ||hasVertexz yvertexCount(connect x y) >=vertexCountxvertexCount(connect x y) <=vertexCountx +vertexCountyedgeCount(connect x y) >=edgeCountxedgeCount(connect x y) >=edgeCountyedgeCount(connect x y) >=vertexCountx *vertexCountyedgeCount(connect x y) <=vertexCountx *vertexCounty +edgeCountx +edgeCountysize(connect x y) ==sizex +sizeyvertexCount(connect 1 2) == 2edgeCount(connect 1 2) == 1
vertices :: [a] -> Graph a Source #
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.
Good consumer of lists and producer of graphs.
vertices [] ==emptyvertices [x] ==vertexx vertices ==overlays. mapvertexhasVertexx . vertices ==elemxvertexCount. vertices ==length.nubvertexSet. vertices == Set.fromList
overlays :: [Graph a] -> Graph a Source #
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.
Good consumer of lists and producer of graphs.
overlays [] ==emptyoverlays [x] == x overlays [x,y] ==overlayx y overlays ==foldroverlayemptyisEmpty. overlays ==allisEmpty
connects :: [Graph a] -> Graph a Source #
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.
Good consumer of lists and producer of graphs.
connects [] ==emptyconnects [x] == x connects [x,y] ==connectx y connects ==foldrconnectemptyisEmpty. connects ==allisEmpty
Graph folding
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b Source #
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 the given functions. As an example, the
complexity of size is O(s), since const and + have constant costs.
Good consumer.
foldgemptyvertexoverlayconnect== id foldgemptyvertexoverlay(flipconnect) ==transposefoldg 1 (const1) (+) (+) ==sizefoldg True (constFalse) (&&) (&&) ==isEmptyfoldg False (== x) (||) (||) ==hasVertexx
buildg :: (forall r. r -> (a -> r) -> (r -> r -> r) -> (r -> r -> r) -> r) -> Graph a Source #
Build a graph given an interpretation of the four graph construction
primitives empty, vertex, overlay and connect, in this order. See
examples for further clarification.
Functions expressed with buildg are good producers.
buildg f == femptyvertexoverlayconnectbuildg (\e _ _ _ -> e) ==emptybuildg (\_ v _ _ -> v x) ==vertexx buildg (\e v o c -> o (foldge v o c x) (foldge v o c y)) ==overlayx y buildg (\e v o c -> c (foldge v o c x) (foldge v o c y)) ==connectx y buildg (\e v o _ ->foldro e (mapv xs)) ==verticesxs buildg (\e v o c ->foldge v o (flipc) g) ==transposegfoldge v o c (buildg f) == f e v o c
Relations on graphs
isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool Source #
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.
Good consumer of both arguments.
isSubgraphOfemptyx == True isSubgraphOf (vertexx)empty== False isSubgraphOf x (overlayx y) == True isSubgraphOf (overlayx y) (connectx y) == True isSubgraphOf (pathxs) (circuitxs) == True isSubgraphOf x y ==> x <= y
(===) :: Eq a => Graph a -> Graph a -> Bool infix 4 Source #
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
Graph properties
isEmpty :: Graph a -> Bool Source #
Check if a graph is empty. Complexity: O(s) time.
Good consumer.
isEmptyempty== True isEmpty (overlayemptyempty) == True isEmpty (vertexx) == False isEmpty (removeVertexx $vertexx) == True isEmpty (removeEdgex y $edgex y) == False
hasVertex :: Eq a => a -> Graph a -> Bool Source #
Check if a graph contains a given vertex. Complexity: O(s) time.
Good consumer.
hasVertex xempty== False hasVertex x (vertexy) == (x == y) hasVertex x .removeVertexx ==constFalse
vertexCount :: Ord a => Graph a -> Int Source #
The number of vertices in a graph. Complexity: O(s * log(n)) time.
Good consumer.
vertexCountempty== 0 vertexCount (vertexx) == 1 vertexCount ==length.vertexListvertexCount x < vertexCount y ==> x < y
vertexList :: Ord a => Graph a -> [a] Source #
edgeList :: Ord a => Graph a -> [(a, a)] Source #
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.
Good consumer of graphs and producer of lists.
edgeListempty== [] edgeList (vertexx) == [] edgeList (edgex y) == [(x,y)] edgeList (star2 [3,1]) == [(2,1), (2,3)] edgeList .edges==nub.sortedgeList .transpose==sort.mapswap. edgeList
adjacencyList :: Ord a => Graph a -> [(a, [a])] Source #
Standard families of graphs
clique :: [a] -> Graph a Source #
The clique on a list of vertices. Complexity: O(L) time, memory and size, where L is the length of the given list.
Good consumer of lists and producer of graphs.
clique [] ==emptyclique [x] ==vertexx clique [x,y] ==edgex y clique [x,y,z] ==edges[(x,y), (x,z), (y,z)] clique (xs ++ ys) ==connect(clique xs) (clique ys) clique .reverse==transpose. clique
biclique :: [a] -> [a] -> Graph a Source #
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.
Good consumer of both arguments and producer of graphs.
biclique [] [] ==emptybiclique [x] [] ==vertexx biclique [] [y] ==vertexy biclique [x1,x2] [y1,y2] ==edges[(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys ==connect(verticesxs) (verticesys)
star :: a -> [a] -> Graph a Source #
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.
Good consumer of lists and good producer of graphs.
star x [] ==vertexx star x [y] ==edgex y star x [y,z] ==edges[(x,y), (x,z)] star x ys ==connect(vertexx) (verticesys)
stars :: [(a, [a])] -> Graph a Source #
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.
Good consumer of lists and producer of graphs.
stars [] ==emptystars [(x, [])] ==vertexx stars [(x, [y])] ==edgex y stars [(x, ys)] ==starx ys stars ==overlays.map(uncurrystar) stars .adjacencyList== idoverlay(stars xs) (stars ys) == stars (xs ++ ys)
tree :: Tree a -> Graph a Source #
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 []) ==vertexx tree (Node x [Node y [Node z []]]) ==path[x,y,z] tree (Node x [Node y [], Node z []]) ==starx [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) ==edges[(1,2), (1,3), (3,4), (3,5)]
forest :: Forest a -> Graph a Source #
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 [] ==emptyforest [x] ==treex forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] ==edges[(1,2), (1,3), (4,5)] forest ==overlays.maptree
mesh :: [a] -> [b] -> Graph (a, b) Source #
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 [] ==emptymesh [] ys ==emptymesh [x] [y] ==vertex(x, y) mesh xs ys ==box(pathxs) (pathys) 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')) ]
torus :: [a] -> [b] -> Graph (a, b) Source #
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 [] ==emptytorus [] ys ==emptytorus [x] [y] ==edge(x,y) (x,y) torus xs ys ==box(circuitxs) (circuitys) 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')) ]
deBruijn :: Int -> [a] -> Graph [a] Source #
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 [] ==emptydeBruijn 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) ==fmapreverse$ deBruijn n xsvertexCount(deBruijn n xs) == (length$nubxs)^n n > 0 ==>edgeCount(deBruijn n xs) == (length$nubxs)^(n + 1)
Graph transformation
removeEdge :: Eq a => a -> a -> Graph a -> Graph a Source #
Remove an edge from a given graph. Complexity: O(s) time, memory and size.
removeEdge x y (edgex y) ==vertices[x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .removeVertexx ==removeVertexx removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2size(removeEdge x y z) <= 3 *sizez
replaceVertex :: Eq a => a -> a -> Graph a -> Graph a Source #
The function replaceVertex x yx with vertex y in a
given Graph. If y already exists, x and y will be merged.
Complexity: O(s) time, memory and size.
Good consumer and producer.
replaceVertex x x == id replaceVertex x y (vertexx) ==vertexy replaceVertex x y ==mergeVertices(== x) y
mergeVertices :: (a -> Bool) -> a -> Graph a -> Graph a Source #
Merge vertices satisfying a given predicate into a given vertex. Complexity: O(s) time, memory and size, assuming that the predicate takes constant time.
Good consumer and producer.
mergeVertices (constFalse) x == id mergeVertices (== x) y ==replaceVertexx y mergeVerticeseven1 (0 * 2) == 1 * 1 mergeVerticesodd1 (3 + 4 * 5) == 4 * 1
splitVertex :: Eq a => a -> [a] -> Graph a -> Graph a Source #
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.
Good consumer of lists and producer of graphs.
splitVertex x [] ==removeVertexx splitVertex x [x] == id splitVertex x [y] ==replaceVertexx y splitVertex 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
transpose :: Graph a -> Graph a Source #
Transpose a given graph. Complexity: O(s) time, memory and size.
Good consumer and producer.
transposeempty==emptytranspose (vertexx) ==vertexx transpose (edgex y) ==edgey x transpose . transpose == id transpose (boxx y) ==box(transpose x) (transpose y)edgeList. transpose ==sort.mapswap.edgeList
induce :: (a -> Bool) -> Graph a -> Graph a Source #
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 constant time.
Good consumer and producer.
induce (constTrue ) x == x induce (constFalse) x ==emptyinduce (/= x) ==removeVertexx induce p . induce q == induce (\x -> p x && q x)isSubgraphOf(induce p x) x == True
induceJust :: Graph (Maybe a) -> Graph a Source #
Construct the induced subgraph of a given graph by removing the vertices
that are Nothing.
Complexity: O(s) time, memory and size.
Good consumer and producer.
induceJust (vertexNothing) ==emptyinduceJust (edge(Justx)Nothing) ==vertexx induceJust .fmapJust==idinduceJust .fmap(\x -> if p x thenJustx elseNothing) ==inducep
simplify :: Ord a => Graph a -> Graph a Source #
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.
Good consumer.
simplify == idsize(simplify x) <=sizex simplifyempty===emptysimplify 1===1 simplify (1 + 1)===1 simplify (1 + 2 + 1)===1 + 2 simplify (1 * 1 * 1)===1 * 1
sparsify :: Graph a -> Graph (Either Int a) Source #
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.reachablex ==sort.rights.reachable(Rightx) . sparsifyvertexCount(sparsify x) <=vertexCountx +sizex + 1edgeCount(sparsify x) <= 3 *sizexsize(sparsify x) <= 3 *sizex
sparsifyKL :: Int -> Graph Int -> Graph Source #
Sparsify a graph whose vertices are integers in the range [1..n], where
n is the first argument of the function, producing an array-based graph
representation from Data.Graph (introduced by King and Launchbury, hence
the name of the function). In the resulting graph, vertices [1..n]
correspond to the original vertices, and all vertices greater than n are
introduced by the sparsification procedure.
Complexity: O(s) time and memory. Note that thanks to sparsification, the resulting graph has a linear number of edges with respect to the size of the original algebraic representation even though the latter can potentially contain a quadratic O(s^2) number of edges.
sort.reachablek ==sort.filter(<= n) .flipreachablek . sparsifyKL nlength(vertices$ sparsifyKL n x) <=vertexCountx +sizex + 1length(edges$ sparsifyKL n x) <= 3 *sizex
Graph composition
compose :: Ord a => Graph a -> Graph a -> Graph a Source #
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.
Good consumer of both arguments and good producer.
composeemptyx ==emptycompose xempty==emptycompose (vertexx) y ==emptycompose x (vertexy) ==emptycompose x (compose y z) == compose (compose x y) z compose x (overlayy z) ==overlay(compose x y) (compose x z) compose (overlayx y) z ==overlay(compose x z) (compose y z) compose (edgex y) (edgey z) ==edgex 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) <=edgeCountx +edgeCounty + 1
box :: Graph a -> Graph b -> Graph (a, b) Source #
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 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 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 (overlayy z) ==overlay(box x y) (box x z) box x (vertex()) ~~ x box xempty~~emptytranspose(box x y) == box (transposex) (transposey)vertexCount(box x y) ==vertexCountx *vertexCountyedgeCount(box x y) <=vertexCountx *edgeCounty +edgeCountx *vertexCounty
Context
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.
context :: (a -> Bool) -> Graph a -> Maybe (Context a) Source #
Extract the Context of a subgraph specified by a given predicate. Returns
Nothing if the specified subgraph is empty.
Good consumer.
context (constFalse) x == Nothing context (== 1) (edge1 2) == Just (Context[ ] [2 ]) context (== 2) (edge1 2) == Just (Context[1 ] [ ]) context (constTrue ) (edge1 2) == Just (Context[1 ] [2 ]) context (== 4) (3 * 1 * 4 * 1 * 5) == Just (Context[3,1] [1,5])