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 data type NonEmptyGraph
for graphs that are known
to be non-empty at compile time. 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
.
- data NonEmptyGraph a
- = Vertex a
- | Overlay (NonEmptyGraph a) (NonEmptyGraph a)
- | Connect (NonEmptyGraph a) (NonEmptyGraph a)
- toNonEmptyGraph :: Graph a -> Maybe (NonEmptyGraph a)
- vertex :: a -> NonEmptyGraph a
- edge :: a -> a -> NonEmptyGraph a
- overlay :: NonEmptyGraph a -> NonEmptyGraph a -> NonEmptyGraph a
- overlay1 :: Graph a -> NonEmptyGraph a -> NonEmptyGraph a
- connect :: NonEmptyGraph a -> NonEmptyGraph a -> NonEmptyGraph a
- vertices1 :: NonEmpty a -> NonEmptyGraph a
- edges1 :: NonEmpty (a, a) -> NonEmptyGraph a
- overlays1 :: NonEmpty (NonEmptyGraph a) -> NonEmptyGraph a
- connects1 :: NonEmpty (NonEmptyGraph a) -> NonEmptyGraph a
- foldg1 :: (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> NonEmptyGraph a -> b
- isSubgraphOf :: Ord a => NonEmptyGraph a -> NonEmptyGraph a -> Bool
- (===) :: Eq a => NonEmptyGraph a -> NonEmptyGraph a -> Bool
- size :: NonEmptyGraph a -> Int
- hasVertex :: Eq a => a -> NonEmptyGraph a -> Bool
- hasEdge :: Ord a => a -> a -> NonEmptyGraph a -> Bool
- vertexCount :: Ord a => NonEmptyGraph a -> Int
- edgeCount :: Ord a => NonEmptyGraph a -> Int
- vertexList1 :: Ord a => NonEmptyGraph a -> NonEmpty a
- edgeList :: Ord a => NonEmptyGraph a -> [(a, a)]
- vertexSet :: Ord a => NonEmptyGraph a -> Set a
- vertexIntSet :: NonEmptyGraph Int -> IntSet
- edgeSet :: Ord a => NonEmptyGraph a -> Set (a, a)
- path1 :: NonEmpty a -> NonEmptyGraph a
- circuit1 :: NonEmpty a -> NonEmptyGraph a
- clique1 :: NonEmpty a -> NonEmptyGraph a
- biclique1 :: NonEmpty a -> NonEmpty a -> NonEmptyGraph a
- star :: a -> [a] -> NonEmptyGraph a
- starTranspose :: a -> [a] -> NonEmptyGraph a
- tree :: Tree a -> NonEmptyGraph a
- mesh1 :: NonEmpty a -> NonEmpty b -> NonEmptyGraph (a, b)
- torus1 :: NonEmpty a -> NonEmpty b -> NonEmptyGraph (a, b)
- removeVertex1 :: Eq a => a -> NonEmptyGraph a -> Maybe (NonEmptyGraph a)
- removeEdge :: Eq a => a -> a -> NonEmptyGraph a -> NonEmptyGraph a
- replaceVertex :: Eq a => a -> a -> NonEmptyGraph a -> NonEmptyGraph a
- mergeVertices :: (a -> Bool) -> a -> NonEmptyGraph a -> NonEmptyGraph a
- splitVertex1 :: Eq a => a -> NonEmpty a -> NonEmptyGraph a -> NonEmptyGraph a
- transpose :: NonEmptyGraph a -> NonEmptyGraph a
- induce1 :: (a -> Bool) -> NonEmptyGraph a -> Maybe (NonEmptyGraph a)
- simplify :: Ord a => NonEmptyGraph a -> NonEmptyGraph a
- box :: NonEmptyGraph a -> NonEmptyGraph b -> NonEmptyGraph (a, b)
Algebraic data type for non-empty graphs
data NonEmptyGraph a Source #
The NonEmptyGraph
data type is a deep embedding of the core graph
construction primitives vertex
, overlay
and connect
. As one can guess from
the name, the empty graph cannot be represented using this data type. See module
Algebra.Graph for a graph data type that allows for the construction of the
empty graph.
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 that the signum
method of the Num
type class cannot be implemented.
The Eq
instance is currently implemented using the AdjacencyMap
as the
canonical graph representation and satisfies the following laws of algebraic
graphs:
overlay
is commutative, associative and idempotent:x + y == y + x x + (y + z) == (x + y) + z x + x == x
connect
is associative: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
connect
satisfies absorption and saturation: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
NonEmptyGraph
expression, defined as the number of vertex leaves. For example,
if g
is a NonEmptyGraph
then n, m and s can be computed as follows:
n ==vertexCount
g m ==edgeCount
g s ==size
g
The size
of any graph is positive and coincides with the result of length
method of the Foldable
type class. We define size
only for the consistency
with the API of other graph representations, such as Algebra.Graph.
Converting a NonEmptyGraph
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.
Vertex a | |
Overlay (NonEmptyGraph a) (NonEmptyGraph a) | |
Connect (NonEmptyGraph a) (NonEmptyGraph a) |
Monad NonEmptyGraph Source # | |
Functor NonEmptyGraph Source # | |
Applicative NonEmptyGraph Source # | |
Foldable NonEmptyGraph Source # | |
Traversable NonEmptyGraph Source # | |
ToGraph NonEmptyGraph Source # | |
Ord a => Eq (NonEmptyGraph a) Source # | |
Num a => Num (NonEmptyGraph a) Source # | |
Show a => Show (NonEmptyGraph a) Source # | |
NFData a => NFData (NonEmptyGraph a) Source # | |
ToGraph (NonEmptyGraph a) Source # | |
type ToVertex (NonEmptyGraph a) Source # | |
toNonEmptyGraph :: Graph a -> Maybe (NonEmptyGraph a) Source #
Basic graph construction primitives
vertex :: a -> NonEmptyGraph a Source #
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) == TruevertexCount
(vertex x) == 1edgeCount
(vertex x) == 0size
(vertex x) == 1
edge :: a -> a -> NonEmptyGraph 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 :: NonEmptyGraph a -> NonEmptyGraph a -> NonEmptyGraph a Source #
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 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
overlay1 :: Graph a -> NonEmptyGraph a -> NonEmptyGraph a Source #
Overlay a possibly empty 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.
overlay1empty
x == x x /=empty
==> overlay1 x y == overlay (fromJust $ toNonEmptyGraph x) y
connect :: NonEmptyGraph a -> NonEmptyGraph a -> NonEmptyGraph a Source #
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 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
vertices1 :: NonEmpty a -> NonEmptyGraph a Source #
edges1 :: NonEmpty (a, a) -> NonEmptyGraph a Source #
overlays1 :: NonEmpty (NonEmptyGraph a) -> NonEmptyGraph a Source #
connects1 :: NonEmpty (NonEmptyGraph a) -> NonEmptyGraph a Source #
Graph folding
foldg1 :: (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> NonEmptyGraph a -> b Source #
Generalised graph folding: recursively collapse a NonEmptyGraph
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 (const 1) (+) (+) ==size
foldg1 (==x) (||) (||) ==hasVertex
x
Relations on graphs
isSubgraphOf :: Ord a => NonEmptyGraph a -> NonEmptyGraph 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.
isSubgraphOf x (overlay
x y) == True isSubgraphOf (overlay
x y) (connect
x y) == True isSubgraphOf (path1
xs) (circuit1
xs) == True
(===) :: Eq a => NonEmptyGraph a -> NonEmptyGraph a -> Bool infix 4 Source #
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
Graph properties
size :: NonEmptyGraph a -> Int Source #
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
hasEdge :: Ord a => a -> a -> NonEmptyGraph a -> Bool Source #
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
vertexCount :: Ord a => NonEmptyGraph a -> Int Source #
The number of vertices in a graph. Complexity: O(s * log(n)) time.
vertexCount (vertex
x) == 1 vertexCount x >= 1 vertexCount ==length
.vertexList1
vertexList1 :: Ord a => NonEmptyGraph a -> NonEmpty a Source #
edgeList :: Ord a => NonEmptyGraph 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.
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
. mapswap
. edgeList
vertexIntSet :: NonEmptyGraph Int -> IntSet Source #
Standard families of graphs
path1 :: NonEmpty a -> NonEmptyGraph a Source #
circuit1 :: NonEmpty a -> NonEmptyGraph a Source #
clique1 :: NonEmpty a -> NonEmptyGraph 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.
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
star :: a -> [a] -> NonEmptyGraph a Source #
starTranspose :: a -> [a] -> NonEmptyGraph 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] ==edges1
((y,x):|
[(z,x)]) starTranspose x ys ==transpose
(star
x ys)
tree :: Tree a -> NonEmptyGraph 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 []]]) ==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)])
mesh1 :: NonEmpty a -> NonEmpty b -> NonEmptyGraph (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.
mesh1 (x:|
[]) (y:|
[]) ==vertex
(x, y) mesh1 xs ys ==box
(path1
xs) (path1
ys) mesh1 (1:|
[2,3]) ('a':|
"b") ==edges1
(fromList
[ ((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')) ])
torus1 :: NonEmpty a -> NonEmpty b -> NonEmptyGraph (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.
torus1 (x:|
[]) (y:|
[]) ==edge
(x, y) (x, y) torus1 xs ys ==box
(circuit1
xs) (circuit1
ys) torus1 (1:|
[2]) ('a':|
"b") ==edges1
(fromList
[ ((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')) ])
Graph transformation
removeVertex1 :: Eq a => a -> NonEmptyGraph a -> Maybe (NonEmptyGraph a) Source #
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
removeEdge :: Eq a => a -> a -> NonEmptyGraph a -> NonEmptyGraph a Source #
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 * 2size
(removeEdge x y z) <= 3 *size
z
replaceVertex :: Eq a => a -> a -> NonEmptyGraph a -> NonEmptyGraph a Source #
The function
replaces vertex replaceVertex
x yx
with vertex y
in a
given NonEmptyGraph
. 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 :: (a -> Bool) -> a -> NonEmptyGraph a -> NonEmptyGraph 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
splitVertex1 :: Eq a => a -> NonEmpty a -> NonEmptyGraph a -> NonEmptyGraph 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.
splitVertex1 x (x:|
[] ) == id splitVertex1 x (y:|
[] ) ==replaceVertex
x y splitVertex1 1 (0:|
[1]) $ 1 * (2 + 3) == (0 + 1) * (2 + 3)
transpose :: NonEmptyGraph a -> NonEmptyGraph a Source #
induce1 :: (a -> Bool) -> NonEmptyGraph a -> Maybe (NonEmptyGraph a) Source #
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)
simplify :: Ord a => NonEmptyGraph a -> NonEmptyGraph 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 simplify 1===
1 simplify (1 + 1)===
1 simplify (1 + 2 + 1)===
1 + 2 simplify (1 * 1 * 1)===
1 * 1
Graph composition
box :: NonEmptyGraph a -> NonEmptyGraph b -> NonEmptyGraph (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 (path1
$fromList
[0,1]) (path1
$fromList
"ab") ==edges1
(fromList
[ ((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
()) ~~ xtranspose
(box x y) == box (transpose
x) (transpose
y)vertexCount
(box x y) ==vertexCount
x *vertexCount
yedgeCount
(box x y) <=vertexCount
x *edgeCount
y +edgeCount
x *vertexCount
y