[pgrouting-dev] GSoC 2020- Final Report - Lengauer Tarjan Dominator Tree and Bipartite algorithm for pgRouting

pgRouting pgrouting-dev
1

Hello everyone,

With GSoC coming to an end, I present to you the final report of my work over the past three months! It has been a great experience and great learning. This report is in accordance with the guidelines set by Google and OSGeo GSoC Admins.

Title - Implement Lengauer Tarjan Dominator Tree and Bipartite algorithm for pgRouting

Organisation - pgRouting under OSGeo

Abstract - This GSoC project dealt with implementing two new graph algorithms in pgRouting. The algorithms are described as follows:

  • Boost::l****engauer_tarjan_dominator_tree The algorithm calculates the immediate dominator (The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly
    dominates n) of each vertex called idom, once idom of each vertex is calculated then by making every idom of each vertex as its parent, the dominator tree can be built.This algorithm is only applicable for directed graphs. It has a linear time complexity of O((V+E)log(V+E)).
  • Boost::is_bipartite A bipartite graph is a graph with two sets of vertices which are connected to each other, but not within themselves. A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. This algorithm is only applicable for undirected graphs. It has a linear time complexity of O(|V| + |E|).

State of the Project Be****fore GSoC - pgRouting currently does not have these algorithms implemented. Current state of pgRouting doesn’t support any algorithm for finding a dominator tree. And also a single standard function does not exist to check whether any graph is Bi-partite or not.

The addition that my project brought to pgRouting: The deliverables are code, documentation, documentation tests, and the pgTAP tests of the two functions.

  • Lengauer Tarjan Dominator Tree (pgr_lengauerTarjanDominatorTree) can be used to find the dominator tree of any graph or immediate dominator of any vertex. It returns the immediate dominator of each vertex. This function is applicable only for directed graphs.
  • Bipartite (pgr_bipartite) can be used to check whether a given graph is bipartite or not. If the graph is bipartite then the function returns the vertex and color. If the graph is not bipartite then the function returns an empty row. This function is applicable only for undirected graphs.

Potential Future Work

  • Edge Coloring algorithm can be implemented, which assigns the color to the edges of a graph, unlike the Bipartite graph algorithm, that assigns the colors to the vortices if the graph is bipartite.
  • The third function pgr_twoGraphsCommonSpanningTrees, can’t be implemented because there was some problem in the boost algorithm itself. The algorithm was not returning the output as expected. In future if it will be fixed in boost algorithm then it can also be implemented in the pgRouting.

Links

Media

I am so glad to have such an interesting and exciting adventure with all of you. Thanks for all your support! I will be happy if my code proves beneficial to the community.

Thanks and Regards,

Prakash Tiwari