Copyright | (c) Andrey Mokhov 2016-2017 |
---|---|
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 data type Graph
and associated algorithms.
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.
- 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
- graph :: [a] -> [(a, a)] -> Graph a
- foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
- 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
- vertexIntSet :: Graph Int -> IntSet
- edgeSet :: Ord a => Graph a -> Set (a, a)
- path :: [a] -> Graph a
- circuit :: [a] -> Graph a
- clique :: [a] -> Graph a
- biclique :: [a] -> [a] -> Graph a
- star :: 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 :: Eq a => (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
- simplify :: Ord a => Graph a -> Graph a
- box :: Graph a -> Graph b -> Graph (a, b)
Algebraic data type for graphs
The Graph
datatype is a deep embedding of the core graph construction
primitives empty
, vertex
, overlay
and connect
. We define a
law-abiding 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))
The Eq
instance is currently implemented using the AdjacencyMap
as the
canonical graph representation and satisfies all axioms of algebraic graphs:
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
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 ==vertexCount
g m ==edgeCount
g s ==size
g
Note that size
is slightly different from the length
method of the
Foldable
type class, as the latter does not count empty
leaves of the
expression:
length
empty
== 0size
empty
== 1length
(vertex
x) == 1size
(vertex
x) == 1length
(empty
+empty
) == 0size
(empty
+empty
) == 2
The size
of any graph is positive, and the difference (
corresponds to the number of occurrences of size
g - length
g)empty
in an expression 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.
Monad Graph Source # | |
Functor Graph Source # | |
Applicative Graph Source # | |
Foldable Graph Source # | |
Traversable Graph Source # | |
Alternative Graph Source # | |
MonadPlus Graph Source # | |
ToGraph Graph Source # | |
Graph Graph Source # | |
Ord a => Eq (Graph a) Source # | |
Num a => Num (Graph a) Source # | |
Show a => Show (Graph a) Source # | |
ToGraph (Graph a) Source # | |
Graph (Graph a) Source # | |
type ToVertex (Graph a) Source # | |
type Vertex (Graph a) Source # | |
Basic graph construction primitives
edge :: a -> a -> Graph a Source #
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) == 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 an
idempotent, commutative and associative operation with the identity empty
.
Complexity: O(1) time and memory, O(s1 + s2) size.
isEmpty
(overlay x y) ==isEmpty
x &&isEmpty
yhasVertex
z (overlay x y) ==hasVertex
z x ||hasVertex
z yvertexCount
(overlay x y) >=vertexCount
xvertexCount
(overlay x y) <=vertexCount
x +vertexCount
yedgeCount
(overlay x y) >=edgeCount
xedgeCount
(overlay x y) <=edgeCount
x +edgeCount
ysize
(overlay x y) ==size
x +size
yvertexCount
(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 the
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
yhasVertex
z (connect x y) ==hasVertex
z x ||hasVertex
z yvertexCount
(connect x y) >=vertexCount
xvertexCount
(connect x y) <=vertexCount
x +vertexCount
yedgeCount
(connect x y) >=edgeCount
xedgeCount
(connect x y) >=edgeCount
yedgeCount
(connect x y) >=vertexCount
x *vertexCount
yedgeCount
(connect x y) <=vertexCount
x *vertexCount
y +edgeCount
x +edgeCount
ysize
(connect x y) ==size
x +size
yvertexCount
(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.
vertices [] ==empty
vertices [x] ==vertex
xhasVertex
x . vertices ==elem
xvertexCount
. vertices ==length
.nub
vertexSet
. vertices == Set.fromList
graph :: [a] -> [(a, a)] -> Graph a Source #
Construct the graph from given lists of vertices V and edges E. The resulting graph contains the vertices V as well as all the vertices referred to by the edges E. Complexity: O(|V| + |E|) time, memory and size.
graph [] [] ==empty
graph [x] [] ==vertex
x graph [] [(x,y)] ==edge
x y graph vs es ==overlay
(vertices
vs) (edges
es)
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 given functions. As an example, the
complexity of size
is O(s), since all functions have cost O(1).
foldgempty
vertex
overlay
connect
== id foldgempty
vertex
overlay
(flipconnect
) ==transpose
foldg [] return (++) (++) ==toList
foldg 0 (const 1) (+) (+) ==length
foldg 1 (const 1) (+) (+) ==size
foldg True (const False) (&&) (&&) ==isEmpty
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.
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
(===) :: 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. A convenient alias for null
.
Complexity: O(s) time.
isEmptyempty
== True isEmpty (overlay
empty
empty
) == True isEmpty (vertex
x) == False isEmpty (removeVertex
x $vertex
x) == True isEmpty (removeEdge
x y $edge
x y) == False
hasVertex :: Eq a => a -> Graph 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 x .removeVertex
x == const False
hasEdge :: Eq a => a -> a -> Graph a -> Bool Source #
Check if a graph contains a given edge. Complexity: O(s) time.
hasEdge x yempty
== False hasEdge x y (vertex
z) == False hasEdge x y (edge
x y) == True hasEdge x y .removeEdge
x y == const False
vertexCount :: Ord a => Graph 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 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.
edgeListempty
== [] edgeList (vertex
x) == [] edgeList (edge
x y) == [(x,y)] edgeList (star
2 [3,1]) == [(2,1), (2,3)] edgeList .edges
==nub
.sort
vertexIntSet :: Graph 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
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).
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).
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 [] ==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 :: [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 [] ==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 :: Int -> [a] -> Graph [a] Source #
Construct a De Bruijn graph of given dimension and symbols of a given alphabet. Complexity: O(A * D^A) time, memory and size, where A is the size of the alphabet and D is the dimention of the graph.
deBruijn k [] ==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") ]
Graph transformation
removeEdge :: Eq a => a -> a -> Graph a -> Graph a Source #
Remove an edge from a given graph. Complexity: O(s) time and memory.
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
replaceVertex :: Eq a => a -> a -> Graph a -> Graph 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 :: Eq a => (a -> Bool) -> a -> Graph a -> Graph a Source #
Merge vertices satisfying a given predicate with 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 => 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.
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 :: (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 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
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.
simplify == idsize
(simplify x) <=size
x simplifyempty
===
empty
simplify 1===
1 simplify (1 + 1)===
1 simplify (1 + 2 + 1)===
1 + 2 simplify (1 * 1 * 1)===
1 * 1
Graph composition
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 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