GSoC 2025 King Ordering Algorithm and Minimum Degree Ordering Algorithm

Table of Contents

• Proposal
  • Brief Description
  • State of the Project Before GSoC
  • Deliverables
  • Detailed Proposal
• Participants
• Timeline
  • Community Bonding Period
    • [Week -1 & Week 0](#Week -1 & Week 0)
  • First Coding Period
    • Week 1
    • Week 2
    • Week 3
    • Week 4
  • Second Coding Period
    • Week 5
    • Week 6
    • Week 7
    • Week 8
  • Third Coding Period
    • Week 9
    • Week 10
    • Week 11
    • Week 12
• Log of Pull Requests
• Slides
• Final Report
• Weekly Reports
  • Third Evaluation Period
    • Week 12
    • Week 11
    • Week 10
    • Week 9
  • Second Evaluation Period
    • Week 8
    • Week 7
    • Week 6
    • Week 5
  • First Evaluation Period
    • Week 4
    • Week 3
    • Week 2
    • Week 1
  • Community Bonding Period
    • [Week -1 & Week 0](#Week -1 & Week 0)
    • Meeting Discussions
    • Tasks
  • Pre-Bonding Period
• References

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

• Reach out to pgRouting mentors and community members to introduce myself and begin building rapport.
• Install and configure all necessary tools to establish a functional development environment for pgRouting.
• Create a wiki page to document and track the weekly progress of my project.

First Coding Period

Week 1

TBD

Week 2

TBD

Week 3

TBD

Week 4

TBD

Second Coding Period

Week 5

TBD

Week 6

TBD

Week 7

TBD

Week 8

TBD

Third Coding Period

Week 9

TBD

Week 10

TBD

Week 11

TBD

Week 12

TBD

Log of Pull Requests

Link to all the Pull Requests made in GSoC-pgRouting repository

Pull Request	Description	Date	Status
# 1604	TBD	TBD	TBD

Slides

TBD

Final Report

TBD

6. Links:

(i) Code Documentation:

TBD

(ii) Tags:

TBD

(iii) Pull Requests:

TBD

(iv) Wiki Pages:

TBD

7. Images:

TBD

8. Media:

TBD

Weekly Reports

Third Evaluation Period

Week 12

• Report Mail - TBD

• What did I get done this week?

TBD

• What do I plan on doing next week? TBD

Week 11

TBD

Week 10

Week 9

Week 8

Week 7

Week 6

Week 5

First Evaluation Period

Week 4

Week 3

Week 2

Week 1

Community Bonding Period

Week 0

Week -1

• 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

Pre-Bonding Period (February 27 - April 8)

• Task 1: Intent of application
• Task 2: Experience with GitHub & Git
• Task 3: Build locally pgRouting
• Task 4: Get familiar with C++
• Task 5: Get familiar with pgRouting

References

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