[SoC] [pgRouting] GSoC'18 Week 10 Report : Implement Bellman-Ford and parallel-Dijkstra algorithm for pgrouting

[Sourabh Garg]

Hi All,

     In this week, I tried implementing parallel-Dijkstra in pgrouting
continuing from last week's work but found some major difficulties in
implementing the parallel version of the algorithms. After the long
discussion with mentors about it, we all decided that the project changes
to implement a non-parallel function for now.  We decided to implement
"directed acyclic graph(DAG) shortest path algorithm". The project report
for Week-10(16 July - 22 July) is as follows:

*What did you get done this week?*

   - Implement Basic code for the functionality.
   - Changed function's signature to consider only directed graph.
   - Working implementation for the one-to-one signature variant.

Details and PR can be found at [1] and [2] respectively.

*What do you plan on doing next week?*

   - Implement the pgr_dagShortestPath function to work for all signatures.
   - Add tests and documentation for the function.

*Are you blocked on anything?*
       No, Currently I am not blocked.

The project wiki and current working branch can be found in [3] and [4]
resp.
The work and tests related to parallel-Dijkstra can be found at [5].

[1].
https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-Parallel-Dijkstra-and-Bellman-Ford#week-10-16-july---22-july
[2]. https://github.com/pgRouting/pgrouting/pull/1068
[3].
https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-Parallel-Dijkstra-and-Bellman-Ford
[4]. https://github.com/pgRouting/pgrouting/tree/gsoc-dag_sp
[5].
https://github.com/pgRouting/pgrouting/tree/gsoc/parallel-dijkstra/src/parallel

Regards,

Sourabh Garg
IIT(BHU), India
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20180723/732f111d/attachment.html>