GSoC 2025 King Ordering Algorithm and Minimum Degree Ordering Algorithm - pgRouting/pgrouting GitHub Wiki
This project aims to implement the King Ordering Algorithm and Minimum Degree Ordering Algorithm from the Boost Graph Library into pgRouting, expanding its graph reordering capabilities beyond the existing Cuthill-McKee ordering. These algorithms optimize graph structures for improved numerical solver performance in scientific computing and network analysis. The King Ordering Algorithm minimizes graph bandwidth by reordering vertex indices based on pseudo-degree, reducing adjacency gaps and enhancing sparse matrix computations. The Minimum Degree Ordering Algorithm reduces fill-in during Cholesky factorization by reordering matrix rows to minimize nonzero elements introduced during Gaussian elimination. By integrating these algorithms, pgRouting will offer more efficient preprocessing options, benefiting large-scale network analysis and pathfinding tasks. Deliverables include the implementation of pgr_kingOrdering() and pgr_minimumDegreeOrdering(), comprehensive documentation, test cases ensuring correctness, and regular progress updates.
Before this project, pgRouting did not support the King Ordering or Minimum Degree Ordering algorithms. The only implemented graph reordering algorithm available was the Cuthill-McKee ordering. Adding these new algorithms will expand pgRouting's capabilities for graph preprocessing and optimization.
- Implementation of pgr_kingOrdering() and pgr_minimumDegreeOrdering() functions.
- Code with detailed and essential comments following the style guide and best practices.
- User documentation for both functions.
- Basic pgTap test cases to ensure correctness and stability.
- A wiki page detailing weekly progress.
- Detailed reports for the first and final evaluations.
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 | @wifi | Fan Wu |
- Introduce myself to the pgRouting mentors and the broader community to begin building connections.
- Set up and configure the development environment required for contributing to pgRouting.
- Explore and understand the pgRouting codebase, development workflow, and best practices.
- Study pgTap and the Boost Graph Library to prepare for effective development and testing.
- Create and regularly update a personal wiki page to document weekly project progress.
- Actively participate in community meetings, discussions, and forums to stay engaged and informed.
- Deepen my understanding of PostgreSQL and PostGIS to support development and integration tasks.
-
What I got done this week?
- Finished up cleaning up the Wiki template and started filling in the relevant fields.
- Finished filling up the OSGeos wiki for OSGeo-GSoC 2025.
- Attended introductory meeting on May 19.
- Set up local dev environment.
-
What I Plan on doing next week?
- Finish up and streamline the wiki and weekly reports.
- Go through and study BGL documentation for king ordering algorithm and minimum degree ordering algorithm.
- Go through pgRouting docs.
- Start planning how to implement pgr_kingOrdering() & pgr_minimumDegreeOrdering and the work for the coding period starting from next week.
- Create my own branch (from develop/upstream)
- Plan out how to structure my weeks and daily routine to meet the Mid-Term Evaluation deliverables
-
Am I Blocked on anything?
No
-
What I got done this week?
- Completed tasks planned last week, including studying BGL and pgRouting documentation.
- Finalized the wiki and weekly report setup.
- Planned the initial implementation structure for pgr_kingOrdering() and pgr_minimumDegreeOrdering().
- Opened a pull request with the following contributions:
- Added my name to doc/src/pgRouting-introduction.rst.
- Built the basic structure for King Ordering and Minimum Degree Ordering algorithms:
- include/drivers/ordering/kingOrdering_driver.h
- include/drivers/ordering/minimumDegreeOrdering_driver.h
- include/ordering/kingOrdering.hpp
- include/ordering/minimumDegreeOrdering.hpp
- sql/ordering/_kingOrdering.sql
- sql/ordering/_minimumDegreeOrdering.sql
- sql/ordering/kingOrdering.sql
- sql/ordering/minimumDegreeOrdering.sql
- src/ordering/kingOrdering.c
- src/ordering/minimumDegreeOrdering.c
- src/ordering/ordering_driver.cpp
- Updated corresponding CMakeLists.txt in sql/ordering/ and src/ordering/
-
What I Plan on doing next week?
- Set up a testing framework using pgTap for both algorithms.
- Document usage and examples.
- Continue refining the wiki and weekly planning.
-
Am I Blocked on anything?
No
-
Links
-
What I got done this week?
- Added new core driver and process interfaces.
- include/drivers/ordering/ordering_driver.hpp – defines unified driver function signature.
- include/ordering/ordering_process.h – defines C-compatible processing interface.
- src/ordering/ordering_process.cpp – implements the shared processing logic for all ordering algorithms.
- Added run.sh script with my macOS system compatibility to automate build and testing steps.
- Temporarily adjusted CMakeLists.txt to comment out incomplete SQL and C files for smooth building.
- Added new core driver and process interfaces.
-
What I Plan on doing next week?
- Continue completing C implementation for King and Minimum Degree Ordering.
- Set up unit testing using pgTap.
- Add initial documentation and examples for both algorithms.
-
Am I Blocked on anything?
No
-
Links
-
What I got done this week?
- Refactored function parameters and renamed variables for consistency.
- Reached a stable, compilable state.
- Updated basic structure for pgr_kingOrdering & pgr_minDegreeOrdering to prepare for future development.
- Updated driver and include files to integrate both ordering functions.
- Cleaned up unused or outdated code.
- Created initial test file framework for both algorithms to facilitate testing setup.
-
What I Plan on doing next week?
- Continue pgr_kingOrdering & pgr_minDegreeOrdering deeper implementation.
- Expand and run pgTap test cases for both ordering methods.
- Start working on SQL interface and documentation updates.
-
Am I Blocked on anything?
No
-
Links
-
What I got done this week?
- Added pgTap scripts to check function existence and argument signatures.
- Implemented version-aware logic to conditionally run tests for PostgreSQL ≥ 4.0.0.
- Verified function headers and ensured argument types are correctly defined.
- Reached a clean, testable state for the SQL interfaces of both ordering functions.
-
What I plan on doing next week?
- Remove unnecessary comments in ordering_driver.cpp.
- Refactor misplaced logic in the driver file.
- Replace II_r_t with standard int64_t and fix related usages.
- Remove redundant includes in kingOrdering.c.
- Review and simplify the C implementation of pgr_kingOrdering.
-
Am I blocked on anything?
No
-
Links
-
What I got done this week?
- Replaced all usage of the custom II_t_rt data structure with standard int64_t types across the codebase.
- Refactored ordering function interfaces to return std::vector<std::vector<int64_t>> instead of custom types.
- Reduced SQL output columns from 3 to 2 and updated corresponding C function definitions.
- Adjusted function signatures and removed legacy structures.
- Cleaned up pgTap test files to reflect the updated function return structure.
-
What I plan on doing next week?
- Implement kingOrdering and minDegreeOrdering functionality in ordering.hpp.
- Add additional pgTap test cases.
- Continue improving test coverage for kingOrdering and minDegreeOrdering.
-
Am I blocked on anything?
No
-
Links
TBD
TBD
TBD
TBD
TBD
TBD
TBD
| Pull Request | Description | Date | Status |
|---|---|---|---|
| # 435 | GSoC 2025 Week 0 | May 27 | Closed |
| # 444 | GSoC 2025 Week 1 | Jun 8 | Closed |
| # 449 | GSoC 2025 Week 2 | Jun 15 | Closed |
| # 452 | GSoC 2025 Week 3 | Jun 22 | Closed |
| # 459 | GSoC 2025 Week 4 | Jun 29 | Closed |
| # 461 | GSoC 2025 Week 5 | Jul 6 | Closed |
TBD
- Links:
(i) Code Documentation:
TBD
(ii) Tags:
TBD
(iii) Pull Requests:
TBD
(iv) Wiki Pages:
TBD
- Images:
TBD
- Media:
TBD