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 data type `Graph`

for algebraic graphs that are known
to be non-empty at compile time. To avoid name clashes with Algebra.Graph,
this module can be imported qualified:

import qualified Algebra.Graph.NonEmpty as NonEmpty

The naming convention generally follows that of Data.List.NonEmpty: we use
suffix `1`

to indicate the functions whose interface must be changed compared
to Algebra.Graph, e.g. `vertices1`

.

## Synopsis

- data Graph a
- toNonEmpty :: Graph a -> Maybe (Graph a)
- vertex :: a -> Graph a
- edge :: a -> a -> Graph a
- overlay :: Graph a -> Graph a -> Graph a
- overlay1 :: Graph a -> Graph a -> Graph a
- connect :: Graph a -> Graph a -> Graph a
- vertices1 :: NonEmpty a -> Graph a
- edges1 :: NonEmpty (a, a) -> Graph a
- overlays1 :: NonEmpty (Graph a) -> Graph a
- connects1 :: NonEmpty (Graph a) -> Graph a
- foldg1 :: (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
- size :: Graph a -> Int
- hasVertex :: Eq a => a -> Graph a -> Bool
- hasEdge :: Eq a => a -> a -> Graph a -> Bool
- vertexCount :: Ord a => Graph a -> Int
- edgeCount :: Ord a => Graph a -> Int
- vertexList1 :: Ord a => Graph a -> NonEmpty a
- edgeList :: Ord a => Graph a -> [(a, a)]
- vertexSet :: Ord a => Graph a -> Set a
- edgeSet :: Ord a => Graph a -> Set (a, a)
- path1 :: NonEmpty a -> Graph a
- circuit1 :: NonEmpty a -> Graph a
- clique1 :: NonEmpty a -> Graph a
- biclique1 :: NonEmpty a -> NonEmpty a -> Graph a
- star :: a -> [a] -> Graph a
- stars1 :: NonEmpty (a, [a]) -> Graph a
- tree :: Tree a -> Graph a
- mesh1 :: NonEmpty a -> NonEmpty b -> Graph (a, b)
- torus1 :: NonEmpty a -> NonEmpty b -> Graph (a, b)
- removeVertex1 :: Eq a => a -> Graph a -> Maybe (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
- splitVertex1 :: Eq a => a -> NonEmpty a -> Graph a -> Graph a
- transpose :: Graph a -> Graph a
- induce1 :: (a -> Bool) -> Graph a -> Maybe (Graph a)
- simplify :: Ord a => Graph a -> Graph a
- sparsify :: Graph a -> Graph (Either Int a)
- box :: Graph a -> Graph b -> Graph (a, b)

# Non-empty algebraic graphs

Non-empty algebraic graphs, which are constructed using three primitives:
`vertex`

, `overlay`

and `connect`

. See module Algebra.Graph for algebraic
graphs that can be empty.

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

method of the type class `Num`

cannot be implemented and
will throw an error. Furthermore, 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 `Eq`

instance satisfies the following laws of non-empty algebraic graphs.

`overlay`

is commutative, associative and idempotent:x + y == y + x x + (y + z) == (x + y) + z x + x == x

`connect`

is associative: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

`connect`

satisfies absorption and saturation: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, defined as the number of vertex leaves (note that *n* <= *s*). If
`g`

is a `Graph`

, the corresponding *n*, *m* and *s* can be computed as follows:

n ==`vertexCount`

g m ==`edgeCount`

g s ==`size`

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.

The total order `Ord`

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

x <= x + y x + y <= x * y

## Instances

# Basic graph construction primitives

vertex :: a -> Graph a Source #

Construct the graph comprising *a single isolated vertex*. An alias for the
constructor `Vertex`

.
Complexity: *O(1)* time, memory and size.

`hasVertex`

x (vertex x) == True`vertexCount`

(vertex x) == 1`edgeCount`

(vertex x) == 0`size`

(vertex x) == 1

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.
Complexity: *O(1)* time and memory, *O(s1 + s2)* size.

`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

overlay1 :: Graph a -> Graph a -> Graph a Source #

Overlay a possibly empty graph (from Algebra.Graph) with a non-empty
graph. If the first argument is `empty`

, the function returns the second
argument; otherwise it is semantically the same as `overlay`

.
Complexity: *O(s1)* time and memory, and *O(s1 + s2)* size.

overlay1`empty`

x == x x /=`empty`

==> overlay1 x y == overlay (fromJust $ toNonEmpty x) y

connect :: Graph a -> Graph a -> Graph a Source #

*Connect* two graphs. An alias for the constructor `Connect`

. This is an
associative operation, 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)*.

`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

overlays1 :: NonEmpty (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.

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

x y

connects1 :: NonEmpty (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.

```
connects1 [x] == x
connects1 [x,y] ==
````connect`

x y

# Graph folding

foldg1 :: (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: 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)*.

foldg1`vertex`

`overlay`

`connect`

== id foldg1`vertex`

`overlay`

(`flip`

`connect`

) ==`transpose`

foldg1 (`const`

1) (+) (+) ==`size`

foldg1 (== x) (||) (||) ==`hasVertex`

x

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

x y) == True isSubgraphOf (`overlay`

x y) (`connect`

x y) == True isSubgraphOf (`path1`

xs) (`circuit1`

xs) == True isSubgraphOf x y ==> x <= y

(===) :: Eq a => Graph a -> Graph a -> Bool infix 4 Source #

Structural equality on graph expressions.
Complexity: *O(s)* time.

x === x == True x + y === x + y == True 1 + 2 === 2 + 1 == False x + y === x * y == False

# Graph properties

size :: Graph a -> Int Source #

The *size* of a graph, i.e. the number of leaves of the expression.
Complexity: *O(s)* time.

size (`vertex`

x) == 1 size (`overlay`

x y) == size x + size y size (`connect`

x y) == size x + size y size x >= 1 size x >=`vertexCount`

x

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

x) == [] edgeList (`edge`

x y) == [(x,y)] edgeList (`star`

2 [3,1]) == [(2,1), (2,3)] edgeList .`edges1`

==`nub`

.`sort`

.`toList`

edgeList .`transpose`

==`sort`

.`map`

`swap`

. edgeList

# Standard families of graphs

clique1 :: NonEmpty 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.

clique1 [x] ==`vertex`

x clique1 [x,y] ==`edge`

x y clique1 [x,y,z] ==`edges1`

[(x,y), (x,z), (y,z)] clique1 (xs`<>`

ys) ==`connect`

(clique1 xs) (clique1 ys) clique1 .`reverse`

==`transpose`

. clique1

stars1 :: NonEmpty (a, [a]) -> Graph a Source #

The *stars* formed by overlaying a non-empty list of `star`

s.
Complexity: *O(L)* time, memory and size, where *L* is the total size of the
input.

stars1 [(x, [] )] ==`vertex`

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

x y stars1 [(x, ys )] ==`star`

x ys stars1 ==`overlays1`

.`fmap`

(`uncurry`

`star`

)`overlay`

(stars1 xs) (stars1 ys) == stars1 (xs`<>`

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

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

[(1,2), (1,3), (3,4), (3,5)]

mesh1 :: NonEmpty a -> NonEmpty 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.

mesh1 [x] [y] ==`vertex`

(x, y) mesh1 xs ys ==`box`

(`path1`

xs) (`path1`

ys) mesh1 [1,2,3] ['a', 'b'] ==`edges1`

[ ((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')) ]

torus1 :: NonEmpty a -> NonEmpty 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.

torus1 [x] [y] ==`edge`

(x,y) (x,y) torus1 xs ys ==`box`

(`circuit1`

xs) (`circuit1`

ys) torus1 [1,2] ['a', 'b'] ==`edges1`

[ ((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')) ]

# Graph transformation

removeVertex1 :: Eq a => a -> Graph a -> Maybe (Graph a) Source #

Remove a vertex from a given graph. Returns `Nothing`

if the resulting
graph is empty.
Complexity: *O(s)* time, memory and size.

removeVertex1 x (`vertex`

x) == Nothing removeVertex1 1 (`vertex`

2) == Just (`vertex`

2) removeVertex1 x (`edge`

x x) == Nothing removeVertex1 1 (`edge`

1 2) == Just (`vertex`

2) removeVertex1 x`>=>`

removeVertex1 x == removeVertex1 x

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

The function `replaceVertex`

`x y`

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

splitVertex1 :: Eq a => a -> NonEmpty 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.

```
splitVertex1 x [x] == id
splitVertex1 x [y] ==
````replaceVertex`

x y
splitVertex1 1 [0,1] $ 1 * (2 + 3) == (0 + 1) * (2 + 3)

induce1 :: (a -> Bool) -> Graph a -> Maybe (Graph a) Source #

Construct the *induced subgraph* of a given graph by removing the
vertices that do not satisfy a given predicate. Returns `Nothing`

if the
resulting graph is empty.
Complexity: *O(s)* time, memory and size, assuming that the predicate takes
*O(1)* to be evaluated.

induce1 (`const`

True ) x == Just x induce1 (`const`

False) x == Nothing induce1 (/= x) ==`removeVertex1`

x induce1 p`>=>`

induce1 q == induce1 (\x -> p x && q x)

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

1 simplify (1 + 1)`===`

1 simplify (1 + 2 + 1)`===`

1 + 2 simplify (1 * 1 * 1)`===`

1 * 1

sparsify :: Graph a -> Graph (Either Int a) Source #

*Sparsify* a graph by adding intermediate `Left`

`Int`

vertices between the
original vertices (wrapping the latter in `Right`

) such that the resulting
graph is *sparse*, i.e. contains only O(s) edges, but preserves the
reachability relation between the original vertices. Sparsification is useful
when working with dense graphs, as it can reduce the number of edges from
O(n^2) down to O(n) by replacing cliques, bicliques and similar densely
connected structures by sparse subgraphs built out of intermediate vertices.
Complexity: O(s) time, memory and size.

`sort`

.`reachable`

x ==`sort`

.`rights`

.`reachable`

(`Right`

x) . sparsify`vertexCount`

(sparsify x) <=`vertexCount`

x +`size`

x + 1`edgeCount`

(sparsify x) <= 3 *`size`

x`size`

(sparsify x) <= 3 *`size`

x

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

[0,1]) (`path1`

['a','b']) ==`edges1`

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

, and has
singleton graphs as *identities*. 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`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