This blog briefly summarises my GSoC 2018 project (Parallel Graph Development) and the results achieved. For a detailed description, please refer to my GSoC blog.
The project is spread over the LightGraphs codebase. It involved:
Producing parallel implementations of crucial graph algorithms.
Improving sequential implementation of crucial graph algorithms in LightGraphs.
Implementing heuristics to obtain good solutions to crucial NP-Hard graph problems.
The benchmarks were conducted on a 64-bit linux machine using 4 cores.
|1||Twitter Social Circles||81,306||1,342,310|
|3||Facebook Social Circles||4,039||88,234|
The graphs were obtained from the SNAPDatasets repository.
|Bellman Ford SSSP||-||-||1.88|
|Floyd Warshall APSP||-||-||1.27|
This section lists the functionality implemented and a link to the corresponding branch in my cloned LightGraphs repository.
The following branches have been merged into LightGraphs master:
Minimum Vertex Cover
Minimum Dominating Set
Maximum Independent Set
Multi-threaded Centrality Measures
The following branches have not been merged into LightGraphs master as the functionality is not suitable to LightGraphs:
The following branches have not been merged into LightGraphs as the parallel implementations are slower than the sequential implementation:
I would like to thank my mentor, Divyansh Srivastava and LightGraphs co-owner, Seth Bromberger for reviewing my code and providing valuable advice during the summer. I would also like to thank The Julia Project and NUMFocus for sponsoring my attendance to JuliaCon 2018.