<div dir="ltr"><p>Hello everyone,</p>
<p>With GSoC coming to an end, I present to you the final report of my
work over the past three months! It has been an incredible experience!
This report is in accordance with the <a href="https://developers.google.com/open-source/gsoc/help/work-product" rel="nofollow">guidelines set by Google</a> and <a href="https://lists.osgeo.org/pipermail/soc/2020-August/004612.html" rel="nofollow">OSGeo GSoC Admins</a>.</p>
<p><strong>Title</strong> - GSoC 2020 Implement Boyer Myrvold Planarity Testing and Make Connected in pgRouting</p>
<p><strong>Organisation</strong> - pgRouting under OSGeo</p>
<p><strong>Abstract</strong> -
This GSoC project dealt with implementing two new graph algorithms in pgRouting. The algorithms are described as follows:</p>
<ul><li>
<strong>Boost::boyer_myrvold_planarity_test</strong> A graph is planar
if it can be drawn in two-dimensional space with no two of its edges
crossing. Such a drawing of a planar graph is called a plane drawing.
Every planar graph also admits a straight-line drawing, which is a plane
drawing where each edge is represented by a line segment. When a graph
has K5 or K3,3 as subgraph then the graph is not planar. This algorithm
is only applicable for <strong>undirected</strong> graphs. It has a linear time complexity of <strong>O(|V|)</strong>.</li><li>
<strong>Boost::make_connected</strong> Adds the minimum number of edges
needed to make the input graph connected. The algorithm first identifies
all of the connected components in the graph, then adds edges to
connect those components together in a path. For example, if a graph
contains three connected components A, B, and C, make_connected will add
two edges. The two edges added might consist of one connecting a vertex
in A with a vertex in B and one connecting a vertex in B with a vertex
in C. 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><strong>State of the Project Before GSoC</strong> -
pgRouting did not have any of the proposed algorithms implemented.</p>
<p><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><li>The Boyer Myrvold Planarity Testing Algorithm (<code>pgr_isPlanar</code>)
can be used to check the planarity of a graph. It returns a boolean
value depending upon the planarity of a graph. This function is
applicable only for undirected graph.</li><li>The Make Connected Algorithm (<code>pgr_makeConnected</code>) can be
used to get the minimum list of edges to make a graph connected. This
function is also applicable only for undirected graphs.</li></ul>
<p><strong>Potential Future Work</strong></p>
<ul><li>More <a href="https://www.boost.org/doc/libs/1_53_0/libs/graph/doc/planar_graphs.html" rel="nofollow">planar graph functions</a>
can be added in the future. The Boyer Myrvold Planarity Testing can be
extended to give a planar embedding or a Kuratowski graph in the future
work.</li><li>A new function <a href="https://www.boost.org/doc/libs/1_53_0/libs/graph/doc/make_biconnected_planar.html" rel="nofollow"><code>pgr_make_biconnected_planar</code></a>
can also be developed which will give the minimum list of edges that
can make a given graph biconnected while preserving the planarity at
the same time.</li><li>A new function <a href="https://www.boost.org/doc/libs/1_53_0/libs/graph/doc/make_maximal_planar.html" rel="nofollow"><code>pgr_make_maximal_planar</code></a> can also be developed which will give the minimum list of edges that can make a given graph maximal planar.</li></ul>
<p><strong>Links</strong></p>
<ul><li>
<strong>Code Documentation</strong>
<ul><li>Boyer Myrvold Planarity Testing (<code>pgr_isPlanar</code>) - <a href="https://docs.pgrouting.org/dev/en/pgr_isPlanar.html" rel="nofollow">https://docs.pgrouting.org/dev/en/pgr_isPlanar.html</a>
</li><li>Make Connected (<code>pgr_makeConnected</code>) - <a href="https://docs.pgrouting.org/dev/en/pgr_makeConnected.html" rel="nofollow">https://docs.pgrouting.org/dev/en/pgr_makeConnected.html</a>
</li></ul>
</li><li>
<strong>Tag</strong>
<ul><li><a href="https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-rajhim2-isPlanar-makeConnected">https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-rajhim2-isPlanar-makeConnected</a></li></ul>
</li><li>
<strong>Pull Requests</strong>
<ul><li>Final pull request (<a href="https://github.com/pgRouting/pgrouting/pull/1605">#1605</a>).</li><li>Pull Request for removing links from linkcheck_ignore (<a href="https://github.com/pgRouting/pgrouting/pull/1606">#1606</a>).</li><li>Intermediate pull requests - <a href="https://github.com/pgRouting/GSoC-pgRouting/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+author%3Arajhim2">https://github.com/pgRouting/GSoC-pgRouting/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+author%3Arajhim2</a>
</li></ul>
</li><li>
<strong>Project Documentation (Wiki Page)</strong>
<ul><li><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Implement-Boyer-Myrvold-Planarity-Testing-and-Make-Connected-in-pgRouting">https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Implement-Boyer-Myrvold-Planarity-Testing-and-Make-Connected-in-pgRouting</a></li></ul>
</li><li>
<strong>Images</strong>
<ul><li>pgr_isPlanar (<a href="https://drive.google.com/file/d/1TRGiKgWOTUlt9CTHYNdnyGimuLaoe-2L/view?usp=sharing" rel="nofollow">https://drive.google.com/file/d/1TRGiKgWOTUlt9CTHYNdnyGimuLaoe-2L/view?usp=sharing</a>)</li><li>pgr_makeConnected (<a href="https://drive.google.com/file/d/1YpeaC05axnkStnYXjLd8gPUWT7NrMsPS/view?usp=sharing" rel="nofollow">https://drive.google.com/file/d/1YpeaC05axnkStnYXjLd8gPUWT7NrMsPS/view?usp=sharing</a>)</li></ul>
</li></ul>
<p><strong>Media</strong></p>
<ul><li>
<strong>Slide Demonstration</strong> - <a href="https://docs.google.com/presentation/d/1odtr2sjBNar306gunpWbeghlNHgSLGyZR1S5avMRUOk/edit?usp=sharingslide=id.g5fc0475bda_1_54" rel="nofollow">https://docs.google.com/presentation/d/1odtr2sjBNar306gunpWbeghlNHgSLGyZR1S5avMRUOk/edit?usp=sharingslide=id.g5fc0475bda_1_54</a>
</li></ul>
<p>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>Best Regards,</p>
<p>Himanshu Raj</p></div>