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 the`Alternative`

class and corresponds to the*empty graph*. This module simply re-exports it. - The
`vertex`

graph construction primitive is an alias for`pure`

of the`Applicative`

type class. - Graph
`overlay`

is an alias for`mplus`

of the`MonadPlus`

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

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) == 1`vertexCount`

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

x`hasVertex`

x . vertices ==`elem`

x`vertexCount`

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

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

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

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

vertexCount`empty`

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

vertexIntSet`empty`

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

. map`tree`

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

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

~~`empty`

`vertexCount`

(box x y) ==`vertexCount`

x *`vertexCount`

y`edgeCount`

(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 == g`show`

(toGraph (1 * 2 ::`Graph`

Int) ::`Fold`

Int) == "edge 1 2"