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.
Detailed Proposal in PDF format
| Pull Request | Description | Date | Status |
|---|---|---|---|
| #1 | GSoC pgRouting Application Requirements | 8 May 2019 | Merged |
| #1197 | Pre-Bonding period documentation improvement | 29 March 2019 | Merged |
- 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.
