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

and associated algorithms.
For graphs that are known to be *non-empty* at compile time, see
Algebra.Graph.NonEmpty. `Graph`

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 Graph a
- empty :: Graph a
- vertex :: a -> Graph a
- edge :: a -> a -> Graph a
- overlay :: Graph a -> Graph a -> Graph a
- connect :: Graph a -> Graph a -> Graph a
- vertices :: [a] -> Graph a
- edges :: [(a, a)] -> Graph a
- overlays :: [Graph a] -> Graph a
- connects :: [Graph a] -> Graph a
- foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Graph a -> b
- buildg :: (forall b. b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> b) -> Graph a
- isSubgraphOf :: Ord a => Graph a -> Graph a -> Bool
- (===) :: Eq a => Graph a -> Graph a -> Bool
- isEmpty :: 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
- vertexList :: Ord a => Graph a -> [a]
- edgeList :: Ord a => Graph a -> [(a, a)]
- vertexSet :: Ord a => Graph a -> Set a
- edgeSet :: Ord a => Graph a -> Set (a, a)
- adjacencyList :: Ord a => Graph a -> [(a, [a])]
- path :: [a] -> Graph a
- circuit :: [a] -> Graph a
- clique :: [a] -> Graph a
- biclique :: [a] -> [a] -> Graph a
- star :: a -> [a] -> Graph a
- stars :: [(a, [a])] -> Graph a
- tree :: Tree a -> Graph a
- forest :: Forest a -> Graph a
- mesh :: [a] -> [b] -> Graph (a, b)
- torus :: [a] -> [b] -> Graph (a, b)
- deBruijn :: Int -> [a] -> Graph [a]
- removeVertex :: Eq a => a -> Graph a -> 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
- splitVertex :: Eq a => a -> [a] -> Graph a -> Graph a
- transpose :: Graph a -> Graph a
- induce :: (a -> Bool) -> Graph a -> Graph a
- induceJust :: Graph (Maybe a) -> Graph a
- simplify :: Ord a => Graph a -> Graph a
- sparsify :: Graph a -> Graph (Either Int a)
- sparsifyKL :: Int -> Graph Int -> Graph
- compose :: Ord a => Graph a -> Graph a -> Graph a
- box :: Graph a -> Graph b -> Graph (a, b)
- data Context a = Context {}
- context :: (a -> Bool) -> Graph a -> Maybe (Context a)

# Algebraic data type for graphs

The `Graph`

data type is a deep embedding 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 `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 `Graph`

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

Deforestation (fusion) is implemented for some functions in this module. This means that when a function tagged as a "good producer" is composed with a "good consumer", the intermediate structure will not be built.

## Instances

# Basic graph construction primitives

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

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

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

Good consumer of lists and producer of graphs.

vertices [] ==`empty`

vertices [x] ==`vertex`

x`hasVertex`

x . vertices ==`elem`

x`vertexCount`

. vertices ==`length`

.`nub`

`vertexSet`

. vertices == Set.`fromList`

overlays :: [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.

Good consumer of lists and producer of graphs.

overlays [] ==`empty`

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

x y overlays ==`foldr`

`overlay`

`empty`

`isEmpty`

. overlays ==`all`

`isEmpty`

connects :: [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.

Good consumer of lists and producer of graphs.

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

Good consumer.

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

buildg :: (forall b. b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> b) -> Graph a Source #

Build a graph given an interpretation of the four graph construction primitives `empty`

,
`vertex`

, `overlay`

and `connect`

, in this order. See examples for further clarification.

Functions expressed with `buildg`

are good producers.

buildg f == f`empty`

`vertex`

`overlay`

`connect`

buildg (\e _ _ _ -> e) ==`empty`

buildg (\_ v _ _ -> v x) ==`vertex`

x buildg (\e v o c -> o (`foldg`

e v o c x) (`foldg`

e v o c y)) ==`overlay`

x y buildg (\e v o c -> c (`foldg`

e v o c x) (`foldg`

e v o c y)) ==`connect`

x y buildg (\e v o _ ->`foldr`

o e (`map`

v xs)) ==`vertices`

xs buildg (\e v o c ->`foldg`

e v o (`flip`

c) g) ==`transpose`

g`foldg`

e v o c (buildg f) == f e v o c

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

Good consumer of both arguments.

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

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

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

```
x === x == True
x === x +
````empty`

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

# Graph properties

isEmpty :: Graph a -> Bool Source #

Check if a graph is empty.
Complexity: *O(s)* time.

Good consumer.

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

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

Good consumer.

hasVertex x`empty`

== False hasVertex x (`vertex`

y) == (x == y) hasVertex x .`removeVertex`

x ==`const`

False

vertexCount :: Ord a => Graph a -> Int Source #

The number of vertices in a graph.
Complexity: *O(s * log(n))* time.

Good consumer.

vertexCount`empty`

== 0 vertexCount (`vertex`

x) == 1 vertexCount ==`length`

.`vertexList`

vertexCount x < vertexCount y ==> x < y

vertexList :: Ord a => Graph a -> [a] Source #

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

Good consumer of graphs and producer of lists.

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 => Graph a -> [(a, [a])] Source #

# Standard families of graphs

clique :: [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.

Good consumer of lists and producer of graphs.

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

Good consumer of both arguments and producer of graphs.

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)

star :: a -> [a] -> Graph a Source #

The *star* formed by a centre vertex connected to a list of leaves.
Complexity: *O(L)* time, memory and size, where *L* is the length of the
given list.

Good consumer of lists and good producer of graphs.

star x [] ==`vertex`

x star x [y] ==`edge`

x y star x [y,z] ==`edges`

[(x,y), (x,z)] star x ys ==`connect`

(`vertex`

x) (`vertices`

ys)

stars :: [(a, [a])] -> Graph 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.

Good consumer of lists and producer of graphs.

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 :: 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 []]]) ==`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 :: Forest a -> Graph 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 :: [a] -> [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.

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 :: [a] -> [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.

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 :: Int -> [a] -> Graph [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

removeEdge :: Eq a => a -> a -> Graph a -> Graph 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

replaceVertex :: Eq a => a -> a -> Graph a -> Graph 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.

Good consumer and producer.

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.

Good consumer and producer.

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

Good consumer of lists and producer of graphs.

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)

transpose :: Graph a -> Graph a Source #

Transpose a given graph.
Complexity: *O(s)* time, memory and size.

Good consumer and producer.

transpose`empty`

==`empty`

transpose (`vertex`

x) ==`vertex`

x transpose (`edge`

x y) ==`edge`

y x transpose . transpose == id transpose (`box`

x y) ==`box`

(transpose x) (transpose y)`edgeList`

. transpose ==`sort`

.`map`

`swap`

.`edgeList`

induce :: (a -> Bool) -> Graph a -> Graph 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.

Good consumer and producer.

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

induceJust :: Graph (Maybe a) -> Graph a Source #

Construct the *induced subgraph* of a given graph by removing the vertices
that are `Nothing`

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

Good consumer and producer.

induceJust (`vertex`

`Nothing`

) ==`empty`

induceJust (`edge`

(`Just`

x)`Nothing`

) ==`vertex`

x induceJust .`fmap`

`Just`

==`id`

induceJust .`fmap`

(\x -> if p x then`Just`

x else`Nothing`

) ==`induce`

p

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.

Good consumer.

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

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

sparsifyKL :: Int -> Graph Int -> Graph Source #

Sparsify a graph whose vertices are integers in the range `[1..n]`

, where
`n`

is the first argument of the function, producing an array-based graph
representation from Data.Graph (introduced by King and Launchbury, hence
the name of the function). In the resulting graph, vertices `[1..n]`

correspond to the original vertices, and all vertices greater than `n`

are
introduced by the sparsification procedure.

Complexity: *O(s)* time and memory. Note that thanks to sparsification, the
resulting graph has a linear number of edges with respect to the size of the
original algebraic representation even though the latter can potentially
contain a quadratic *O(s^2)* number of edges.

`sort`

.`reachable`

k ==`sort`

.`filter`

(<= n) .`flip`

`reachable`

k . sparsifyKL n`length`

(`vertices`

$ sparsifyKL n x) <=`vertexCount`

x +`size`

x + 1`length`

(`edges`

$ sparsifyKL n x) <= 3 *`size`

x

# Graph composition

compose :: Ord a => Graph a -> Graph a -> Graph 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(n))* time, *O(n + m)* memory, and *O(m1 + m2)*
size, where *n* and *m* stand for the number of vertices and edges in the
resulting graph, while *m1* and *m2* are the number of edges in the original
graphs. Note that the number of edges in the resulting graph may be
quadratic, i.e. *m = O(m1 * m2)*, but the algebraic representation requires
only *O(m1 + m2)* operations to list them.

Good consumer of both arguments and good producer.

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

(compose x y) <=`edgeCount`

x +`edgeCount`

y + 1

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

`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

# Context

The `Context`

of a subgraph comprises its `inputs`

and `outputs`

, i.e. all
the vertices that are connected to the subgraph's vertices. Note that inputs
and outputs can belong to the subgraph itself. In general, there are no
guarantees on the order of vertices in `inputs`

and `outputs`

; furthermore,
there may be repetitions.

context :: (a -> Bool) -> Graph a -> Maybe (Context a) Source #

Extract the `Context`

of a subgraph specified by a given predicate. Returns
`Nothing`

if the specified subgraph is empty.

Good consumer.

context (`const`

False) x == Nothing context (== 1) (`edge`

1 2) == Just (`Context`

[ ] [2 ]) context (== 2) (`edge`

1 2) == Just (`Context`

[1 ] [ ]) context (`const`

True ) (`edge`

1 2) == Just (`Context`

[1 ] [2 ]) context (== 4) (3 * 1 * 4 * 1 * 5) == Just (`Context`

[3,1] [1,5])