Repository files navigation

Alga is a library for algebraic construction and manipulation of graphs in Haskell. Seethis Haskell Symposium paper and thecorrespondingtalk for the motivationbehind the library, the underlying theory and implementation details. There is also aHaskell eXchange talk,and atutorial by Alexandre Moine.

Consider the following data type, which is defined in the top-level moduleAlgebra.Graphof the library:

dataGrapha=Empty |Vertexa |Overlay (Grapha) (Grapha) |Connect (Grapha) (Grapha)

We can give the following semantics to the constructors in terms of the pair(V, E) of graphvertices andedges:

• 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 followingtype class and specifying a set of laws for its instances (see moduleAlgebra.Graph.Class):

classGraphgwheretypeVertexgempty::gvertex::Vertexg->goverlay::g->g->gconnect::g->g->g

The laws of the type class are remarkably similar to those of asemiring,so we use+ and* as convenient shortcuts foroverlay andconnect, 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 tounlabelled directed graphs: every expression represents a graph, and everygraph can be represented by an expression. Other types of graphs (e.g. undirected) can be obtained by modifying theabove 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 representnon-empty graphs, we can drop theEmpty constructor -- see moduleAlgebra.Graph.NonEmpty.

To representedge-labelled graphs, we can switch to the following data type, asexplained in myHaskell eXchange 2018 talk:

dataGraphea=Empty               |Vertexa               |Connecte (Graphea) (Graphea)

Heree is the type of edge labels. Ife is a monoid(<+>, zero) then graph overlay can be recoveredasConnect zero, and<+> corresponds toparallel composition of edge labels.

Alga can handle graphs comprising millions of vertices and billions of edges in a matter of seconds, which is fastenough for many applications. We believe there is a lot of potential for improving the performance of the library, andthis 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 foundhere.

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 were implemented in a few other languages, includingAgda,F#,Scala andTypeScript.