Algebraic graphs

Hackage version Linux & OS X status Windows status

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.

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.

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 in doc/benchmarks.

Blog posts

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

Changes

Change log

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.