A library for algebraic construction and manipulation of graphs in Haskell. The following series of blog posts describes the code in detail:
- 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 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 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 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 |