GSoC 2025 Sloan Ordering Algorithm - pgRouting/pgrouting GitHub Wiki
Table of Contents
Proposal
Brief Description
The project aims to add the following algorithm to in pgRouting during GSoC 2025:
- Sloan Ordering
Sloan ordering 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.
State of the Project Before GSoC
The absence of the Sloan ordering algorithm creates a functionality gap for users working with large network problems where matrix ordering significantly impacts computational efficiency. Current workarounds require users to export data to external tools, apply ordering algorithms, and re-import results, breaking workflow continuity and efficiency. Some proprietary GIS solutions include matrix ordering capabilities, but no open-source spatial database extension currently offers this functionality. The project aligns with pgRouting's roadmap for expanding advanced graph analysis capabilities beyond basic routing functions.
Deliverables
- Fully implemented Sloan ordering algorithm
- PostgreSQL/pgRouting integration
- Comprehensive documentation
- Performance benchmarks
- Extensive test suite
- Usage examples and tutorials plus prepare wiki report.
Detailed Proposal
Detailed Proposal Link (Google Doc)
Participants
| Title | GitHub Handle | Name |
|---|---|---|
| 1st Mentor | @cvvergara | Vicky Vergara |
| 2nd Mentor | @robe2 | Regina Obe |
| 3rd Mentor | @iosefa | Iosefa Percival |
| 4th Mentor | @sanak | Ko Nagase |
| Student Developer | @bipashabg | Bipasha Gayary |
Timeline
Community Bonding Period (May 8th- June 1st)
- Introduce myself to the pgRouting mentor(s) and other community members
- Set up my development environment
- Familiarize myself with the pgRouting codebase and development practices
- Learn pgTap and Boost Graph Library to help with the project
- Setup wiki page for tracking weekly progress of the project
- Participate in community discussions, meetings, or forums to engage with the project
- Engage with PostgreSQL and PostGIS to gain more insight and comfort for working on the project
Week -1 and 0 (What have I got done?)
- Set up my development environment
- Familiarize myself with the pgRouting codebase and development practices
- Go over pgTap practices and Boost Graph Library to help with the project and also go through the posgresql docs for the C-language functions.
- Setup wiki page for tracking weekly progress of the project.
- Update proposal for minor changes to ensure proper implementation of the function.
- Attended two weekly meetings during the bonding period.
- Created my own branch in the GSoC-pgRouting repository and laid out a folder structure where I would be writing the code in.
First Coding Period
Week 1
(2nd June- 8th June)
Original plan from proposal
- Review Boost Graph Library's sloan ordering algorithm
- Design data structures needed for pgr_sloanOrdering()
Revised plan
-
Create initial C++ implementation skeleton
-
sql/ordering/pgr_sloanOrdering.sql
-
sql/ordering/_pgr_sloanOrdering.sql
-
include/drivers/ordering_driver.hpp
-
include/process/ordering_process.h
-
src/ordering/ordering_driver.cpp
-
src/ordering/ordering_process.cpp
-
src/ordering/_sloanOrdering.c
What I got done?
-
Attended this week's weekly meeting on 2/06/2025
-
Added basic structure of the following files:-
-
sql/ordering/pgr_sloanOrdering.sql
-
sql/ordering/_pgr_sloanOrdering.sql
-
include/drivers/ordering_driver.hpp
-
include/process/ordering_process.h
-
src/ordering/ordering_driver.cpp
-
src/ordering/ordering_process.cpp
-
src/ordering/_sloanOrdering.c
-
Also updated CMakeLists.txt files.
Pull requests:
Week 2
(9th June- 15th June)
Original plan from proposal
- Implement core Sloan ordering algorithm logic
- Begin writing unit tests
Revised Plan
- Fix naming of files.
- Fix the licenses.
- Fix compilation errors.
- Add include/ordering/sloanOrdering.hpp file.
- Update the CMakeLists.txt files.
What I got done?
- Attended this week's weekly meetings on 8/06/2025 and 9/06/2025
- Add include/ordering/sloanOrdering.hpp file.
- Update the CMakeLists.txt files.
- Fix naming of files.
- [src/ordering] sloanOrdering_process.cpp -> ordering_process.cpp
- [src/ordering] sloanOrdering_driver.cpp -> ordering_driver.cpp
- [include/drivers] ordering_driver.hpp
- [include/process] sloanOrdering_process.h -> ordering_process.h
- Fix the licenses.
- Fix compilation errors.
Pull requests:
Week 3
(9th June- 15th June)
Original plan from proposal
- Set up continuous integration framework
- Initial code review and mentor feedback
Revised Plan
- Clear all compilation errors and warnings so far.
- Fix parameters and data types according to Boost implementation.
What I got done?
- Attended this week's weekly meeting on 16/06/2025
- Clear all compilation errors and warnings so far.
- Fix parameters and data types according to Boost implementation.
- Update ordering_process.cpp file.
- Fix code in SQL file.
Pull requests:
Week 4
(23rd June- 29th June)
Original plan from proposal
- Refine Sloan ordering implementation
- Develop PostgreSQL integration methods
Revised Plan
- Fix ordering driver file and wrap the updated code.
- Replace sloanOrdering.hpp file with ordering.hpp file to write basic skeleton for calling boost function.
- Fix more compilation errors due to ordering_driver.cpp file. (Need to be refined more)
- Create types_check.pg file for sloan ordering
What I got done?
- Attended this week's weekly meeting on 23/06/2025
- Fix ordering driver file and wrap the updated code.
- Replace sloanOrdering.hpp file with ordering.hpp file to write basic skeleton for calling boost function.
- Fix more compilation errors due to ordering_driver.cpp file. (Need to be refined more)
- Create types_check.pg file for sloan ordering
Pull requests:
Week 5
(June 30 - July 6)
Original Plan from Proposal
- Create comprehensive test cases
- Begin performance optimization
Revised Plan
- Fix input parameters in SQL file.
- Create the initial files of the documentation queries.
- Fix the intial pgTap test file.
- Delete unused code.
- Adjust build configuration files to include new and updated source and documentation files.
- Refactor function signatures and parameter types, replacing custom tuple types with int64_t arrays.
- Remove extra whitespace and corrected function signature in comments.
- Simplify result tuple logic and removed unused helper and type includes.
What I got done?
- Attended this week's weekly meeting on 30/06/2025
- Fix input parameters in SQL file.
- Create the initial files of the documentation queries.
- Fix the intial pgTap test file.
- Delete unused code.
- Adjust build configuration files to include new and updated source and documentation files.
- Refactor function signatures and parameter types, replacing custom tuple types with int64_t arrays.
- Remove extra whitespace and corrected function signature in comments.
- Simplify result tuple logic and removed unused helper and type includes.
- Minor formatting and include adjustments; no logic changes.
Pull requests:
Week 6
(July 7 - July 13)
Original Plan from Proposal
- Implement error handling and edge cases
- Midpoint code review with mentors
Revised Plan
- Write boost function call for sloan ordering in sloanOrdering.hpp file
- Add result file for initial docqueries testing.
- Mark unneeded code.
- Resolve subsequent compilation errors.
- Ensured all checks are passing at this stage.
- Improvised code in
sloanOrdering.cfile to house boost implementation.
What I got done?
- Attended this week's weekly meeting on 07/07/2025
- Write boost function call for sloan ordering in sloanOrdering.hpp file
- Add result file for initial docqueries testing.
- Mark unneeded code.
- Resolve subsequent compilation errors.
- Ensured all checks are passing at this stage.
- Improvised code in
sloanOrdering.cfile to house boost implementation.
Pull requests:
Second Coding Period
Week 7
(July 14 - July 20) Mid Term Period
Original Plan from Proposal
- Implement weighted graph support
- Add advanced configuration options
Revised Plan
- Make necessary changes in the sloanOrdering.hpp file to call the correct boost function call.
- Add sloan ordering version without weighted graph support.
- Fix existing errors in ordering_driver.cpp file and make the previously disabled code reach a compilable stage.
- Fix necessary code alignment and style issues.
- Call the get_results function to generate results table from function call.
- Remove unrequired code block from sloanOrdering.c file and modified the logic for calling boost function.
- Add example boost query to sloanOrdering.pg file in docqueries/ordering.
What I got done?
- Attended this week's weekly meeting on 14/07/2025
- Make necessary changes in the sloanOrdering.hpp file to call the correct boost function call.
- Add sloan ordering version without weighted graph support.
- Fix existing errors in ordering_driver.cpp file and make the previously disabled code reach a compilable stage.
- Fix necessary code alignment and style issues.
- Call the get_results function to generate results table from function call.
- Remove unrequired code block from sloanOrdering.c file and modified the logic for calling boost function.
- Add example boost query to sloanOrdering.pg file in docqueries/ordering.
Pull requests:
Week 8
(July 21 - July 27)
Original Plan from Proposal
- Develop detailed user and developer documentation
- Begin pgTAP test suite
Revised Plan
- Begin writing the rest of pgTap tests.
- Write no_crash_test.pg
- Write inner_query,pg
- Modify structure of return queries according to mentor's feedback
- Remove unrequired testing queries
- Mark todo for unsure test queries
- Create edge_cases.pg
What I got done?
- Attended this week's weekly meeting on 21/07/2025
- Begin writing the rest of pgTap tests.
- Write no_crash_test.pg
- Write inner_query,pg
- Modify structure of return queries according to mentor's feedback
- Remove unrequired testing queries
- Mark todo for unsure test queries
- Create edge_cases.pg
Pull requests:
Week 9
(July 28 - August 3)
Original Plan from Proposal
- Prepare integration examples
- Continue performance improvements
Revised Plan
- Created the documentation files for sloan ordering and add new file pgr_sloanOrdering.rst in doc/ordering
- Updated ordering-family.rst file to add the new documentation
- Modify the number of planned tests
- Updated CMakeLists
- Add new page entry for version 4.0
What I got done?
- Attended this week's weekly meeting on 27/07/2025
- Created the documentation files for sloan ordering and add new file pgr_sloanOrdering.rst in doc/ordering
- Updated ordering-family.rst file to add the new documentation
- Modify the number of planned tests
- Updated CMakeLists
- Add new page entry for version 4.0
Pull requests:
Week 10
(August 4 - August 10)
Original Plan from Proposal
- Final code optimization
- Comprehensive documentation review
Revised Plan
- Add test query for 3 connected vertices in edge_cases.pg
- Modified the documentation files
- Added example graph from boost
- Modify number of planned tests
What I got done?
- [] Attended this week's weekly meeting on 4/08/2025
- Add test query for 3 connected vertices in edge_cases.pg
- Modified the documentation files
- Added example graph from boost
- Modify number of planned tests
Pull requests:
Week 11
(August 11 - August 17)
Original Plan from Proposal
- Create usage tutorials and examples
- Final round of testing and bug fixing
Revised Plan
- Add result query in sloanOrdering.pg file
- Update ordering_driver.cpp to insert vertices in order of id
- Fix other configuration and build errors
- Update documentation of the function
What I got done?
- Add result query in
sloanOrdering.pgfile - Update ordering_driver.cpp to insert vertices in order of id
- Fix other configuration and build errors
- Update documentation of the function
Pull requests:
Week 12
(August 18 - August 24)
Original Plan from Proposal
- Prepare submission package
- Final polish
Revised Plan
- Add name in
doc/src/pgRouting-introduction.rstfile - Raise the final PR
- Ensure all the checks are passing
- Review and work on feedback
- Attend weekly meeting with mentors on 24/08/2025
What I got done?
- Add name in
doc/src/pgRouting-introduction.rstfile - Raise the final PR
- Ensure all the checks are passing
- Review and work on feedback
- Attend weekly meeting with mentors on 24/08/2025
Pull requests:
Issue link:
Log of Pull Requests
Link to all the Pull Requests made in GSoC-pgRouting repository
Final Report
Report Mail - OSGeo Discourse(https://discourse.osgeo.org/t/gsoc-2025-final-report-implementing-sloan-ordering-algorithm-to-pgrouting/149122)
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 (https://github.com/pgRouting/pgrouting/pull/2957).
- Intermediate pull requests: https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+is%3Aclosed+author%3Abipashabg
- Project Documentation (Wiki Page): https://github.com/pgRouting/pgrouting/wiki/GSoC-2025-Sloan-Ordering-Algorithm
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