# algebraic-graphs

A library for algebraic graph construction and transformation

https://github.com/snowleopard/alga

 Version on this page: 0.0.5 LTS Haskell 22.22: 0.7@rev:2 Stackage Nightly 2024-05-22: 0.7@rev:3 Latest on Hackage: 0.7@rev:3

See all snapshots `algebraic-graphs` appears in

This version can be pinned in stack with:`algebraic-graphs-0.0.5@sha256:661ae784c7d148cf63d6f1f08d830ef39a01fa13d27a8d25df8424820e8bf952,6454`

#### Module documentation for 0.0.5

Depends on 3 packages(full list with versions):

# Algebraic graphs

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.

## 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:

# Change log

## 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.