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.
The following series of blog posts also describe the ideas behind the library:
- 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/
You can find more code in this old experimental repo: https://github.com/snowleopard/graph-algebra.
Some quick benchmarks with Criterion, I'll keep adding more graph instances, with some high-performance options too.
2D meshes are constructed as path [1..n] `box` path [1..n].
| Benchmark | |V| | |E| | Runtime |
|---|---|---|---|
| Compute the size of VertexSet | 1 | 0 | 318 ns |
| 100 | 180 | 154 μs | |
| 10 000 | 19 800 | 31.8 ms | |
| 1 000 000 | 1 998 000 | 7.33 s | |
| Compute the size of Relation | 1 | 0 | 250 ns |
| 100 | 180 | 152 μs | |
| 10 000 | 19 800 | 35.7 ms | |
| 1 000 000 | 1 998 000 | 8.79 s | |
| Compute the number of edges in AdjacencyMap | 1 | 0 | 334 ns |
| 100 | 180 | 223 μs | |
| 10 000 | 19 800 | 49.5 ms | |
| 1 000 000 | 1 998 000 | 10.5 s | |
| Compute the size of Int.VertexSet | 1 | 0 | 315 ns |
| 100 | 180 | 52 μs | |
| 10 000 | 19 800 | 7.4 ms | |
| 1 000 000 | 1 998 000 | 1.54 s | |
| Compute the number of edges in Int.AdjacencyMap | 1 | 0 | 303 ns |
| 100 | 180 | 98.9 μs | |
| 10 000 | 19 800 | 18 ms | |
| 1 000 000 | 1 998 000 | 4.24 s |
A clique is simply clique [1..n]. We can handle cliques with billions of edges thanks to the
simple connectivity structure exploited by AdjacencyMap. The VertexSet instance ignores edges
altogether and eats cliques for breakfast.
| Benchmark | |V| | |E| | Runtime |
|---|---|---|---|
| Compute the size of Int.VertexSet | 1 | 1 | 43.2 ns |
| 10 | 45 | 375 ns | |
| 100 | 4 950 | 3.67 μs | |
| 1 000 | 499 500 | 55.3 μs | |
| 10 000 | 49 995 000 | 2.08 ms | |
| 44 722 | 1 000 006 281 | 13.8 ms | |
| Compute the size of Relation | 1 | 1 | 38.9 ns |
| 10 | 45 | 7.74 μs | |
| 100 | 4 950 | 969 μs | |
| 1 000 | 499 500 | 93.8 ms | |
| 10 000 | 49 995 000 | 11.2 s | |
| Compute the number of edges in Int.AdjacencyMap | 1 | 1 | 45.4 ns |
| 10 | 45 | 1.72 μs | |
| 100 | 4 950 | 49.3 μs | |
| 1 000 | 499 500 | 3.68 ms | |
| 10 000 | 49 995 000 | 376 ms | |
| 44 722 | 1 000 006 281 | 10.2 s |
De Bruijn graphs are constructed as deBruijn n "0123456789"
and as gmap fastRead $ deBruijn n "0123456789" for Int instances,
where fastRead = foldr (\c r -> r + ord c - ord '0') 0. Note that
gmap fastRead takes roughly 5% of Int.AdjacencyMap runtime and
15% of Int.VertexMap runtime.
| Benchmark | |V| | |E| | Runtime |
|---|---|---|---|
| Compute the size of VertexSet | 10 | 100 | 4.86 μs |
| 100 | 1 000 | 104 μs | |
| 1 000 | 10 000 | 2.09 ms | |
| 10 000 | 100 000 | 34.8 ms | |
| 100 000 | 1 000 000 | 430 ms | |
| 1 000 000 | 10 000 000 | 6.35 s | |
| Compute the size of Relation | 10 | 100 | 7.13 μs |
| 100 | 1 000 | 282 μs | |
| 1 000 | 10 000 | 6.05 ms | |
| 10 000 | 100 000 | 83.1 ms | |
| 100 000 | 1 000 000 | 960 ms | |
| 1 000 000 | 10 000 000 | 11.4 s | |
| Compute the number of edges in AdjacencyMap | 10 | 100 | 7.83 μs |
| 100 | 1 000 | 159 μs | |
| 1 000 | 10 000 | 3.04 ms | |
| 10 000 | 100 000 | 47.5 ms | |
| 100 000 | 1 000 000 | 644 ms | |
| 1 000 000 | 10 000 000 | 8.13 s | |
| Compute the size of Int.VertexSet | 10 | 100 | 5.13 μs |
| 100 | 1 000 | 61.8 μs | |
| 1 000 | 10 000 | 882 μs | |
| 10 000 | 100 000 | 8.93 ms | |
| 100 000 | 1 000 000 | 105 ms | |
| 1 000 000 | 10 000 000 | 1.10 s | |
| Compute the number of edges in Int.AdjacencyMap | 10 | 100 | 8.59 μs |
| 100 | 1 000 | 175 μs | |
| 1 000 | 10 000 | 2.76 ms | |
| 10 000 | 100 000 | 30.4 ms | |
| 100 000 | 1 000 000 | 368 ms | |
| 1 000 000 | 10 000 000 | 3.77 s |