# algebraic-graphs

A library for algebraic graph construction and transformation https://github.com/snowleopard/alga

Version on this page: | 0.0.5 |

LTS Haskell 12.22: | 0.2 |

Stackage Nightly 2018-12-12: | 0.3 |

Latest on Hackage: | 0.3 |

**Andrey Mokhov**

**, github: @snowleopard**

**, Alexandre Moine**

**, github: @nobrakal**

#### Module documentation for 0.0.5

- Algebra

# Algebraic graphs

**Alga** is a library for algebraic construction and manipulation of graphs in Haskell. See
this Haskell Symposium paper and the
corresponding talk for the motivation
behind the library, the underlying theory and implementation details. There is also a
Haskell eXchange talk,
and a tutorial by Alexandre Moine.

## Main idea

Consider the following data type, which is defined in the top-level module Algebra.Graph of the library:

```
data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)
```

We can give the following semantics to the constructors in terms of the pair **(V, E)** of graph *vertices* and *edges*:

`Empty`

constructs the empty graph**(∅, ∅)**.`Vertex x`

constructs a graph containing a single vertex, i.e.**({x}, ∅)**.`Overlay x y`

overlays graphs**(Vx, Ex)**and**(Vy, Ey)**constructing**(Vx ∪ Vy, Ex ∪ Ey)**.`Connect x y`

connects graphs**(Vx, Ex)**and**(Vy, Ey)**constructing**(Vx ∪ Vy, Ex ∪ Ey ∪ Vx × Vy)**.

Alternatively, we can give an algebraic semantics to the above graph construction primitives by defining the following type class and specifying a set of laws for its instances (see module Algebra.Graph.Class):

```
class Graph g where
type Vertex g
empty :: g
vertex :: Vertex g -> g
overlay :: g -> g -> g
connect :: g -> g -> g
```

The laws of the type class are remarkably similar to those of a semiring,
so we use `+`

and `*`

as convenient shortcuts for `overlay`

and `connect`

, respectively:

- (
`+`

,`empty`

) is an idempotent commutative monoid. - (
`*`

,`empty`

) is a monoid. `*`

distributes over`+`

, that is:`x * (y + z) == x * y + x * z`

and`(x + y) * z == x * z + y * z`

.`*`

can be decomposed:`x * y * z == x * y + x * z + y * z`

.

This algebraic structure corresponds to *unlabelled directed graphs*: every expression represents a graph, and every
graph can be represented by an expression. Other types of graphs (e.g. undirected) can be obtained by modifying the
above set of laws. Algebraic graphs provide a convenient, safe and powerful interface for working with graphs in Haskell,
and allow the application of equational reasoning for proving the correctness of graph algorithms.

To represent *non-empty graphs*, we can drop the `Empty`

constructor – see module
Algebra.Graph.NonEmpty.

To represent *edge-labelled graphs*, we can switch to the following data type, as
explained in my Haskell eXchange 2018 talk:

```
data Graph e a = Empty
| Vertex a
| Connect e (Graph e a) (Graph e a)
```

Here `e`

is the type of edge labels. If `e`

is a monoid `(<+>, zero)`

then graph overlay can be recovered
as `Connect zero`

, and `<+>`

corresponds to *parallel composition* of edge labels.

## How fast is the library?

Alga can handle graphs comprising millions of vertices and billions of edges in a matter of seconds, which is fast enough for many applications. We believe there is a lot of potential for improving the performance of the library, and this is one of our top priorities. If you come across a performance issue when using the library, please let us know.

Some preliminary benchmarks can be found here.

## Blog posts

The development of the library has been documented in the series of blog posts:

- Introduction: https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/
- A few different flavours of the algebra: https://blogs.ncl.ac.uk/andreymokhov/graphs-a-la-carte/
- Graphs in disguise or How to plan you holiday using Haskell: https://blogs.ncl.ac.uk/andreymokhov/graphs-in-disguise/
- Old graphs from new types: https://blogs.ncl.ac.uk/andreymokhov/old-graphs-from-new-types/

## Algebraic graphs in other languages

See draft implementations in Agda and Scala.

## Changes

# Change log

## 0.3

- #129: Add a testsuite for rewrite rules based on the
`inspection-testing`

library. - #63, #148: Add relational composition of algebraic graphs.
- #139, #146: Add relational operations to adjacency maps.
- #146: Rename
`preorderClosure`

to`closure`

. - #146: Switch to left-to-right composition in
`Relation.compose`

. - #143: Allow newer QuickCheck.
- #140, #142: Fix
`Show`

instances. - #128, #130: Modify the SCC algorithm to return non-empty graph components.
- #130: Move adjacency map algorithms to separate modules.
- #130: Export
`fromAdjacencySets`

and`fromAdjacencyIntSets`

. - #138: Do not require
`Eq`

instance on the string type when exporting graphs. - #136: Rename
`Algebra.Graph.NonEmpty.NonEmptyGraph`

to`Algebra.Graph.NonEmpty.Graph`

. - #136: Add
`Algebra.Graph.NonEmpty.AdjacencyMap`

. - #136: Remove
`vertexIntSet`

from the API of basic graph data types. Also remove`Algebra.Graph.adjacencyMap`

and`Algebra.Graph.adjacencyIntMap`

. This functionality is still available from the type class`ToGraph`

. - #126, #131: Implement custom
`Ord`

instance. - #17, #122, #125, #149: Add labelled algebraic graphs.
- #121: Drop
`Foldable`

and`Traversable`

instances. - #113: Add
`Labelled.AdjacencyMap`

.

## 0.2

- #117: Add
`sparsify`

. - #115: Add
`isDfsForestOf`

. - #114: Add a basic implementation of edge-labelled graphs.
- #107: Drop
`starTranspose`

. - #106: Extend
`ToGraph`

with algorithms based on adjacency maps. - #106: Add
`isAcyclic`

and`reachable`

. - #106: Rename
`isTopSort`

to`isTopSortOf`

. - #102: Switch the master branch to GHC 8.4.3. Add a CI instance for GHC 8.6.1.
- #101: Drop
`-O2`

from the`ghc-options`

section of the Cabal file. - #100: Rename
`fromAdjacencyList`

to`stars`

. - #79: Improve the API consistency: rename
`IntAdjacencyMap`

to`AdjacencyIntMap`

, and then rename the function that extracts its adjacency map to`adjacencyIntMap`

to avoid the clash with`AdjacencyMap.adjacencyMap`

, which has incompatible type. - #82, #92: Add performance regression suite.
- #76: Remove benchmarks.
- #74: Drop dependency of
`Algebra.Graph`

on graph type classes. - #62: Move King-Launchbury graphs into
`Data.Graph.Typed`

. - #67, #68, #69, #77, #81, #93, #94, #97, #103, #110: Various performance improvements.
- #66, #72, #96, #98: Add missing
`NFData`

instances.

## 0.1.1.1

- #59: Allow
`base-compat-0.10`

.

## 0.1.1

- #58: Update documentation.
- #57: Allow newer QuickCheck.

## 0.1.0

- Start complying with PVP.
- #48: Add
`starTranspose`

. - #48: Add
`foldg`

to`ToGraph`

. - #15: Optimise
`removeEdge`

. - #39: Factor out difference lists into
`Algebra.Graph.Internal`

. - #31: Add
`Algebra.Graph.NonEmpty`

. - #32: Remove smart constructor
`graph`

. - #27, #55: Support GHC versions 7.8.4, 7.10.3, 8.0.2, 8.2.2, 8.4.1.
- #25: Add
`NFData Graph`

instance. - General improvements to code, documentation and tests.

## 0.0.5

- Add
`dfs`

. - #19: Move
`GraphKL`

to an internal module. - #18: Add
`dfsForestFrom`

. - #16: Add support for graph export, in particular in DOT format.
- Make API more consistent, e.g. rename
`postset`

to`postSet`

. - Improve documentation and tests.