GSoC 2019 Edward Moore's Algorithm, Breadth First Search and Binary Breadth First Search
- Proposal
- Log of Pull Requests
- Weekly Reports
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.
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).
- Connect Boosts Breadth First Search to pgRouting.
- Implementation of Binary Breadth First Search for pgRouting.
- Implementation of Edward Moore's algorithm for pgRouting.
Each implemented function will include relevant documentation and tests.
- 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.
- Design pgr_BreadthFirstSearch() function.
- Create a basic skeleton for documentation and tests.
- Create the code skeleton of the SQL and C code which allows the C++ implementation of the function to work with PostgreSQL.
- Implement pgr_BreadthFirstSearch() function along with its helper files.
- Prepare documentation for pgr_BreadthFirstSearch() function.
- Complete testing along with writing pgTap tests for pgr_BreadthFirstSearch() function.
- Prepare a report for First Evaluation.
- Design pgr_BinaryBreadthFirstSearch() function.
- Create a basic skeleton for documentation and tests.
- Work on feedback provided from the first evaluation.
- Create the code skeleton of the SQL and C code which allows the C++ implementation of the function to work with PostgreSQL.
- Implement pgr_BinaryBreadthFirstSearch() function along with its helper files.
- Prepare documentation for pgr_BinaryBreadthFirstSearch() function.
- Complete testing along with writing pgTap tests for pgr_BinaryBreadthFirstSearch() function.
- Prepare a report for Second Evaluation.
- Work on feedback provided from the second evaluation.
- Design pgr_EdwardMoore() function.
- Create a basic skeleton for documentation and tests.
- 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.
- Finish pgr_EdwardMoore() implementation.
- Complete testing along with writing pgTap tests for pgr_EdwardMoore() function.
- Review, complete and finalize all documentation and tests for all algorithms implemented.
- Create a detailed final report.
| Title | GitHub Handle | Name |
|---|---|---|
| 1st Mentor | @codeSG | Sourabh Garg |
| 2nd Mentor | @cayetanobv | Cayetano Benavent |
| Student Developer | @vicennial | Gudesa Venkata Sai Akhil |
Detailed Proposal in PDF format
| Pull Request | Description | Date | Status |
|---|---|---|---|
| #10 | GSOC-2019 week 3 work | 10 June 2019 | Review |
| #8 | GSOC-2019 week 2 work | 5 June 2019 | Merged |
| #5 | GSOC-2019 week 1 work | 28 May 2019 | Merged |
| #1197 | Pre-Bonding period documentation improvement | 29 March 2019 | Merged |
| #1 | GSoC pgRouting Application Requirements | 27 March 2019 | Merged |
- 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.
- 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.
- 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.
- 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.
