Skip to content

GSoC 2025 King Ordering Algorithm and Minimum Degree Ordering Algorithm

Jump to bottom Edit New page
wifi edited this page Aug 12, 2025 · 32 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

TBD

Week 12

TBD

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

Final Report

TBD

  1. Links:

(i) Code Documentation:

TBD

(ii) Tags:

TBD

(iii) Pull Requests:

TBD

(iv) Wiki Pages:

TBD

  1. Images:

TBD

  1. Media:

TBD

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