Skip to content

GSoC 2022 Implement Cuthill Mckee Ordering Algorithm for pgRouting by the Boost Graph Library

Jump to bottom Edit New page
Shobhit Chaurasia edited this page Aug 28, 2022 · 46 revisions

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Created a branch in the GSoC-pgRouting repository.
    • Made a PR of adding my name to the contributor's list.

  • What do I plan on doing next week?

    • Catch up on my week 1 work.
    • Create a basic skeleton for documentation, C, C++, and SQL.
    • Start creating the pgr_CuthillMckeeOrdering() function.

  • Am I blocked on anything?

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Basic structuring of the src, SQL and include files.
    • Started working on the pgr_CuthillMckeeOrdering() function.
    • Learned about code checker and GitHub Action.
    • Made a PR with the basic structuring of the files (#220).

  • What do I plan on doing next week?

    • Modify the include and src files for array output.
    • Create the necessary class wrappers for the Boost function.
    • Basic structuring of doc and docqueries directory.
    • Transfer data to C++ containers suitably for use with Cuthill-Mckee.

  • Am I blocked on anything?

    • No, I don't have any issues.

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Basic structuring of the docqueries files.
    • Fixing compilation errors.
    • Adding c_type for ordering.
    • Adding include file for header
    • Made a PR with these changes (#222).

  • What do I plan on doing next week?

    • Improve the include and src files for Boost function.
    • Process the data with Boost function.
    • Solving any compilation errors and Github action errors.
    • Create the necessary class wrapper for the Boost function.

  • Am I blocked on anything?

    • No, I don't have any issues.

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Improved to the src and include files for boost function.
    • Getting results of Boost Example.
    • Solved the Graph data type error.
    • Added one more example query in docqueries.
    • Made a PR with these changes (#226).

  • What do I plan on doing next week?

    • Making the code work for real data.
    • Solving the warning errors.
    • Processing with queries.
    • Enhancing the functionalities.

  • Am I blocked on anything?

    • No, I don't have any issues.

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Added documentation.
    • Added boost example result.
    • Trying out code without Boost example
    • Performed necessary changes in some files
    • Made a PR with these changes (#232).

  • What do I plan on doing next week?

    • Improving documentation and solving its errors.
    • Try to run code without boost example.
    • Improving functionalities according to the proposal.

  • Am I blocked on anything?

    • I was stuck at PostgreSQL error and unable to run doc queries commands. I solved that error but it still have some warnings. I will try to solve it completely next week.

Week 6 (July 18th - July 24th)

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

Week 6 Report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Added ordering-family.rst
    • Improved documentation and solved link error
    • Added basic pgtap files structures
    • Started working on calling the function without boost example
    • Made a PR with these changes (#234).

  • What do I plan on doing next week?

    • To complete the task given by the mentor.
    • To improve pgtap test.
    • To adjust cpp code that calls boost function.
    • Save the result in the container and output the result.

  • Am I blocked on anything?

    • No

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Initial progress toward making hpp file for boost function
    • Learned some coding practices.
    • Made a PR with these changes (#244).

  • What do I plan on doing next week?

    • Try to solve all errors of include and driver files.
    • Do some pgTap test
    • Output the result in the database.

  • Am I blocked on anything?

    • I was stuck on how to make changes according to to the boost function keeping in mind the coding practice and previous code used in pgRouting. I will continue to learn concepts and try to solve all errors in week 8

Week 8 (August 01st - August 07th)

  • Fix all the bugs/problems and documentation details.

Week 8 Report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Tried making the function work without creating a separate graph type but failed
    • Added no_crash_test.pg
    • Made a PR with these changes (#249).

  • What do I plan on doing next week?

    • Final approach for .hpp and driver files for making it boost compatible.
    • Complete all pgTap testing.
    • Complete all the logical and time taking work next week.

  • Am I blocked on anything?

    • Nothing major, this week I was busy with some other stuff.

Week 9 (August 08th - August 14th)

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

Week 9 Report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Finally made the function work with all required parameters and identified graph type error.
    • Made a PR with these changes (#250).

  • 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 stuck on how to make hpp and driver files compatible for boost function and I had to dig deeper to solve it. Hence, it consumed much more time than I expected. I will try to complete all the remaining work at a fast pace.

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], [pgrouting-dev]

  • 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], [pgrouting-dev]

  • 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 (#254).

  • 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 mentor and finally made my function for version 3 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.

Log of Pull Requests

Pull Request Description Date Status
#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

Final Report

  • Will be added at the end of the second coding period

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

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally