Minimum spanning tree calculation and dynamic re-calculation by using Kruskal's and Prim's algorithms
Implemented by:
Prerequisites:
- CMake (version 3.13 or higher)
- Make (tested with GNU Make 4.2.1)
- C++17 compatible compiler (tested with g++ 9.3.0)
(Should work in Windows as well with either nmake or msbuild combined with cmake, but it's untested)
For Plotting:
There is a Makefile provided for the project. From the project source running running
make
will create a build
directory and compile the main executable and test executables.
It will also copy the main executable under project root directory for convenience.
It detects CMake automatically and makes the necessary build calls. This Makefile
should be able compile even when CMake is not present.
Alternatively running the following commands will give the same results
mkdir build && cd build
cmake ..
make -j
There are some unit tests included with this project. Running the following command from the root directory after the project is built will run them show their outputs.
make test
Alternatively you can do the following and get the same result
cd build
ctest -j
Important: Makefile
may not be as comprehensive as the CMake version. It's
highly recommended that you have CMake on your machine before running above commands.
A python script is provided to regenerate the plots and from scratch. Running
the following commands from project root will install prerequisites and regenerate
the plots under results
directory by running the executable with all the datasets
available under data
directory.
pip install -r requirements.txt
python3 results/plotter.py
Both Kruskal's and Prim's version is implemented. Although, without using Fibonacci heap,
both have the same complexity of O(E*log(V))
, Kruskal's run slower in practice due to
a rather inefficient implementation of finding sets within forest, this could be improved
further, however, current implementation doesn't go into details of optimization. If
Fibonacci heap is used with Prim's algorithm it's complexity becomes O(E+V*log(V))
Re-compute MST:
When a new edge is added to the current MST. This forms exactly one cycle in the
MST. Let e = (u,v)
be the new edge with the weight w
. In order to update the
MST we first find the unique path from u
to v
in the existing MST. Then we find
the edge with the maximum weight w*
in this path. If w < w*
we replace the new
edge with this edge otherwise our MST is already optimal and we make no changes.
Finding the unique path and the maximum of that path takes O(V)
time, which is
the cost of this operation.
The results in the graphs seems they match the expected results, both dynamic and static