[pgrouting-dev] GSoC 2022 - Final Report: Implement Cuthill-Mckee Ordering Algorithm for pgRouting by the Boost Graph Library

pgRouting pgrouting-dev
1

Hello everyone,

With GSoC coming to an end, I hereby present my final report of the work I have done over the past three months. It has been an amazing experience and great learning, working with the pgRouting community and mentors. This report follows the guidelines set by Google and OSGeo GSoC Admins.

Title: Implement Cuthill-Mckee Ordering Algorithm for pgRouting by the Boost Graph Library

Organisation: pgRouting under OSGeo

Abstract: This GSoC project dealt with the implementation of one new Graph algorithm in pgRouting. The algorithm is described below:

  • Cuthill-Mckee Ordering: It is an algorithm used to reduce the bandwidth of a graph by reordering the indices assigned to each vertex. The vertices are basically assigned a breadth-first search order, except that at each step, the adjacent vertices are placed in the queue in order of increasing degree. This algorithm is from the class of Sparse Matrix Ordering of Boost Graph Library.

It is used in a linear system of equations, can be used to reduce the size needed to store the sparse matrix, improve the usage of distributed memory, enhance data locality, in constraint satisfaction problems, etc. It is implemented in Boost Graph Library (BGL) as boost::cuthill_mckee_ordering. It is applicable for undirected graphs. It has a time complexity of O(m log(m)|V|) where m = max { degree(v) | v in V }.

State of the Project Before GSoC: pgRouting currently does not have this algorithm implemented. A single standard function does not exist for this ordering algorithm. This algorithm will be the first one from the Sparse Matrix Ordering family.

The addition that my project brought to pgRouting: The deliverables are code, documentation, documentation tests, and the pgTAP tests of the function.

Potential Future Work:

  • The implementation of Cuthill-Mckee Ordering completes one algorithm out of five algorithms of the Boost Graph Library in pgRouting. In future, we can implement King Ordering, Sloan Ordering, Minimum Degree Ordering, etc.

Cuthill-Mckee Ordering has 3 versions defined in the Boost Graph Library. I have implemented the most practical version which is version 2. There are still left version 1 and version 3. If I will get time then I will definitely implement version 1 myself. It basically lets the user choose the starting vertex i.e. we have to give the starting vertex in the query of the Cuthill-Mckee ordering function. Whereas, version 2 finds the starting vertex itself.

Links:

Images:

Media:

I am so glad to be a part of the amazing GSoC and OSGeo communities. I have learned a lot during this period and I am sure that it will help me in my future development journey. I would be happy if my code proves beneficial to the community. Last but not the least, thank you everyone for the support!

Thanks and Regards,

Shobhit Chaurasia