The repository contains the code associated with a parallel MSTp solver I implemented as well as the code for the latex report written for the project. For the project I decided to follow what was written in the paper A generic and highly efficient parallel variant of Boruvka's algorithm. The solution suffers from a series of problems that I discovered during the project and for which I proposed a possibile solution in the conclusions section.
The code was developed in the "free for use" development platform from Google, Colab.
The whole notebook can be imported in the environment and run, should already contain everything it needs to work, as far as tests are concerned two different approaches can be followed:
- A graph generator, mind that if the graph is not sparse the performance of the algorithm will fail to meet expectations
- The graphs proposed in the 9th DIMACS challenge (Benchmarks) due to the weird format of the data they should be cleaned with something like a python script or similar because the reading script is expecting a file very similar to a csv.
The conclusions for the project can be found in the report