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: Implementing Sloan Ordering Algorithm to pgRouting from 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:
- Sloan Ordering: It is an algorithm for profile and wavefront reduction of sparse matrices. The algorithm generates an optimal vertex ordering that reduces the profile and bandwidth of a graph, improving the efficiency of matrix operations, finite element analysis, and graph-based computational methods. The Sloan algorithm works by selecting a starting vertex and using a pseudo-peripheral node strategy to systematically reorder graph vertices, with a time complexity of O(V + E) and space complexity of O(V), where V is the number of vertices and E is the number of edges. This implementation will enhance pgRouting’s capabilities in graph optimization, benefiting with sparse graph representations.
It is implemented in Boost Graph Library (BGL) as boost::sloan_ordering.
State of the Project Before GSoC: pgRouting currently does not have this algorithm implemented. Currently, only the experimental reverse Cuthill Mckee Algorithm has been implemented from the Sparse Matrix Ordering Algorithms 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:
- After the completion of the implementation of
pgr_sloanOrdering(), I will focus on resolving any potential bugs or usability issues that may come up during extended testing and community feedback. - I would like to improve the implementation by adding support for directed and more complex weighted graphs after the program ends, so I can experiment and develop at a more relaxed pace.
- I would like to further explore and possibly implement the parallel execution of proposed pgr_sloanOrdering() and existing pgr_cuthillMckeeOrdering() functions for improving metrics.
Links:
- Pull Requests:
- Final Pull Request: (#2957) Experimental Function - sloanOrdering (New function pgr_sloanOrdering by bipashabg · Pull Request #2957 · pgRouting/pgrouting · GitHub).
- Intermediate pull requests: Pull requests · pgRouting/GSoC-pgRouting · GitHub
- Project Documentation (Wiki Page): GSoC 2025 Sloan Ordering Algorithm · pgRouting/pgrouting Wiki · GitHub
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 improve my existing knowledge of contributing to open source and also got me better at programming. Last but not the least, thank you to my mentors and the entire community for the continuous support, guidance and helpful communication!
Thank you and Regards,
Bipasha Gayary