Note: Some functions of some libraries are not implemented so we use a "hand-made" implementation. Defintions can be found in
bench/. Suggestions are welcome!
What is benchmarked
In this folder, you will find the lastest benchmarks of 4 haskell graphs libraries:
- Alga (algebraic-graphs) v0.2.0.0 (not yet on hackage)
- Data.Graph from containers v0.5.11.0
- FGL v18.104.22.168
- Hash-Graph (not yet on hackage)
The benchmarks were realised using
Stack and the
Time benchmarks were run using Criterion v22.214.171.124
Space benchmarks were run using Weigh v0.12
Data size benchmarks were run using ghc-datasize v0.2.0
For the main results, we produce a generic list of edges (in ascending orders, but none of the libraries rely on this), create a graph from it, fully evaluate this graph to Normal Form, then pass it to then benchmarked function.
This may not reflect the reality, so we produced an alternative table where creation time (from a list of edges) is taken into account:
The list of edges
Containers, Fgl and Hash-Graph are dealing well with a list of edges. This is not the case with Alga, so we produced an alternative table where we used the alga representation instead of a list of edges:
Some words about graphs
The functions are benchmarked against:
- A mesh: This graph can be represented as a regular tiling of a plane, with edges going only right or up. It is a good example of a sparse graph. For example a mesh with nine vertices can be viewed as:
- A clique: This a graph such as every two distinct vertices are adjacent. It is a good example of a dense graph. The list of the edges of a clique with 5 vertices will look like:
- RealLife graphs are graphs from the real life, please see https://github.com/haskell-perf/graphs/tree/master/src/BenchGraph/RealLife/Graphs
The two first graphs are built with successive ten powers vertices. Here, with 1, 10, 100 and 1000 vertices.
Libraries are benchmarked against graphs with Int vertices.
All the functions are tested with arguments in the domain of the graph, where applicable: unless it is mentioned, edges and vertices generated for the test can be in the complete graph with the same number of vertices.
- Results are condensed in table, without the detail of arguments. For more precise results, please run the benchmark suite.
- Other graphs are supported (path, circuit and complete), you can run the benchmark suite using them.