Experimental analysis on the impact of different algorithms and heap-based data structures for solving the minimal spanning tree problem on directed and undirected graphs. The goal is to identify strengths and weaknesses of various approaches. The study is conducted on random graphs of various size and density. You can read a complete overview of the project and its results in the report.
Focus of our study are:
- Kruskal's and Prim's algorithms for the minimum spanning tree problem;
- Chu–Liu/Edmonds' algorithm for the minimum spanning arborescence problem;
- binary, d-ary and Fibonacci heap data structures and counting sort.
I welcome you to read the conclusions in the final section of the report.
Install googletest and benchmark, then:
make test: compiles and runs the tests; andmake benchmark: compiles and runs the benchmarks.
The plots have been drawn with Python's Matplotlib. The scripts used to generate
the plots in the report are made available in the results directory.
They are not intended to be reused; nevertheless, you can give it a shot by
generating your own .bench data with, for example, ./bin/size > results/mst-size.bench. In this case, you should probably tweak
main.cpp as you like; for example, you might want to comment out the
stuff you don't need and set custom nodes, degrees and weights parameters.
