@hackage / algebraic-edge-graphs

A library for algebraic edge-graph construction and transformation

Latest0.1.1

About

Metadata

  • Last updated , by jackliellcock
  • License MIT
  • Categories Algorithms, Data Structures, Mathematics

  • Maintained by: Jack Liell-Cock <jackliellcock@gmail.com>

  • Lottery factor: 1

Links

Installation

Tested Compilers

  1. 9.12.1
  2. 9.10.1
  3. 9.8.4
  4. 9.6.6

Readme

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.