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

[Helmut Kudrnovsky]

Thanks for your final report.

Helmut on behalf of the OSGeo GSoC admins

GVS Akhil <gvs.akhil1997 at gmail.com> schrieb am So., 25. Aug. 2019, 19:18:

> 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
>
>
>
> _______________________________________________
> SoC mailing list
> SoC at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/soc
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20190825/e9cdd874/attachment-0001.html>