Skip to content

GSoC 2025 King Ordering Algorithm and Minimum Degree Ordering Algorithm

Jump to bottom Edit New page
wifi edited this page Aug 28, 2025 · 37 revisions

Table of Contents

Proposal

Brief Description

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.

State of the Project Before GSoC

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.

Deliverables

  • 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

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 @wifi Fan Wu

Timeline

Community Bonding Period

  • 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.

Week -1 & Week 0

  • 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

First Coding Period

Week 1

  • 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

Week 2

  • 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.

  • 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

Week 3

  • 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

Week 4

  • 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

Week 5

  • 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

Week 6

  • What I got done this week?

    • Updated function signatures in both C and C++ ordering-related files:
      • Replaced C-style const char* with std::string.
    • Changed the return type of kingOrdering to std::vector<int64_t> and integrated Boost king ordering logic.
    • Added blank line separation after memory context switches in kingOrdering.c and minDegreeOrdering.c for clarity.

  • What I plan on doing next week?

    • Continue the implementation of minDegreeOrdering with Boost and unify its interface with kingOrdering.
    • Write pgTap tests to validate the new argument handling and return behavior.
    • Begin to write documentation and usage examples.

  • Am I blocked on anything?

    No

  • Links

Second Coding Period

Week 7

  • What I got done this week?

    • Refactored kingOrdering and minDegreeOrdering to improve type safety and memory handling.
      • Updated their return types and replaced raw pointers with modern C++ types (std::vector<int64_t>).
    • Activated previously disabled logic in ordering_driver.cpp for algorithm selection and output checks.
    • Added a new SQL test file (docqueries/ordering/kingOrdering.pg) to create and populate the kot test table (initial version; pending minor syntax fixes).

  • What I plan on doing next week?

    • Finalize and correct the SQL in kingOrdering.pg.
    • Continue integrating minDegreeOrdering with Boost backend.
    • Expand pgTap test coverage for both algorithms.

  • Am I blocked on anything?

    No

  • Links

Week 8

  • What I got done this week?

    • Refined output mapping of kingOrdering and minDegreeOrdering to return vertex IDs instead of internal indices.
    • Replaced exception-based error handling with PostgreSQL-compatible NOTICE messages and safe early returns in the driver.
    • Finalized and corrected SQL test file docqueries/ordering/kingOrdering.pg, removing incorrect table setup logic.
    • Added comprehensive pgTAP test coverage:
      • Crash-resilience and edge case tests for both ordering algorithms.
      • Inner query tests with conditional execution based on PostgreSQL version.
    • Ensured both algorithms now return valid, testable outputs in SQL and PL/pgSQL contexts.

  • What I Plan on doing next week?

    • Continue improving the inner_query part in pgTap and enhance test coverage.
    • Start writing documentation for both pgr_kingOrdering and pgr_minDegreeOrdering.

  • Am I Blocked on anything?

    No

  • Links

Week 9

  • What I got done this week?

    • Completed documentation for pgr_kingOrdering and pgr_minDegreeOrdering:
      • Added .rst files for both functions.
      • Updated ordering-family.rst and added marker directives to pgr_cuthillMckeeOrdering.rst.
      • Registered new documentation in CMakeLists.txt and docqueries.
    • Added and enhanced pgTAP test coverage:
      • Crash-resilience and edge case tests for both algorithms.
      • Added inner_query tests with PostgreSQL version conditionals.
    • Cleaned up and corrected SQL test files:
      • Removed incorrect table setup code from kingOrdering.pg.
      • Ensured both algorithms now return valid, testable outputs in SQL and PL/pgSQL contexts.
    • Removed obsolete C/C++ driver header files:
      • Deleted kingOrdering_driver.h and minimumDegreeOrdering_driver.h.

  • What I plan on doing next week?

    • Continue refining the documentation for both pgr_kingOrdering and pgr_minDegreeOrdering.
    • Investigate and fix the crash issue caused by 1-vertex and 2-vertices pgTAP tests in minDegreeOrdering.
    • Continue debugging the inconsistent outputs issue when running the same graph input multiple times.

  • Am I Blocked on anything?

    No

  • Links

Week 10

  • What I got done this week?

    • Expanded documentation for pgr_kingOrdering and pgr_minDegreeOrdering:
      • Added detailed descriptions, algorithm characteristics, and complexity notes.
      • Included example queries with sample data and expected results.
      • Added Graphviz diagrams to illustrate execution flow.
    • Internally refactored ordering algorithm implementation:
      • Unified internal types to match G::V for consistency.
      • Made degree precomputation explicit for clarity.

  • What I Plan on doing next week?

    • Continue refining documentation for both pgr_kingOrdering and pgr_minDegreeOrdering.
    • Enhance and extend test coverage for both algorithms.
    • Resolve issue with pgr_minDegreeOrdering not handling directed graph inputs.

  • Am I Blocked on anything?
    No

  • Links

Week 11

  • What I got done this week?

    • Expanded documentation for pgr_kingOrdering and pgr_minDegreeOrdering:
      • Added dedicated .rst files with detailed descriptions, usage examples, and expected results.
      • Updated ordering-family.rst and integrated into CMake and docqueries.
    • Extended test coverage for both functions:
      • Added new pgTAP tests for edge cases, crash-resilience, and PostgreSQL version–specific queries.
      • Cleaned and corrected SQL test files to ensure stable and verifiable outputs.
    • Refactored internal implementation of ordering algorithms:
      • Improved type consistency, code readability, and maintainability.

  • What I Plan on doing next week?

    • Continue refining documentation for both pgr_kingOrdering and pgr_minDegreeOrdering.
    • Organize and clean up commits in preparation.
    • Open a final consolidated PR to the main pgRouting repository.

  • Am I Blocked on anything?

    No

  • Links

Week 12

  • What I got done this week?

    • Raise the final PR in pgRouting/pgrouting repo.
    • Added my name to introduction.rst.
    • Review and work on feedback

  • What I Plan on doing next week?

    • Complete the final report

  • Am I Blocked on anything?

    No

  • Links

Log of Pull Requests

Pull Request Description Date Status
# 435 GSoC 2025 Week 0 May 27 Merged
# 444 GSoC 2025 Week 1 Jun 8 Merged
# 449 GSoC 2025 Week 2 Jun 15 Merged
# 452 GSoC 2025 Week 3 Jun 22 Merged
# 459 GSoC 2025 Week 4 Jun 29 Merged
# 461 GSoC 2025 Week 5 Jul 6 Merged
# 464 GSoC 2025 Week 6 Jul 13 Merged
# 467 GSoC 2025 Week 7 Jul 20 Merged
# 471 GSoC 2025 Week 8 Jul 27 Merged
# 476 GSoC 2025 Week 9 Aug 3 Merged
# 477 GSoC 2025 Week 10 Aug 10 Merged
# 480 GSoC 2025 Week 11 Aug 17 Merged
# 484 GSoC 2025 Week 12 Aug 24 Merged

Final Report

Hello everyone,

As GSoC 2025 is coming to a close, I am pleased to share my final report on the work accomplished over the past three months. This journey has been a truly rewarding experience, during which I not only learned a great deal about software engineering and open-source collaboration, but also had the privilege of working closely with the pgRouting community and my mentors.

Title: Implementing King Ordering Algorithm and Minimum Degree Ordering Algorithm for pgRouting

Organization: pgRouting under the umbrella of OSGeo

Abstract:

The aim of this project was to integrate two graph reordering algorithms—King Ordering and Minimum Degree Ordering—from the Boost Graph Library into pgRouting. These algorithms are important for optimizing matrix computations and improving the efficiency of numerical solvers in scientific computing and network analysis.

  • King Ordering Algorithm reduces graph bandwidth by reordering vertex indices to minimize adjacency gaps. It is based on a breadth-first search strategy, where vertices are selected according to pseudo-degree (the number of unvisited neighbors), and is particularly useful for reducing the complexity of solving sparse linear systems.

  • Minimum Degree Ordering Algorithm is a heuristic designed to minimize fill-in during Cholesky factorization of sparse matrices. By reordering rows to reduce nonzero elements introduced during Gaussian elimination, it achieves more efficient storage and computation. The algorithm relies on local degree-based heuristics to approximate an optimal ordering.

State of the Project Before GSoC:

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.

State of the Project After GSoC:

For pgr_kingOrdering, the work has been fully completed. The deliverables include the code implementation, detailed documentation, documentation tests, and pgTAP tests. The function is stable and ready to be used within pgRouting.

For pgr_minDegreeOrdering, the required deliverables have also been completed, including the code, documentation, documentation tests, and pgTAP tests. However, due to the underlying Boost implementation not being fully functional, the function may encounter infinite cycling in certain cases. Further debugging and fixes on the Boost side are needed before the function can be considered fully stable.

Overall, the project has successfully delivered a new fully functional ordering algorithm and prepared the foundation for another, with the remaining work focused on stabilizing the Boost implementation of pgr_minDegreeOrdering.

Potential Future Work:

  • Provide more extensive test cases for pgr_kingOrdering and pgr_minDegreeOrdering to promote them from experimental to proposed status.

  • Design large-scale performance benchmarks to evaluate the efficiency of both algorithms under diverse graph structures and data sizes.

  • Investigate incorporating additional reordering algorithms from the Boost Graph Library to further broaden pgRouting’s set of preprocessing tools.

Links:

Acknowledgments:

I am deeply grateful to my mentors and the pgRouting community for their constant guidance, encouragement, and patience throughout this project. Their support has been instrumental not only in completing my tasks, but also in helping me grow as a developer.

Participating in GSoC under the OSGeo umbrella has been a transformative experience—it has strengthened my confidence in contributing to open-source software and inspired me to stay engaged with this community in the future. I hope the work I have done will prove valuable to pgRouting, and I look forward to continuing to contribute and learn in the open-source world.

Thanks once again to everyone who made this journey meaningful!

Best regards,

Fan Wu

Pre-Bonding Period (February 27 - April 8)

References

  1. Boost king_ordering
  2. Boost minimum_degree_ordering
  3. Wikipedia: Minimum degree algorithm
  4. Sparse Matrix Reordering Algorithms for Cluster Identification

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally