Skip to content

GSoC 2020 Implement Boyer Myrvold Planarity Testing and Make Connected in pgRouting

Jump to bottom Edit New page
Himanshu Raj edited this page Aug 25, 2020 · 15 revisions

Table of Contents

Proposal

Brief Description

  • ​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|).

I propose to add the above two algorithms to pgRouting during the GSoC period.

State of the Project Before GSoC

  • pgRouting currently does not have these algorithms implemented.

Deliverables

  1. Implementation of pgr_isPlanar() for pgRouting.
  2. Implementation of pgr_makeConnected() for pgRouting.
  3. Documentation, test, pgTap of above implemented functions.

Participants

Title GitHub Handle Name
1st Mentor @cvvergara Vicky Vergara
2nd Mentor @dkastl Daniel Kastl
Student Developer @rajhim2 Himanshu Raj

Timeline

Community Bonding Period (May 4th - June 1st)

  • Set up the development environment.
  • Interact with mentors, introduce myself to the community, and actively get involved in the discussion.
  • Make a wiki page for setting up TODO lists and weekly reports.
  • Getting familiar with the community, the BGL docs.
  • Get familiar with the PgRouting architecture.
  • Develop a better understanding of PostgreSQL, PostGIS, Pl/pgSQL, and how they interact with pgRouting.
  • Get familiar with postgreSQL procedural language.
  • Go through pgTap to create unit tests for PostgreSQL.
  • Learn to create unit tests using pgTap.
  • Implement simple dummy functions to better understand pgRouting.

Note: Due to COVID-19 our Institute exams have been shifted. After discussing with mentors I have planned to complete some work of the official coding period in the community bonding period. So I will be having some buffer time when exams are held.

First Coding Period (June 1st - June 29th)

Week 1 (June 1st - June 8th)

  • Developing pgr_isPlanar() starts.
  • Create a basic skeleton for C, C++, SQL code, and for documentation and tests.

Week 2 (June 8th - June 15th)

  • Prepare user documentation.
  • Read data from PostgreSQL.
  • Transform results to C++ containers suitable for using with Boost.

Week 3 (June 15th - June 22nd)

  • Create the necessary class wrappers for the Boost function.
  • Process the data with the Boost function.
  • Transform results to C containers suitable for passing to PostgreSQL.

Week 4 (June 22nd - June 29th)

  • Prepare user documentation.
  • Create suitable queries using the sample data of the pgRouting documentation.
  • Create the first term report.

Second Coding Period (June 29th - July 27th)

Week 5 (June 29th - July 6th)

  • Work on feedback provided from the first evaluation.
  • Developing pgr_makeConnected() starts.
  • Create a basic skeleton for C, C++, SQL code, and for documentation and tests.

Week 6 (July 6th - July 13th)

  • Read data from PostgreSQL.
  • Transform data to C++ containers suitable for using with Boost.

Week 7 (July 13th - July 20th)

  • Create the necessary class wrappers for the Boost function.
  • Process the data with the Boost function.
  • Transform results to C containers suitable for passing to PostgreSQL.

Week 8 (July 20th - July 27th)

  • Prepare user documentation.
  • Create suitable queries using the sample data of the pgRouting documentation.
  • Create the first term report.

Third Coding Period (July 27th - August 24th)

Week 9 (July 27th - August 3rd)

  • Work on feedback provided from the second evaluation.
  • Tests for function pgr_​isPlanar().
    • create pgTap tests to check no server crash.
    • create pgTap unit tests for expected results for different small graphs:
      • one vertex graph
      • one edge graph
      • two edge graph
      • cycle graph with 3 edges

Week 10 (August 3rd - August 10th)

  • Tests for function pgr_makeConnected().
    • create pgTap tests to check no server crash.
    • create pgTap unit tests for expected results for different small graphs:
      • one vertex graph
      • one edge graph
      • two edge graph
      • cycle graph with 3 edges

Week 11 (August 10th - August 17th)

Week 12 (August 17th - August 24th)

  • Preparation of final report.

Log of Pull Requests

Pull Request Description Date Status
#1606 GSoC 2020 Removed links from linkcheck_ignore August 19th, 2020 Merged
#1605 [GSoC-2020] Experimental Functions - pgr_makeConnected, pgr_isPlanar August 18th, 2020 Merged
#132 Himanshu GSoC-2020 Week [11] August 15th, 2020 Merged
#119 Himanshu GSoC-2020 Week [10] August 7th, 2020 Merged
#115 Himanshu GSoC-2020 Week [9] August 2nd, 2020 Merged
#74 Himanshu GSoC-2020 Week [8] July 25th, 2020 Merged
#66 pgr_makeConnected GSoC-2020 Week [7] Part 2 July 19th, 2020 Merged
#63 pgr_makeConnected GSoC-2020 Week [7] July 14th, 2020 Merged
#58 pgr_makeConnected GSoC-2020 Week [6] July 12th, 2020 Merged
#52 pgr_makeConnected GSoC-2020 Week [5] July 05th, 2020 Merged
#49 pgr_boyerMyrvold GSoC-2020 Week [4] June 28th, 2020 Merged
#47 pgr_boyerMyrvold GSoC-2020 Week [3] June 21th, 2020 Merged
#42 pgr_boyerMyrvold GSoC-2020 Week [2] June 14th, 2020 Merged
#41 Himanshu GSoC-2020 Week [1] June 06th, 2020 Merged
#36 Rebase to 3.0.0 and GSoC 2020 Week [0] May 25th, 2020 Merged

Slides

Final Report

The below report was sent to the GSoC mailing list of OSGeo which can be found in SoC and pgrouting-dev

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_planar 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 can also be developed which will give the minimum list of edges that can make a given graph maximal planar.

Links

Media

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

Weekly Reports

Third Evaluation Period (July 27th - August 24th)

Week 12 (August 17th - August 24th)

  • What did I get done this week?

  • What do I plan on doing next week?

    • Prepare for final evaluation of my mentors.

  • Am I blocked on anything?

    • No, I don't have any blocking issues.

Week 11 (August 10th - August 17th)

  • What did I get done this week?

    • Moved the contents of makeConnected directory into components directory. This was done because makeConnected function is more related to the components directory.
    • Modified the coding implementation of the function pgr_makeConnected() and pgr_isPlanar. Included the try catch block for boost calls. Included CHECK_FOR_INTERRUPTS() snippet for pgr_isPlanar() before boost calls to catch cancellation from user.
      • Modified the .hpp file in this directory include/components/- pgr_makeConnected.hpp
      • Modified the .hpp file in this directory include/planar/ - pgr_boyerMyrvold.hpp
    • Modified the documentation of pgr_makeConnected(). Renamed the output columns to seq, start_vid and end_vid. This was done to make the output columns similar to the already existing functions in the pgRouting.
      • Modified the doc file in this directory doc/components/- pgr_makeConnected.rst, CMakeLists.txt
      • Modified the docqueries files in this directory docqueries/components/- doc-pgr_makeConnected.test.sql, doc-pgr_makeConnected.result, test.conf, CMakeLists.txt.
    • Modified documentation for the function components-family. Added the function pgr_makeConnected() in the experimental section of components-family.
      • Modified the doc file in this directory doc/components/- pgr_components-family.rst.
      • Modified the experimental section files in this directory doc/src/- experimental.rst.
    • Completed the pgTAP tests of pgr_isPlanar() in types_check which were earlier in TODO list.
      • Modified the pgtap tests file in this directory pgtap/planar/isPlanar/- types_check.sql.
    • Modified the pgTAP tests of pgr_makeConnected() according to the new modified documentation.
      • Modified the pgtap tests file in this directory pgtap/components/makeConected/- types_check.sql.
    • Created a tag 2020-rajhim2-isPlanar-makeConnected of the work product done till week 11.
    • Merged a pull request with all these changes (#132).
    • Opened a pull request with my final work product to be merged in develop branch of pgRouting (#1605).

  • What do I plan on doing next week?

    • Merge the pull request (#1605) after all the mentors review and approve.
    • Implement the remaining pgTAP tests of pgr_isPlanar() that are currently in todo.
    • Generate a video of my contributions using gsource and ffmpeg.
    • Complete my work product of the program and make a PR to the develop branch with all the files.

  • Am I blocked on anything?

    • No

Week 10 (August 3rd - August 10th)

  • What did I get done this week?

    • Modified the coding implementation of the function pgr_makeConnected() . Included the CHECK_FOR_INTERRUPTS() to before boost calls to catch cancellation from user.

      • Modified the .hpp file in this directory include/makeConnected/- pgr_makeConnected.hpp

    • Modified the documentation of pgr_isPlanar(). Included the image of non-planar graph in Additional Example of documentation. The image of non-planar graph was generated using QGIS. I used three layers to generate the image i.e., planar, Edges, and Vertices.

      • Modified the doc file in this directory doc/isPlanar/- pgr_isPlanar.rst, CMakeLists.txt
      • Modified the docqueries files in this directory docqueries/isPlanar/- doc-pgr_isPlanar.test.sql, doc-pgr_isPlanar.result, test.conf, CMakeLists.txt.
      • Added the image in the directory doc/isPlanar/images - nonPlanar.png, CMakeLists.txt

    • Modified documentation for the function pgr_makeConnected(). Earlier it had too many example queries in the documentation. Removed the addtional queries.

      • Modified the doc file in this directory doc/makeConnected/- pgr_makeConnected.rst, CMakeLists.txt
      • Modified the docqueries files in this directory docqueries/makeConnected/- doc-pgr_makeConnected.test.sql, doc-pgr_makeConnected.result, test.conf, CMakeLists.txt.

    • Modified the pgTAP tests of pgr_isPlanar() to include types_check and no_crash_test in TODO.

      • Modified the pgtap tests file in this directory pgtap/planar/isPlanar/- edge_cases.sql, inner_query.sql, types_check.sql, no_crash_test.sql .

    • Modified the pgTAP tests of pgr_makeConnected() to include new format of types_check.

      • Modified the pgtap tests file in this directory pgtap/makeConnected/makeConected/- types_check.sql.

    • Merged a pull request with all these changes (#119).

  • What do I plan on doing next week?

    • Implement the remaining pgTAP tests of pgr_isPlanar() that are currently in todo.
    • Generate a video of my contributions using gsource and ffmpeg.
    • Make a presentation of my work and functions which I have Implemented.
    • Complete my work product of the program and make a PR to the develop branch with all the files.

  • Am I blocked on anything?

    • No

Week 9 (July 27th - August 3rd)

  • What did I get done this week?

    • Completed with coding implementation of the function pgr_isPlanar(). It is now working as a true/false function.

      • Modified the .hpp file in this directory include/planar/- pgr_boyerMyrvold.hpp

    • Completed the documentation of pgr_isPlanar() which provides a short description of the function, sample usage of the function through sample queries and results, tables that explain the input parameters as well as output parameters and finally reference links to Boost's boyerMyrvold documentation. Also added the additional examples section in the documentation.

      • Modified the doc file in this directory doc/isPlanar/- pgr_isPlanar.rst, CMakeLists.txt
      • Modified the docqueries files in this directory docqueries/isPlanar/- doc-pgr_isPlanar.test.sql, doc-pgr_isPlanar.result, test.conf, CMakeLists.txt.

    • Completed documentation for the function pgr_makeConnected() which provides a short description of the function, sample usage of the function through sample queries and results, tables that explain the input parameters as well as output parameters and finally reference links to Boost's make_connected() documentation.

      • Modified the doc file in this directory doc/makeConnected/- pgr_makeConnected.rst, CMakeLists.txt
      • Modified the docqueries files in this directory docqueries/makeConnected/- doc-pgr_makeConnected.test.sql, doc-pgr_makeConnected.result, test.conf, CMakeLists.txt.

    • Modified the pgTAP directory structure for my functions which may become the standard directory structure for pgRouting in future. Modified the names of pgTAP test files because earlier it was redundant to include name of function in every file.

      • Modified the pgtap tests file in this directory pgtap/planar/isPlanar/- edge_cases.sql, inner_query.sql, types_check.sql, no_crash_test.sql .
      • Modified the pgtap tests file in this directory pgtap/makeConnected/makeConected/- edge_cases.sql, inner_query.sql, types_check.sql, no_crash_test.sql .

    • Merged a pull request with all these changes (#115).

  • What do I plan on doing next week?

    • Implement the suggested changes for pgtap tests for the functions pgr_isPlanar() and pgr_makeConnected().
    • Add the CHECK_FOR_INTERRUPTS() snippet before the boost calls to catch cancellation from postgres user.
    • Use .editorconfig to make my code as it is required in pgRouting coding style.

  • Am I blocked on anything?

    • No

Second Evaluation Period (June 29th - July 27th)

Week 8 (July 20th - July 27th)

  • What did I get done this week?

    • Added documentation for the function pgr_makeConnected() which provides a short description of the function, sample usage of the function through sample queries and results, tables that explain the input parameters as well as output parameters and finally reference links to Boost's make_connected() documentation.
      • Modified the doc file in this directory doc/makeConnected/- pgr_makeConnected.rst, CMakeLists.txt
      • Modified the docqueries files in this directory docqueries/makeConnected/- doc-pgr_makeConnected.test.sql, doc-pgr_makeConnected.result, test.conf, CMakeLists.txt.
    • Prepared a shared doc file to show possible applications of my implemented functions to my mentor. My mentor suggested some changes to the doc file and my functions.
    • My mentor reviewed my code till now and suggested the changes to the function pgr_boyerMyvold( ).The suggested changes were - a true/false function instead of returning whole graph, pgTAP tests for 2 edges disconnected graphs and smaller non-planar graphs.
    • So, I made copies of the directories of pgr_boyerMyrvold() to have a backup function. Started working for the suggested changes on the backup function.
    • Merged a pull request with all these changes (#74).

  • What do I plan on doing next week?

    • Implement the suggested changes for the function pgr_boyerMyrvold() i.e. a true / false function, pgTAP tests for 2 edges disconnected graphs and smaller non-planar graphs.
    • Complete the remaining documentation of the function pgr_makeConnected() i.e. complete the Additional Examples section of the doc.
    • Finalize the shared doc file of implemented functions report and move it to the wiki.

  • Am I blocked on anything?

    • No

Week 7 (July 13th - July 20th)

  • What did I get done this week?

    • Removed all the redundant debug files, comments and headers and headers.
    • Added all the pgTap Tests for my function pgr_makeConnected:
      • Completed function input/output parameter type-check pgTap tests.
      • Completed algorithm edge-cases pgTap tests.
      • Completed additional inner-query pgTap tests.
      • Completed additional no crash pgTap tests.
      • Completed additional rows consistency pgTap tests.
      • Modified the files in this directory pgtap/makeConnected/- makeConnected-edge-cases.sql, makeConnected-innerQuery.sql, makeConnected-types-check.sql, no_crash_test-makeConnected.sql
    • Modified and completed the documentation of my previous function pgr_boyerMyrvold() based on the recommendations given by my mentor during Bolsena Code Spirint.
    • Modified the doc file in this directory doc/planarGraph/- pgr_boyerMyrvold.rst, CMakeLists.txt
    • Modified the docqueries files in this directory docqueries/planarGraph/- doc-pgr_boyerMyrvold.test.sql, doc-pgr_boyerMyrvold.result.
    • Performed the rebase to 3.1.0 and resolved all code conflicts.
    • Merged a pull request with all these changes (#63).
    • Merged another pull request after rebase with all these changes (#66).

  • What do I plan on doing next week?

    • The documentation of pgr_makeConnected is remaining. So, in the coming week, I plan to add all the documentation files for my function.
    • In next week, I will also make a doc file in which I will show the possible applications of my functions that could be implemented within pgRouting. My mentor will be reviewing my code next week. I will also refine the code based on my mentor's recommendations.

  • Am I blocked on anything?

    • No

  • Meetings Attended

    • July 14: Performed the rebase to 3.1.0 and resolved all code conflicts.

Week 6 (July 6th - July 13th)

  • What did I get done this week?

    • Completed with coding implementation of boost Graph function pgr_makeConnected. The correct set of rows are getting returned at the ouput.
    • Modified the coding implementation of my previous function pgr_boyerMyrvold() based on my mentor's reviews during Bolsena Code Spirint.
    • Modified and added all the required files for the implementation of my function:
      • include/drivers/makeConnected/ - makeConnected.h
      • pgtap/makeConnected/- makeConnected-edge-cases.sql, makeConnected-innerQuery.sql, makeConnected-types-check.sql, no_crash_test-makeConnected.sql
      • Modified sql/makeConnected/ - CMakeLists.txt, _makeConnected.sql, makeConnected.sql
      • Modified src/makeConnected/ - CMakeLists.txt, makeConnected.c, makeConnected_driver.cpp
      • Modified the configuration.conf file in the root of the repository
    • Modified the .github/workflows/ubuntu.yml to fix the ubuntu build error.
    • Fixed all Travis CI and Appveyor warnings and errors.
    • Merged a pull request with all these changes (#58).

  • What do I plan on doing next week?

    • The pgTAP tests of pgr_makeConnected are remaining. So, in the coming week, I plan to add all the pgTAP tests - Server no crash test for null parameters, parameters type check, inner query tests, and the unit tests - one vertex, one edge, two edges, cycle with 3 edges, etc.
    • I will also be working on the documentation of this function.
    • I will also be modifying the pgTap tests implementation, documentation of my previous function pgr_boyerMyrvold() based on my mentor's reviews which was given during the Bolsena Code Spirint.

  • Am I blocked on anything?

    • No, I don't have any blocking issues.

Week 5 (June 29th - July 6th)

  • What did I get done this week?

    • Completed designing my next boost Graph function pgr_makeConnected. Completed with designing of the function. Able to read data from postgresql. Currently the data returned after the query is 0 row.
    • Modified and added all the required files for the implementation of my function:
      • include/drivers/makeConnected/ - makeConnected.h
      • pgtap/makeConnected/- makeConnected-edge-cases.sql, makeConnected-innerQuery.sql, makeConnected-types-check.sql, no_crash_test-makeConnected.sql
      • Modified sql/makeConnected/ - CMakeLists.txt, _makeConnected.sql, makeConnected.sql
      • Modified src/makeConnected/ - CMakeLists.txt, makeConnected.c, makeConnected_driver.cpp
      • Modified the function signatures in sql/sigs/pgrouting--3.0.0.sig
      • Modified the configuration.conf file in the root of the repository
    • Merged a pull request with all these changes (#52).
    • Attended meetings which were a part of the Bolsena Online Code Sprint 2020:
      • June 30th: Discussed and presented all the functions, code, documentation, pgTap Tests which I had done during the first phase evaluations for the GSoC '20 program, with the mentor and pgRouting community who reviewed the work and suggested some modifications.
      • July 2nd: Attended and reviewed the workshop of MobilityDB team with pgRouting and PostGIS. It came under pgRouting release 3.0.1

  • What do I plan on doing next week?

    • Currently the data returned after the query for my new function pgr_makeConnected() is 0 row.
    • The coding of .hpp file in the directory include/makeConnected for function pgr_makeConnected() is remaining. So, in the coming week, I plan to study and implement the function boost::make_connected() in .hpp file.
    • I will also be modifying the pgTap tests implementation, documentation of my previous function pgr_boyerMyrvold() based on my mentor's reviews which was given during the Bolsena Code Spirint.

  • Am I blocked on anything?

    • No, I don't have any blocking issues.

First Evaluation Period (June 1st - June 29th)

Week 4 (June 22nd - June 29th)

  • What did I get done this week?

    • Removed unnecessary header files, redundant code and comments from the files.
    • Added name to the contributors list in pgRouting.
    • Added documentation for the function pgr_boyerMyrvold() which provides a short description of the function, sample usage of the function through sample queries and results, tables that explain the input parameters as well as output parameters and finally reference links to Boost's Boyer Myrvold planarity documentation as well as Wikipedia's explanation of the Planarity explanation.
    • Modified the doc file in this directory doc/planarGraph/- pgr_boyerMyrvold.rst, CMakeLists.txt
    • Modified the docqueries files in this directory docqueries/planarGraph/- doc-pgr_boyerMyrvold.test.sql, doc-pgr_boyerMyrvold.result, test.conf, CMakeLists.txt.
    • Completed the pgr_boyerMyrvold() function with coding, documentation and pgTap Tests.
    • Started designing my next planar graph boost function boost::make_connected().
      • Added sql files in this directory sql/makeConnected - makeConnected.sql, _makeConnected.sql, CMakeLists.txt
    • Merged a pull request with all these changes (#49).
    • Fixed all Travis CI, Appveyor warnings and errors.

  • What do I plan on doing next week?

    • Complete designing of next boost function boost::make_connected().
    • I will be creating a basic skeleton for C, C++, SQL code, and for the documentation and tests. For this, I will be adding all the required files in their required directories, containing basic code related with the new function. I will also add the function name in the configuration file and update the signature file accordingly.

  • Am I blocked on anything?

    • Currently I am getting error on doxygen dot files on my pc.
    • Error: /home/himanshu/GSoC-pgRouting/build/doxygen/html/inline_dotgraph_2.dot: syntax error in line 14 near '-'
    • Apart from this I don't have any blocking issues.

Week 3 (June 15th - June 22nd)

  • What did I get done this week?

    • Previously the data returned after the query was displayed incorrectly at the respective columns. One of the columns was showing garbage values. I finally fixed this bug.
    • Added all the pgTap Tests for my function pgr_boyerMyrvold:
      • Completed function input/output parameter type-check pgTap tests.
      • Completed algorithm edge-cases pgTap tests.
      • Completed additional inner-query pgTap tests.
      • Completed additional no crash pgTap tests.
      • Modified the files in this directory pgtap/planarGraph/- boyerMyrvold-edge-cases.sql, boyerMyrvold-innerQuery.sql, boyerMyrvold-types-check.sql, no_crash_test-boyerMyrvold.sql
    • Merged a pull request with all these changes (#47).

  • What do I plan on doing next week?

    • The documentation of pgr_boyerMyrvold is remaining. So, in the coming week, I plan to add all the documentation files for my function.
    • Meanwhile, I will also start preparation for my next planar Graph boost algorithm.

  • Am I blocked on anything?

    • Currently I am getting error on doxygen dot files on my pc.
    • Error: /home/himanshu/GSoC-pgRouting/build/doxygen/html/inline_dotgraph_2.dot: syntax error in line 14 near '-'
    • Apart from this I don't have any blocking issues.

Week 2 (June 8th - June 15th)

  • What did I get done this week?

    • Started coding on my boost planar Graph function pgr_boyerMyrvold. Completed with coding of the function. Able to read data from postgresql. Currently the data which returns after the query is not getting displayed properly.
    • Modified and added all the required files for the implementation of my function:
      • include/drivers/planarGraph/ - boyerMyrvold.h
      • pgtap/planarGraph/- boyerMyrvold-edge-cases.sql, boyerMyrvold-innerQuery.sql, boyerMyrvold-types-check.sql, no_crash_test-boyerMyrvold.sql
      • Modified sql/planarGraph/ - CMakeLists.txt, _boyerMyrvold.sql, boyerMyrvold.sql
      • Modified src/planarGraph/ - CMakeLists.txt, boyerMyrvold.c, boyerMyrvold_driver.cpp
      • Modified the function signatures in sql/sigs/pgrouting--3.0.0.sig
    • Merged a pull request with all these changes (#42).

  • What do I plan on doing next week?

    • Currently the data returned after the query is displayed incorrectly at the respective columns. I will be fixing this bug.
    • The pgTAP tests of pgr_boyerMyrvold are remaining. So, in the coming week, I plan to add all the pgTAP tests - Server no crash test for null parameters, parameters type check, inner query tests, and the unit tests - one vertex, one edge, two edges, cycle with 3 edges, etc after the above bug is removed.
    • I will also be working on the documentation of this function.

  • Am I blocked on anything?

    • Currently the data returned after the query is displayed incorrectly at the respective columns. One of the columns is showing garbage values. I am trying to fix this bug.
    • Apart from this I don't have any blocking issues.

Week 1 (June 1st - June 7th)

  • What did I get done this week?

    • Continued coding on my function pgr_kargersContraction. Completed with designing the skeleton of the function. Able to read data from postgresql. Currently it is returning (0 rows) on the query.
    • Modified and added all the required files for the implementation of my function:
      • doc/kargersContraction/ - CMakeLists.txt, pgr_kargersContraction.rst
      • docqueries/kargersContraction/ - CMakeLists.txt, doc-pgr_kargersContraction.result, doc-pgr_kargersContraction.test.sql, test.conf
      • include/drivers/kargersContraction/ - kargersContraction.h
      • pgtap/kargersContraction/- kargersContraction-edge-cases.sql, kargersContraction-innerQuery.sql, kargersContraction-types-check.sql, no_crash_test-kargersContraction.sql
      • Modified sql/kargersContraction/ - CMakeLists.txt, _kargersContraction.sql, kargersContraction.sql
      • Modified src/kargersContraction/ - CMakeLists.txt, kargersContraction.c, kargersContraction_driver.cpp
      • Modified the function signatures in sql/sigs/pgrouting--3.0.0.sig
    • Merged a pull request with all these changes (#41).
    • Fixed all the Travis-CI warnings and errors.
    • Discussed about the areaContraction technique and its algorithm in the meeting discussions June 5th and June 6th.

  • What do I plan on doing next week?

    • Based on the discussion of June 5th and June 6th with my mentor I will start coding a new boost function which will give support of planar graph algorithms in pgRouting.
    • I will be designing the skeleton and C++ containers of this new boost function in the coming week.
    • Meanwhile, I will be verifying and designing the contraction function pgTap Tests manually. I will be planning the pseudo-code of the function.
    • I will be modifying the name of my contraction function from pgr_kargersContraction() to pgr_areaContraction() and do the same for all the header/c/c++ files.

  • Am I blocked on anything?

    • No, currently I don't have any blocking issue.

Community Bonding Week 3 ( May 17 - May 24)

  • Added some basic dummy sql functions on my forkpgr_funnyDijkstra , pgr_funnyContraction
  • To perform rebase on my forked repository : I executed these commands on my forked repository.
    git checkout him
    git fetch upstream
    git rebase upstream/master
    git push -f
  • Now I want to merge these basic dummy changes in my GSoC-pgRouting repo branch edgeContract: https://github.com/pgRouting/GSoC-pgRouting/tree/edgeContract. This is just being done to check how this whole system works.
  • Week 1 Coding Period
    • Designing of pgr_kargersContraction function.
    • Created a basic skeleton for C, C++, SQL code.
  • Merged a pull request with all these changes (#36).

Meeting Discussions

  1. May 6th

    • Understood the file structure of the functions of pgRouting - sql, src, include, pgtap, doc, docqueries.
    • Analyzed the code sequence of the pgr_dijkstra function, so that any other function developed would follow the same code sequence.

  2. May 7th

    • Understood the testing schema of pgRouting.
    • Understood how is a test designed, and how to do the testing using pgTAP (types-check, inner-query, no-crash-test, edge-cases) and docqueries (creating custom tests and verifying).

  3. May 10th

    • Understood how to design a function.
    • Analyzed how to store the graph in the database and the functions related to that (e.g. functions in edges_input.c).

  4. May 12th

    • Set up a branch named edgeContract on the pgRouting GSoC-repository for sending pull requests.
    • Learned how to create a simple dummy function (pgr_funnyDijkstra, pgr_span2trees).

  5. May 15th

    • Understood the releases of pgRouting (alpha, beta, rc1) and that v3.0.0 will be released later.
    • Understood the Continuous Integration on Travis CI, Appveyor and GitHub build, and how to report the build problems, if encountered.

  6. May 28th

    • Discussion regarding Contraction documentation in pgRouting.
    • Discussion about existing Contraction techniques dead end and linear contraction.
    • How to process the contracted graph to use other functions available in pgRouting
    • What changes need to be done to edge_table and edge_table_vertices_pgr to use contracted graph with other functions.

  7. June 1st

    • Discussion about pgr_dijkstra with SQL combinations.
    • How we should be approaching the GSoC-2020.
      • When mentors are not available do documentation of your functions and code.
      • It is a full time commitment and community expects 40 hrs of work from us.
      • Merge our generated pull requests by the end of the week.

  8. June 5th

    • Thorough discussion about areaContraction technique and algorithm.
    • How to use the small contracted graphs to make the contracted graph of bigger size.

  9. June 6th

    • pgr_dijkstra many to many as a way to get the results of areaContraction.
    • Coding for a new boost function planar graph algorithms in pgRouting.
    • Based on this discussion I will be coding the planar graph algorithms till the time my mentor tells me to resume the contraction work. So , I will be working on planar graph algorithms for now.

  10. June 30

    • Discussed and presented all the functions, code, documentation, pgTap Tests which I had done during the first phase evaluations for the GSoC '20 program, with the mentor and pgRouting community who reviewed the work and suggested some modifications.

  11. July 2nd

    • Attended and reviewed the workshop of MobilityDB team with pgRouting and PostGIS. It came under pgRouting release 3.0.1 .

  12. July 12th

    • During mobilityDB workshop I installed postgresql 12. And when I started working on my function nothing got updated on database. So in this meeting on jitsi my mentor helped me to reconfigure the build and setup postgresql 12.

  13. July 14th

    • Performed the rebase to 3.1.0 and resolved all code conflicts.

Community Bonding Period (May 4th - June 1st)

  • Set up the development environment.
  • Interact with mentors, introduce myself to the community, and actively get involved in the discussion.
  • Set up a wiki page to keep track of weekly progress.
  • Add a wiki link to OSGeo's accepted student's wiki page.
  • Introduce myself and my project on OSGeo's SOC mailing list.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Develop a better understanding of PostgreSQL, PostGIS, Pl/pgSQL, and how they interact with pgRouting.
  • Learn to create unit tests using pgTap.
  • Implement simple dummy functions to better understand pgRouting.

Pre-Bonding Period (February 25th - March 31st)

References

  1. ​Boyer Myrvold Planarity Testing​ from Boost Graph Library.
  2. ​Planar Graphs​ from Boost Graph Library.
  3. ​Make Connected​ from Boost Graph Library.
  4. ​pgRouting Sample Data​.
  5. pgRouting Documentation.

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally