[SoC] [pgRouting] GSoC 2018 Final Report : Implement bellman-ford and parallel dijkstra for pgRouting.

[Sourabh Garg]

Hello all,

I am Sourabh Garg, and This is my final report for my GSoC project.

*Title: *Implement Parallel Dijkstra’s and Bellman-Ford algorithm by the
Boost Graph Library.

*Organization: *PgRouting under OSGeo

*Abstract: *

*Graph Algorithms like Dijkstra’s single source shortest path algorithm is
widely applied in many routing applications, but it is constrained by
non-negative edge's weight and is more efficient to use DAG shortest path
algorithm(topological sort) in case of Directed Acyclic Graph.*

Finding the shortest path from a source vertex to target using the
*bellman-ford
algorithm* for Graphs with negative weighted edges and *dag_shortest_path*
*algorithm *for the Directed acyclic graph are major



deliverables.
 Often such algorithms are applied over Large-scale graphs, where
computation problem may arise. It may be beneficial to exploit the
high-performance parallel computing system, by implementing distributed
graph algorithms in pgRouting. I have developed the testing base for
parallel Boost Graph algorithm.

*Implemented functions:*

   - pgr_bellmanFord()  - Returns the shortest path for the graph with
   negative weighted edges.
   - pgr_dagShortestPath() - Returns the shortest path for the Directed
   Acyclic Graph.


*State of the art before the project: *pgRouting didn't have above
functionalities before my GSoC.


*Addition that my project brought to pgRouting: *

*The deliverables are code, full documentation, documentation tests, pgTap
of above functions.*



*Pending Work:* I have done experimentation with boost parallel graph
library to generate distributed graph and apply dijkstra's algorithm
over it. It was quite challenging to integrate the parallel version of
algorithms with pgRouting architecture.

* Future Directions: *

   -

* Implement full functionality of parallel Dijkstra in pgrouting
   architecture.*
   -

* Implement the feature to include the negative weighted edges in pgRouting
   graphs.*

*Links:*

   - *Wiki: *https://github.com/pgRouting/pgrouting/wiki/GSoC-
   2018-Parallel-Dijkstra-and-Bellman-Ford
   <https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-Parallel-Dijkstra-and-Bellman-Ford>
   - *Last Pull Request:* https://github.com/pgRouting/pgrouting/pull/1082
   - *Slide: *https://docs.google.com/presentation/d/
   1ESngDemJKLmvWCO6uisd1bmhXGYdjc5ERa-ZEWdqOx0/edit?usp=sharing
   <https://docs.google.com/presentation/d/1ESngDemJKLmvWCO6uisd1bmhXGYdjc5ERa-ZEWdqOx0/edit?usp=sharing>
   - *Tag:* https://github.com/pgRouting/pgrouting/releases/
   tag/gsoc2018-codeSG-lw


Best Regards,

*Sourabh Garg*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20180814/e725ec73/attachment.html>