GSoC 2018 Parallel Dijkstra and Bellman Ford

Content

• Proposal
  • Brief Description
  • State of the project before GSoC
  • Proposal Pdf
• Branch
• Reports
  • Community Bonding Period

Proposal

Brief Description

Graph Algorithms like Dijkstra’s single source shortest path algorithm are widely applied in many routing applications, but for the Large-scale graph, computation problem may arise. It may be beneficial to exploit the high-performance parallel computing system, by implementing distributed graph algorithms in pgRouting.

This project aims to add Parallel Dijkstra’s Algorithm using Parallel BGL functionalities and additionally a classical sequential graph algorithm namely, bellman_ford_shortest_paths to pgRouting.

State of the project before GSoC

The current state of the pgRouting doesn’t support any parallel algorithm. Therefore, we may need to create a separate branch for parallel algorithms in pgRouting.

Proposal-pdf

Project Proposal

Branch

https://github.com/pgRouting/pgrouting/tree/gsoc/bellford-pdijkstra

Reports

Community Bonding Period

Task 1: Get familiar with C++

Issue: https://github.com/codeSG/pgrouting/issues/2

• https://www.youtube.com/watch?v=eidEEmGLQcU
• https://www.youtube.com/watch?v=u5senBJUkPc
• https://www.youtube.com/watch?v=YnWhqhNdYyk
• https://www.youtube.com/watch?v=1OEu9C51K2A
• https://www.youtube.com/watch?v=xnqTKD8uD64
• https://www.youtube.com/watch?v=86xWVb4XIyE
• Make Report

Task 2: Add demo function funnyDijkstra (codesgDijkstra)

Issue: https://github.com/codeSG/pgrouting/issues/3#issue-310302148

• Make a new branch (codesg_demo)
• Make changes to add pgr_codesgDijkstra in that branch. It created files in src, pgtap, sql, doc, include, test for codesgDijkstra function.

Task 3: Guidelines for Community Bonding Period(Handwritten Content)

Issue: https://github.com/codeSG/pgrouting/issues/4

References

1. Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A Parallelization of Dijkstra's Shortest Path Algorithm. In Mathematical Foundations of Computer Science (MFCS), volume 1450 of Lecture Notes in Computer Science, pages 722--731, 1998. Springer.

2. Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.

3. R. Bellman. On a routing problem. Quarterly of Applied Mathematics , 16(1):87-90, 1958

4. L. R. Ford and D. R. Fulkerson. Flows in networks . Princeton University Press, 1962.

5. The Parallel Boost graph library function for Crauser Dijkstra’s Algorithm dijkstra_shortest_path.

6. The Boost graph library function for Bellman-Ford Shortest path algorithm bellman_ford_algorithm