Skip to content

GSoC 2021 Implement Edge Coloring Algorithm for pgRouting by the Boost Graph Library

Jump to bottom Edit New page
Veenit Kumar edited this page Aug 17, 2021 · 41 revisions

Table of Contents

Proposal

Brief Description

Edge Coloring is an algorithm used for coloring of the edges for the vertices in the graph. It is an assignment of colors to the edges of the graph so that no two adjacent edges have the same color.

If edges are ordered as e1, e2, ..., en it assigns colors c1, c2, ..., cn in such a way that no vertex connects with 2 edges of the same color.

It is used in several representations of real-world systems like traffic signalling, bi-processors, fiber-optic communication, etc. It can also tell us if a graph is Bipartite. It is implemented in Boost Graph Library (BGL) as Boost::Edge Coloring. It is applicable for undirected and loop-free (i.e no self-loops and no parallel edges) graph. It has a polynomial-time complexity of O(|E| |V|).

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

State of the Project Before GSoC

pgRouting currently does not have the proposed algorithm implemented.

Edge Coloring is not implemented before in pgRouting. The Sequential Vertex Coloring has been implemented in pgRouting during the GSoC 2020 period by Ashish Kumar. However, a single standard function does not exist for this coloring algorithm, besides it has various other applications apart from checking if a graph is Bipartite. Also, it helps complete the coloring algorithms part of the Boost Graph Library in pgRouting.

Benefits to the Community

  • Adding Boost::Edge Coloring algorithm to pgRouting adds more functionality to it and helps future users and developers to use and integrate it with other routing algorithms. It allows access to the algorithm with a single function. It has applications in traffic signalling, scheduling problems, processors and in frequency assignment for fiber optic networks.

  • One of the benefits is, it can tell us whether a graph is Bipartite or not. If in a graph (G), the chromatic number χ′(G) i.e. minimum number of colors needed for proper edge coloring of G is equal to degree Δ(G) (largest number of edges incident to any single vertex) of the graph, (i.e. χ′(G) = Δ(G)) then G is said to be Bipartite.

  • One of the most useful real-world benefits is in fiber-optic communication, the Edge Coloring algorithm is the problem of assigning colors (frequencies of light) to pairs of nodes (edges) that wish to communicate with each other, and paths through a fiber-optic communications network for each pair, subject to the restriction that no two paths that share a segment of fiber use the same frequency (color) as each other.

To provide users of pgRouting more functionality I am going to implement this algorithm from Boost Graph Library (BGL). As due to new changes in GSoC this year the time has been reduced but if the time permits I intend to create lots of tests and implement more applications. All these algorithms and applications are helpful for future developers, users and development of pgRouting as a whole.

Deliverables

The deliverables for the proposal would be:

  • Implementation of pgr_edgeColoring().
  • SQL, C, C++ code related to the function.
  • A wiki page for the project.
  • User documentation.
  • Example Query for the documentation.
  • Basic pgTap tests.
  • Report for evaluations.

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor @dkastl Daniel Kastl
2nd Mentor @ashrafroni Ashraf Hossain
3rd Mentor @rahulworld Rahul Chauhan
Student Developer @Veenits123 Veenit Kumar

Timeline

Community Bonding Period (May 17th - June 6th)

  • Set up the development environment.
  • Interact with mentors, introduce myself to the community, and actively get involved in the discussion.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Set up a wiki page to keep track of weekly progress.
  • Develop a better understanding of PostgreSQL, PostGIS, Pl/pgSQL, and how they interact with pgRouting.
  • Learn to create unit tests using pgTap.
  • Implement simple dummy functions to better understand pgRouting.

First Coding Period (June 7th - July 11th)

Week 1 (June 7th - June 13th)

  • Design pgr_edgeColoring() function.
  • Create a basic skeleton for documentation and tests.
  • Create code skeleton of SQL and C code which allows the C++ implementation of the function to work with PostgreSQL.

Week 2 (June 14th - June 20th)

  • Design the detailed signature for the pgr_edgeColoring() function.
  • Go through the Boost related work in pgRouting for a better understanding and skills on the implementation.
  • Implement pgr_edgeColoring() function along with its helper files.

Week 3 (June 21st - June 27th)

  • Read data from PostgreSQL.
  • Transfer data to C++ containers suitable for use with Boost Graph Library.

Week 4 (June 28th - July 4th)

  • 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 5 (July 5th - July 11th)

  • Prepare user documentation.
  • Create suitable queries using the sample data provided on pgRouting documentation.
  • Work on the submissions required as part of the first evaluation.
  • Prepare the First Coding Period report.

Second Coding Period (July 12th - August 16th)

Week 6 (July 12th - July 18th)

  • Work on the feedback as provided from the First Evaluation.
  • Finalize the above coding part (if remaining) to get an overall solution.
  • Prepare Second Coding Period synopsis.
  • Prepare a basic outline and framework for the pgTap tests.

Week 7 (July 19th - July 25th)

  • Create units and internal tests for the pgr_edgeColoring() function.
    • Create pgTap tests to check no server crash.
    • Create pgTap unit tests for expected results for different small graphs:
      • One vertex graph.
      • One edge graph.
      • Two edge graph.
      • Cyclic graph with 3 edges.
    • Test all the critical edge cases.
  • Fix bugs if found (any).

Week 8 (July 26th - August 1st)

  • Fix all the bugs and documentation details.
  • Review, complete and finalize all the tests and documentation for all the functions implemented.

Week 9 (August 2nd - August 8th)

  • Integration to the develop branch in the main repository of pgRouting.

Week 10 (August 9th - August 15th)

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

Log of Pull Requests

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

Pull Request Description Date Status
#2084 [GSoC-2021] Updating pgr_edgeColoring Doc August 13th, 2021 Merged
#2061 [GSoC-2021] Experimental Function - pgr_edgeColoring August 11th, 2021 Merged
#188 GSoC-2021 Week9: pgr_edgeColoring August 6th, 2021 Merged
#186 GSoC-2021 Week8: pgr_edgeColoring August 2nd, 2021 Merged
#184 GSoC-2021 Week7: pgr_edgeColoring July 24th, 2021 Merged
#182 GSoC-2021 Week6: pgr_edgeColoring July 19th, 2021 Merged
#179 GSoC-2021 Week5: pgr_edgeColoring July 11th, 2021 Merged
#176 GSoC-2021 Week4: pgr_edgeColoring July 04th, 2021 Merged
#173 GSoC-2021 Week3: pgr_edgeColoring June 27th, 2021 Merged
#171 GSoC-2021 Week2: pgr_edgeColoring June 19th, 2021 Merged
#169 GSoC-2021 Week1: pgr_edgeColoring June 12th, 2021 Merged
#142 Task 2: Experience with GitHub & Git February 9th, 2021 GSoC Task Pull Request - Not to Merge

Slides

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

Final Report

Report Mail - [SoC], [pgrouting-dev] (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 two and half months. It has been an awesome experience and great learning, working with the pgRouting community and mentors. This report is following the guidelines set by Google and OSGeo GSoC Admins.

Title: Implement Edge Coloring 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:

  • Edge Coloring: It is an algorithm used for coloring the edges for the vertices in the graph. It is an assignment of colors to the edges of the graph so that no two adjacent edges have the same color. If edges are ordered as e1, e2, ..., en it assigns colors c1, c2, ..., cn in such a way that no vertex connects with 2 edges of the same color. It is used in several representations of real-world systems like traffic signaling, bi-processors, fiber-optic communication, etc. It can also tell us if a graph is Bipartite. It is implemented in Boost Graph Library (BGL) as boost::edge_coloring . It is applicable for undirected and loop-free (i.e no self-loops and no parallel edges) graphs. It has a polynomial-time complexity of O(|E| |V|).

State of the Project Before GSoC: pgRouting currently does not have this algorithm implemented. A single standard function does not exist for this coloring algorithm.

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

  • Edge Coloring (pgr_edgeColoring) can be used to check whether a graph is Bipartite or not. If in a graph (G), the chromatic number χ′(G) i.e. the minimum number of colors needed for proper edge coloring of G is equal to degree Δ(G) (largest number of edges incident to any single vertex) of the graph, (i.e. χ′(G) = Δ(G)) then G is said to be Bipartite.

Potential Future Work:

  • The implementation of Edge Coloring completes the coloring algorithms part of the Boost Graph Library in pgRouting. But, we can implement Boman et al Graph Coloring Algorithm by the Parallel Boost Graph Library, which colors the vertices of an undirected, distributed graph such that no two adjacent vertices have the same color.

  • Cuthill-Mckee Algorithm can be implemented by the Boost Graph Library, it adds functionality to pgRouting for reducing the bandwidth of an undirected graph.

Links:

Images:

Media:

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

Thanks and Regards,

Veenit Kumar

Weekly Reports

Second Coding Period (July 12th - August 15th)

Week 10 (August 9th - August 15th)

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

  • What did I get done this week?

    • Merged two Pull Requests in the pgRouting develop branch:
      • #2061: Experimental Function - pgr_edgeColoring
      • #2084: Updating pgr_edgeColoring Doc
    • Created a issue for adding pgr_edgeColoring in pgRouting:
      • #2060: Detailed signature of the new function pgr_edgeColoring to be added in pgRouting
    • Created a tag in GSoC-pgRouting containing the code of experimental function pgr_edgeCOloring: GSoC-2021-veenits123-edgeColoring

  • What do I plan on doing next week?

    • Make the final report along with the presentation of the work.
    • Submit the final evaluation of my mentors.

  • Am I blocked on anything?

    • No, I am not blocked on anything.

Week 9 (August 2nd - August 8th)

Week 8 (July 26th - August 1st)

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

  • What did I get done this week?

    • Refined the pgTap files.
    • Added more pgTap tests to the file edge-cases.sql.
    • Made a pull request with all these changes (#186).

  • What do I plan on doing next week?

  • Am I blocked on anything?

    • No, I am not blocked on anything.

Week 7 (July 19th - July 25th)

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

  • What did I get done this week?

    • Refined all the files.
    • Removed all the unwanted code and comments.
    • Made a pull request with all these changes (#184).

  • What do I plan on doing next week?

    • Refine pgTap files.
    • Make more pgTap tests of various Graphs types.

  • Am I blocked on anything?

    • No, I am not blocked on anything.

Week 6 (July 12th - July 18th)

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

  • What did I get done this week?

    • Made tools/testers/doc_queries_generator.pl -alg coloring test pass.
    • Made tools/developer/taptest.sh coloring/edgeColoring -p 5432 pass.
    • Made a pull request with all these changes (#182).

  • What do I plan on doing next week?

    • Rectify coding styles of C++ files.

  • Am I blocked on anything?

    • No, I am not blocked on anything.

First Coding Period (June 7th - July 11th)

Week 5 (July 5th - July 11th)

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

  • What did I get done this week?

    • Created the necessary class wrapper for the Boost function.
    • Worked on include/coloring/pgr_edgeColoring.hpp.
    • Worked on src/coloring/edgeColoring_driver.cpp.
    • Worked on src/coloring/pgr_edgeColoring.cpp.
    • Made a pull request with all these changes (#179).

  • What do I plan on doing next week?

    • Make pgTap tests pass.
    • Make tools/testers/doc_queries_generator.pl -alg coloring pass.

  • Am I blocked on anything?

    • No, I am not blocked on anything.

Week 4 (June 28th - July 4th)

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

  • What did I get done this week?

    • Created the necessary files for pgTap tests.
    • Worked on pgtap/coloring/edgeColoring/
      • Modified innerQuery.sql
      • Modified types_check.sql
      • Modified no_crash_test.sql
      • Modified edge-cases.sql
    • Made a pull request with all these changes (#176).

  • What do I plan on doing next week?

  • Am I blocked on anything?

    • Yes, I am blocked.
    • Due to an external situation I will use less time for Week 5 that will be compensated on week 6 as follows:
      • Originally there are 2 objectives for Weeks 5 & 6:
        • Week 5: Objective is to have tools/testers/doc_queries_generator.pl -alg coloring working.
        • Week 6: Objective pgTap test must pass.
    • So, because of reducing the time on Week 5 and moving it to week 6:
      • Week 5: Initial work on the objective: tools/testers/doc_queries_generator.pl -alg coloring working.
      • Week 6: Final work on the objective: tools/testers/doc_queries_generator.pl -alg coloring working and pgTap test must pass.

Week 3 (June 21st - June 27th)

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

  • What did I get done this week?

    • Created the necessary class wrapper for the Boost function.
    • Created a new file src/coloring/pgr_edgeColoring.cpp containing all the necessary function to be called by the driver file.
    • Worked on include/coloring/pgr_edgeColoring.hpp to read data.
    • Worked on src/coloring/edgeColoring_driver.cpp, the main file responsible for reading data of type SQL.
    • Updated doc/conf.py.in by adding links to ignore so that it gets compiled on GitHub action.
    • Updated docqueries/coloring/test.conf by adding doc-edgeColoring.
    • Made a pull request with all these changes (#173).

  • What do I plan on doing next week?

  • Am I blocked on anything?

    • No, I am not blocked on anything.

Week 2 (June 14th - June 20th)

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

  • What did I get done this week?

    • Created the necessary class wrapper for the Boost function.
    • Worked on include/coloring/pgr_edgeColoring.hpp to read data.
    • Worked on documentation for the pgr_edgeColoring function.
    • Updated doc/coloring/: pgr_edgeColoring.rst, coloring-family.rst and docqueries/coloring/: doc-edgeColoring.result, doc-edgeColoring.test.sql files.
    • Made a pull request with all these changes (#171).

  • What do I plan on doing next week?

  • Am I blocked on anything?

Week 1 (June 7th - June 13th)

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

  • What did I get done this week?

    • Started working on the pgr_edgeColoring function.
    • Dummy placements of all the files that I need to create during the GSoC period.
    • Checked the code after committing using command: bash tools/scripts/code_checker.sh coloring
    • Updated CMakeLists.txt for sql, src, doc, docqueries files.
    • Learned about license_check, News_check, shell_check, signature_check, etc.
    • Learned how to use terminal and GitHub Action to check the error while building files.
    • Made a pull request with all these changes (#169).

  • What do I plan on doing next week?

    • Fix all the Bugs and Errors getting on the building and compiling of files during Week-1.
    • Design boost::edge_coloring().
    • Create the necessary class wrapper for the Boost function.
    • Process the data with the Boost Function.

  • Am I blocked on anything?

    • No, I have no issues.

Community Bonding Period (May 17th - June 6th)

Tasks

  • 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.
  • Learn to create unit tests using pgTAP.
  • 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.
  • Created a new branch named veenit-2021 in the GSoC-pgRouting repository, where I will be merging all the Pull Requests.

Meeting Discussions

  1. May 21st

    • Introduction meeting with the mentors.
    • Discussion on the future plans of the GSoC period.

  2. May 28th

    • Cancelled due to Cyclone in my area.

  3. June 1st

    • Basic Repository preparation of pgRouting.
    • Understood the files and structures: sql, src, include, pgtap, doc, docqueries of various functions.
    • Understood and analyzed the coding style of pgr_dijkstra, pgr_bdDijkstra, pgr_bipartite, etc.

  4. June 4th

    • Learned how to design the functions, create various tests, run tests, etc.
    • Understood how is a test designed and how to do the testing using pgTAP like types-check, inner-query, no-crash-test, edge-cases.
    • Understood the development and coding style of C++, SQL and C files of the functions.
    • Learned how and where to create Pull Request, how to commit, etc.

  5. June 11th

    • Checked the code after committing using command: bash tools/scripts/code_checker.sh
    • Learned about license_check, News_check, shell_check, signature_check, etc.
    • Learned how to use terminal and GitHub Action to check the error while building files.

  6. June 18th

#if 0
.....what to comment inside;
#endif

  1. June 25th

  2. July 2nd

  3. July 09

    • Meeting was cancelled and scheduled for July 13.

  4. July 13

    • Made pgTap and docqueries tests pass.
    • Discussed new coding styles in C++ files.

  5. July 23

    • Discussion about how to create pgTap tests on different types of Graphs.

  6. July 30

  7. August 06

  8. August 10

    • Reviewing of the final pull request that needs to get merged in the pgRouting develop branch: (#2061): Experimental Function - pgr_edgeColoring.
    • Discussion on how to create a tag for the GSoC work.

Pre-Bonding Period (March 10th - April 13th)

References

  1. Misra & Gries Edge Coloring Algorithm https://en.wikipedia.org/wiki/Misra_%26_Gries_edge_coloring_algorithm
  2. Edge Coloring https://en.wikipedia.org/wiki/Edge_coloring
  3. https://www.cs.utexas.edu/users/misra/psp.dir/vizing.pdf Misra, Jayadev; Gries, David(1992). "A constructive proof of Vizing's theorem"
  4. https://github.com/pgRouting/pgrouting/tree/master
  5. https://github.com/pgRouting/pgrouting/tree/develop
  6. Graph Coloring https://en.wikipedia.org/wiki/Graph_coloring
  7. Graph Bandwidth https://en.wikipedia.org/wiki/Graph_bandwidth
  8. https://codeforces.com/blog/entry/75431 Story about Edge Coloring of Graph
  9. pgRouting queries on Stack Overflow https://stackoverflow.com/search?q=pgrouting
  10. pgRouting GSoC Ideas: 2021 https://github.com/pgRouting/pgrouting/wiki/GSoC-Ideas:-2021
  11. https://github.com/pgRouting/GSoC-pgRouting/wiki/Creating-a-GSoC-schedule
  12. pgRouting Workshop https://workshop.pgrouting.org/2.6/en/index.html
  13. https://docs.pgrouting.org/3.2/en/genindex.html pgRouting Documentation
  14. MIT 6.042J Mathematics for Computer Science, Fall 2010 http://www.youtube.com/watch?v=h9wxtqoa1jY
  15. https://www.youtube.com/watch?v=_3-XbvYqMEo 2019 - Shortest path in the database and more with pgRouting
  16. Google Summer of Code Recommendations for Students https://wiki.osgeo.org/wiki/Google_Summer_of_Code_Recommendations_for_Students
  17. https://www.openstreetmap.org/ OpenStreetMap

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally