The project aims to add the following two algorithms in pgRouting:
Depth First Search: It is the implementation of a standard graph traversal algorithm, and 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|).
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 analyzes the behavior of several algorithms after ordering the input rows in a particular order.