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 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.

- 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
- 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 :: Ord 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
- starTranspose :: 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
- simplify :: Ord a => Graph a -> Graph a
- box :: Graph a -> Graph b -> Graph (a, b)

# 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 == 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 has`empty`

as the identity:x * empty == x empty * x == x x * (y * z) == (x * y) * z

`connect`

distributes over`overlay`

: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`

has`empty`

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`

== 0`size`

`empty`

== 1`length`

(`vertex`

x) == 1`size`

(`vertex`

x) == 1`length`

(`empty`

+`empty`

) == 0`size`

(`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 # | |

NFData a => NFData (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) == True`edgeCount`

(edge x y) == 1`vertexCount`

(edge 1 1) == 1`vertexCount`

(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) ==`isEmpty`

x &&`isEmpty`

y`hasVertex`

z (overlay x y) ==`hasVertex`

z x ||`hasVertex`

z y`vertexCount`

(overlay x y) >=`vertexCount`

x`vertexCount`

(overlay x y) <=`vertexCount`

x +`vertexCount`

y`edgeCount`

(overlay x y) >=`edgeCount`

x`edgeCount`

(overlay x y) <=`edgeCount`

x +`edgeCount`

y`size`

(overlay x y) ==`size`

x +`size`

y`vertexCount`

(overlay 1 2) == 2`edgeCount`

(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) ==`isEmpty`

x &&`isEmpty`

y`hasVertex`

z (connect x y) ==`hasVertex`

z x ||`hasVertex`

z y`vertexCount`

(connect x y) >=`vertexCount`

x`vertexCount`

(connect x y) <=`vertexCount`

x +`vertexCount`

y`edgeCount`

(connect x y) >=`edgeCount`

x`edgeCount`

(connect x y) >=`edgeCount`

y`edgeCount`

(connect x y) >=`vertexCount`

x *`vertexCount`

y`edgeCount`

(connect x y) <=`vertexCount`

x *`vertexCount`

y +`edgeCount`

x +`edgeCount`

y`size`

(connect x y) ==`size`

x +`size`

y`vertexCount`

(connect 1 2) == 2`edgeCount`

(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`

x`hasVertex`

x . vertices ==`elem`

x`vertexCount`

. vertices ==`length`

.`nub`

`vertexSet`

. 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.

overlays [] ==`empty`

overlays [x] == x overlays [x,y] ==`overlay`

x y overlays ==`foldr`

`overlay`

`empty`

`isEmpty`

. overlays ==`all`

`isEmpty`

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.

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) -> 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)*.

foldg`empty`

`vertex`

`overlay`

`connect`

== id foldg`empty`

`vertex`

`overlay`

(flip`connect`

) ==`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*.

isSubgraphOf`empty`

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.

isEmpty`empty`

== 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 x`empty`

== False hasVertex x (`vertex`

x) == True hasVertex 1 (`vertex`

2) == False hasVertex x .`removeVertex`

x == const False

vertexCount :: Ord a => Graph a -> Int Source #

The number of vertices in a graph.
Complexity: *O(s * log(n))* time.

vertexCount`empty`

== 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*.

edgeList`empty`

== [] 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

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.

vertexIntSet`empty`

== IntSet.`empty`

vertexIntSet .`vertex`

== IntSet.`singleton`

vertexIntSet .`vertices`

== IntSet.`fromList`

vertexIntSet .`clique`

== IntSet.`fromList`

# 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.

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] -> 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.

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 :: a -> [a] -> Graph 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 :: 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 []) ==`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 :: 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 [] ==`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`

. map`tree`

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 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 xs`vertexCount`

(deBruijn n xs) == (`length`

$`nub`

xs)^n n > 0 ==>`edgeCount`

(deBruijn n xs) == (`length`

$`nub`

xs)^(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 (`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`size`

(removeEdge x y z) <= 3 *`size`

z

replaceVertex :: Eq a => a -> a -> Graph a -> Graph a Source #

The function

replaces vertex `replaceVertex`

x y`x`

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 :: (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
*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 == id`size`

(simplify x) <=`size`

x simplify`empty`

`===`

`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 x`empty`

~~`empty`

`transpose`

(box x y) == box (`transpose`

x) (`transpose`

y)`vertexCount`

(box x y) ==`vertexCount`

x *`vertexCount`

y`edgeCount`

(box x y) <=`vertexCount`

x *`edgeCount`

y +`edgeCount`

x *`vertexCount`

y