GSoC 2019 Edward Moore's Algorithm, Breadth First Search and Binary Breadth First Search - pgRouting/pgrouting GitHub Wiki

Table of Contents

Proposal

Brief Description

Edward Moore's Algorithm is an improvement over Bellman-Ford algorithm and can compute single-source minimum cost paths in weighted (including negative weights) directed graphs. It has an average running time of O(E) on random graphs and the same worst-case complexity as Bellman-Ford's algorithm of O(V*E).

Boost::Breadth First Search is the implementation of the classic Breadth First Algorithm in the Boost Graph Library. It is a basic graph traversal algorithm which can be applied to any type of graph. One of its various applications is to find the path with minimum edges from a given source to any arbitrary destination. It has a linear time complexity of O(V + E).

Binary Breadth First Search is a modification of the standard Breadth First Search algorithm and can calculate single-source minimum cost paths in a weighted graph where weights of all edges are either zero or some constant C. It has a linear time complexity of O(V+E) compared to O(E + V log V) of Dijkstra’s algorithm.

This project aims to add the above three algorithms into pgRouting during the GSoC period.

State of the Project Before GSoC

pgRouting currently does not have any of the proposed algorithms implemented.

The algorithm to be improved by Edward Moore's algorithm, i.e Bellman-Ford algorithm has been implemented in pgRouting during the 2018 GSoC period by Sourabh Garg.

Breadth First Search is used in various other already-implemented algorithms. However, a single standard function does not exist.

The variants of Dijkstra’s algorithm implemented in pgRouting have a run-time complexity no better than O(E + V log V). This can be improved for the special case of binary weighted graphs using Binary Breadth First Search for a run-time complexity of O(E + V).

Deliverables

  1. Connect Boosts Breadth First Search to pgRouting.
  2. Implementation of Binary Breadth First Search for pgRouting.
  3. Implementation of Edward Moore's algorithm for pgRouting.

Each implemented function will include relevant documentation and tests.

Timeline

Community Bonding Period (May 6th - May 27th)

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

First Coding Period (May 27th - June 23rd)

Week 1 (May 27th - June 2nd)

  • Design pgr_BreadthFirstSearch() function.
  • Create a basic skeleton for documentation and tests.

Week 2 (June 3rd - June 9th)

  • Create the code skeleton of the SQL and C code which allows the C++ implementation of the function to work with PostgreSQL.

Week 3 (June 10th - June 16th)

  • Implement pgr_BreadthFirstSearch() function along with its helper files.

Week 4 (June 17th - June 23rd)

  • Prepare documentation for pgr_BreadthFirstSearch() function.
  • Complete testing along with writing pgTap tests for pgr_BreadthFirstSearch() function.
  • Prepare a report for First Evaluation.

Second Coding Period (June 24th - July 21st)

Week 5 (June 24th - June 30th)

  • Design pgr_BinaryBreadthFirstSearch() function.
  • Create a basic skeleton for documentation and tests.
  • Work on feedback provided from the first evaluation.

Week 6 (July 1st - July 7th)

  • Create the code skeleton of the SQL and C code which allows the C++ implementation of the function to work with PostgreSQL.

Week 7 (July 8th - July 14th)

  • Implement pgr_BinaryBreadthFirstSearch() function along with its helper files.

Week 8 (July 15th - July 21st)

  • Prepare documentation for pgr_BinaryBreadthFirstSearch() function.
  • Complete testing along with writing pgTap tests for pgr_BinaryBreadthFirstSearch() function.
  • Prepare a report for Second Evaluation.

Third Coding Period (July 22nd - August 18th)

Week 9 (July 22nd - July 28th)

  • Work on feedback provided from the second evaluation.
  • Design pgr_EdwardMoore() function.
  • Create a basic skeleton for documentation and tests.

Week 10 (July 29th - August 4th)

  • Create the code skeleton of the SQL and C code which allows the C++ implementation of the function to work with PostgreSQL.
  • Begin pgr_EdwardMoore() implementation.

Week 11 (August 5th - August 11th)

  • Finish pgr_EdwardMoore() implementation.
  • Complete testing along with writing pgTap tests for pgr_EdwardMoore() function.

Week 12 (August 12th - August 18th)

  • Review, complete and finalize all documentation and tests for all algorithms implemented.
  • Create a detailed final report.

Participants

Title GitHub Handle Name
1st Mentor @codeSG Sourabh Garg
2nd Mentor @cayetanobv Cayetano Benavent
Student Developer @vicennial Gudesa Venkata Sai Akhil

Detailed Proposal

Detailed Proposal in PDF format

Slides

https://docs.google.com/presentation/d/e/2PACX-1vQ3gGxNNlhozU9RBkWGvyBFxSAfFMZt6mV6u9xifi4SGjlnMWhCOZ_F8Ulr2dqjdoaO8Ssi6bRvNlXd/pub?start=false&loop=false&delayms=3000&slide=id.g5fc0475bda_1_54

Log of Pull Requests

Pull Request Description Date Status
#33 GSOC-2019 Week 12 - Documentation 16 August 2019 Merged
#32 GSOC-2019 Week 12 - pgr_edwardMoore Tests 16 August 2019 Merged
#31 GSOC-2019 Week 11 - pgr_edwardMoore - Doc/Tests 11 August 2019 Merged
#29 GSOC-2019 Week 11 - pgr_edwardMoore - Lint/Misc Changes 9 August 2019 Merged
#27 GSOC-2019 Week 11 - pgr_edwardMoore - Pre Week Changes 5 August 2019 Merged
#25 GSOC-2019 Week 10 - pgr_edwardMoore 3 August 2019 Merged
#23 GSOC-2019 Week 9 - pgr_edwardMoore 28 July 2019 Merged
#20 GSOC-2019 Week 8 - pgr_binaryBreadthFirstSearch 21 July 2019 Merged
#18 GSOC-2019 Week 7 - pgr_binaryBreadthFirstSearch 14 July 2019 Merged
#17 GSOC-2019 Week 6 - pgr_binaryBreadthFirstSearch 07 July 2019 Merged
#15 GSOC-2019 Week 5 - pgr_binaryBreadthFirstSearch 28 June 2019 Merged
#12 GSOC-2019 Week 4 - pgr_breadthFirstSearch 19 June 2019 Merged
#10 GSOC-2019 Week 3 - pgr_breadthFirstSearch 10 June 2019 Merged
#8 GSOC-2019 Week 2 - pgr_breadthFirstSearch 5 June 2019 Merged
#5 GSOC-2019 Week 1 - pgr_breadthFirstSearch 28 May 2019 Merged
#1197 Pre-Bonding period documentation improvement 29 March 2019 Merged
#1 GSoC pgRouting Application Requirements 27 March 2019 Merged

Summary Video of Contributions Made

https://www.youtube.com/watch?v=3DJNHBzjY4s

Weekly Reports

Third Evaluation Period (July 22nd - August 18th)

Week 12 (August 12th - August 18th)

  • What did I complete this week?
    • Added additional comparison based pgTap test and documentation queries for Edward Moore's algorithm.
    • Documentation clean-up for all implemented algorithms.
    • Merged three pull requests containing the above changes. (#32, #33, #1240)
  • What am I going to achieve for next week?
    • I will be making the final report as per the guidelines set by Google as well as the ones set by Margherita Di Leo
  • Is there any blocking issue?
    • No.

Week 11 (August 5th - August 11th)

  • What did I complete this week?
    • Reorganised files and made lint changes to being code up to Google's C++ standards in preparation for branch deployment.
    • Added documentation and no-crash pgTap test for Edward Moore's algorithm.
    • Merged three pull requests containing the above changes. (#27, #29, #31)
  • What am I going to achieve for next week?
    • In the following week, I will begin integrating all the code I have written and the changes I have made into pgRouting's main repository. (Currently, code resides on pgRouting's GSoC repository)
  • Is there any blocking issue?
    • Not a blocking issue, I had mentioned in last week's report that I would be implementing Edward Moore's algorithm for negative-weighted graphs but after discussion with my mentors, We have decided to forgo this feature due to extensive internal changes and tests required to support negative-weighted graphs on pgRouting (Currently, pgRouting is not compatible with negative-weighted graphs)

Week 10 (July 29th - August 4th)

  • What did I complete this week?
    • Created C++ file which contains the core algorithm and linked the file to the pgr_edwardMoore function.
    • Added a simple, base version of the target algorithm which is able to calculate the correct path as well as the cost between two nodes in a graph containing only edges with a non-negative cost.
    • Merged a pull request with the changes made. (#25)
  • What am I going to achieve for next week?
    • In the following week, I aim to have the full implementation of the target algorithm ready. In the final state, the algorithm will be able to work on graphs containing edges of any cost value.
  • Is there any blocking issue?
    • No blocking issue.

Week 9 (July 22nd - July 28th)

  • What did I complete this week?
    • Set up a branch named pgr_edwardMoore on my local repository.
    • Added SQL files that contain the function signature for One-to-One, One-to-Many, Many-to-One, Many-to-Many type queries as well as the signature for the internal version of the function.
    • Added function C file which accepts the data from Postgres, sets up input/output arrays, calls a function to begin the algorithm, extracts the results and returns it.
    • Added function C++ driver file. This file contains the algorithm to process the input data. In the current state, the function will simply return an empty set without processing any of the input data.
    • Added InnerQuery pgTap test.
    • Added Documentation queries and their (dummy)results. The results would be updated later once the actual algorithm has been implemented.
    • Added the function signatures to pgrouting--3.0.0.sig .
    • Merged a pull request with the changes made. (#23)
  • What am I going to achieve for next week?
    • For the next two weeks, I will be implementing Edward's Moore Algorithm from scratch. For the next week, in particular, I aim to have an implementation of the algorithm that will work on graphs containing non-negative edge costs. (The full algorithm can work on graphs containing edge costs of any value)

Second Evaluation Period (June 24th - July 21st)

Week 8 (July 15th - July 21st)

  • What did I complete this week?
    • Added the following categories of pgTap tests:
      • Inner Query Tests
      • Edge Case Tests
      • Parameter Type Checks
      • Crash Tests
      • Comparison Tests
    • Added function documentation page which also includes sample queries.
    • Modified method of displaying pre-processing error.(Previously used the 'assert' function to throw an error but have now shifted to simply printing the error message and terminating the function execution.)
    • Merged a pull request with the changes made. (#20)
  • What am I going to achieve for next week?
    • From the next week onwards, I will begin working on the last deliverable of my project, which is, implementing Edward Moore's Algorithm in pgRouting. I will be designing the function definition as well as creating a basic skeleton of the function's documentation and tests next week.
  • Is there any blocking issue?
    • No blocking issue.

Week 7 (July 8th - July 14th)

  • What did I complete this week?
    • Added path-cost calculation to the algorithm.
    • Replaced usage of a C++ STL map container with a C++ STL vector container. (Vector container has a lower runtime complexity compared to map container for accessing stored elements)
    • Refactored the path-generation and cost-calculation sections into multiple, easy-to-read modules.
    • Added a pre-processing check that verifies that the input graph satisfies the restrictions set by the algorithm which are required to be followed for successful execution. An error is thrown if restrictions are not met.
    • Merged a pull request with the changes made. (#18)
  • What am I going to achieve for next week?
    • In the following week, I plan to write tests as well as documentation for the algorithm. By the end of the week, I aim to have the algorithm be ready-to-implement with all relevant work completed before moving on to the next deliverable of my project in the third coding period.
  • Is there any blocking issue?
    • No blocking issue.

Week 6 (July 1st - July 7th)

  • What did I complete this week?
    • Created C++ file which contains the core algorithm and linked the file to the pgr_binaryBreadthFirstSearch function.
    • Added a simple, base version of the target algorithm which is able to calculate the correct path between two nodes in the graph in its current state.
    • Merged a pull request with the changes made. (#17)
  • What am I going to achieve for next week?
    • In the following week, I aim to have the full implementation of the target algorithm ready. This would include pre-processing checks, elimination of code inefficiencies, refactoring and more.
  • Is there any blocking issue?
    • No blocking issue.

Week 5 (June 24th - June 30th)

  • What did I complete this week?
    • Set up a branch named pgr_binaryBreadthFirstSearch on my local repository.
    • Added SQL files that contain the function signature for One-to-One, One-to-Many, Many-to-One, Many-to-Many type queries as well as the signature for the internal version of the function.
    • Added function C file which accepts the data from Postgres, sets up input/output arrays, calls a function to begin the algorithm, extracts the results and returns it.
    • Added function C++ driver file. This file contains the algorithm to process the input data. In the current state, the function will simply return an empty set without processing any of the input data.
    • Added InnerQuery pgTap test.
    • Added Documentation queries and their (dummy)results. The results would be updated later once the actual algorithm has been implemented.
    • Added the function signatures to pgrouting--3.0.0.sig .
    • Merged a pull request with the changes made. (#15)
  • What am I going to achieve for next week?
    • For the next two weeks, I will be implementing the Binary Breadth-First Search Algorithm from scratch. For the next week, in particular, I aim to have a simplified version of the algorithm implemented, which I can then work on in the third week.
  • Is there any blocking issue?
    • No blocking issues.

First Evaluation Period (May 27th - June 23rd)

Week 4 (June 17th - June 23rd)

  • What did I complete this week?
    • Added a negative value check on the 'max_depth' input parameter of the pgr_breadthFirstSearch function. An error is thrown to the user instead of displaying an empty result.
    • Modified the implemented algorithm to return the traversal starting at depth zero instead of depth one. This was done to avoid empty output when the input graph contains only a single vertex which is also the source vertex in the function call.
    • Modified the implemented algorithm to return an empty table when the source vertex is not present in the input graph.
    • Added function input/output parameter type-check pgTap tests.
    • Added algorithm edge-cases pgTap tests.
    • Added additional inner-query pgTap tests.
    • Added more example queries and their results in the function's documentation page.
    • Merged a pull request with the changes made. (#12)
  • What am I going to achieve for next week?
    • I will begin working on the next deliverable of my project, which is, implementing the Binary Breadth First Search algorithm in pgRouting. I will be designing the function definition as well as creating a basic skeleton of the function's documentation and tests next week.
  • Is there any blocking issue?
    • No blocking issues.

Week 3 (June 10th - June 16th)

  • What did I complete this week?
    • Removed unnecessary header files, redundant code and comments from the files.
    • Updated test directory query result files to match the current(expected) output of the algorithm. Previously, a dummy result was used since the algorithms had not been implemented yet.
    • Added documentation for the function 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 Breadth First Search documentation as well as Wikipedia's explanation of the Breadth First Search Algorithm.
    • Merged a pull request with the changes made. (#10)
  • What am I going to achieve for next week?
    • I will be adding input validity checks wherever required, pgTap tests and additional documentation if required. The goal for next week, as well as the first evaluation, would be a fully functional pgRouting function with all the appropriate tests and documentation.
  • Is there any blocking issue?
    • I have found cases of unexpected output which shall be dealt with in the upcoming week.

Week 2 (June 2nd - June 9th)

  • What did I complete this week?
    • Added the core algorithm(Boost's Breadth First Search) which works on the input data to provide the requested traversal order of the graph in file pgr_breadthFirstSearch.hpp (C++ File).
    • Added the logic to transport the input data to the implemented algorithm as well as the logic to process the algorithm's output data in file breadthFirstSearch_driver.cpp.
    • Fixed minor typos in previous week's code.
    • Merged a pull request with the changes made. (#8)
  • What am I going to achieve for next week?
    • I will be cleaning up all the files and code involved up till now by removing unnecessary lines, renaming variables and refactoring code where ever possible. This is to make sure the code is up to the code standards being upheld by pgRouting, to allow future developers to understand and analyse the code without external assistance.
  • Is there any blocking issue?
    • None as of now.

Week 1 (May 27th - June 2nd)

  • What did I complete this week?
    • Set up a branch named pgr_breadthFirstSearch on my local repository.
    • Added breadthFirstSearch.sql. It contains the function signature for both the One-to-Depth and Many-to-Depth query types.
    • Added _breadthFirstSearch.sql. It contains the internal function signature.
    • Added breadthFirstSearch.c . It accepts the data from Postgres, sets up input/output arrays, calls a function to perform the algorithm, extracts the results and returns it.
    • Added breadthFirstSearch_driver.cpp . This file contains the algorithm to process the input data. In the current state, the function will simply return an empty set without processing any of the input data.
    • Added breadthFirstSearch_driver.h . It contains the function definition of "do_pgr_breadthFirstSearch" which is present in the breadthFirstSearch_driver.cpp file.
    • Set up the CMakeLists.txt files in the src/ and sql/ directories.
    • Added no_crash_test-breadthFirstSearch.sql and breadthFirstSearch-innerQuery.sql which are pgTap tests.
    • Added doc-pgr_breadthFirstSearch.test.sql and doc-pgr_breadthFirstSearch.result. These are execution based tests.
    • Added the function signatures to pgrouting--3.0.0.sig .
    • Configured the Continuous Integration system named Travis to include the pgr_breadthFirstSearch function in it's builds.
    • Merged a pull request with the changes made. (#5)
  • What am I going to achieve for next week?
    • In the function's current state, It accepts the input data but does not process the data and will return an empty output. In the next week, I will be porting the Breadth First Search algorithm from the Boost C++ Libraries to my development branch to process the input data.
  • Is there any blocking issue?
    • Currently, I do not have any blocking issue and will be able to begin coding the functionalities planned for the next week.

Community Bonding Period (May 6th - May 27th)

  • 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 (March 25th - April 9th)

Final Report

(The below report was sent to the GSoC mailing list of OSGeo which can be found here)

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!

Title - Implementation of Edward Moore's Algorithm, Breadth-First Search and Binary Breadth-First Search in pgRouting.

Organisation - pgRouting under OSGeo

Abstract - This GSoC project dealt with implementing three new graph algorithms in pgRouting. The algorithms are described as follows:

Edward Moore's Algorithm is an improvement over Bellman-Ford algorithm and can compute single-source minimum cost paths in weighted (including negative weights) directed graphs. It has an average running time of O(E) on random graphs and the same worst-case complexity as Bellman-Ford's algorithm of O(V*E).

Boost::Breadth-First Search is the implementation of the classic Breadth-First Algorithm in the Boost Graph Library. It is a basic graph traversal algorithm which can be applied to any type of graph. One of its various applications is to find the path with minimum edges from a given source to any arbitrary destination. It has a linear time complexity of O(V + E).

Binary Breadth-First Search is a modification of the standard Breadth-First Search algorithm and can calculate single-source minimum cost paths in a weighted graph where weights of all edges are either zero or some constant C. It has a linear time complexity of O(V+E) compared to O(E + V log V) of Dijkstra’s algorithm.

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

pgRouting lacked a single standard function for Breadth-First Search graph traversal, which is used in various other implemented algorithms. This led to the repetition of code as well as sub-standard internal implementations.

pgRouting has a variety of least-cost path algorithms implemented but these algorithms are suited for general use. For specific situations, faster algorithms exist that produce equivalent results.

Value of Project to pgRouting The 'Breadth-First Search' algorithm is now a function of its own and is meant for general use. Since it is a common sub-step in different algorithms, this function reduces repetition of code across different implementations as well as provides a one-stop, efficient solution.

The 'Binary Breadth-First Search' algorithm allows users to quickly process very large graphs when their graphs meet a specific set of conditions rather than use a slower, all-purpose function.

The 'Edward Moore's' algorithm can be extended as the 'all-purpose' least-cost path finding algorithm when pgRouting enables support for graphs with negative weights. Currently, it can be used as a replacement for Dijkstra's algorithm since the average running time of Edward Moore's algorithm is faster by a log factor.

Potential Future Work

  • A 'cost' version of pgr_binaryBreadthFirstSearch as well pgr_edwardMoore. A 'cost' version of the algorithm extracts only the aggregate cost of the shortest path(s) found, for the combination of vertices given rather than printing the path.
  • Extend pgr_edwardMoore to support negative-weighted graphs once pgRouting supports the same.

Links

Media