The project is spread over the LightGraphs codebase. It involved:
The benchmarks were conducted on a 64-bit linux machine using 4 cores.
Benchmark Graph Datasets:
|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.
Speed-up on parallelization with 4 cores:
|Bellman Ford SSSP||-||-||1.88|
|Floyd Warshall APSP||-||-||1.27|
Speed-up on sequential optimization:
Absolute runtime (in ms) of Bread-First Search:
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:
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.