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 Jun 12, 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
#142 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

Weekly Reports

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

Week 10 (August 9th - August 15th)

Week 9 (August 2nd - August 8th)

Week 8 (July 26th - August 1st)

Week 7 (July 19th - July 25th)

Week 6 (July 12th - July 18th)

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

Week 5 (July 5th - July 11th)

Week 4 (June 28th - July 4th)

Week 3 (June 21st - June 27th)

Week 2 (June 14th - June 20th)

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.

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