Copyright | (c) Andrey Mokhov 2016-2019 |
---|---|

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.

## Synopsis

- data Relation a
- domain :: Relation a -> Set a
- relation :: Relation a -> Set (a, a)
- empty :: Relation a
- vertex :: 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
- 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)]
- adjacencyList :: Eq a => Relation a -> [(a, [a])]
- vertexSet :: Relation a -> Set a
- 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
- stars :: 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
- induceJust :: Ord a => Relation (Maybe a) -> Relation a
- compose :: Ord a => Relation a -> Relation a -> Relation a
- closure :: Ord 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
- consistent :: Ord a => Relation a -> Bool

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

**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 :: 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) == "overlay (vertex 3) (edge 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.

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`

2`vertex`

3 <`edge`

1 2`vertex`

1 <`edge`

1 1`edge`

1 1 <`edge`

1 2`edge`

1 2 <`edge`

1 1 +`edge`

2 2`edge`

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

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. Complexity: *O(1)* time and memory.

# Basic graph construction primitives

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

`isEmpty`

empty == True`hasVertex`

x empty == False`vertexCount`

empty == 0`edgeCount`

empty == 0

vertex :: 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 y) == (x == y)`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 a commutative, associative and idempotent
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 `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`

# 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 isSubgraphOf x y ==> x <= y

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

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

vertexCount x < vertexCount y ==> x < y

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

adjacencyList :: Eq a => Relation a -> [(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

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

The *stars* formed by overlaying a list of `star`

s. An inverse of
`adjacencyList`

.
Complexity: *O(L * log(n))* 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`

== id`overlay`

(stars xs) (stars ys) == stars (xs ++ ys)

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

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(n + 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

# Relational operations

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

Left-to-right *relational composition* of graphs: vertices `x`

and `z`

are
connected in the resulting graph if there is a vertex `y`

, such that `x`

is
connected to `y`

in the first graph, and `y`

is connected to `z`

in the
second graph. There are no isolated vertices in the result. This operation is
associative, has `empty`

and single-`vertex`

graphs as *annihilating zeroes*,
and distributes over `overlay`

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

compose`empty`

x ==`empty`

compose x`empty`

==`empty`

compose (`vertex`

x) y ==`empty`

compose x (`vertex`

y) ==`empty`

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

y z) ==`overlay`

(compose x y) (compose x z) compose (`overlay`

x y) z ==`overlay`

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

x y) (`edge`

y z) ==`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]

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

Compute the *reflexive and transitive closure* of a graph.
Complexity: *O(n * m * log(n) * log(m))* time.

closure`empty`

==`empty`

closure (`vertex`

x) ==`edge`

x x closure (`edge`

x x) ==`edge`

x x closure (`edge`

x y) ==`edges`

[(x,x), (x,y), (y,y)] closure (`path`

$`nub`

xs) ==`reflexiveClosure`

(`clique`

$`nub`

xs) closure ==`reflexiveClosure`

.`transitiveClosure`

closure ==`transitiveClosure`

.`reflexiveClosure`

closure . closure == closure`postSet`

x (closure y) == Set.`fromList`

(`reachable`

x y)

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

Compute the *transitive closure* of a graph.
Complexity: *O(n * m * log(n) * log(m))* time.

transitiveClosure`empty`

==`empty`

transitiveClosure (`vertex`

x) ==`vertex`

x transitiveClosure (`edge`

x y) ==`edge`

x y transitiveClosure (`path`

$`nub`

xs) ==`clique`

(`nub`

xs) transitiveClosure . transitiveClosure == transitiveClosure

# Miscellaneous

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

Check that the internal representation of a relation is consistent, i.e. if all
pairs of elements in the `relation`

refer to existing elements in the `domain`

.
It should be impossible to create an inconsistent `Relation`

, and we use this
function in testing.

consistent`empty`

== True consistent (`vertex`

x) == True consistent (`overlay`

x y) == True consistent (`connect`

x y) == True consistent (`edge`

x y) == True consistent (`edges`

xs) == True consistent (`stars`

xs) == True