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:

1. Producing parallel implementations of crucial graph algorithms.

2. Improving sequential implementation of crucial graph algorithms in LightGraphs.

3. 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.

Benchmark Graph Datasets

No.	Graph	Vertices	Edges
1	Twitter Social Circles	81,306	1,342,310
2	Astro-Physics Collaboration	17,903	197,031
3	Facebook Social Circles	4,039	88,234

The graphs were obtained from the SNAPDatasets repository.

Speed-up on parallelization with 4 cores

Algorithm	Twitter	Astro-Physics	Facebook
Breadth-First Search	1.92	2.59	1.54
PageRank	1.77	1.54	1.65
Bellman Ford SSSP	-	-	1.88
Floyd Warshall APSP	-	-	1.27
Johnson APSP	-	-	2.10
Randomized Heuristic	1.88	1.70	1.66
Betweenness Centrality	-	-	1.96
Closeness Centrality	-	-	2.17
Stress Centrality	-	-	1.66

Speed-up on sequential optimization

Algorithm	Twitter	Astro-Physics	Facebook
PageRank	3.05	3.37	3.17
Dijkstra SSSP	2.80	2.10	1.68
Prim MST	7.65	4.25	4.05
Kruskal MST	7.70	3.37	2.80

Absolute runtime (in ms) of Bread-First Search

Algorithm	Twitter	Astro-Physics	Facebook
Parallel	7.07	1.20	0.26
Sequential	13.63	3.11	0.41

Get the code

This section lists the functionality implemented and a link to the corresponding branch in my cloned LightGraphs repository.

Completed and merged

The following branches have been merged into LightGraphs master:

• Parallel Breadth-First Search

• Kruskal MST

• Sequential/Parallel Johnson APSP

• Parallel Floyd Warshall APSP

• Parallel Bellman Ford SSSP

• Parallel PageRank

• PageRank

• Load-balanced Partitioning

• Prim MST

• Dijkstra SSSP I

• Dijkstra SSSP II

• Greedy Heuristics

  1. Minimum Vertex Cover

  2. Minimum Dominating Set

  3. Maximum Independent Set

  4. Vertex Connectivity

• Parallel Random Heuristics

• Karger Minimum Cut

• Multi-threaded Centrality Measures

  1. Betweeness Centrality

  2. Closeness Centrality

  3. Stress Centrality

Completed but not applicable

The following branches have not been merged into LightGraphs master as the functionality is not suitable to LightGraphs:

• Minimum Steiner Tree

• Metric Travelling Salesman

Requires Improvement

The following branches have not been merged into LightGraphs as the parallel implementations are slower than the sequential implementation:

• Parallel Kruskal MST

• Parallel Prim MST

• Parallel Dijkstra SSSP

Acknowledgements

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.