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

[shobhit chaurasia]

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
<https://developers.google.com/open-source/gsoc/help/work-product> and OSGeo
GSoC Admins
<https://lists.osgeo.org/pipermail/soc/2022-September/004962.html>.

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
<https://www.boost.org/doc/libs/1_78_0/libs/graph/doc/cuthill_mckee_ordering.html>.
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:

   -

   Tags:
   - Cuthill-Mckee Ordering
      (2022-shobhit162-cuthillMckeeOrdering-function):
      https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2022-shobhit162-cuthillMckeeOrdering-function
   -

   Pull Requests:
   -

      Final Pull Request: (#2364)
      <https://github.com/pgRouting/pgrouting/pull/2364> Experimental
      Function - cuthillMckeeOrdering (
      https://github.com/pgRouting/pgrouting/pull/2364).
      -

      Intermediate pull requests:
      https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Ashobhit162
      -

   Project Documentation (Wiki Page):
   https://github.com/pgRouting/pgrouting/wiki/GSoC-2022-Implement-Cuthill-Mckee-Ordering-Algorithm-for-pgRouting-by-the-Boost-Graph-Library

Images:

   - cuthillMckeeOrdering:
   https://drive.google.com/file/d/1MwY9RagANABOTdctxyOxAKu3n7c7T7Ie/view?usp=sharing

Media:

   - Slide Demonstration:
   https://docs.google.com/presentation/d/1zaQNMn-A8hT8l-9tK0krTOzF8JADkCtzVN_oSNfoRFo/edit?usp=sharing

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20220911/3dab85e9/attachment.htm>