A library for algebraic edge-graph construction and transformation.

A library for algebraic construction and manipulation of edge-indexed graphs in Haskell. Based on the theory of algebraic edge graphs.

The top-level module EdgeGraph defines the core data type EdgeGraph.EdgeGraph which is a deep embedding of six graph construction primitives EdgeGraph.empty, EdgeGraph.edge, EdgeGraph.overlay, EdgeGraph.into, EdgeGraph.pits and EdgeGraph.tips. More conventional graph representations can be found in EdgeGraph.AdjacencyMap and EdgeGraph.Incidence.

The type classes defined in EdgeGraph.Class and EdgeGraph.HigherKinded.Class can be used for polymorphic graph construction and manipulation. Also see EdgeGraph.Fold that defines the Boehm-Berarducci encoding of algebraic edge graphs and provides additional flexibility for polymorphic graph manipulation.

This is an experimental library and the API will be unstable until version 1.0.0.

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

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.