GSoC 2024 - Final Report | Implementing Brandes Betweenness Centrality - pgRouting

Initiatives Google Summer of Code
1

Hello everyone,

With GSoC coming to an end, I hereby present my final report of the work I have done over the past three months. It has been an amazing learning experience and great time working with the pgRouting community and mentors.

Title: Implement Brandes Betweenness Centrality Algorithm for pgRouting by the Boost Graph Library

Organisation: pgRouting under the umbrella of OSGeo

Abstract: This GSoC project dealt with the implementation of one new Graph algorithm in pgRouting. The algorithm is described below:

  • Betweenness Centrality: It is an algorithm used to compute the betweenness centrality of all vertices of a graph. Betweenness centrality is a measure that quantifies the importance of a vertex based on its occurrence on shortest paths between other vertices. Higher the betweenness centrality score, higher its importance to the graph as most of the routing will occur through it.

It is implemented in Boost Graph Library (BGL) as boost::brandes_betweenness_centrality. Brandes’s algorithm computes the betweenness centrality score for all vertices in the graph in O(VE) for unweighted graphs and O(VE + V(V+E) log V) for weighted graphs. The space complexity is O(VE)

State of the Project Before GSoC: pgRouting currently does not have this algorithm implemented. A single standard function does not exist for the betweenness centrality algorithm. This algorithm will be the first one from the Metrics family.

State of the Project After GSoC: The deliverables are code, documentation, documentation tests, and the pgTAP tests of the function pgr_betweennessCentrality.

Potential Future Work:

  • I would like to provide more tests for my function to promote it from experimental to proposed status.

  • My implementation of Betweenness Centrality in pgRouting is based on older pgRouting function templates. I aim to refactor the code into a header-only file, similar to the Boost Library’s approach which is the case for some of the pgRouting functions.

  • The implementation of Brandes Betweenness Centrality is just one of the several metrics family algorithms in the BGL. I would love to implement all the remaining algorithms in this family after GSoC.

Links:

I am so grateful to be a part of the amazing GSoC and OSGeo communities. I have learned a lot during this program and It has helped me kick start my software development journey. I would be happy if my code proves beneficial to the community. Last but not the least, thank you to my mentors and the entire community for the support!

Thanks and Regards,

Arun Thakur