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 and OSGeo GSoC Admins.
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 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_planarcan 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_planarcan 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
- Boyer Myrvold Planarity Testing (
- Tag
- Pull Requests
- Final pull request (#1605).
- Pull Request for removing links from linkcheck_ignore (#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)
- Images
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