<div dir="auto"><p style="font-family:sans-serif;font-size:12.8px">Hello everyone,</p><p style="font-family:sans-serif;font-size:12.8px">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 <a href="https://developers.google.com/open-source/gsoc/help/work-product" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">guidelines set by Google</a> and <a href="https://lists.osgeo.org/pipermail/soc/2020-August/004612.html" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">OSGeo GSoC Admins</a>.</p><p style="font-family:sans-serif;font-size:12.8px"><strong>Title</strong> - <span style="color:rgba(0,0,0,0.87);font-family:'roboto','helvetica neue',sans-serif">Implement Lengauer Tarjan Dominator Tree and Bipartite algorithm for pgRouting</span></p><p style="font-family:sans-serif;font-size:12.8px"><strong>Organisation</strong> - pgRouting under OSGeo</p><p style="font-family:sans-serif;font-size:12.8px"><strong>Abstract</strong> - This GSoC project dealt with implementing two new graph algorithms in pgRouting. The algorithms are described as follows:</p><ul style="font-family:sans-serif;font-size:12.8px"><li style="margin-left:15px"><strong>Boost::l</strong><b>engauer_tarjan_dominator_tree</b> The algorithm calculates the<span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px"> </span><em style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px">immediate dominator</em><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px"> (</span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px">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<br>dominates n) of each vertex called</span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px"> </span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px;font-weight:700">idom</span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px">, once</span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px"> </span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px;font-weight:700">idom</span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px"> </span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px">of each vertex is calculated then by making every</span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px"> </span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px;font-weight:700">idom</span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px"> </span><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px">of each vertex as its parent, the dominator tree can be built.</span>This algorithm is only applicable for <strong>directed</strong> graphs. It has a linear time complexity of <i style="font-family:'times new roman';font-size:medium">O((V+E)log(V+E)).</i></li><li style="margin-left:15px"><strong>Boost::is_bipartite </strong><span style="color:rgb(51,51,51);font-family:'helvetica neue','helvetica','arial',sans-serif;font-size:14px">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.</span> This algorithm is only applicable for <strong>undirected</strong> graphs. It has a linear time complexity of <strong>O(|V| + |E|)</strong>.</li></ul><p style="font-family:sans-serif;font-size:12.8px"><strong>State of the Project Be</strong><strong>fore GSoC</strong><font color="#000000" face="sans-serif"> - </font><span style="color:rgb(34,34,34);font-family:'arial','helvetica',sans-serif;font-size:small">pgRouting currently does not have these algorithms implemented. </span><span style="color:rgb(34,34,34);font-family:'arial','helvetica',sans-serif;font-size:small">Current state of pgRouting doesn’t support any algorithm for finding a dominator tree. And</span><span style="color:rgb(34,34,34);font-family:'arial','helvetica',sans-serif;font-size:small"> also a single standard function does not exist to check whether any graph is </span><span style="color:rgb(34,34,34);font-family:'arial','helvetica',sans-serif;font-size:small">B</span><span style="color:rgb(34,34,34);font-family:'arial','helvetica',sans-serif;font-size:small">i-partite or not.</span></p><p style="font-family:sans-serif;font-size:12.8px"><strong>The addition that my project brought to pgRouting:</strong> The deliverables are code, documentation, documentation tests, and the pgTAP tests of the two functions.</p><ul style="font-family:sans-serif;font-size:12.8px"><li style="margin-left:15px">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.</li><li style="margin-left:15px">Bipartite (<code>pgr_bipartite</code>) 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.</li></ul><p style="font-family:sans-serif;font-size:12.8px"><strong>Potential Future Work</strong></p><ul style="font-family:sans-serif;font-size:12.8px"><li>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.</li><li>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. </li></ul><p style="font-family:sans-serif;font-size:12.8px"><strong><font size="4">Links</font></strong></p><ul style="font-size:12.8px;font-family:"helvetica neue",helvetica,arial,sans-serif"><li style="margin-left:15px"><strong style="font-family:sans-serif">Code Documentation</strong><ul><li style="margin-left:15px"><font face="sans-serif" style="font-size:15px"><span style="font-size:12.8px">Lengauer Tarjan Dominator Tree (pgr_lengauerTarjanDominatorTree )- </span></font><a href="https://docs.pgrouting.org/3.2/en/pgr_lengauerTarjanDominatorTree.html" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://docs.pgrouting.org/3.2/en/pgr_lengauerTarjanDominatorTree.html</a></li><li style="font-family:sans-serif;margin-left:15px">Bipartite (<code>pgr_bipartite</code>) - <a href="https://docs.pgrouting.org/3.2/en/pgr_bipartite.html" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://docs.pgrouting.org/3.2/en/pgr_bipartite.html</a></li></ul></li><li style="font-family:sans-serif;margin-left:15px"><strong>Tags</strong><ul><li style="margin-left:15px"><a href="https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-prakashupes-lengauerTarjanDominatorTree-bipartite" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-prakashupes-lengauerTarjanDominatorTree-bipartite</a><br></li><li style="margin-left:15px"><a href="https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-prakashupes-common-spanning-tree" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-prakashupes-common-spanning-tree</a><br></li></ul></li><li style="font-family:sans-serif;margin-left:15px"><strong>Pull Requests</strong><ul><li style="margin-left:15px">Final pull request (<a href="https://github.com/pgRouting/pgrouting/pull/1608" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">#1608</a>).</li><li style="margin-left:15px">Pull Request for removing links from linkcheck_ignore (<a href="https://github.com/pgRouting/pgrouting/pull/1609" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">#1609</a>).</li><li style="margin-left:15px">Intermediate pull requests - <a href="https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+is%3Aclosed+author%3Aprakashupes" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+is%3Aclosed+author%3Aprakashupes</a></li></ul></li><li style="font-family:sans-serif;margin-left:15px"><strong>Project Documentation (Wiki Page)</strong><ul><li style="margin-left:15px"><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Lengauer-Tarjan-dominator-tree-and-Bipartite" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Lengauer-Tarjan-dominator-tree-and-Bipartite</a><br></li></ul></li><li style="font-family:sans-serif;margin-left:15px"><strong>Images</strong><ul><li style="margin-left:15px">pgr_lengauerTarjanDominatorTree (<a href="https://drive.google.com/file/d/1_3yn0PmF_OeBcw2yTfv9GP-sk9vdAiLA/view?usp=drivesdk" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://drive.google.com/file/d/1_3yn0PmF_OeBcw2yTfv9GP-sk9vdAiLA/view?usp=drivesdk</a>)</li><li style="margin-left:15px">pgr_bipartie (<a href="https://drive.google.com/file/d/1YHxv8yMkNYuogd2sgnJeJtOAK0f1Uhqd/view?usp=drivesdk" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://drive.google.com/file/d/1YHxv8yMkNYuogd2sgnJeJtOAK0f1Uhqd/view?usp=drivesdk</a>)</li></ul></li></ul><p style="font-family:sans-serif;font-size:12.8px"><strong>Media</strong></p><ul style="font-family:sans-serif;font-size:12.8px"><li style="margin-left:15px"><strong>Slide Demonstration</strong> - <a href="https://docs.google.com/presentation/d/1uvQc4GUUYr1pzRH4KfwOg5YoRZ6TFC8bMQw81QUjnfA/edit?usp=drivesdk" style="text-decoration-line:none;color:rgb(66,133,244)" rel="noreferrer noreferrer" target="_blank">https://docs.google.com/presentation/d/1uvQc4GUUYr1pzRH4KfwOg5YoRZ6TFC8bMQw81QUjnfA/edit?usp=drivesdk</a></li></ul><p style="font-family:sans-serif;font-size:12.8px">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.</p><p style="font-family:sans-serif;font-size:12.8px">Thanks and Regards,</p><p style="font-family:sans-serif;font-size:12.8px">Prakash Tiwari</p></div>