[SoC] GSoC 2019 - Final Report - Implement Edward Moore's Algorithm, Breadth First Search and Binary Breadth First Search Algorithms in pgRouting

[GVS Akhil]

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!

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

*2. Organisation* - pgRouting under OSGeo

*3. 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 runtime 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 runtime 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 non-negative integer 'C'. It has a linear runtime complexity
of O(V+E) compared to O(E + V log V) of Dijkstra’s algorithm.

*4. State of the Project Before GSoC* *2019*-
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.

*5. Value of GSoC 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 pathfinding 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.

*6. 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.


*7. Links*
- *Code Documentation*
  - Breadth First Search (pgr_breadthFirstSearch) -
https://docs.pgrouting.org/dev/en/pgr_breadthFirstSearch.html
  - Binary Breadth First Search (pgr_binaryBreadthFirstSearch) -
https://docs.pgrouting.org/dev/en/pgr_binaryBreadthFirstSearch.html
  - Edward Moore (pgr_edwardMoore) -
https://docs.pgrouting.org/dev/en/pgr_edwardMoore
- *Pull Requests*
   - Final pull request - https://github.com/pgRouting/pgrouting/pull/1240
   - Intermediate pull requests -
https://github.com/pgRouting/GSoC-pgRouting/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+author%3Avicennial
- *Project Documentation (Wiki Page)* -
https://github.com/pgRouting/pgrouting/wiki/GSoC-2019-Edward-Moore's-Algorithm,-Breadth-First-Search-and-Binary-Breadth-First-Search


*8. Media*
- *Slide Demonstration* -
https://docs.google.com/presentation/d/e/2PACX-1vQ3gGxNNlhozU9RBkWGvyBFxSAfFMZt6mV6u9xifi4SGjlnMWhCOZ_F8Ulr2dqjdoaO8Ssi6bRvNlXd/pub?start=false&loop=false&delayms=3000&slide=id.g5fc0475bda_1_54
- *Video of Contributions* - https://www.youtube.com/watch?v=3DJNHBzjY4s

It has been an exciting journey!
Thanks everyone for all your support :)

Regards,
GVS Akhil
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20190826/b0df1683/attachment.html>