GSoC 2025 Sloan Ordering Algorithm
The project aims to add the following algorithm to in pgRouting during GSoC 2024:
- 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.
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.
- 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 Link (Google Doc)
| 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 |
- 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
- 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.
- Review Boost Graph Library's sloan ordering algorithm
- Design data structures needed for pgr_sloanOrdering()
-
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
-
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:
- Implement core Sloan ordering algorithm logic
- Begin writing unit tests
- Fix naming of files.
- Fix the licenses.
- Fix compilation errors.
- Add include/ordering/sloanOrdering.hpp file.
- Update the CMakeLists.txt files.
- 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:
- Set up continuous integration framework
- Initial code review and mentor feedback
- Clear all compilation errors and warnings so far.
- Fix parameters and data types according to Boost implementation.
- 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:
- Refine Sloan ordering implementation
- Develop PostgreSQL integration methods
- 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
- 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:
- Create comprehensive test cases
- Begin performance optimization
- 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.
- 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:
- Implement error handling and edge cases
- Midpoint code review with mentors
- 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.
- 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:
- Implement weighted graph support
- Add advanced configuration options
- 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.
- 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:
- Develop detailed user and developer documentation
- Begin pgTAP test suite
- 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
- 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:
- Prepare integration examples
- Continue performance improvements
- 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
- 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:
- Final code optimization
- Comprehensive documentation review
- Create usage tutorials and examples
- Final round of testing and bug fixing
- Prepare submission package
- Final polish
Link to all the Pull Requests made in GSoC-pgRouting repository
| Pull Request | Description | Date | Status |
|---|---|---|---|
| https://github.com/pgRouting/GSoC-pgRouting/pull/440 | Add my name into doc/src/pgRouting-introduction.rst | 02-06-2025 | Closed |
| https://github.com/pgRouting/GSoC-pgRouting/pull/442 | GSoC 2025 Week-1 | 07-06-2025 | Closed and Merged |
| https://github.com/pgRouting/GSoC-pgRouting/pull/446 | GSoC 2025 Week-2 | 09-06-2025 | Closed and Merged |
| https://github.com/pgRouting/GSoC-pgRouting/pull/451 | GSoC 2025 Week-3 | 16-06-2025 | Closed and Merged |
| https://github.com/pgRouting/GSoC-pgRouting/pull/457 | GSoC 2025 Week-4 | 23-06-2025 | Closed and Merged |
| https://github.com/pgRouting/GSoC-pgRouting/pull/460 | GSoC 2025 Week-5 | 30-06-2025 | Closed and Merged |
| https://github.com/pgRouting/GSoC-pgRouting/pull/466 | GSoC 2025 Week-6 | 07-07-2025 | Closed and Merged |
| https://github.com/pgRouting/GSoC-pgRouting/pull/469 | GSoC 2025 Week-7 | 17-07-2025 | Closed and Merged |
| https://github.com/pgRouting/GSoC-pgRouting/pull/472 | GSoC 2025 Week-8 | 21-07-2025 | Closed and Merged |
| https://github.com/pgRouting/GSoC-pgRouting/pull/475 | GSoC 2025 Week-9 | 28-07-2025 | Closed and Merged |
TBD
Potential Future Work:
TBD
Links:
-
Pull Requests:
-
Final Pull Request: TBD
-
Intermediate pull requests: TBD
-
