GSoC 2022 Implement Cuthill Mckee Ordering Algorithm for pgRouting by the Boost Graph Library - pgRouting/pgrouting GitHub Wiki

Table of Contents

Proposal

Brief Description

Cuthill-Mckee Ordering 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 implemented in Boost Graph Library (BGL) as Boost::Cuthill-Mckee. 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 }.

I propose to add the above algorithm into pgRouting during the GSoC period.

State of the Project Before GSoC

As of now, Cuthill-Mckee is not implemented in pgRouting. Also, there is no single algorithm implemented in pgRouting from the Sparse Matrix Ordering section of Boost Graph Library. This algorithm will be the first one from this section.

Benefits to the Community

  • It is used to reduce the bandwidth of the graph which is a very useful process for solving the linear system of equations. It can be used to handle sparse matrices.

  • Adding this algorithm to pgRouting will result in more functionalities in pgRouting which will help the current and future users and developers to use and integrate it with other algorithms.

  • It is used to reduce the size needed to store the sparse matrix. Reordering a sparse matrix to reduce its bandwidth can speed up many sparse matrix computations

To provide users of pgRouting more functionality I am going to implement this algorithm from Boost Graph Library (BGL).

Deliverables

The deliverables for the proposal would be:

  • Implementation of pgr_CuthillMckeeOrdering( ) function.
  • SQL, C, C++ code related to the function with comments.
  • A wiki page for the project.
  • User documentation.
  • Example Query for the documentation.
  • Basic pgTap tests for the mentioned function.
  • Detailed report for each evaluation.

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor @dkastl Daniel Kastl
2nd Mentor @Veenits123 Veenit Kumar
Student Developer @shobhit162 Shobhit Chaurasia

Weekly Report and Plan

Community Bonding Period (May 20th - June 12th)

  • Introduce myself to the community, interact with my mentors, and learn more about pgRouting.
  • Setup the development environment.
  • Understand the coding style, generating documentation, and the interaction of pgRouting with other applications.
  • Set up a wiki page to keep track of weekly progress.
  • Learn more about PostGIS and PostgreSQL
  • Learn to create unit tests using pgTap.
  • Implement simple dummy functions to better understand pgRouting.

First Coding Period (June 13th - July 25th)

Week 1 (June 13th - June 19th)

  • Design pgr_CuthillMckeeOrdering() function.
  • Create a basic skeleton for documentation and tests.
  • Deeply study boost parameters and files.

Week 1 Report

Yes, due to my end semesters examination I was not able to complete my proposed work for week 1 but I will catch up on all my work in week 2. I already communicated regarding this and got the agreements from mentors.

Week 2 (June 20th - June 26th)

  • Create a basic skeleton for C, C++, SQL, and pgTap tests.
  • Go through the Boost related work in pgRouting for a better understanding and skills on the implementation.
  • Start creating the pgr_CuthillMckeeOrdering() function.

Week 2 Report

Week 3 (June 27th - July 03rd)

  • Read data from PostgreSQL.
  • Create C++ containers for passing SQL data to C++ containers for data processing.
  • Transfer data to C++ containers suitably for use with Cuthill-Mckee.

Week 3 Report

Week 4 (July 04th - July 10th)

  • Create the necessary class wrapper for the Boost function.
  • Process the data with the Boost Function.
  • Transform result to C containers suitable for executing with PostgreSQL queries.

Week 4 Report

Week 5 (July 11th - July 17th)

  • Create suitable queries using the sample data provided on pgRouting documentation.
  • Work on the submissions required as part of the first evaluation.

Week 5 Report

Week 6 (July 18th - July 24th)

  • Prepare user documentation.
  • Prepare a report for the first evaluation.

Week 6 Report

Second Coding Period (July 25th - September 04th)

Week 7 (July 25th - July 31st)

  • Work on the feedback as provided from the First Evaluation.
  • Learn to create pgTap tests.
  • Prepare Second Coding Period synopsis.
  • Prepare a basic outline and framework for the pgTap tests.

Week 7 Report

Week 8 (August 01st - August 07th)

  • Fix all the bugs/problems and documentation details.

Week 8 Report

Week 9 (August 08th - August 14th)

  • Write meaningful pgTap tests for the proposed function for all the edge cases and functionalities.

Week 9 Report

Week 10 (August 15th - August 21st)

  • Fix bugs of unit test.
  • Create queries for documentation using the pgRouting sample data.

Week 10 Report

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2022-August/004948.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-August/002305.html)

  • What did I get done this week?

    • Tried to generate correct results but failed.
    • Wrote the expected result in docqueries.
    • Made a PR with these changes (#254).

  • What do I plan on doing next week?

    • Complete all pgTap testing and docqueries.
    • Solve the error of not generating the correct output.

  • Am I blocked on anything?

    • I was busy with my placement activities and rest I also tried to identify the cause of not giving the correct output but it looks like I have to give more time to understand how boost is generating and giving output. I know I have only 2 weeks left but I will try my level best to complete my function in the upcoming 2 weeks dedicatedly.

Week 11 (August 22nd - August 28th)

  • Review, complete and finalize all the tests and documentation.
  • Integration to the development branch of the pgRouting repository.

Week 11 Report

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2022-August/004954.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-August/002313.html)

  • What did I get done this week?

    • Made my function only for version 3 i.e. without giving the starting vertex.
    • Added pgTap tests.
    • Made a PR with these changes (#255).

  • What do I plan on doing next week?

    • Some minor improvements.
    • Adding code comments, improving documentation and adding developers' documentation if possible.
    • Integration to the main branch if necessary.

  • Am I blocked on anything?

    • Version 1 i.e. giving the starting vertex in function was giving the wrong results, so I discussed it with my mentor and finally made my function for version 2 as it is more practical and better than version 1.

Week 12 (August 29th - September 04th)

  • Prepare final submission along with full documentation.
  • Create a detailed final report.

Week 12 Report

Log of Pull Requests

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

Pull Request Description Date Status
#2364 GSoC-2022: Experimental Function: cuthillMckeeOrdering Sep 07th, 2022 Opened
#262 GSoC-2022: All changes with stashing and git Sep 04th, 2022 Opened
#260 GSoC-2022: All changes without stashing Sep 04th, 2022 Closed
#258 GSoC-2022: Shobhit Chaurasia Week 12 Sep 04th, 2022 Merged
#255 GSoC-2022: Shobhit Chaurasia Week 11 Aug 28th, 2022 Merged
#254 GSoC-2022: Shobhit Chaurasia Week 10 Aug 21st, 2022 Merged
#250 GSoC-2022: Shobhit Chaurasia Week 9 Aug 14th, 2022 Merged
#249 GSoC-2022: Shobhit Chaurasia Week 8 Aug 07th, 2022 Merged
#244 GSoC-2022: Shobhit Chaurasia Week 7 July 31st, 2022 Merged
#234 GSoC-2022: Shobhit Chaurasia Week 6 July 24th, 2022 Merged
#232 GSoC-2022: Shobhit Chaurasia Week 5 July 17th, 2022 Merged
#226 GSoC-2022: Shobhit Chaurasia Week 4 July 10th, 2022 Merged
#222 GSoC-2022: Shobhit Chaurasia Week 3 July 3rd, 2022 Merged
#220 GSoC-2022: Shobhit Chaurasia Week 2 June 26th, 2022 Merged
#216 GSoC-2022: Shobhit Chaurasia Week 1 June 18th, 2022 Merged
#201 Task 2: Experience with GitHub & Git February 11th, 2022 GSoC Task Pull Request - Not to Merge

Slides

https://docs.google.com/presentation/d/1MlRfA0WbTF_YgRtkGNfRJkC1XiqByn1CjAcbOh4tPiA/edit?usp=sharing

https://docs.google.com/presentation/d/1QtAJ2sQFDNx5cmDoAoBXrHYmTwS7LiNozybHMHUd5yg/edit?usp=sharing

FOSS4G Presentation Slides

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

Final Report

Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2022-September/004965.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2022-September/002322.html) (sent to these two mailing lists of OSGeo).

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:

Blog: https://medium.com/@000shobhitchaurasia/being-a-part-of-the-google-summer-of-code-program-2022-f94f028543a7

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

Community Bonding Period (May 20th - June 12th)

Tasks

  • Request writing access to the OSGeo wiki, for editing all info related to my project.
  • Set up the development environment.
  • Interact with mentors, introduce myself to the community, and actively get involved in the discussion.
  • Set up a wiki page to keep track of weekly progress.
  • Add a wiki link to OSGeo's accepted student's wiki page.
  • Studied GSoC students guide and the OSGeo recommendations for students.
  • Introduce myself and my project on OSGeo's SOC and pgrouting-dev mailing list.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Develop a better understanding of PostgreSQL, PostGIS, Pl/pgSQL, and how they interact with pgRouting.
  • Created a public repository GSoC-pgRouting where all my works are reflected in the GSoC period.
  • Learned how and where to create Pull Request, merge and how to commit, etc.
  • Create a new branch named [shobhit-2022] in the GSoC-pgRouting repository, where I will be merging all the Pull Requests.

Meeting Discussions

  1. June 3rd

    • Introduction meeting with the mentors.
    • Basic Repository preparation of pgRouting.
    • Understood the files and structures of functions.

  2. June 22nd

    • Learned about code structures.
    • Learned about the work of different directories.
    • Learned about building commands and how to build new files.

  3. July 1st

    • Review of the PR.
    • Learned how to fix compilation errors.
    • Learned how to make docqueries.

  4. July 6th

    • Learned how to add example code in pgRouting.
    • Learned various developer techniques.

Pre-Bonding Period (March 07th - April 19th)

References

  1. https://github.com/pgRouting/pgrouting/tree/master
  2. https://github.com/pgRouting/pgrouting/tree/develop
  3. Graph Bandwidth https://en.wikipedia.org/wiki/Graph_bandwidth
  4. pgRouting queries on Stack Overflow https://stackoverflow.com/search?q=pgrouting
  5. pgRouting GSoC Ideas: 2022 https://github.com/pgRouting/pgrouting/wiki/GSoC-Ideas:-2022
  6. https://github.com/pgRouting/GSoC-pgRouting/wiki/Creating-a-GSoC-schedule
  7. pgRouting Workshop https://workshop.pgrouting.org/2.6/en/index.html
  8. https://docs.pgrouting.org/3.2/en/genindex.html pgRouting Documentation
  9. Google Summer of Code Recommendations for Students https://wiki.osgeo.org/wiki/Google_Summer_of_Code_Recommendations_for_Students
  10. https://www.openstreetmap.org/ OpenStreetMap
  11. https://docs.pgrouting.org/latest/en/sampledata.html
  12. https://docs.pgrouting.org/dev/en/genindex.html
  13. https://www.geeksforgeeks.org/reverse-cuthill-mckee-algorithm/
  14. https://www.researchgate.net/publication/238753649_Comparative_Analysis_of_the_Cuthill--McKee_and_the_Reverse_Cuthill--McKee_Ordering_Algorithms_for_Sparse_Matrices
  15. https://crd.lbl.gov/assets/Uploads/RCM-ipdps17.pdf
  16. https://www.boost.org/doc/libs/1_78_0/libs/graph/doc/sparse_matrix_ordering.html
  17. http://heath.cs.illinois.edu/courses/cs598mh/george_liu.pdf
  18. https://www.boost.org/doc/libs/1_80_0/libs/graph/doc/cuthill_mckee_ordering.html