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 Jul 24, 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 - August 01st)

  • 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 8 (August 02nd - August 08th)

  • Fix all the bugs/problems and documentation details.

Week 9 (August 09th - August 15th)

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

Week 10 (August 16th - August 22nd)

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

Week 11 (August 23rd - August 29th)

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

Week 12 (August 30th - September 04th)

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

Log of Pull Requests

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