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

[Prakash Tiwari]

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
<https://developers.google.com/open-source/gsoc/help/work-product> and OSGeo
GSoC Admins <https://lists.osgeo.org/pipermail/soc/2020-August/004612.html>.

*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*

   - *Code Documentation*
      - Lengauer Tarjan Dominator Tree (pgr_lengauerTarjanDominatorTree )-
      https://docs.pgrouting.org/3.2/en/pgr_lengauerTarjanDominatorTree.html
      - Bipartite (pgr_bipartite) -
      https://docs.pgrouting.org/3.2/en/pgr_bipartite.html
   - *Tags*
      -
      https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-prakashupes-lengauerTarjanDominatorTree-bipartite
      -
      https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-prakashupes-common-spanning-tree
      - *Pull Requests*
      - Final pull request (#1608
      <https://github.com/pgRouting/pgrouting/pull/1608>).
      - Pull Request for removing links from linkcheck_ignore (#1609
      <https://github.com/pgRouting/pgrouting/pull/1609>).
      - Intermediate pull requests -
      https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+is%3Aclosed+author%3Aprakashupes
   - *Project Documentation (Wiki Page)*
      -
      https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Lengauer-Tarjan-dominator-tree-and-Bipartite
      - *Images*
      - pgr_lengauerTarjanDominatorTree (
      https://drive.google.com/file/d/1_3yn0PmF_OeBcw2yTfv9GP-sk9vdAiLA/view?usp=drivesdk
      )
      - pgr_bipartie (
      https://drive.google.com/file/d/1YHxv8yMkNYuogd2sgnJeJtOAK0f1Uhqd/view?usp=drivesdk
      )

*Media*

   - *Slide Demonstration* -
   https://docs.google.com/presentation/d/1uvQc4GUUYr1pzRH4KfwOg5YoRZ6TFC8bMQw81QUjnfA/edit?usp=drivesdk

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20200827/ae86a3b7/attachment-0001.html>