<div dir="ltr">Hello everyone,<br><br>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].<br><br>*Title:*  Implement Edge Coloring Algorithm for pgRouting by the Boost Graph Library<br><br>*Organisation:*  pgRouting under OSGeo<br><br>*Abstract:*  This GSoC project dealt with the implementation of one new Graph algorithm in pgRouting. The algorithm is described below:<br>        - *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.<br>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.<br>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|)`.<br><br>*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.<br><br>*The addition that my project brought to pgRouting:* The deliverables are code, documentation, documentation tests, and the pgTAP tests of the function.<br>        - *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.<br><br>*Potential Future Work:*<br>     - 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.<br><br>       - `Cuthill-Mckee Algorithm` can be implemented by the Boost Graph Library, it adds functionality to pgRouting for reducing the bandwidth of an undirected graph.<br><br>*Links:*<br>  - *Code Documentation:*<br>               - *Edge Coloring (pgr_edgeColoring):* <a href="https://docs.pgrouting.org/3.3/en/pgr_edgeColoring.html">https://docs.pgrouting.org/3.3/en/pgr_edgeColoring.html</a><br>    - *Tags:*<br>                   - Edge Coloring (GSoC-2021-veenits123-edgeColoring): <a href="https://github.com/pgRouting/GSoC-pgRouting/releases/tag/GSoC-2021-veenits123-edgeColoring">https://github.com/pgRouting/GSoC-pgRouting/releases/tag/GSoC-2021-veenits123-edgeColoring</a><br>        - *Pull Requests:*<br>           - *Final Pull Request:* (#2061) Experimental Function - pgr_edgeColoring (<a href="https://github.com/pgRouting/pgrouting/pull/2061">https://github.com/pgRouting/pgrouting/pull/2061</a>)<br>             - *Pull Request for removing links from linkcheck_ignore:* (#2084) Updating pgr_edgeColoring Doc (<a href="https://github.com/pgRouting/pgrouting/pull/2084">https://github.com/pgRouting/pgrouting/pull/2084</a>)<br>             - *Intermediate pull requests:* <a href="https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Aveenits123">https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Aveenits123</a><br><br>- *Project Documentation (Wiki Page):* <a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2021-Implement-Edge-Coloring-Algorithm-for-pgRouting-by-the-Boost-Graph-Library">https://github.com/pgRouting/pgrouting/wiki/GSoC-2021-Implement-Edge-Coloring-Algorithm-for-pgRouting-by-the-Boost-Graph-Library</a><br><br>*Images:*<br>      - *pgr_edgeColoring:* <a href="https://drive.google.com/file/d/1cPMjYeNolHJ2YjAsFc4RrOkbxcsheVMY/view?usp=sharing">https://drive.google.com/file/d/1cPMjYeNolHJ2YjAsFc4RrOkbxcsheVMY/view?usp=sharing</a><br><br>*Media:*<br>   - *Slide Demonstration:* <a href="https://docs.google.com/presentation/d/1NMg7qBB1QMqyygdzpqZvp6aRlG7iUkGWrpYQy1ddK2E/edit?usp=sharing">https://docs.google.com/presentation/d/1NMg7qBB1QMqyygdzpqZvp6aRlG7iUkGWrpYQy1ddK2E/edit?usp=sharing</a><br><br>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!<br><br><div>Thanks and Regards,</div>Veenit Kumar<br><br>[1] <a href="https://developers.google.com/open-source/gsoc/help/work-product">https://developers.google.com/open-source/gsoc/help/work-product</a><br>[2] <a href="https://lists.osgeo.org/pipermail/soc/2021-August/004804.html">https://lists.osgeo.org/pipermail/soc/2021-August/004804.html</a></div>