algebraic-edge-graphs

A library for algebraic construction and manipulation of edge-indexed graphs in Haskell. See this paper for the motivation behind the library and the underlying theory.

Installation

cabal install algebraic-edge-graphs

Getting started

The core data type is EdgeGraph, built from six primitives:

import EdgeGraph
import EdgeGraph.Class

-- A single edge labelled 1
e1 = edge 1 :: EdgeGraph Int

-- Two edges connected in sequence: 1 flows into 2
p = into (edge 1) (edge 2) :: EdgeGraph Int

-- A path through edges 1, 2, 3
p3 = path [1, 2, 3] :: EdgeGraph Int

-- Overlay places edges side by side (no connection)
disconnected = overlay (edge 1) (edge 2) :: EdgeGraph Int

-- A cycle through edges 1 and 2
c = circuit [1, 2] :: EdgeGraph Int

Folding over graphs

The EdgeGraph.Fold module provides semiring-based path algorithms via the Boehm-Berarducci encoding:

import EdgeGraph
import qualified EdgeGraph.Fold as F

-- Convert to Fold representation
g = into (edge 1) (edge 2) :: EdgeGraph Int
f = toFold g

-- Shortest paths using edge labels as weights
sp = F.shortestPaths id f

-- Widest (bottleneck) paths
wp = F.widestPaths id f

-- Reachability, cycle detection
r  = F.reachable f
ac = F.isAcyclic f

Adjacency map representation

For algorithms like DFS, topological sort, and strongly connected components, convert to AdjacencyMap:

import EdgeGraph
import qualified EdgeGraph.AdjacencyMap as AM

g = path [1, 2, 3] :: EdgeGraph Int
m = AM.fromEdgeGraph g

AM.topSort m   -- Just [1, 2, 3]
AM.dfsForest m -- depth-first search forest
AM.scc m       -- strongly connected components

Key modules

Module	Description
EdgeGraph	Core data type and graph operations
EdgeGraph.Class	Type class for polymorphic graph construction
EdgeGraph.Fold	Boehm-Berarducci encoding and semiring path algorithms
EdgeGraph.AdjacencyMap	Adjacency map with DFS, topological sort, SCC
EdgeGraph.IntAdjacencyMap	Int-specialised adjacency map
EdgeGraph.Incidence	Incidence representation for node-level structure
EdgeGraph.HigherKinded.Class	Higher-kinded type class for graph construction

Acknowledgements

This project was originally forked from Andrey Mokhov's algebraic-graphs library, the theory of which was provided in this paper. The codebase has changed substantially, but the original work provided the foundation for this project.