algebraic-graphs

A library for algebraic graph construction and transformation

LTS Haskell 21.23:	0.7@rev:2
Stackage Nightly 2023-12-03:	0.7@rev:2
Latest on Hackage:	0.7@rev:2

See all snapshots algebraic-graphs appears in

MIT licensed by Andrey Mokhov, github: @snowleopard

Maintained by Andrey Mokhov, github: @snowleopard, Alexandre Moine, github: @nobrakal

This version can be pinned in stack with:algebraic-graphs-0.7@sha256:75f8bbfffc8bc6c8a0a3c61f7f3ed2129fee35fd929822230b693786059f4fdf,8800

Module documentation for 0.7

Algebra
- Algebra.Graph
  - Algebra.Graph.Acyclic
    - Algebra.Graph.Acyclic.AdjacencyMap
  - Algebra.Graph.AdjacencyIntMap
    - Algebra.Graph.AdjacencyIntMap.Algorithm
  - Algebra.Graph.AdjacencyMap
    - Algebra.Graph.AdjacencyMap.Algorithm
  - Algebra.Graph.Bipartite
    - Algebra.Graph.Bipartite.AdjacencyMap
      - Algebra.Graph.Bipartite.AdjacencyMap.Algorithm
  - Algebra.Graph.Class
  - Algebra.Graph.Example
    - Algebra.Graph.Example.Todo
  - Algebra.Graph.Export
    - Algebra.Graph.Export.Dot
  - Algebra.Graph.HigherKinded
    - Algebra.Graph.HigherKinded.Class
  - Algebra.Graph.Internal
  - Algebra.Graph.Label
  - Algebra.Graph.Labelled
    - Algebra.Graph.Labelled.AdjacencyMap
    - Algebra.Graph.Labelled.Example
      - Algebra.Graph.Labelled.Example.Automaton
      - Algebra.Graph.Labelled.Example.Network
  - Algebra.Graph.NonEmpty
    - Algebra.Graph.NonEmpty.AdjacencyMap
  - Algebra.Graph.Relation
    - Algebra.Graph.Relation.Preorder
    - Algebra.Graph.Relation.Reflexive
    - Algebra.Graph.Relation.Symmetric
    - Algebra.Graph.Relation.Transitive
  - Algebra.Graph.ToGraph
  - Algebra.Graph.Undirected
Data
- Data.Graph
  - Data.Graph.Typed

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 Haskell Symposium paper and the corresponding talk for the motivation behind the library, the underlying theory and implementation details. There is also a Haskell eXchange talk, and a tutorial by Alexandre Moine.

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.

To represent edge-labelled graphs, we can switch to the following data type, as explained in my Haskell eXchange 2018 talk:

data Graph e a = Empty
               | Vertex a
               | Connect e (Graph e a) (Graph e a)

Here e is the type of edge labels. If e is a monoid (<+>, zero) then graph overlay can be recovered as Connect zero, and <+> corresponds to parallel composition of edge labels.

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

Blog posts

The development of the library has been documented in the series of blog posts:

Introduction: https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/
A few different flavours of the algebra: https://blogs.ncl.ac.uk/andreymokhov/graphs-a-la-carte/
Graphs in disguise or How to plan you holiday using Haskell: https://blogs.ncl.ac.uk/andreymokhov/graphs-in-disguise/
Old graphs from new types: https://blogs.ncl.ac.uk/andreymokhov/old-graphs-from-new-types/

Algebraic graphs in other languages

Algebraic graphs were implemented in a few other languages, including Agda, F#, Scala and TypeScript.

Changes

Change log

0.7

#294: Change the argument order of bfs*, dfs* and reachable algorithms.
#293: Fix the ToGraph instance of symmetric relations.

0.6.1

Drop dependency on mtl.

0.6

#276: Add Monoid and Semigroup instances.
#278: Stop supporting GHC 8.0 and GHC 8.2.
#274, #277: Expand the API and add algorithms for bipartite graphs, drop the Undirected component in Bipartite.Undirected.AdjacencyMap.
#273: Add attribute quoting style to Export.Dot.
#259: Allow newer QuickCheck.
#257: Add IsString instances.
#226: Expand the API of Bipartite.Undirected.AdjacencyMap.

0.5

#217, #224, #227, #234, #235: Add new BFS, DFS, topological sort, and SCC algorithms for adjacency maps.
#228, #247, #254: Improve algebraic graph fusion.
#207, #218, #255: Add Bipartite.Undirected.AdjacencyMap.
#220, #237, #255: Add Algebra.Graph.Undirected.
#203, #215, #223: Add Acyclic.AdjacencyMap.
#202, #209, #211: Add induceJust and induceJust1.
#172, #245: Stop supporting GHC 7.8 and GHC 7.10.
#208: Add fromNonEmpty to NonEmpty.AdjacencyMap.
#208: Add fromAdjacencyMap to AdjacencyIntMap.
#208: Drop Internal modules for AdjacencyIntMap, AdjacencyMap, Labelled.AdjacencyMap, NonEmpty.AdjacencyMap, Relation and Relation.Symmetric.
#206: Add Algebra.Graph.AdjacencyMap.box.
#205: Drop dependencies on base-compat and base-orphans.
#205: Remove Algebra.Graph.Fold.
#151: Remove ToGraph.size. Demote ToGraph.adjacencyMap, ToGraph.adjacencyIntMap, ToGraph.adjacencyMapTranspose and ToGraph.adjacencyIntMapTranspose to functions.
#204: Derive Generic and NFData for Algebra.Graph and Algebra.Graph.Labelled.

0.4

#174: Add Symmetric.Relation.
#143: Allow newer QuickCheck.
#171: Implement sparsification for King-Launchbury graph representation.
#178: Derive Generic for adjacency maps.

0.3

#129: Add a testsuite for rewrite rules based on the inspection-testing library.
#63, #148: Add relational composition of algebraic graphs.
#139, #146: Add relational operations to adjacency maps.
#146: Rename preorderClosure to closure.
#146: Switch to left-to-right composition in Relation.compose.
#143: Allow newer QuickCheck.
#140, #142: Fix Show instances.
#128, #130: Modify the SCC algorithm to return non-empty graph components.
#130: Move adjacency map algorithms to separate modules.
#130: Export fromAdjacencySets and fromAdjacencyIntSets.
#138: Do not require Eq instance on the string type when exporting graphs.
#136: Rename Algebra.Graph.NonEmpty.NonEmptyGraph to Algebra.Graph.NonEmpty.Graph.
#136: Add Algebra.Graph.NonEmpty.AdjacencyMap.
#136: Remove vertexIntSet from the API of basic graph data types. Also remove Algebra.Graph.adjacencyMap and Algebra.Graph.adjacencyIntMap. This functionality is still available from the type class ToGraph.
#126, #131: Implement custom Ord instance.
#17, #122, #125, #149: Add labelled algebraic graphs.
#121: Drop Foldable and Traversable instances.
#113: Add Labelled.AdjacencyMap.

0.2

#117: Add sparsify.
#115: Add isDfsForestOf.
#114: Add a basic implementation of edge-labelled graphs.
#107: Drop starTranspose.
#106: Extend ToGraph with algorithms based on adjacency maps.
#106: Add isAcyclic and reachable.
#106: Rename isTopSort to isTopSortOf.
#102: Switch the master branch to GHC 8.4.3. Add a CI instance for GHC 8.6.1.
#101: Drop -O2 from the ghc-options section of the Cabal file.
#100: Rename fromAdjacencyList to stars.
#79: Improve the API consistency: rename IntAdjacencyMap to AdjacencyIntMap, and then rename the function that extracts its adjacency map to adjacencyIntMap to avoid the clash with AdjacencyMap.adjacencyMap, which has incompatible type.
#82, #92: Add performance regression suite.
#76: Remove benchmarks.
#74: Drop dependency of Algebra.Graph on graph type classes.
#62: Move King-Launchbury graphs into Data.Graph.Typed.
#67, #68, #69, #77, #81, #93, #94, #97, #103, #110: Various performance improvements.
#66, #72, #96, #98: Add missing NFData instances.

0.1.1.1

#59: Allow base-compat-0.10.

0.1.1

#58: Update documentation.
#57: Allow newer QuickCheck.

0.1.0

Start complying with PVP.
#48: Add starTranspose.
#48: Add foldg to ToGraph.
#15: Optimise removeEdge.
#39: Factor out difference lists into Algebra.Graph.Internal.
#31: Add Algebra.Graph.NonEmpty.
#32: Remove smart constructor graph.
#27, #55: Support GHC versions 7.8.4, 7.10.3, 8.0.2, 8.2.2, 8.4.1.
#25: Add NFData Graph instance.
General improvements to code, documentation and tests.

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.