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 |
|---|---|---|---|
| #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?
- Set up 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 students 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.
