GSoC 2020 Depth First Search and Sequential Vertex Coloring - pgRouting/pgrouting GitHub Wiki

Table of Contents

Proposal

Brief Description

The project aims to add the following two algorithms in pgRouting during the GSoC ‘20 period:

  • Depth First Search

    • It is the implementation of a standard graph traversal algorithm for both directed graphs and undirected graphs.
    • It has been implemented in Boost Graph Library as two different algorithms - Boost::Depth First Search for directed graphs and Boost::Undirected DFS for undirected graphs.
    • One of its applications is to find any path in the graph from a source vertex to all other vertices.
    • It has a linear time complexity of O(|V| + |E|).

  • Sequential Vertex Coloring

    • It is an algorithm to compute the vertex coloring of a graph. This involves assigning colors to the vertices of a graph sequentially in such a way that no two adjacent vertices have the same color.
    • It has been implemented in the Boost Graph Library as Boost::Sequential Vertex Coloring for undirected graphs.
    • One of its applications is to check if a graph is bipartite.
    • It has a time complexity of O(|V| * (|d| + |k|)), where |d| and |k| are the maximum degree and the number of colors used in the graph, respectively.

The project also analyzes the behavior of several algorithms after ordering the input rows in a particular order.

State of the Project Before GSoC

pgRouting currently does not have these algorithms implemented.

  • Depth First Search is a standard graph searching algorithm and is used in various other already implemented algorithms such as Prim’s and Kruskal’s algorithm for finding MST. However, not a single standard function exists in pgRouting, either for directed graphs or for undirected graphs, i.e., pgRouting does not have it in the PostgreSQL functionality.

  • Sequential Vertex Coloring is not implemented before in pgRouting, and a single standard function does not exist.

Deliverables

  1. Implementation of Depth First Search algorithm: The function pgr_depthFirstSearch() must be constructed which will be applicable for both directed and undirected graphs, and it will return a possible ordering of the vertices of the graph during depth-first search traversal.

  2. Implementation of the Sequential Vertex Coloring algorithm: The function ​ pgr_sequentialVertexColoring() must be constructed, and it will return the colors to be assigned to the vertices of the graph, in sequential order.

Each implemented function will be delivered with the relevant documentation and the tests included.

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor @dkastl Daniel Kastl
2nd Mentor @cayetanobv Cayetano Benavent
Student Developer @krashish8 Ashish Kumar

Timeline

Community Bonding Period (May 4th - May 31st)

  • Set up the development environment.
  • Interact with mentors, introduce myself to the community, and actively get involved in the discussion.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Set up a wiki page to keep track of weekly progress.
  • 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.

Note:

Due to the Coronavirus pandemic, the University Exams have been shifted. As per the current schedule, the exams are likely to occur between June 1st - June 17th (Week 1 and Week 2) in my college. Therefore, I need to have a buffer time of those 2 weeks to utilize for the exams, and the amount of work accomplished in those weeks will be dependent on how much free time I get.

So, in order to ensure that the project is completed before the deadline, I plan to work during the latter part of the Community Bonding Period and complete the tasks of Week 1 and Week 2 during the Week -1 and Week 0 of the Community Bonding Period.

Week -1 (May 18th - May 24th)

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

Week 0 (May 25th - May 31st)

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

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

Week 1 (June 1st - June 7th)

  • Work on the feedback from the previous weeks, and complete any pending work.
  • Prepare for the forthcoming weeks.

Week 2 (June 8th - June 14th)

  • Work on the feedback from the previous weeks, and complete any pending work.
  • Prepare for the forthcoming weeks.

Week 3 (June 15th - June 21st)

  • 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 28th)

  • 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 26th)

Week 5 (June 29th - July 5th)

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

Week 6 (July 6th - July 12th)

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

Week 7 (July 13th - July 19th)

  • 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 26th)

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

Third Coding Period (July 27th - August 23rd)

Week 9 (July 27th - August 2nd)

  • Tests for function pgr_depthFirstSearch().
    • 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
  • Work on the feedback provided from the second evaluation.
  • Basic implementation of the function.
  • Basic testing.

Week 10 (August 3rd - August 9th)

  • Tests for function pgr_sequentialVertexColoring().
    • 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
  • Work on the feedback provided from the second evaluation.
  • Basic implementation of the function.
  • Basic testing.

Week 11 (August 10th - August 16th)

Week 12 (August 17th - August 23rd)

  • Preparation of final report.

Log of Pull Requests

Link to all the Pull Requests made in GSoC-pgRouting repository

Pull Request Description Date Status
#1604 [GSoC-2020] Fixed coloring family and pgr_sequentialVertexColoring documentation August 14th, 2020 Merged
#1602 [GSoC-2020] Removed the generated links from linkcheck_ignore August 10th, 2020 Merged
#1599 [GSoC-2020] Experimental Functions - pgr_depthFirstSearch, pgr_sequentialVertexColoring August 6th, 2020 Merged
#121 Code review GSoC-2020 Week 10 August 6th, 2020 Merged
#114 pgr_depthFirstSearch and code review GSoC-2020 Week 9 August 2nd, 2020 Merged
#108 Ashish GSoC-2020 Week 8 July 24th, 2020 Merged
List of PRs PRs and Issues labeled ordering July 24th, 2020 Merged
#65 Fixing ordering issues in v3 GSoC-2020 Week 7 July 18th, 2020 Merged
#59 pgr_sequentialVertexColoring GSoC-2020 Week 6 July 11th, 2020 Merged
#54 pgr_sequentialVertexColoring GSoC-2020 Week 5 July 4th, 2020 Merged
#50 pgr_sequentialVertexColoring GSoC-2020 Week 4 June 26th, 2020 Merged
#46 pgr_sequentialVertexColoring GSoC-2020 Week 3 June 19th, 2020 Merged
#43 pgr_depthFirstSearch GSoC-2020 Week 2 June 13th, 2020 Merged
#39 pgr_depthFirstSearch GSoC-2020 Week 1 June 6th, 2020 Merged
#38 pgr_depthFirstSearch GSoC-2020 Week 0 May 29th, 2020 Merged
#34 pgr_depthFirstSearch GSoC-2020 Week -1 May 25th, 2020 Merged

Slides

https://docs.google.com/presentation/d/1E0T8sKlQpSbfrv1xcSqF7GrLQ1JoodtZgZVMJGqW6sY/edit?usp=sharing

Final Report

(The below report was sent to the two mailing lists of OSGeo - SoC and pgrouting-dev)

Hello everyone,

With the GSoC period coming to an end, I hereby present the final report of my work, which I did over the past three months. It has been a great experience working with the pgRouting community and the mentors. This report is in accordance with the guidelines set by Google and OSGeo GSoC Admins.

  1. (a) Title: Depth First Search, Sequential Vertex Coloring, and analysis of Graph Input Ordering for pgRouting.
    (b) Organization: pgRouting under OSGeo.

  2. Abstract:

The GSoC project dealt with the implementation of two new graph algorithms in pgRouting:

(i) Depth First Search: It is the implementation of a standard graph traversal algorithm for both directed and undirected graphs. It has been implemented in Boost Graph Library as two different algorithms - boost::depth_first_search for directed graphs and boost::undirected_dfs for undirected graphs. One of its applications is to find a path in the graph from a source vertex to all other vertices. It has a linear time complexity of O(|V| + |E|).

(ii) Sequential Vertex Coloring: It is an algorithm to compute the vertex coloring of a graph. This involves assigning colors to the vertices of a graph sequentially in such a way that no two adjacent vertices have the same color. It has been implemented in the Boost Graph Library as boost::sequential_vertex_coloring for undirected graphs. One of its applications is to do a proper coloring of the graph or to check if a graph is bipartite. It has a time complexity of O(|V| * (d + k)), where |V| is the number of vertices, d is the maximum degree of the vertices in the graph, and k is the number of colors used.

The project also analyzed the behavior of several algorithms after ordering the input rows in a particular order.

  1. The state of the project before GSoC:

pgRouting did not have these two graph algorithms implemented.

(i) Depth First Search is a standard graph searching algorithm and is used in various other already implemented algorithms such as Prim’s and Kruskal’s algorithm for finding MST. However, not a single standard function exists in pgRouting, either for directed graphs or for undirected graphs.

(ii) The Sequential Vertex Coloring algorithm was not implemented before in pgRouting.

  1. The addition that my project brought to pgRouting:

The deliverables are code, documentation, documentation tests, and the pgTAP tests of the two functions.

(i) The Depth First Search algorithm is now a function of its own and is meant for general use. Moreover, it can be used to find a path in a graph from a source vertex to all other vertices.

(ii) The Sequential vertex coloring algorithm can be used to check if a graph is bipartite. It can also be used to color a geographical map, such that no two adjacent neighbors have the same color.

  1. Potential Future Work:

(i) Edge Coloring algorithm can be implemented, which assigns the color to the edges of a graph, unlike the Sequential Vertex Coloring algorithm, that assigns the color to the vertices.

(ii) Since the Sequential Vertex Coloring algorithm doesn't provide optimal coloring of the graph, other heuristic-based graph coloring algorithms, or planar graph algorithms can be implemented that can guarantee the coloring of the graph using a fixed number of available colors.

(iii) The third function pgr_maximumAdjacencySearch, was an additional idea. However, it can't be implemented because it was present in the Boost version 1.54.0 and later, and was not available for Boost v1.53.0. pgRouting has to cover a lot of Operating Systems and, in particular, for CENTOS 6, version 1.53 is the one that is installed automatically. This function may be implemented later, once CENTOS 6 ends the EOL.

  1. Links:

(i) Code Documentation:

(ii) Tags:

(iii) Pull Requests:

(iv) Wiki Pages:

  1. Images:

  2. Media:

I'm glad to be a part of the GSoC community. The things I learned during this summer would surely be helpful to me in the future. I'd be happy if my code proves beneficial to the community. Thanks to everyone for the support!

Thank you,
Ashish Kumar.

Weekly Reports

Third Evaluation Period (July 27th - August 23rd)

Week 12 (August 17th - August 23rd)

Week 11 (August 10th - August 16th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-August/004602.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-August/002119.html)

  • What did I get done this week?

    • Merged three pull requests to the pgRouting repository's develop branch:
    • (#1599) - Final merge PR containing the code for the two experimental functions - pgr_depthFirstSearch and pgr_sequentialVertexColoring.
    • (#1602) - Removed the generated links from linkcheck_ignore.
    • (#1604) - Fixed coloring family and pgr_sequentialVertexColoring documentation, by defining the parameters in the coloring family doc and referencing them in the sequentialVertexColoring doc.
    • Created a tag 2020-krashish8-depthFirstSearch-sequentialVertexColoring in GSoC-pgRouting containing the code for the two experimental functions - pgr_depthFirstSearch and pgr_sequentialVertexColoring.

  • What do I plan on doing next week?

    • I will make the presentation and the video of contributions for the functions which I implemented.
    • I will also be making the final report as per the guidelines set by Google.

  • Am I blocked on anything?

    • No blocking issues, just my college has opened, so I have to devote some time to the classes and other works related to that.

Week 10 (August 3rd - August 9th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-August/004590.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-August/002116.html)

  • What did I get done this week?

    • Modified the documentation and docqueries of the pgr_depthFirstSearch and pgr_sequentialVertexColoring function, based on the review.
    • Renamed node to vertex_id everywhere for sequentialVertexColoring.
    • Created traversal directory and moved depthFirstSearch to it. Also renamed graphColoring directory to coloring.
    • Created documentation for coloring family and traversal family.
    • Merged a pull request with all these changes (#121).
    • Made a pull request to the main pgRouting repository's develop branch (#1599), containing the code for these two experimental functions - pgr_depthFirstSearch and pgr_sequentialVertexColoring.

  • What do I plan on doing next week?

    • I will be merging the pull request made to the main repository after it gets properly reviewed.
    • I will wrap up my work and make the presentation for the functions which I implemented.

  • Am I blocked on anything?

    • No blocking issues.

Week 9 (July 27th - August 2nd)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-August/004580.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-August/002112.html)

  • What did I get done this week?

    • Modified the implementation of pgr_depthFirstSearch for both directed and undirected graphs, by creating a new DFS visitor file.
    • Added the statement to catch cancelation from Postgres user
    • Added extra pgTAP tests to test the modified implementation, to test the equivalence of DFS with BFS and Single Vertex with Multiple Vertices signature of the function.
    • Removed the redundant pgTAP tests, and separated the edge_cases into two files - for undirected and directed graphs.
    • Changed color to color_id in the pgr_sequentialVertexColoring algorithm.
    • Changed the ordering of the named parameters and updated the signatures file.
    • Renamed edges_sql and start_vid to Edges SQL and Root vid everywhere, and source/start vertex to root.
    • Fixed minor styling issues and removed the comments which over-documented the code.
    • Modified the documentation and docqueries of the pgr_depthFirstSearch and pgr_sequentialVertexColoring function, based on the review.
    • Merged a pull request with all these changes (#114).

  • What do I plan on doing next week?

    • I will be making the required changes to the pgr_depthFirstSearch and pgr_sequentialVertexColoring function based on the mentor's review.

  • Am I blocked on anything?

    • No blocking issues.

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

Week 8 (July 20th - July 26th)

Week 7 (July 13th - July 19th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-July/004558.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-July/002107.html)

  • What did I get done this week?

    • Added the pgTAP tests for all the functions already implemented in pgRouting.
    • These tests check whether the same set of rows are returned for any ordering of the input rows edges_sql.
    • It was found that a lot of pgRouting functions failed these tests. So, I tried to fix the code of those functions.
    • For fixing most of the problems, I added a function insert_edges_sorted in the pgr_base_graph.hpp file, and used it wherever required, so that always the same graph will get created internally for any ordering of the input rows.
    • For some other functions which were directly coded in pgRouting, I sorted the rows in the order of id, source, target where the function was implemented to fix the problem.
    • Merged a pull request with all these changes (#65).
    • Merged two pull requests (squash & merge) - #72 and #73 to the demo-master branch, to understand how to merge these changes to the main pgRouting repository's master branch.

  • What do I plan on doing next week?

    • I will be creating issues on the main pgRouting repository to fix the ordering problem of the functions.
    • For every directory, I will be making pull requests to the master branch to add the pgTAP test.
    • If the pgTAP tests fail for the official and proposed functions, I will be fixing their code.

  • Am I blocked on anything?

    • No blocking issues.

  • Meetings attended in this week

    • June 14th: Rebased the pgr_depthFirstSearch and pgr_sequentialVertexColoring branch to the develop branch of pgRouting repository and the fixing-ordering-issues-in-v3 branch to the master branch of pgRouting repository.

Week 6 (July 6th - July 12th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-July/004545.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-July/002100.html)

  • What did I get done this week?

    • Added pgTAP test - server no-crash-test - no_crash_test-sequentialVertexColoring.sql.
    • Added pgTAP test - parameter types check - sequentialVertexColoring-types-check.sql.
    • Added pgTAP test - inner query test - sequentialVertexColoring-innerQuery.sql.
    • Added pgTAP unit tests for different small graphs - sequentialVertexColoring-edge-cases.sql (empty graph, one vertex graph, two vertices graph, three vertices graph, four vertices graph)
    • Added prepared statement in the queries and tested all prepared statements - depthFirstSearch-edge-cases.sql.
    • Added test to check whether the same set of rows are returned always - depthFirstSearch-rows-check.sql and sequentialVertexColoring-rows-check.sql.
    • So, now both the functions pgr_depthFirstSearch and pgr_sequentialVertexColoring are complete along with all the documentation and tests.
    • Merged a pull request with all these changes (#59).
    • Created an issue in pgRouting/GSoC-pgRouting repository (#62) listing the steps to be followed for the next week's work - Fixing pgRouting functions so that same set of rows are returned for any ordering of input rows

  • What do I plan on doing next week?

    • It has been found that around 15-20% (maybe more) of the pgRouting functions produce different output for different ordering of the input rows. e.g.: pgr_primDFS, pgr_bdDijkstra, pgr_drivingDistance, pgr_breadthFirstSearch, pgr_edwardMoore, etc. They should return same set of rows irrespective of the ordering, since PostgreSQL rows are a set.
    • So, this week, I will be adding the pgTAP tests for all the function already implemented in pgRouting to check whether they satisfy this requirement. If the test fails, then I'll do the fix in the code, by ordering the rows internally in a particular order.

  • Am I blocked on anything?

    • No blocking issues.

Week 5 (June 29th - July 5th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-July/004535.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-July/002094.html)

  • What did I get done this week?

    • Modified implementation of pgr_sequentialVertexColoring and pgr_depthFirstSearch based on the mentor's reviews.
      • Removed seq column from the output of pgr_sequentialVertexColoring.
      • Sorted the edges of both pgr_depthFirstSearch and pgr_sequentialVertexColoring in an ascending order of their id before creating the graph, so that always the same set of rows will be returned.
      • Sorted results in an ascending order of the node id.
    • Edited documentation of pgr_depthFirstSearch
      • Added "experimental" in index, edited "See Also" section
      • Removed the "Vertex Out of Graph" section.
      • Added some points in the description section.
    • Completed the documentation for pgr_sequentialVertexColoring in the pgr_sequentialVertexColoring.rst file.
      • Added docqueries for the documentation using the pgRouting Sample Data.
      • Included the docqueries in the documentation file (.rst).
      • Generated documentation locally and deployed it for preview [deployed link].
      • Updated the configuration.conf file to generate the documentation for the function pgr_sequentialVertexColoring.
    • Updated the GitHub Actions workflow (Build for Ubuntu) to run proper checks on every commit, which initially gave some errors.
    • Merged a pull request with all these changes (#54).

  • What do I plan on doing next week?

    • The implementation of the function along with its documentation is complete. Only the pgTAP tests 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.
    • For pgr_depthFirstSearch function, I will be adding and modifying some pgTAP tests, based on the mentor's reviews (testing prepared statements, adding test to check whether same set of rows are returned).
    • I will also be refactoring the code a bit, wherever required, and will make sure the code is up to the pgRouting standards and should adhere to the Google C++ Style Guide, which I will ensure using the code_checker.sh file. If necessary, I would be renaming variables, removing unnecessary lines, and adding comments.
    • The goal of the coming week would be to submit a working pgr_sequentialVertexColoring function along with its documentation and pgTAP tests included.

  • Am I blocked on anything?

    • No blocking issues.

  • Meetings attended in this week

    • These meetings were a part of the Bolsena Online Code Sprint 2020:

      • June 30th: Discussed and presented all the work I had done so far, for the GSoC '20 program, with the mentor, who reviewed the work and suggested some modifications.
      • July 2nd: Attended and reviewed the workshop of MobilityDB team with pgRouting and PostGIS.

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

Week 4 (June 22nd - June 28th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-June/004522.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-June/002086.html)

  • What did I get done this week?

    • Studied the corresponding boost function (boost::sequential_vertex_coloring), and how to implement it in pgRouting.
    • Modified sequentialVertexColoring_driver.cpp to call the main function present in the .hpp file.
    • Added pgr_sequentialVertexColoring.hpp file.
    • Added the boost function boost::sequential_vertex_coloring in the .hpp file, and did the implementation of the Sequential Vertex Coloring algorithm by calling this function. For this:
      • Created the necessary class wrappers for the Boost function.
      • Processed the data with the Boost function.
      • Returned the resulting set of rows.
    • Merged a pull request with all these changes (#50).

  • What do I plan on doing next week?

    • Since the implementation is complete, I plan to add the documentation of the function pgr_sequentialVertexColoring.
    • I also plan to add the docqueries test of the corresponding function using the pgRouting's sample data.
    • In case some extra time remains, I will add some basic pgTAP tests like inner query types and parameter types check.

  • Am I blocked on anything?

    • This isn't a blocking issue, but I could not figure out how to create a graph with isolated vertices in pgRouting using the insert_edges function present. Creating a graph with isolated vertices may be needed in future.

Week 3 (June 15th - June 21st)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-June/004509.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-June/002083.html)

  • What did I get done this week?

    • Started coding my second function pgr_sequentialVertexColoring in a branch named pgr_sequentialVertexColoring in my forked repository. This branch is checked out from the previous pgr_depthFirstSearch branch.
    • Opened an issue in pgRouting's main repository for the discussion of the new functionality, containing the function's name, signature, description, and usage. - Issue #1362
    • Created a basic skeleton for C, C++, SQL code, and for the documentation and tests. Add all the required files:
      • doc/graphColoring/ - CMakeLists.txt, pgr_sequentialVertexColoring.rst
      • docqueries/graphColoring/ - CMakeLists.txt, doc-pgr_sequentialVertexColoring.result, doc-pgr_sequentialVertexColoring.test.sql, test.conf
      • include/drivers/graphColoring/ - sequentialVertexColoring_driver.h
      • pgtap/graphColoring/ - sequentialVertexColoring-edge-cases.sql, sequentialVertexColoring-innerQuery.sql, sequentialVertexColoring-types-check.sql, no_crash_test-sequentialVertexColoring.sql
      • sql/graphColoring/ - CMakeLists.txt, _sequentialVertexColoring.sql, sequentialVertexColoring.sql
      • src/graphColoring/ - CMakeLists.txt, sequentialVertexColoring.c, sequentialVertexColoring_driver.cpp
    • Modified the files for the current implementation of the function.
    • Added the function name in the configuration file - configuration.conf.
    • Updated the signatures file to contain the signature of the new function - sql/sigs/pgrouting--3.0.0.sig.
    • Merged a pull request with all these changes (#46).

  • What do I plan on doing next week?

    • Currently, the function returns an empty row for every query. So, I need to complete the implementation of the function, so that it returns correct results.
    • I will be studying the boost function boost::sequential_vertex_coloring, its source code and will study how it can be implemented efficiently in pgRouting.
    • I will add the C++ Header file which will call the boost function boost::sequential_vertex_coloring and will modify the driver file to call the function defined in the HPP file.

  • Am I blocked on anything?

    • This isn't actually a "blocking" issue, but it would be great if it is fixed. The GitHub build is always failing, probably because the postgresql on port 5433 is down. The builds on Travis and Appveyor are successfully passing.

Week 2 (June 8th - June 14th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-June/004499.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-June/002080.html)

  • What did I get done this week?

    • Added pgTAP test - server no-crash-test - no_crash_test-depthFirstSearch.sql.
    • Added pgTAP test - parameter types check - depthFirstSearch-types-check.sql.
    • Added pgTAP test - inner query test - depthFirstSearch-innerQuery.sql.
    • Added pgTAP unit tests for different small graphs - depthFirstSearch-edge-cases.sql (empty graph, vertex not present in graph, negative depths, one vertex graph, two vertices graph, three vertices graph, four vertices graph)
    • Refactored the code, to meet the pgRouting guidelines and Google C++ Style Guide.
    • Changed named notation from := to => everywhere (A newer syntax starting from PostgreSQL v9.4).
    • Added relevant docstrings and comments in all the C, CPP, and HPP files for better display of Developer's documentation using Doxygen.
    • The first function pgr_depthFirstSearch is complete along with all the documentation and tests.
    • Merged a pull request with all these changes (#43).

  • What do I plan on doing next week?

    • The implementation of the first function pgr_depthFirstSearch is complete, along with all the documentation and tests. So, I plan to start developing the next function pgr_sequentialVertexColoring() from the next week.
    • I will create a separate branch named pgr_sequentialVertexColoring in my forked repository, for starting the implementation of this function. (This branch will be created by checking out from the previous pgr_depthFirstSearch branch).
    • I will be opening an issue for the discussion of the new functionality, containing the function's name, signature, description and usage.
    • After deciding the relevant characteristics of the function, 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?

    • No blocking issues.

Week 1 (June 1st - June 7th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-June/004488.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-June/002078.html)

  • What did I get done this week?

    • Added boost functionality for undirected graphs by calling boost::undirected_dfs.
    • Removed some redundant code from the files.
    • Completed the documentation for pgr_depthFirstSearch in the pgr_depthFirstSearch.rst file.
    • Added docqueries for the documentation using the pgRouting Sample Data.
    • Included the docqueries in the documentation file (.rst).
    • Generated documentation locally and deployed it for preview [deployed link].
    • Added extra test queries using the sample table mentioned in Issue #1348 - Usage section.
    • Added my name in pgRouting-introduction.rst file - Contributors section.
    • Updated the configuration.conf file to generate the documentation for the function pgr_depthFirstSearch.
    • Merged a pull request with all these changes (#39).

  • What do I plan on doing next week?

    • The implementation of the function along with its documentation is complete. Only the pgTAP tests 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 refactoring the code a bit, wherever required, and will make sure the code is up to the pgRouting standards and should adhere to the Google C++ Style Guide, which I will ensure using the code_checker.sh file. If necessary, I would be renaming variables, removing unnecessary lines, and adding comments.
    • The goal of the coming week would be to submit a working pgr_depthFirstSearch function along with its documentation and pgTAP tests included.

  • Am I blocked on anything?

    • No blocking issues.

  • Meetings attended in this week

    • June 2nd: Discussions regarding contraction algorithms and techniques.
    • June 5th: More Discussion regarding contraction, particularly area contraction. Also, learned how to use the run.sh file effectively for building and testing the files locally.

Community Bonding Period (May 4th - May 31st)

Week 0 (May 25th - May 31st)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-May/004477.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-May/002062.html)

  • What did I get done this week?

    • Studied the corresponding boost function (boost::depth_first_search and boost::undirected_dfs), and how to implement it in pgRouting.
    • Modified depthFirstSearch_driver.cpp to call the main function present in the .hpp file.
    • Added pgr_depthFirstSearch.hpp file.
    • Removed the old docqueries and pgTAP tests. (previously, they contained the tests when the function returned empty rows)
    • Added the boost function boost::depth_first_search in the .hpp file, and did the implementation for both undirected and directed graphs by calling this function.
    • Merged a pull request with all these changes (#38).

  • What do I plan on doing next week?

    • I have used only boost::depth_first_search for doing the implementation of both the directed and undirected graphs. Though this function produces the correct output in both the cases, I plan to call boost::undirected_dfs using if-then-else in case of undirected graphs.
    • Since the implementation is complete, I plan to add the documentation of the function pgr_depthFirstSearch.
    • I also plan to add the docqueries test of the corresponding function using the sample data, as well as using another sample table created by me. (queries mentioned in #1348).

  • Am I blocked on anything?

    • No blocking issues.

  • Meetings attended in this week

    • May 26th: More discussions regarding the functionality request of the pgr_dijkstra with the combinations SQL.
    • May 28th: Discussion regarding Contraction Techniques in pgRouting.

Week -1 (May 18th - May 24th)

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2020-May/004465.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2020-May/002057.html)

  • What did I get done this week?

    • Started coding my first function pgr_depthFirstSearch in a branch named pgr_depthFirstSearch in my forked repository.
    • Added all the required files for the implementation of this function:
      • doc/depthFirstSearch/ - CMakeLists.txt, pgr_depthFirstSearch.rst
      • docqueries/depthFirstSearch/ - CMakeLists.txt, doc-pgr_depthFirstSearch.result, doc-pgr_depthFirstSearch.test.sql, test.conf
      • include/drivers/depthFirstSearch/ - depthFirstSearch_driver.h
      • pgtap/depthFirstSearch/- depthFirstSearch-edge-cases.sql, depthFirstSearch-innerQuery.sql, depthFirstSearch-types-check.sql, no_crash_test-depthFirstSearch.sql
      • sql/depthFirstSearch/ - CMakeLists.txt, _depthFirstSearch.sql, depthFirstSearch.sql
      • src/depthFirstSearch/ - CMakeLists.txt, depthFirstSearch.c, depthFirstSearch_driver.cpp
      • Added the function name in configuration.conf
      • Added the function signatures in sql/sigs/pgrouting--3.0.0.sig
    • Made a pull request with all these changes (#34).

  • What do I plan on doing next week?

    • Currently, the function returns an empty row for every query. So, I will first transform the data to C++ containers suitable for using with boost and will try to add the boost functionality to this function.

  • Am I blocked on anything?

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

  • Meetings attended in this week

    • May 18th: Discussion regarding combinations SQL for Mobility DB.

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 gsoc-ashish 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.

    • What did I plan to do the next week?

      • Start coding my first function pgr_depthFirstSearch in a separate branch in my forked repository.
      • Create a basic skeleton for C, C++, SQL code, and for documentation and tests.
      • Try to understand pgRouting better and adding Boost's functionality to the function.

    • Am I blocked on anything?

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

Tasks

  • 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. "The Boost Graph Library (BGL) - Version 1.72.0 Documentation", https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/index.html
  2. "Undirected DFS - Boost Graph Library (Boost 1.72.0 Library Documentation)", https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/undirected_dfs.html
  3. "Depth First Search - Boost Graph Library (Boost 1.72.0 Library Documentation)", https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/depth_first_search.html
  4. "Depth First Search - Wikipedia, the Free Encyclopedia", https://en.wikipedia.org/wiki/Depth-first_search
  5. "Sequential Vertex Coloring - Boost Graph Library (Boost 1.72.0 Library Documentation)", https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/sequential_vertex_coloring.html
  6. "Graph Coloring - Wikipedia, the Free Encyclopedia", https://en.wikipedia.org/wiki/Graph_coloring
  7. "Four Color Theorem - Wikipedia, the Free Encyclopedia", https://en.wikipedia.org/wiki/Four_color_theorem
  8. "Andrew W. Appel. Kempe’s Graph Coloring algorithm. Princeton University; 2016", https://www.cs.princeton.edu/~appel/Color.pdf
  9. "Maximum Adjacency Search - Boost Graph Library (Boost 1.72.0 Library Documentation)", https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/maximum_adjacency_search.html
  10. "Anne Berry, Jean R. S. Blair, and Pinar Heggernes. Maximum Cardinality Search for Computing Minimal Triangulations", http://www.ii.uib.no/~pinar/MCS-M.pdf
  11. "Jean R. S. Blair, Barry W. Peyton. An introduction to Chordal Graphs and Clique Trees. Oak Ridge National Laboratory; November 1992. p. 4-9", https://www.researchgate.net/publication/236366775_An_introduction_to_chordal_graphs_and_clique_trees
  12. "pgr_kruskalDFS Documentation - pgRouting Manual v3.0.0-rc1", https://docs.pgrouting.org/latest/en/pgr_kruskalDFS.html
  13. "pgRouting Sample Data - pgRouting v3.0.0-rc1", https://docs.pgrouting.org/dev/en/sampledata.html