GSoC 2025 Final Report: King Ordering Algorithm and Minimum Degree Ordering Algorithm

Initiatives Google Summer of Code
1

GSoC 2025 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! :cowboy_hat_face:

Best regards,
Fan Wu