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 provides a minimal and experimental implementation of algebraic graphs with edge labels. The API will be expanded in the next release.

## Synopsis

- data Graph e a
- empty :: Graph e a
- vertex :: a -> Graph e a
- edge :: e -> a -> a -> Graph e a
- (-<) :: a -> e -> (a, e)
- (>-) :: (a, e) -> a -> Graph e a
- overlay :: Monoid e => Graph e a -> Graph e a -> Graph e a
- connect :: e -> Graph e a -> Graph e a -> Graph e a
- vertices :: Monoid e => [a] -> Graph e a
- edges :: Monoid e => [(e, a, a)] -> Graph e a
- overlays :: Monoid e => [Graph e a] -> Graph e a
- foldg :: b -> (a -> b) -> (e -> b -> b -> b) -> Graph e a -> b
- isSubgraphOf :: (Eq e, Monoid e, Ord a) => Graph e a -> Graph e a -> Bool
- isEmpty :: Graph e a -> Bool
- size :: Graph e a -> Int
- hasVertex :: Eq a => a -> Graph e a -> Bool
- hasEdge :: (Eq e, Monoid e, Ord a) => a -> a -> Graph e a -> Bool
- edgeLabel :: (Eq a, Monoid e) => a -> a -> Graph e a -> e
- vertexList :: Ord a => Graph e a -> [a]
- edgeList :: (Eq e, Monoid e, Ord a) => Graph e a -> [(e, a, a)]
- vertexSet :: Ord a => Graph e a -> Set a
- edgeSet :: (Eq e, Monoid e, Ord a) => Graph e a -> Set (e, a, a)
- removeVertex :: Eq a => a -> Graph e a -> Graph e a
- removeEdge :: (Eq a, Eq e, Monoid e) => a -> a -> Graph e a -> Graph e a
- replaceVertex :: Eq a => a -> a -> Graph e a -> Graph e a
- replaceEdge :: (Eq e, Monoid e, Ord a) => e -> a -> a -> Graph e a -> Graph e a
- transpose :: Graph e a -> Graph e a
- emap :: (e -> f) -> Graph e a -> Graph f a
- induce :: (a -> Bool) -> Graph e a -> Graph e a
- induceJust :: Graph e (Maybe a) -> Graph e a
- closure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a
- reflexiveClosure :: (Ord a, Semiring e) => Graph e a -> Graph e a
- symmetricClosure :: Monoid e => Graph e a -> Graph e a
- transitiveClosure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a
- type UnlabelledGraph a = Graph Any a
- type Automaton a s = Graph (RegularExpression a) s
- type Network e a = Graph (Distance e) a
- data Context e a = Context {}
- context :: (Eq e, Monoid e) => (a -> Bool) -> Graph e a -> Maybe (Context e a)

# Algebraic data type for edge-labelled graphs

Edge-labelled graphs, where the type variable `e`

stands for edge labels.
For example, `Graph`

`Bool`

`a`

is isomorphic to unlabelled graphs defined in
the top-level module Algebra.Graph.Graph, where `False`

and `True`

denote
the lack of and the existence of an unlabelled edge, respectively.

## Instances

Construct the *empty graph*. An alias for the constructor `Empty`

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

`isEmpty`

empty == True`hasVertex`

x empty == False`vertexCount`

empty == 0`edgeCount`

empty == 0

vertex :: a -> Graph e a Source #

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

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

`isEmpty`

(vertex x) == False`hasVertex`

x (vertex y) == (x == y)`vertexCount`

(vertex x) == 1`edgeCount`

(vertex x) == 0

edge :: e -> a -> a -> Graph e a Source #

Construct the graph comprising *a single labelled edge*.
Complexity: *O(1)* time, memory and size.

edge e x y ==`connect`

e (`vertex`

x) (`vertex`

y) edge`zero`

x y ==`vertices`

[x,y]`hasEdge`

x y (edge e x y) == (e /=`zero`

)`edgeLabel`

x y (edge e x y) == e`edgeCount`

(edge e x y) == if e ==`zero`

then 0 else 1`vertexCount`

(edge e 1 1) == 1`vertexCount`

(edge e 1 2) == 2

(-<) :: a -> e -> (a, e) infixl 5 Source #

The left-hand part of a convenient ternary-ish operator `x-<e>-y`

for
creating labelled edges.

`x -<e>- y == ``edge`

e x y

(>-) :: (a, e) -> a -> Graph e a infixl 5 Source #

The right-hand part of a convenient ternary-ish operator `x-<e>-y`

for
creating labelled edges.

`x -<e>- y == ``edge`

e x y

overlay :: Monoid e => Graph e a -> Graph e a -> Graph e a Source #

*Overlay* two graphs. An alias for `Connect`

`zero`

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

(overlay 1 2) == 2`edgeCount`

(overlay 1 2) == 0

Note: `overlay`

composes edges in parallel using the operator `<+>`

with
`zero`

acting as the identity:

`edgeLabel`

x y $ overlay (`edge`

e x y) (`edge`

`zero`

x y) == e`edgeLabel`

x y $ overlay (`edge`

e x y) (`edge`

f x y) == e`<+>`

f

Furthermore, when applied to transitive graphs, `overlay`

composes edges in
sequence using the operator `<.>`

with `one`

acting as the identity:

`edgeLabel`

x z $`transitiveClosure`

(overlay (`edge`

e x y) (`edge`

`one`

y z)) == e`edgeLabel`

x z $`transitiveClosure`

(overlay (`edge`

e x y) (`edge`

f y z)) == e`<.>`

f

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

*Connect* two graphs with edges labelled by a given label. An alias for
`Connect`

.
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 e x y) ==`isEmpty`

x &&`isEmpty`

y`hasVertex`

z (connect e x y) ==`hasVertex`

z x ||`hasVertex`

z y`vertexCount`

(connect e x y) >=`vertexCount`

x`vertexCount`

(connect e x y) <=`vertexCount`

x +`vertexCount`

y`edgeCount`

(connect e x y) <=`vertexCount`

x *`vertexCount`

y +`edgeCount`

x +`edgeCount`

y`vertexCount`

(connect e 1 2) == 2`edgeCount`

(connect e 1 2) == if e ==`zero`

then 0 else 1

vertices :: Monoid e => [a] -> Graph e 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 :: Monoid e => [Graph e a] -> Graph e 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`

# Graph folding

foldg :: b -> (a -> b) -> (e -> b -> b -> b) -> Graph e 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 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`

`connect`

==`id`

foldg`empty`

`vertex`

(`fmap`

`flip`

`connect`

) ==`transpose`

foldg 1 (`const`

1) (`const`

(+)) ==`size`

foldg True (`const`

False) (`const`

(&&)) ==`isEmpty`

foldg False (== x) (`const`

(||)) ==`hasVertex`

x foldg Set.`empty`

Set.`singleton`

(`const`

Set.`union`

) ==`vertexSet`

# Relations on graphs

isSubgraphOf :: (Eq e, Monoid e, Ord a) => Graph e a -> Graph e 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 x y ==> x <= y

# Graph properties

isEmpty :: Graph e a -> Bool Source #

Check if a graph is empty.
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`

e x y) == False

hasVertex :: Eq a => a -> Graph e a -> Bool Source #

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

hasVertex x`empty`

== False hasVertex x (`vertex`

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

x ==`const`

False

edgeLabel :: (Eq a, Monoid e) => a -> a -> Graph e a -> e Source #

Extract the label of a specified edge from a graph.

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

# Graph transformation

removeEdge :: (Eq a, Eq e, Monoid e) => a -> a -> Graph e a -> Graph e a Source #

Remove an edge from a given graph.
Complexity: *O(s)* time, memory and size.

removeEdge x y (`edge`

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

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

x) ==`vertex`

y replaceVertex x y ==`fmap`

(\v -> if v == x then y else v)

emap :: (e -> f) -> Graph e a -> Graph f a Source #

Transform a graph by applying a function to each of its edge labels.
Complexity: *O(s)* time, memory and size.

The function `h`

is required to be a *homomorphism* on the underlying type of
labels `e`

. At the very least it must preserve `zero`

and `<+>`

:

h`zero`

==`zero`

h x`<+>`

h y == h (x`<+>`

y)

If `e`

is also a semiring, then `h`

must also preserve the multiplicative
structure:

h`one`

==`one`

h x`<.>`

h y == h (x`<.>`

y)

If the above requirements hold, then the implementation provides the following guarantees.

emap h`empty`

==`empty`

emap h (`vertex`

x) ==`vertex`

x emap h (`edge`

e x y) ==`edge`

(h e) x y emap h (`overlay`

x y) ==`overlay`

(emap h x) (emap h y) emap h (`connect`

e x y) ==`connect`

(h e) (emap h x) (emap h y) emap`id`

==`id`

emap g . emap h == emap (g . h)

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

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

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

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

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

# Relational operations

closure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a Source #

Compute the *reflexive and transitive closure* of a graph over the
underlying star semiring using the Warshall-Floyd-Kleene algorithm.

closure`empty`

==`empty`

closure (`vertex`

x) ==`edge`

`one`

x x closure (`edge`

e x x) ==`edge`

`one`

x x closure (`edge`

e x y) ==`edges`

[(`one`

,x,x), (e,x,y), (`one`

,y,y)] closure ==`reflexiveClosure`

.`transitiveClosure`

closure ==`transitiveClosure`

.`reflexiveClosure`

closure . closure == closure`postSet`

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

(`reachable`

x y)

reflexiveClosure :: (Ord a, Semiring e) => Graph e a -> Graph e a Source #

Compute the *reflexive closure* of a graph over the underlying semiring by
adding a self-loop of weight `one`

to every vertex.
Complexity: *O(n * log(n))* time.

reflexiveClosure`empty`

==`empty`

reflexiveClosure (`vertex`

x) ==`edge`

`one`

x x reflexiveClosure (`edge`

e x x) ==`edge`

`one`

x x reflexiveClosure (`edge`

e x y) ==`edges`

[(`one`

,x,x), (e,x,y), (`one`

,y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure

symmetricClosure :: Monoid e => Graph e a -> Graph e a Source #

Compute the *symmetric closure* of a graph by overlaying it with its own
transpose.
Complexity: *O((n + m) * log(n))* time.

symmetricClosure`empty`

==`empty`

symmetricClosure (`vertex`

x) ==`vertex`

x symmetricClosure (`edge`

e x y) ==`edges`

[(e,x,y), (e,y,x)] symmetricClosure x ==`overlay`

x (`transpose`

x) symmetricClosure . symmetricClosure == symmetricClosure

transitiveClosure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a Source #

Compute the *transitive closure* of a graph over the underlying star
semiring using a modified version of the Warshall-Floyd-Kleene algorithm,
which omits the reflexivity step.

transitiveClosure`empty`

==`empty`

transitiveClosure (`vertex`

x) ==`vertex`

x transitiveClosure (`edge`

e x y) ==`edge`

e x y transitiveClosure . transitiveClosure == transitiveClosure

# Types of edge-labelled graphs

type UnlabelledGraph a = Graph Any a Source #

A type synonym for *unlabelled graphs*.

type Automaton a s = Graph (RegularExpression a) s Source #

A type synonym for *automata* or *labelled transition systems*.

type Network e a = Graph (Distance e) a Source #

A *network* is a graph whose edges are labelled with distances.

# Context

The `Context`

of a subgraph comprises its `inputs`

and `outputs`

, i.e. all
the vertices that are connected to the subgraph's vertices (along with the
corresponding edge labels). 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 :: (Eq e, Monoid e) => (a -> Bool) -> Graph e a -> Maybe (Context e a) Source #

Extract the `Context`

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

if the specified subgraph is empty.

context (`const`

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

e 1 2) == if e ==`zero`

then Just (`Context`

[] []) else Just (`Context`

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

e 1 2) == if e ==`zero`

then Just (`Context`

[] []) else Just (`Context`

[(e,1)] [ ]) context (`const`

True ) (`edge`

e 1 2) == if e ==`zero`

then Just (`Context`

[] []) else Just (`Context`

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

[(`one`

,3), (`one`

,1)] [(`one`

,1), (`one`

,5)])