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

== 0`size`

`empty`

== 1`vertexCount`

(`vertex`

x) == 1`size`

(`vertex`

x) == 1`vertexCount`

(`empty`

+`empty`

) == 0`size`

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

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

# Basic graph construction primitives

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

`isEmpty`

empty == True`hasVertex`

x empty == False`vertexCount`

empty == 0`edgeCount`

empty == 0`size`

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) == False`hasVertex`

x (vertex x) == True`vertexCount`

(vertex x) == 1`edgeCount`

(vertex x) == 0`size`

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

(edge x y) == 1`vertexCount`

(edge 1 1) == 1`vertexCount`

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

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

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

x`hasVertex`

x . vertices ==`elem`

x`vertexCount`

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

foldg`empty`

`vertex`

`overlay`

`connect`

== id foldg`empty`

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

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 :: Fold 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 -> Fold a -> Bool Source #

Check if a graph contains a given vertex.
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 => Fold 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`

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

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

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

adjacencyList`empty`

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

== id`overlay`

(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 * 2`size`

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