[SoC] GSoC 2020 Final Report  Lengauer Tarjan Dominator Tree and Bipartite algorithm for pgRouting
Prakash Tiwari
85prakash2017 at gmail.com
Thu Aug 27 02:05:24 PDT 2020
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/opensource/gsoc/help/workproduct> and OSGeo
GSoC Admins <https://lists.osgeo.org/pipermail/soc/2020August/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 Bipartite 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/GSoCpgRouting/releases/tag/2020prakashupeslengauerTarjanDominatorTreebipartite

https://github.com/pgRouting/GSoCpgRouting/releases/tag/2020prakashupescommonspanningtree
 *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/GSoCpgRouting/pulls?q=is%3Apr+is%3Aclosed+author%3Aprakashupes
 *Project Documentation (Wiki Page)*

https://github.com/pgRouting/pgrouting/wiki/GSoC2020LengauerTarjandominatortreeandBipartite
 *Images*
 pgr_lengauerTarjanDominatorTree (
https://drive.google.com/file/d/1_3yn0PmF_OeBcw2yTfv9GPsk9vdAiLA/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/attachment0001.html>
More information about the SoC
mailing list