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

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

, a few graph subclasses, and
basic polymorphic graph construction primitives. Functions that cannot be
implemented fully polymorphically and require the use of an intermediate data
type are not included. For example, to compute the number of vertices in a
`Graph`

expression you will need to use a concrete data type, such as
Algebra.Graph.Graph or Algebra.Graph.AdjacencyMap.

See Algebra.Graph.HigherKinded.Class for the higher-kinded version of the core graph type class.

## Synopsis

- class Graph g where
- class Graph g => Undirected g
- class Graph g => Reflexive g
- class Graph g => Transitive g
- class (Reflexive g, Transitive g) => Preorder g
- edge :: Graph g => Vertex g -> Vertex g -> g
- vertices :: Graph g => [Vertex g] -> g
- overlays :: Graph g => [g] -> g
- connects :: Graph g => [g] -> g
- edges :: Graph g => [(Vertex g, Vertex g)] -> g
- isSubgraphOf :: (Graph g, Eq g) => g -> g -> Bool
- path :: Graph g => [Vertex g] -> g
- circuit :: Graph g => [Vertex g] -> g
- clique :: Graph g => [Vertex g] -> g
- biclique :: Graph g => [Vertex g] -> [Vertex g] -> g
- star :: Graph g => Vertex g -> [Vertex g] -> g
- tree :: Graph g => Tree (Vertex g) -> g
- forest :: Graph g => Forest (Vertex g) -> g

# The core type class

The core type class for constructing algebraic graphs, characterised by the
following minimal set of axioms. In equations we use `+`

and `*`

as convenient
shortcuts for `overlay`

and `connect`

, respectively.

`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

The core type class `Graph`

corresponds to unlabelled directed graphs.
`Undirected`

, `Reflexive`

, `Transitive`

and `Preorder`

graphs can be obtained
by extending the minimal set of axioms.

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.

Construct the empty graph.

vertex :: Vertex g -> g Source #

Construct the graph with a single vertex.

overlay :: g -> g -> g Source #

Overlay two graphs.

connect :: g -> g -> g Source #

Connect two graphs.

#### Instances

# Undirected graphs

class Graph g => Undirected g Source #

The class of *undirected graphs* that satisfy the following additional axiom.

`connect`

is commutative:x * y == y * x

#### Instances

Undirected () Source # | |

Defined in Algebra.Graph.Class | |

Undirected g => Undirected (Maybe g) Source # | |

Defined in Algebra.Graph.Class | |

Ord a => Undirected (Relation a) Source # | |

Defined in Algebra.Graph.Class | |

Undirected (Graph a) Source # | |

Defined in Algebra.Graph.Class | |

Undirected g => Undirected (a -> g) Source # | |

Defined in Algebra.Graph.Class | |

(Undirected g, Undirected h) => Undirected (g, h) Source # | |

Defined in Algebra.Graph.Class | |

(Undirected g, Undirected h, Undirected i) => Undirected (g, h, i) Source # | |

Defined in Algebra.Graph.Class |

# Reflexive graphs

class Graph g => Reflexive g Source #

The class of *reflexive graphs* that satisfy the following additional axiom.

Each vertex has a

*self-loop*:vertex x == vertex x * vertex x

Note that by applying the axiom in the reverse direction, one can always remove
all self-loops resulting in an *irreflexive graph*. This type class can
therefore be also used in the context of irreflexive graphs.

#### Instances

Reflexive () Source # | |

Defined in Algebra.Graph.Class | |

Reflexive g => Reflexive (Maybe g) Source # | |

Defined in Algebra.Graph.Class | |

Ord a => Reflexive (ReflexiveRelation a) Source # | |

Defined in Algebra.Graph.Relation.Reflexive | |

Ord a => Reflexive (PreorderRelation a) Source # | |

Defined in Algebra.Graph.Relation.Preorder | |

Reflexive g => Reflexive (a -> g) Source # | |

Defined in Algebra.Graph.Class | |

(Reflexive g, Reflexive h) => Reflexive (g, h) Source # | |

Defined in Algebra.Graph.Class | |

(Reflexive g, Reflexive h, Reflexive i) => Reflexive (g, h, i) Source # | |

Defined in Algebra.Graph.Class |

# Transitive graphs

class Graph g => Transitive g Source #

The class of *transitive graphs* that satisfy the following additional axiom.

The

*closure*axiom: graphs with equal transitive closures are equal.y /= empty ==> x * y + x * z + y * z == x * y + y * z

By repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction.

#### Instances

Transitive () Source # | |

Defined in Algebra.Graph.Class | |

Transitive g => Transitive (Maybe g) Source # | |

Defined in Algebra.Graph.Class | |

Ord a => Transitive (TransitiveRelation a) Source # | |

Defined in Algebra.Graph.Relation.Transitive | |

Ord a => Transitive (PreorderRelation a) Source # | |

Defined in Algebra.Graph.Relation.Preorder | |

Transitive g => Transitive (a -> g) Source # | |

Defined in Algebra.Graph.Class | |

(Transitive g, Transitive h) => Transitive (g, h) Source # | |

Defined in Algebra.Graph.Class | |

(Transitive g, Transitive h, Transitive i) => Transitive (g, h, i) Source # | |

Defined in Algebra.Graph.Class |

# Preorders

class (Reflexive g, Transitive g) => Preorder g Source #

The class of *preorder graphs* that are both reflexive and transitive.

#### Instances

Preorder () Source # | |

Defined in Algebra.Graph.Class | |

Preorder g => Preorder (Maybe g) Source # | |

Defined in Algebra.Graph.Class | |

Ord a => Preorder (PreorderRelation a) Source # | |

Defined in Algebra.Graph.Relation.Preorder | |

Preorder g => Preorder (a -> g) Source # | |

Defined in Algebra.Graph.Class | |

(Preorder g, Preorder h) => Preorder (g, h) Source # | |

Defined in Algebra.Graph.Class | |

(Preorder g, Preorder h, Preorder i) => Preorder (g, h, i) Source # | |

Defined in Algebra.Graph.Class |

# Basic graph construction primitives

# Relations on graphs

isSubgraphOf :: (Graph g, Eq g) => g -> g -> Bool Source #

The `isSubgraphOf`

function takes two graphs and returns `True`

if the
first graph is a *subgraph* of the second. Here is the current implementation:

`isSubgraphOf x y = ``overlay`

x y == y

The complexity therefore depends on the complexity of equality testing of the specific graph instance.

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

# Standard families of graphs

biclique :: Graph g => [Vertex g] -> [Vertex g] -> g 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)

tree :: Graph g => Tree (Vertex g) -> g 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 :: Graph g => Forest (Vertex g) -> g 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`