[SoC] GSoC 2020 - Final Report - Depth First Search, Sequential Vertex Coloring and analysis of Graph Input Ordering for pgRouting

[Ashish Kumar]

Hello everyone,

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.
This report is in accordance with the guidelines set by Google
<https://developers.google.com/open-source/gsoc/help/work-product> and OSGeo
GSoC Admins <https://lists.osgeo.org/pipermail/soc/2020-August/004612.html>.

1. (a) *Title*: Depth First Search, Sequential Vertex Coloring, and
analysis of Graph Input Ordering for pgRouting.
    (b) *Organization*: pgRouting under OSGeo.

2. *Abstract*:
The GSoC project dealt with the implementation of two new graph algorithms
in pgRouting:

(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 -
boost::depth_first_search for directed graphs and boost::undirected_dfs 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 O(|V| + |E|).

(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
boost::sequential_vertex_coloring 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 O(|V| * (d + k)), where |V| is
the number of vertices, d is the maximum degree of the vertices in the
graph, and k is the number of colors used.

The project also analyzed the behavior of several algorithms after ordering
the input rows in a particular order.

3. *The state of the project before GSoC*:
pgRouting did not have these two graph algorithms implemented.

(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.
(ii) The Sequential Vertex Coloring algorithm was not implemented before in
pgRouting.

4. *The addition that my project brought to pgRouting*:
The deliverables are code, documentation, documentation tests, and the
pgTAP tests of the two functions.
(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.
(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.

5. *Potential Future Work*:
(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.
(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.
(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.

6. *Links*:

(i) *Code Documentation*:

   - Depth First Search (pgr_depthFirstSearch):
   http://docs.pgrouting.org/dev/en/pgr_depthFirstSearch.html
   - Sequential Vertex Coloring (pgr_sequentialVertexColoring):
   http://docs.pgrouting.org/dev/en/pgr_sequentialVertexColoring.html

(ii) *Tags*:

   - Depth First Search and Sequential Vertex Coloring
   (2020-krashish8-depthFirstSearch-sequentialVertexColoring):
   https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-krashish8-depthFirstSearch-sequentialVertexColoring
   - Tests and fixes for ordering issue
   (2020-krashish8-input-ordering-tests-and-fixes):
   https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-krashish8-input-ordering-tests-and-fixes

(iii) *Pull Requests*:

   - Final Pull Request: Experimental Functions - pgr_depthFirstSearch,
   pgr_sequentialVertexColoring (
   https://github.com/pgRouting/pgrouting/pull/1599)
   - Subsequent Pull Requests (fixes): Removed the generated links from
   linkcheck_ignore (https://github.com/pgRouting/pgrouting/pull/1602), Fixed
   coloring family and pgr_sequentialVertexColoring documentation (
   https://github.com/pgRouting/pgrouting/pull/1604).
   - PRs and Issues labeled ordering:
   https://github.com/pgRouting/GSoC-pgRouting/issues?q=label%3Aordering
   - Intermediate Pull Requests:
   https://github.com/pgRouting/GSoC-pgRouting/pulls?q=author%3Akrashish8

(iv) *Wiki Pages*:

   - GSoC Project:
   https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Depth-First-Search-and-Sequential-Vertex-Coloring
   - Analysis of Graph Input Ordering:
   https://github.com/pgRouting/pgrouting/wiki/Analysis:-Graph-input-ordering

7. *Images*:

   - pgr_depthFirstSearch (
   https://drive.google.com/file/d/1QRZYEWZKo0rcC92EKyEFJiG8yjSf6Y19/view?usp=sharing),
   pgr_sequentialVertexColoring (
   https://drive.google.com/file/d/1ssXlw2UvJFfeOkUsnotwOMowawnCbyUt/view?usp=sharing
   )

8. *Media*:

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


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!

Thank you,
Ashish Kumar.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20200822/4d932616/attachment-0001.html>