1# Algebraic graphs 2 3[](https://hackage.haskell.org/package/algebraic-graphs) [](https://travis-ci.org/snowleopard/alga) [](https://ci.appveyor.com/project/snowleopard/alga) 4 5**Alga** is a library for algebraic construction and manipulation of graphs in Haskell. See 6[this Haskell Symposium paper](https://github.com/snowleopard/alga-paper) and the 7corresponding [talk](https://www.youtube.com/watch?v=EdQGLewU-8k) for the motivation 8behind the library, the underlying theory and implementation details. There is also a 9[Haskell eXchange talk](https://skillsmatter.com/skillscasts/10635-algebraic-graphs), 10and a [tutorial](https://nobrakal.github.io/alga-tutorial) by Alexandre Moine. 11 12## Main idea 13 14Consider the following data type, which is defined in the top-level module 15[Algebra.Graph](http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph.html) 16of the library: 17 18```haskell 19data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a) 20``` 21 22We can give the following semantics to the constructors in terms of the pair **(V, E)** of graph *vertices* and *edges*: 23 24* `Empty` constructs the empty graph **(∅, ∅)**. 25* `Vertex x` constructs a graph containing a single vertex, i.e. **({x}, ∅)**. 26* `Overlay x y` overlays graphs **(Vx, Ex)** and **(Vy, Ey)** constructing **(Vx ∪ Vy, Ex ∪ Ey)**. 27* `Connect x y` connects graphs **(Vx, Ex)** and **(Vy, Ey)** constructing **(Vx ∪ Vy, Ex ∪ Ey ∪ Vx × Vy)**. 28 29Alternatively, we can give an algebraic semantics to the above graph construction primitives by defining the following 30type class and specifying a set of laws for its instances (see module [Algebra.Graph.Class](http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-Class.html)): 31 32```haskell 33class Graph g where 34 type Vertex g 35 empty :: g 36 vertex :: Vertex g -> g 37 overlay :: g -> g -> g 38 connect :: g -> g -> g 39``` 40 41The laws of the type class are remarkably similar to those of a [semiring](https://en.wikipedia.org/wiki/Semiring), 42so we use `+` and `*` as convenient shortcuts for `overlay` and `connect`, respectively: 43 44* (`+`, `empty`) is an idempotent commutative monoid. 45* (`*`, `empty`) is a monoid. 46* `*` distributes over `+`, that is: `x * (y + z) == x * y + x * z` and `(x + y) * z == x * z + y * z`. 47* `*` can be decomposed: `x * y * z == x * y + x * z + y * z`. 48 49This algebraic structure corresponds to *unlabelled directed graphs*: every expression represents a graph, and every 50graph can be represented by an expression. Other types of graphs (e.g. undirected) can be obtained by modifying the 51above set of laws. Algebraic graphs provide a convenient, safe and powerful interface for working with graphs in Haskell, 52and allow the application of equational reasoning for proving the correctness of graph algorithms. 53 54To represent *non-empty graphs*, we can drop the `Empty` constructor -- see module 55[Algebra.Graph.NonEmpty](http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-NonEmpty.html). 56 57To represent *edge-labelled graphs*, we can switch to the following data type, as 58explained in my [Haskell eXchange 2018 talk](https://skillsmatter.com/skillscasts/12361-labelled-algebraic-graphs): 59 60```haskell 61data Graph e a = Empty 62 | Vertex a 63 | Connect e (Graph e a) (Graph e a) 64``` 65 66Here `e` is the type of edge labels. If `e` is a monoid `(<+>, zero)` then graph overlay can be recovered 67as `Connect zero`, and `<+>` corresponds to *parallel composition* of edge labels. 68 69## How fast is the library? 70 71Alga can handle graphs comprising millions of vertices and billions of edges in a matter of seconds, which is fast 72enough for many applications. We believe there is a lot of potential for improving the performance of the library, and 73this is one of our top priorities. If you come across a performance issue when using the library, please let us know. 74 75Some preliminary benchmarks can be found [here](https://github.com/haskell-perf/graphs). 76 77## Blog posts 78 79The development of the library has been documented in the series of blog posts: 80* Introduction: https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ 81* A few different flavours of the algebra: https://blogs.ncl.ac.uk/andreymokhov/graphs-a-la-carte/ 82* Graphs in disguise or How to plan you holiday using Haskell: https://blogs.ncl.ac.uk/andreymokhov/graphs-in-disguise/ 83* Old graphs from new types: https://blogs.ncl.ac.uk/andreymokhov/old-graphs-from-new-types/ 84 85## Algebraic graphs in other languages 86 87See draft implementations in [Agda](http://github.com/algebraic-graphs/agda) 88and [Scala](http://github.com/algebraic-graphs/scala). 89
){kind=link}
){kind=link}
){kind=link}