[pgrouting-dev] GSoC 2020 - Final Report - Implement Boyer Myrvold Planarity Testing and Make Connected in pgRouting

[Himanshu Raj]

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 an incredible experience! 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* - GSoC 2020 Implement Boyer Myrvold Planarity Testing and Make
Connected in 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::boyer_myrvold_planarity_test* 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 *undirected* graphs. It has a linear time complexity of *O(|V|)*.
   - *Boost::make_connected* 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 *undirected* graphs. It has a linear time complexity
   of *O(|V| + |E|)*.

*State of the Project Before GSoC* - pgRouting did not have any of the
proposed algorithms implemented.

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

   - The Boyer Myrvold Planarity Testing Algorithm (pgr_isPlanar) 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.
   - The Make Connected Algorithm (pgr_makeConnected) can be used to get
   the minimum list of edges to make a graph connected. This function is also
   applicable only for undirected graphs.

*Potential Future Work*

   - More planar graph functions
   <https://www.boost.org/doc/libs/1_53_0/libs/graph/doc/planar_graphs.html>
   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.
   - A new function pgr_make_biconnected_planar
   <https://www.boost.org/doc/libs/1_53_0/libs/graph/doc/make_biconnected_planar.html>
   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.
   - A new function pgr_make_maximal_planar
   <https://www.boost.org/doc/libs/1_53_0/libs/graph/doc/make_maximal_planar.html>
   can also be developed which will give the minimum list of edges that can
   make a given graph maximal planar.

*Links*

   - *Code Documentation*
      - Boyer Myrvold Planarity Testing (pgr_isPlanar) -
      https://docs.pgrouting.org/dev/en/pgr_isPlanar.html
      - Make Connected (pgr_makeConnected) -
      https://docs.pgrouting.org/dev/en/pgr_makeConnected.html
   - *Tag*
      -
      https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2020-rajhim2-isPlanar-makeConnected
   - *Pull Requests*
      - Final pull request (#1605
      <https://github.com/pgRouting/pgrouting/pull/1605>).
      - Pull Request for removing links from linkcheck_ignore (#1606
      <https://github.com/pgRouting/pgrouting/pull/1606>).
      - Intermediate pull requests -
      https://github.com/pgRouting/GSoC-pgRouting/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+author%3Arajhim2
   - *Project Documentation (Wiki Page)*
      -
      https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Implement-Boyer-Myrvold-Planarity-Testing-and-Make-Connected-in-pgRouting
   - *Images*
      - pgr_isPlanar (
      https://drive.google.com/file/d/1TRGiKgWOTUlt9CTHYNdnyGimuLaoe-2L/view?usp=sharing
      )
      - pgr_makeConnected (
      https://drive.google.com/file/d/1YpeaC05axnkStnYXjLd8gPUWT7NrMsPS/view?usp=sharing
      )

*Media*

   - *Slide Demonstration* -
   https://docs.google.com/presentation/d/1odtr2sjBNar306gunpWbeghlNHgSLGyZR1S5avMRUOk/edit?usp=sharingslide=id.g5fc0475bda_1_54

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.

Best Regards,

Himanshu Raj
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20200823/f6d27014/attachment.html>