[pgrouting-dev] GSoC-2021 Introduction: Veenit Kumar - Implement Edge Coloring Algorithm for pgRouting by the Boost Graph Library.

pgRouting pgrouting-dev
1

Hello Community,

I am Veenit Kumar from Netaji Subhash Engineering College, Kolkata, India currently in my junior year doing Bachelors in Computer Science and Engineering. Here’s my GitHub and LinkedIn handle [1] and [2].

First of all, I would like to thank the OSGeo and the pgRouting community for selecting me and giving me this wonderful opportunity to work as a Student Developer this Google Summer of Code 2021.

I am going to work on the project titled “Implement Edge Coloring Algorithm for pgRouting by the Boost Graph Library” [3]. As the title says I am going to implement Edge Coloring Algorithm by the C++ Boost Graph Library in pgRouting.

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. Furthermore, at most Δ + 1 colors are used, where Δ is the degree of the graph. It is implemented in Boost Graph Library (BGL) as Boost::Edge Coloring [4].

I have done all the work including writing this introductory mail as mentioned in the SoC mail [5]:

  • Created my GSoC project wiki page where all the weekly work and report will be documented [6].
  • Forked [7], the pgRouting’s GSoC-pgRouting repository [8] where I will be working and making PR and at the end, this will be merged to pgRouting [9].
  • Added the links to both the wiki pages and public repository in the accepted students’ wiki page [10].
  • Read Google’s GSoC students guide and OSGeo’s specific instructions.

I request Community members to please provide some feedback or suggestions on my project as it will improve the projects developments and my overall performances.

I am excited and looking forward to achieving many great this summer with OSGeo and pgRouting.

Thanks!

Veenit Kumar

[1] https://github.com/Veenits123

[2] https://www.linkedin.com/in/veenits123/

[3] https://summerofcode.withgoogle.com/projects/#4897201601380352

[4] https://www.boost.org/doc/libs/1_76_0/libs/graph/doc/edge_coloring.html

[5] https://lists.osgeo.org/pipermail/soc/2021-May/004665.html

[6] https://github.com/pgRouting/pgrouting/wiki/GSoC-2021-Implement-Edge-Coloring-Algorithm-for-pgRouting-by-the-Boost-Graph-Library

[7] https://github.com/Veenits123/GSoC-pgRouting/

[8] https://github.com/pgRouting/GSoC-pgRouting

[9] https://github.com/pgRouting/pgrouting

[10] https://wiki.osgeo.org/wiki/Google_Summer_of_Code_2021_Accepted