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 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.
Synopsis
- data Fold a
- empty :: Fold a
- vertex :: a -> Fold a
- edge :: a -> a -> Fold a
- overlay :: Fold a -> Fold a -> Fold a
- connect :: Fold a -> Fold a -> Fold a
- vertices :: [a] -> Fold a
- edges :: [(a, a)] -> Fold a
- overlays :: [Fold a] -> Fold a
- connects :: [Fold a] -> Fold a
- foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Fold a -> b
- isSubgraphOf :: Ord a => Fold a -> Fold a -> Bool
- isEmpty :: Fold a -> Bool
- size :: Fold a -> Int
- hasVertex :: Eq a => a -> Fold a -> Bool
- hasEdge :: Eq a => a -> a -> Fold a -> Bool
- vertexCount :: Ord a => Fold a -> Int
- edgeCount :: Ord a => Fold a -> Int
- vertexList :: Ord a => Fold a -> [a]
- edgeList :: Ord a => Fold a -> [(a, a)]
- vertexSet :: Ord a => Fold a -> Set a
- edgeSet :: Ord a => Fold a -> Set (a, a)
- adjacencyList :: Ord a => Fold a -> [(a, [a])]
- path :: [a] -> Fold a
- circuit :: [a] -> Fold a
- clique :: [a] -> Fold a
- biclique :: [a] -> [a] -> Fold a
- star :: a -> [a] -> Fold a
- stars :: [(a, [a])] -> Fold a
- removeVertex :: Eq a => a -> Fold a -> Fold a
- removeEdge :: Eq a => a -> a -> Fold a -> Fold a
- transpose :: Fold a -> Fold a
- induce :: (a -> Bool) -> Fold a -> Fold a
- simplify :: Ord a => Fold a -> Fold a
Boehm-Berarducci encoding of algebraic graphs
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:
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 Fold
then n, m and s can be
computed as follows:
n ==vertexCount
g m ==edgeCount
g s ==size
g
Note that size
counts all leaves of the expression:
vertexCount
empty
== 0size
empty
== 1vertexCount
(vertex
x) == 1size
(vertex
x) == 1vertexCount
(empty
+empty
) == 0size
(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:
- 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:
vertex
1 <vertex
2vertex
3 <edge
1 2vertex
1 <edge
1 1edge
1 1 <edge
1 2edge
1 2 <edge
1 1 +edge
2 2edge
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
Instances
Basic graph construction primitives
Construct the empty graph. Complexity: O(1) time, memory and size.
isEmpty
empty == TruehasVertex
x empty == FalsevertexCount
empty == 0edgeCount
empty == 0size
empty == 1
vertex :: a -> Fold a Source #
Construct the graph comprising a single isolated vertex. Complexity: O(1) time, memory and size.
isEmpty
(vertex x) == FalsehasVertex
x (vertex x) == TruevertexCount
(vertex x) == 1edgeCount
(vertex x) == 0size
(vertex x) == 1
edge :: a -> a -> Fold 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 :: Fold a -> Fold a -> Fold a Source #
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
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 :: Fold a -> Fold a -> Fold a Source #
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
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] -> Fold 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 :: [Fold a] -> Fold 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 :: [Fold a] -> Fold 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
Graph folding
foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Fold 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
(flip
connect
) ==transpose
foldg 1 (const
1) (+) (+) ==size
foldg True (const
False) (&&) (&&) ==isEmpty
foldg False (== x) (||) (||) ==hasVertex
x
Relations on graphs
isSubgraphOf :: Ord a => Fold a -> Fold 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 isSubgraphOf x y ==> x <= y
Graph properties
isEmpty :: Fold 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 -> Fold a -> Bool Source #
Check if a graph contains a given vertex. 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 => Fold 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
vertexCount x < vertexCount y ==> x < y
vertexList :: Ord a => Fold a -> [a] Source #
edgeList :: Ord a => Fold 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
edgeList .transpose
==sort
.map
swap
. edgeList
adjacencyList :: Ord a => Fold a -> [(a, [a])] Source #
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.
adjacencyListempty
== [] adjacencyList (vertex
x) == [(x, [])] adjacencyList (edge
1 2) == [(1, [2]), (2, [])] adjacencyList (star
2 [3,1]) == [(1, []), (2, [1,3]), (3, [])]stars
. adjacencyList == id
Standard families of graphs
clique :: [a] -> Fold 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.
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
biclique :: [a] -> [a] -> Fold 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)
stars :: [(a, [a])] -> Fold a Source #
The stars formed by overlaying a list of star
s. 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
== idoverlay
(stars xs) (stars ys) == stars (xs ++ ys)
Graph transformation
removeEdge :: Eq a => a -> a -> Fold a -> Fold a Source #
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 * 2size
(removeEdge x y z) <= 3 *size
z
induce :: (a -> Bool) -> Fold a -> Fold 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 => Fold a -> Fold a Source #
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 == 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