[pgrouting-dev] GSoC 2021 - Final Report: Implement Edge Coloring Algorithm for pgRouting by the Boost Graph Library

[Veenit Kumar]

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 [1] and
OSGeo GSoC Admins [2].

*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:*
- *Code Documentation:*
  - *Edge Coloring (pgr_edgeColoring):*
https://docs.pgrouting.org/3.3/en/pgr_edgeColoring.html
- *Tags:*
    - Edge Coloring (GSoC-2021-veenits123-edgeColoring):
https://github.com/pgRouting/GSoC-pgRouting/releases/tag/GSoC-2021-veenits123-edgeColoring
- *Pull Requests:*
  - *Final Pull Request:* (#2061) Experimental Function - pgr_edgeColoring (
https://github.com/pgRouting/pgrouting/pull/2061)
  - *Pull Request for removing links from linkcheck_ignore:* (#2084)
Updating pgr_edgeColoring Doc (
https://github.com/pgRouting/pgrouting/pull/2084)
  - *Intermediate pull requests:*
https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Aveenits123

- *Project Documentation (Wiki Page):*
https://github.com/pgRouting/pgrouting/wiki/GSoC-2021-Implement-Edge-Coloring-Algorithm-for-pgRouting-by-the-Boost-Graph-Library

*Images:*
- *pgr_edgeColoring:*
https://drive.google.com/file/d/1cPMjYeNolHJ2YjAsFc4RrOkbxcsheVMY/view?usp=sharing

*Media:*
- *Slide Demonstration:*
https://docs.google.com/presentation/d/1NMg7qBB1QMqyygdzpqZvp6aRlG7iUkGWrpYQy1ddK2E/edit?usp=sharing

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

[1] https://developers.google.com/open-source/gsoc/help/work-product
[2] https://lists.osgeo.org/pipermail/soc/2021-August/004804.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20210818/fe658b05/attachment.html>