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

data type, as well as associated
operations and algorithms. `Relation`

is an instance of the `Graph`

type
class, which can be used for polymorphic graph construction and manipulation.

- data Relation a
- domain :: Relation a -> Set a
- relation :: Relation a -> Set (a, a)
- empty :: Ord a => Relation a
- vertex :: Ord a => a -> Relation a
- edge :: Ord a => a -> a -> Relation a
- overlay :: Ord a => Relation a -> Relation a -> Relation a
- connect :: Ord a => Relation a -> Relation a -> Relation a
- vertices :: Ord a => [a] -> Relation a
- edges :: Ord a => [(a, a)] -> Relation a
- overlays :: Ord a => [Relation a] -> Relation a
- connects :: Ord a => [Relation a] -> Relation a
- graph :: Ord a => [a] -> [(a, a)] -> Relation a
- fromAdjacencyList :: Ord a => [(a, [a])] -> Relation a
- isSubgraphOf :: Ord a => Relation a -> Relation a -> Bool
- isEmpty :: Relation a -> Bool
- hasVertex :: Ord a => a -> Relation a -> Bool
- hasEdge :: Ord a => a -> a -> Relation a -> Bool
- vertexCount :: Relation a -> Int
- edgeCount :: Relation a -> Int
- vertexList :: Relation a -> [a]
- edgeList :: Relation a -> [(a, a)]
- vertexSet :: Relation a -> Set a
- vertexIntSet :: Relation Int -> IntSet
- edgeSet :: Relation a -> Set (a, a)
- preSet :: Ord a => a -> Relation a -> Set a
- postSet :: Ord a => a -> Relation a -> Set a
- path :: Ord a => [a] -> Relation a
- circuit :: Ord a => [a] -> Relation a
- clique :: Ord a => [a] -> Relation a
- biclique :: Ord a => [a] -> [a] -> Relation a
- star :: Ord a => a -> [a] -> Relation a
- tree :: Ord a => Tree a -> Relation a
- forest :: Ord a => Forest a -> Relation a
- removeVertex :: Ord a => a -> Relation a -> Relation a
- removeEdge :: Ord a => a -> a -> Relation a -> Relation a
- replaceVertex :: Ord a => a -> a -> Relation a -> Relation a
- mergeVertices :: Ord a => (a -> Bool) -> a -> Relation a -> Relation a
- transpose :: Ord a => Relation a -> Relation a
- gmap :: Ord b => (a -> b) -> Relation a -> Relation b
- induce :: (a -> Bool) -> Relation a -> Relation a
- compose :: Ord a => Relation a -> Relation a -> Relation a
- reflexiveClosure :: Ord a => Relation a -> Relation a
- symmetricClosure :: Ord a => Relation a -> Relation a
- transitiveClosure :: Ord a => Relation a -> Relation a
- preorderClosure :: Ord a => Relation a -> Relation a

# Data structure

The `Relation`

data type represents a graph as a *binary relation*. 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 `Show`

instance is defined using basic graph construction primitives:

show (empty :: Relation Int) == "empty" show (1 :: Relation Int) == "vertex 1" show (1 + 2 :: Relation Int) == "vertices [1,2]" show (1 * 2 :: Relation Int) == "edge 1 2" show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Relation Int) == "graph [1,2,3] [(1,2)]"

The `Eq`

instance 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* and *m*
will denote the number of vertices and edges in the graph, respectively.

relation :: Relation a -> Set (a, a) Source #

The set of pairs of elements that are *related*. It is guaranteed that
each element belongs to the domain.

# Basic graph construction primitives

empty :: Ord a => Relation a Source #

Construct the *empty graph*.
Complexity: *O(1)* time and memory.

`isEmpty`

empty == True`hasVertex`

x empty == False`vertexCount`

empty == 0`edgeCount`

empty == 0

vertex :: Ord a => a -> Relation a Source #

Construct the graph comprising *a single isolated vertex*.
Complexity: *O(1)* time and memory.

`isEmpty`

(vertex x) == False`hasVertex`

x (vertex x) == True`hasVertex`

1 (vertex 2) == False`vertexCount`

(vertex x) == 1`edgeCount`

(vertex x) == 0

edge :: Ord a => a -> a -> Relation 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 :: Ord a => Relation a -> Relation a -> Relation a Source #

*Overlay* two graphs. This is an idempotent, commutative and associative
operation with the identity `empty`

.
Complexity: *O((n + m) * log(n))* time and *O(n + m)* memory.

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

(overlay 1 2) == 2`edgeCount`

(overlay 1 2) == 0

connect :: Ord a => Relation a -> Relation a -> Relation a Source #

*Connect* two graphs. This is an associative operation with the identity
`empty`

, which distributes over the overlay and obeys the decomposition axiom.
Complexity: *O((n + m) * log(n))* time and *O(n + m)* memory. 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`vertexCount`

(connect 1 2) == 2`edgeCount`

(connect 1 2) == 1

vertices :: Ord a => [a] -> Relation a Source #

Construct the graph comprising a given list of isolated vertices.
Complexity: *O(L * log(L))* time and *O(L)* memory, 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`

graph :: Ord a => [a] -> [(a, a)] -> Relation 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((n + m) * log(n))* time and *O(n + m)* memory.

graph [] [] ==`empty`

graph [x] [] ==`vertex`

x graph [] [(x,y)] ==`edge`

x y graph vs es ==`overlay`

(`vertices`

vs) (`edges`

es)

fromAdjacencyList :: Ord a => [(a, [a])] -> Relation a Source #

# Relations on graphs

isSubgraphOf :: Ord a => Relation a -> Relation a -> Bool Source #

The `isSubgraphOf`

function takes two graphs and returns `True`

if the
first graph is a *subgraph* of the second.
Complexity: *O((n + m) * log(n))* time.

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

isEmpty :: Relation a -> Bool Source #

Check if a relation is empty.
Complexity: *O(1)* 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 :: Ord a => a -> Relation a -> Bool Source #

Check if a graph contains a given vertex.
Complexity: *O(log(n))* time.

hasVertex x`empty`

== False hasVertex x (`vertex`

x) == True hasVertex x .`removeVertex`

x == const False

vertexCount :: Relation a -> Int Source #

The number of vertices in a graph.
Complexity: *O(1)* time.

vertexCount`empty`

== 0 vertexCount (`vertex`

x) == 1 vertexCount ==`length`

.`vertexList`

vertexList :: Relation a -> [a] Source #

preSet :: Ord a => a -> Relation a -> Set a Source #

The *preset* of an element `x`

is the set of elements that are related to
it on the *left*, i.e. `preSet x == { a | aRx }`

. In the context of directed
graphs, this corresponds to the set of *direct predecessors* of vertex `x`

.
Complexity: *O(n + m)* time and *O(n)* memory.

preSet x`empty`

== Set.`empty`

preSet x (`vertex`

x) == Set.`empty`

preSet 1 (`edge`

1 2) == Set.`empty`

preSet y (`edge`

x y) == Set.`fromList`

[x]

postSet :: Ord a => a -> Relation a -> Set a Source #

The *postset* of an element `x`

is the set of elements that are related to
it on the *right*, i.e. `postSet x == { a | xRa }`

. In the context of directed
graphs, this corresponds to the set of *direct successors* of vertex `x`

.
Complexity: *O(n + m)* time and *O(n)* memory.

postSet x`empty`

== Set.`empty`

postSet x (`vertex`

x) == Set.`empty`

postSet x (`edge`

x y) == Set.`fromList`

[y] postSet 2 (`edge`

1 2) == Set.`empty`

# Standard families of graphs

tree :: Ord a => Tree a -> Relation a Source #

The *tree graph* constructed from a given `Tree`

data structure.
Complexity: *O((n + m) * log(n))* time and *O(n + m)* memory.

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

# Graph transformation

removeEdge :: Ord a => a -> a -> Relation a -> Relation a Source #

Remove an edge from a given graph.
Complexity: *O(log(m))* time.

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 :: Ord a => a -> a -> Relation a -> Relation a Source #

The function

replaces vertex `replaceVertex`

x y`x`

with vertex `y`

in a
given `AdjacencyMap`

. If `y`

already exists, `x`

and `y`

will be merged.
Complexity: *O((n + m) * log(n))* time.

replaceVertex x x == id replaceVertex x y (`vertex`

x) ==`vertex`

y replaceVertex x y ==`mergeVertices`

(== x) y

mergeVertices :: Ord a => (a -> Bool) -> a -> Relation a -> Relation a Source #

Merge vertices satisfying a given predicate with a given vertex.
Complexity: *O((n + m) * log(n))* time, 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

transpose :: Ord a => Relation a -> Relation a Source #

Transpose a given graph.
Complexity: *O(m * log(m))* time.

transpose`empty`

==`empty`

transpose (`vertex`

x) ==`vertex`

x transpose (`edge`

x y) ==`edge`

y x transpose . transpose == id transpose .`path`

==`path`

.`reverse`

transpose .`circuit`

==`circuit`

.`reverse`

transpose .`clique`

==`clique`

.`reverse`

`edgeList`

. transpose ==`sort`

. map`swap`

.`edgeList`

gmap :: Ord b => (a -> b) -> Relation a -> Relation b Source #

Transform a graph by applying a function to each of its vertices. This is
similar to `Functor`

's `fmap`

but can be used with non-fully-parametric
`Relation`

.
Complexity: *O((n + m) * log(n))* time.

gmap f`empty`

==`empty`

gmap f (`vertex`

x) ==`vertex`

(f x) gmap f (`edge`

x y) ==`edge`

(f x) (f y) gmap id == id gmap f . gmap g == gmap (f . g)

induce :: (a -> Bool) -> Relation a -> Relation a Source #

Construct the *induced subgraph* of a given graph by removing the
vertices that do not satisfy a given predicate.
Complexity: *O(m)* time, 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

# Operations on binary relations

compose :: Ord a => Relation a -> Relation a -> Relation a Source #

*Compose* two relations: `R = `

. Two elements `compose`

Q P`x`

and `y`

are
related in the resulting relation, i.e. `xRy`

, if there exists an element `z`

,
such that `xPz`

and `zQy`

. This is an associative operation which has `empty`

as the *annihilating zero*.
Complexity: *O(n * m * log(m))* time and *O(n + m)* memory.

compose`empty`

x ==`empty`

compose x`empty`

==`empty`

compose x (compose y z) == compose (compose x y) z compose (`edge`

y z) (`edge`

x y) ==`edge`

x z compose (`path`

[1..5]) (`path`

[1..5]) ==`edges`

[(1,3),(2,4),(3,5)] compose (`circuit`

[1..5]) (`circuit`

[1..5]) ==`circuit`

[1,3,5,2,4]