<div dir="ltr">Hello everyone, <br><br>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!<br><br><b>1. Title </b>- Implementation of Edward Moore's Algorithm, Breadth-First Search and Binary Breadth-First Search in pgRouting.<br><br><b>2. Organisation</b> - pgRouting under OSGeo<br><br><b>3. Abstract</b> - <br>This GSoC project dealt with implementing three new graph algorithms in pgRouting. The algorithms are described as follows:<br><br><i>- Edward Moore's Algorithm</i> 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).<div><br><i>- Boost::Breadth-First Search</i> 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).</div><div><br><i>- Binary Breadth-First Search</i> 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.<br><br><b>4. State of the Project Before GSoC</b> <b>2019</b>-<br>pgRouting did not have any of the proposed algorithms implemented.<br><br>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.<br><br>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.<br><br><b>5. Value of GSoC Project to pgRouting -</b><br>The '<i>Breadth-First Search</i>' 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. <br><br>The '<i>Binary Breadth-First Search</i>' 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.<br><br>The '<i>Edward Moore's</i>' 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.<br><br><b>6. Potential Future Work</b><br><br>- 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.<br>- Extend pgr_edwardMoore to support negative-weighted graphs once pgRouting supports the same.<br><br><br><b>7. Links</b><br>- <b>Code Documentation</b><br>  - Breadth First Search (pgr_breadthFirstSearch) - <a href="https://docs.pgrouting.org/dev/en/pgr_breadthFirstSearch.html">https://docs.pgrouting.org/dev/en/pgr_breadthFirstSearch.html</a><br>  - Binary Breadth First Search (pgr_binaryBreadthFirstSearch) - <a href="https://docs.pgrouting.org/dev/en/pgr_binaryBreadthFirstSearch.html">https://docs.pgrouting.org/dev/en/pgr_binaryBreadthFirstSearch.html</a><br>  - Edward Moore (pgr_edwardMoore) - <a href="https://docs.pgrouting.org/dev/en/pgr_edwardMoore">https://docs.pgrouting.org/dev/en/pgr_edwardMoore</a><br>- <b>Pull Requests</b><br>   - Final pull request - <a href="https://github.com/pgRouting/pgrouting/pull/1240">https://github.com/pgRouting/pgrouting/pull/1240</a> <br>   - Intermediate pull requests - <a href="https://github.com/pgRouting/GSoC-pgRouting/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+author%3Avicennial">https://github.com/pgRouting/GSoC-pgRouting/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+author%3Avicennial</a><br>- <b>Project Documentation (Wiki Page)</b> - <a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2019-Edward-Moore's-Algorithm,-Breadth-First-Search-and-Binary-Breadth-First-Search">https://github.com/pgRouting/pgrouting/wiki/GSoC-2019-Edward-Moore's-Algorithm,-Breadth-First-Search-and-Binary-Breadth-First-Search </a> <br><br><b>8. Media</b><br>- <b>Slide Demonstration</b> - <a href="https://docs.google.com/presentation/d/e/2PACX-1vQ3gGxNNlhozU9RBkWGvyBFxSAfFMZt6mV6u9xifi4SGjlnMWhCOZ_F8Ulr2dqjdoaO8Ssi6bRvNlXd/pub?start=false&loop=false&delayms=3000&slide=id.g5fc0475bda_1_54">https://docs.google.com/presentation/d/e/2PACX-1vQ3gGxNNlhozU9RBkWGvyBFxSAfFMZt6mV6u9xifi4SGjlnMWhCOZ_F8Ulr2dqjdoaO8Ssi6bRvNlXd/pub?start=false&loop=false&delayms=3000&slide=id.g5fc0475bda_1_54</a> <br>- <b>Video of Contributions</b> - <a href="https://www.youtube.com/watch?v=3DJNHBzjY4s">https://www.youtube.com/watch?v=3DJNHBzjY4s</a><br><br>It has been an exciting journey! </div><div>Thanks everyone for all your support :) </div><div><br>Regards,</div><div>GVS Akhil </div><div><br><br><br></div><div></div><span><img alt="" width="1" height="1" src="https://gml.email/v3.2/t/image/VUlEfDE3MTdjYzcwLTY0MTEtNDlhMy1hYTUxLWEzZjlhNGYwZGJmNnxzb2NAbGlzdHMub3NnZW8ub3Jn.gif" id="gml-gvs.akhil1997@gmail.com1566753480"></span></div>