# algebraic-graphs

A library for algebraic graph construction and transformation

https://github.com/snowleopard/alga

 Version on this page: 0.1.1.1 LTS Haskell 21.12: 0.7@rev:1 Stackage Nightly 2023-09-22: 0.7@rev:1 Latest on Hackage: 0.7@rev:1

See all snapshots algebraic-graphs appears in

This version can be pinned in stack with:algebraic-graphs-0.1.1.1@sha256:af54e89839521f04f3b4bd980112701a31c7cf0d612776f8aa65083bcd1f3090,7734

#### Module documentation for 0.1.1.1

Depends on 5 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.

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:

# Change log

## 0.1.1.1

• #59: Allow base-compat-0.10.

## 0.1.1

• #58: Update documentation.

## 0.1.0

• Start complying with PVP.
• #48: Add foldg to ToGraph.
• #15: Optimise removeEdge.
• #39: Factor out difference lists into Algebra.Graph.Internal.