Copyright | (c) Andrey Mokhov 2016-2018 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
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.
- class (Traversable g, MonadPlus g) => Graph g where
- empty :: Alternative f => forall a. f a
- vertex :: Graph g => a -> g a
- overlay :: Graph g => g a -> g a -> g a
- class Graph g => Undirected g
- class Graph g => Reflexive g
- class Graph g => Transitive g
- class (Reflexive g, Transitive g) => Preorder g
- edge :: Graph g => a -> a -> g a
- vertices :: Graph g => [a] -> g a
- edges :: Graph g => [(a, a)] -> g a
- overlays :: Graph g => [g a] -> g a
- connects :: Graph g => [g a] -> g a
- isSubgraphOf :: (Graph g, Eq (g a)) => g a -> g a -> Bool
- isEmpty :: Graph g => g a -> Bool
- hasVertex :: (Eq a, Graph g) => a -> g a -> Bool
- hasEdge :: (Eq (g a), Graph g, Ord a) => a -> a -> g a -> Bool
- vertexCount :: (Ord a, Graph g) => g a -> Int
- vertexList :: (Ord a, Graph g) => g a -> [a]
- vertexSet :: (Ord a, Graph g) => g a -> Set a
- vertexIntSet :: Graph g => g Int -> IntSet
- path :: Graph g => [a] -> g a
- circuit :: Graph g => [a] -> g a
- clique :: Graph g => [a] -> g a
- biclique :: Graph g => [a] -> [a] -> g a
- star :: Graph g => a -> [a] -> g a
- starTranspose :: Graph g => a -> [a] -> g a
- tree :: Graph g => Tree a -> g a
- forest :: Graph g => Forest a -> g a
- mesh :: Graph g => [a] -> [b] -> g (a, b)
- torus :: Graph g => [a] -> [b] -> g (a, b)
- deBruijn :: Graph g => Int -> [a] -> g [a]
- removeVertex :: (Eq a, Graph g) => a -> g a -> g a
- replaceVertex :: (Eq a, Graph g) => a -> a -> g a -> g a
- mergeVertices :: Graph g => (a -> Bool) -> a -> g a -> g a
- splitVertex :: (Eq a, Graph g) => a -> [a] -> g a -> g a
- induce :: Graph g => (a -> Bool) -> g a -> g a
- box :: Graph g => g a -> g b -> g (a, b)
- class ToGraph t where
The core type class
class (Traversable g, MonadPlus g) => Graph g where Source #
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:
- The
empty
method comes from theAlternative
class and corresponds to the empty graph. This module simply re-exports it. - The
vertex
graph construction primitive is an alias forpure
of theApplicative
type class. - Graph
overlay
is an alias formplus
of theMonadPlus
type class.
The Graph
type class is characterised by the following minimal set of axioms.
In equations we use +
and *
as convenient shortcuts for overlay
and
connect
, respectively.
overlay
is commutative and associative:x + y == y + x x + (y + z) == (x + y) + z
connect
is associative and hasempty
as the identity:x * empty == x empty * x == x x * (y * z) == (x * y) * z
connect
distributes overoverlay
:x * (y + z) == x * y + x * z (x + y) * z == x * z + y * z
connect
can be decomposed:x * y * z == x * y + x * z + y * z
The following useful theorems can be proved from the above set of axioms.
overlay
hasempty
as the identity and is idempotent:x + empty == x empty + x == x x + x == x
Absorption and saturation of
connect
:x * y + x + y == x * y x * x * x == x * x
The core type class Graph
corresponds to unlabelled directed graphs.
Undirected
, Reflexive
, Transitive
and Preorder
graphs can be obtained
by extending the minimal set of axioms.
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.
empty :: Alternative f => forall a. f a #
The identity of <|>
vertex :: Graph g => a -> g a Source #
Construct the graph comprising a single isolated vertex. An alias for pure
.
Undirected graphs
class Graph g => Undirected g Source #
The class of undirected graphs that satisfy the following additional axiom.
connect
is commutative:x * y == y * x
Reflexive graphs
class Graph g => Reflexive g Source #
The class of reflexive graphs that satisfy the following additional axiom.
Each vertex has a self-loop:
vertex x == vertex x * vertex x
Or, alternatively, if we remember that vertex
is an alias for pure
:
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.
Transitive graphs
class Graph g => Transitive g Source #
The class of transitive graphs that satisfy the following additional axiom.
The closure axiom: graphs with equal transitive closures are equal.
y /= empty ==> x * y + x * z + y * z == x * y + y * z
By repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction.
Preorders
class (Reflexive g, Transitive g) => Preorder g Source #
The class of preorder graphs that are both reflexive and transitive.
Basic graph construction primitives
edge :: Graph g => a -> a -> g a Source #
Construct the graph comprising a single edge. Complexity: O(1) time, memory and size.
edge x y ==connect
(vertex
x) (vertex
y)vertexCount
(edge 1 1) == 1vertexCount
(edge 1 2) == 2
vertices :: Graph g => [a] -> g 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.
vertices [] ==empty
vertices [x] ==vertex
xhasVertex
x . vertices ==elem
xvertexCount
. vertices ==length
.nub
vertexSet
. vertices == Set.fromList
overlays :: Graph g => [g a] -> g 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.
overlays [] ==empty
overlays [x] == x overlays [x,y] ==overlay
x y overlays ==foldr
overlay
empty
isEmpty
. overlays ==all
isEmpty
connects :: Graph g => [g a] -> g 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.
connects [] ==empty
connects [x] == x connects [x,y] ==connect
x y connects ==foldr
connect
empty
isEmpty
. connects ==all
isEmpty
Relations on graphs
isSubgraphOf :: (Graph g, Eq (g a)) => g a -> g a -> Bool Source #
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.
isSubgraphOfempty
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
Graph properties
hasVertex :: (Eq a, Graph g) => a -> g a -> Bool Source #
Check if a graph contains a given vertex. A convenient alias for elem
.
Complexity: O(s) time.
hasVertex xempty
== False hasVertex x (vertex
x) == True hasVertex 1 (vertex
2) == False hasVertex x .removeVertex
x == const False
vertexCount :: (Ord a, Graph g) => g a -> Int Source #
The number of vertices in a graph. Complexity: O(s * log(n)) time.
vertexCountempty
== 0 vertexCount (vertex
x) == 1 vertexCount ==length
.vertexList
vertexList :: (Ord a, Graph g) => g a -> [a] Source #
vertexIntSet :: Graph g => g Int -> IntSet Source #
The set of vertices of a given graph. Like vertexSet
but specialised for
graphs with vertices of type Int
.
Complexity: O(s * log(n)) time and O(n) memory.
vertexIntSetempty
== IntSet.empty
vertexIntSet .vertex
== IntSet.singleton
vertexIntSet .vertices
== IntSet.fromList
vertexIntSet .clique
== IntSet.fromList
Standard families of graphs
biclique :: Graph g => [a] -> [a] -> g 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.
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)
starTranspose :: Graph g => a -> [a] -> g a Source #
The star transpose formed by a list of leaves connected to a centre vertex. Complexity: O(L) time, memory and size, where L is the length of the given list.
starTranspose x [] ==vertex
x starTranspose x [y] ==edge
y x starTranspose x [y,z] ==edges
[(y,x), (z,x)] starTranspose x ys ==connect
(vertices
ys) (vertex
x) starTranspose x ys == transpose (star
x ys)
tree :: Graph g => Tree a -> g 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 []) ==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)]
forest :: Graph g => Forest a -> g 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 [] ==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
. maptree
mesh :: Graph g => [a] -> [b] -> g (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 [] ==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')) ]
torus :: Graph g => [a] -> [b] -> g (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 [] ==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')) ]
deBruijn :: Graph g => Int -> [a] -> g [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 [] ==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 xsvertexCount
(deBruijn n xs) == (length
$nub
xs)^n n > 0 ==>edgeCount
(deBruijn n xs) == (length
$nub
xs)^(n + 1)
Graph transformation
removeVertex :: (Eq a, Graph g) => a -> g a -> g a Source #
replaceVertex :: (Eq a, Graph g) => a -> a -> g a -> g a Source #
The function
replaces vertex 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.
replaceVertex x x == id replaceVertex x y (vertex
x) ==vertex
y replaceVertex x y ==mergeVertices
(== x) y
mergeVertices :: Graph g => (a -> Bool) -> a -> g a -> g a Source #
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
splitVertex :: (Eq a, Graph g) => a -> [a] -> g a -> g 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.
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)
induce :: Graph g => (a -> Bool) -> g a -> g 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 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
Graph composition
box :: Graph g => g a -> g b -> g (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 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 xempty
~~empty
vertexCount
(box x y) ==vertexCount
x *vertexCount
yedgeCount
(box x y) <=vertexCount
x *edgeCount
y +edgeCount
x *vertexCount
y
Conversion between graph data types
class ToGraph t where Source #
The ToGraph
type class captures data types that can be converted to
polymorphic graph expressions. The conversion method toGraph
semantically
acts as the identity on graph data structures, but allows to convert graphs
between different data representations.
toGraph (g ::Graph
a ) ::Graph
a == gshow
(toGraph (1 * 2 ::Graph
Int) ::Fold
Int) == "edge 1 2"