<div dir="ltr"><div dir="ltr">Hello everyone,<br><br>With the GSoC period coming to an end, I hereby present the final report of my work, which I did over the past three months. It has been a great experience working with the pgRouting community and the mentors.</div><div dir="ltr">This report is in accordance with the <a href="https://developers.google.com/open-source/gsoc/help/work-product" target="_blank">guidelines set by Google</a> and <a href="https://lists.osgeo.org/pipermail/soc/2020-August/004612.html" target="_blank">OSGeo GSoC Admins</a>.<br><br><div>1. (a) <b>Title</b>: Depth First Search, Sequential Vertex Coloring, and analysis of Graph Input Ordering for pgRouting.</div><div>    (b) <b>Organization</b>: pgRouting under OSGeo.</div><div><br></div><div>2. <b>Abstract</b>:</div><div>The GSoC project dealt with the implementation of two new graph algorithms in pgRouting:<br></div><div><br></div><div>(i) Depth First Search: It is the implementation of a standard graph traversal algorithm for both directed and undirected graphs. It has been implemented in Boost Graph Library as two different algorithms - <font face="monospace">boost::depth_first_search</font> for directed graphs and <font face="monospace">boost::undirected_dfs</font> for undirected graphs. One of its applications is to find a path in the graph from a source vertex to all other vertices. It has a linear time complexity of <font face="monospace">O(|V| + |E|)</font>.</div><div><br></div><div>(ii) Sequential Vertex Coloring: It is an algorithm to compute the vertex coloring of a graph. This involves assigning colors to the vertices of a graph sequentially in such a way that no two adjacent vertices have the same color. It has been implemented in the Boost Graph Library as <font face="monospace">boost::sequential_vertex_coloring</font> for undirected graphs. One of its applications is to do a proper coloring of the graph or to check if a graph is bipartite. It has a time complexity of <font face="monospace">O(|V| * (d + k))</font>, where <font face="monospace">|V|</font> is the number of vertices, <font face="monospace">d</font> is the maximum degree of the vertices in the graph, and <font face="monospace">k</font> is the number of colors used.<br></div><div><br></div><div>The project also analyzed the behavior of several algorithms after ordering the input rows in a particular order.</div><div><br></div><div>3. <b>The state of the project before GSoC</b>:</div><div>pgRouting did not have these two graph algorithms implemented.<br></div><div><br></div><div>(i) Depth First Search is a standard graph searching algorithm and is used in various other already implemented algorithms such as Prim’s and Kruskal’s algorithm for finding MST. However, not a single standard function exists in pgRouting, either for directed graphs or for undirected graphs.</div><div>(ii) The Sequential Vertex Coloring algorithm was not implemented before in pgRouting.</div><div><br></div><div>4. <b>The addition that my project brought to pgRouting</b>:</div><div>The deliverables are code, documentation, documentation tests, and the pgTAP tests of the two functions.<br></div><div>(i) The Depth First Search algorithm is now a function of its own and is meant for general use. Moreover, it can be used to find a path in a graph from a source vertex to all other vertices.<br></div><div>(ii) The Sequential vertex coloring algorithm can be used to check if a graph is bipartite. It can also be used to color a geographical map, such that no two adjacent neighbors have the same color.</div><div><br></div><div>5. <b>Potential Future Work</b>:</div><div>(i) Edge Coloring algorithm can be implemented, which assigns the color to the edges of a graph, unlike the Sequential Vertex Coloring algorithm, that assigns the color to the vertices.</div><div>(ii) Since the Sequential Vertex Coloring algorithm doesn't provide optimal coloring of the graph, other heuristic-based graph coloring algorithms, or planar graph algorithms can be implemented that can guarantee the coloring of the graph using a fixed number of available colors.</div><div>(iii) The third function pgr_maximumAdjacencySearch, was an additional idea. However, it can't be implemented because it was present in the Boost version 1.54.0 and later, and was not available for Boost v1.53.0. pgRouting has to cover a lot of Operating Systems and, in particular, for CENTOS 6, version 1.53 is the one that is installed automatically. This function may be implemented later, once CENTOS 6 ends the EOL.</div><div><br></div><div>6. <b>Links</b>:</div><div><br></div><div>(i) <b>Code Documentation</b>:</div><div><ul><li>Depth First Search (<font face="monospace">pgr_depthFirstSearch</font>): <a href="http://docs.pgrouting.org/dev/en/pgr_depthFirstSearch.html" target="_blank">http://docs.pgrouting.org/dev/en/pgr_depthFirstSearch.html</a></li><li>Sequential Vertex Coloring (<font face="monospace">pgr_sequentialVertexColoring</font>): <a href="http://docs.pgrouting.org/dev/en/pgr_sequentialVertexColoring.html" target="_blank">http://docs.pgrouting.org/dev/en/pgr_sequentialVertexColoring.html</a></li></ul><div>(ii) <b>Tags</b>:</div><div><ul><li>Depth First Search and Sequential Vertex Coloring (2020-krashish8-depthFirstSearch-sequentialVertexColoring): <a href="https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-krashish8-depthFirstSearch-sequentialVertexColoring" target="_blank">https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-krashish8-depthFirstSearch-sequentialVertexColoring</a><br></li><li>Tests and fixes for ordering issue (2020-krashish8-input-ordering-tests-and-fixes): <a href="https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-krashish8-input-ordering-tests-and-fixes" target="_blank">https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-krashish8-input-ordering-tests-and-fixes</a></li></ul></div>(iii) <b>Pull Requests</b>:</div><div><ul><li>Final Pull Request: Experimental Functions - pgr_depthFirstSearch, pgr_sequentialVertexColoring (<a href="https://github.com/pgRouting/pgrouting/pull/1599" target="_blank">https://github.com/pgRouting/pgrouting/pull/1599</a>)</li><li>Subsequent Pull Requests (fixes): Removed the generated links from linkcheck_ignore (<a href="https://github.com/pgRouting/pgrouting/pull/1602" target="_blank">https://github.com/pgRouting/pgrouting/pull/1602</a>), Fixed coloring family and pgr_sequentialVertexColoring documentation (<a href="https://github.com/pgRouting/pgrouting/pull/1604" target="_blank">https://github.com/pgRouting/pgrouting/pull/1604</a>).</li><li>PRs and Issues labeled ordering: <a href="https://github.com/pgRouting/GSoC-pgRouting/issues?q=label%3Aordering" target="_blank">https://github.com/pgRouting/GSoC-pgRouting/issues?q=label%3Aordering</a><br></li><li>Intermediate Pull Requests: <a href="https://github.com/pgRouting/GSoC-pgRouting/pulls?q=author%3Akrashish8" target="_blank">https://github.com/pgRouting/GSoC-pgRouting/pulls?q=author%3Akrashish8</a></li></ul>(iv) <b>Wiki Pages</b>:</div><div><ul><li>GSoC Project: <a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Depth-First-Search-and-Sequential-Vertex-Coloring" target="_blank">https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Depth-First-Search-and-Sequential-Vertex-Coloring</a></li><li>Analysis of Graph Input Ordering: <a href="https://github.com/pgRouting/pgrouting/wiki/Analysis:-Graph-input-ordering" target="_blank">https://github.com/pgRouting/pgrouting/wiki/Analysis:-Graph-input-ordering</a></li></ul>7. <b>Images</b>:</div><div><ul><li>pgr_depthFirstSearch (<a href="https://drive.google.com/file/d/1QRZYEWZKo0rcC92EKyEFJiG8yjSf6Y19/view?usp=sharing" target="_blank">https://drive.google.com/file/d/1QRZYEWZKo0rcC92EKyEFJiG8yjSf6Y19/view?usp=sharing</a>), pgr_sequentialVertexColoring (<a href="https://drive.google.com/file/d/1ssXlw2UvJFfeOkUsnotwOMowawnCbyUt/view?usp=sharing" target="_blank">https://drive.google.com/file/d/1ssXlw2UvJFfeOkUsnotwOMowawnCbyUt/view?usp=sharing</a>)<br></li></ul>8. <b>Media</b>:</div><div><ul><li>Slide Demonstration: <a href="https://docs.google.com/presentation/d/1E0T8sKlQpSbfrv1xcSqF7GrLQ1JoodtZgZVMJGqW6sY/edit?usp=sharing" target="_blank">https://docs.google.com/presentation/d/1E0T8sKlQpSbfrv1xcSqF7GrLQ1JoodtZgZVMJGqW6sY/edit?usp=sharing</a></li></ul></div><div><br></div><div>I'm glad to be a part of the GSoC community. The things I learned during this summer would surely be helpful to me in the future. I'd be happy if my code proves beneficial to the community. Thanks to everyone for the support!</div><div><br></div><div>Thank you,<br>Ashish Kumar.</div></div></div>