GSoC 2018 Parallel Dijkstra and Bellman Ford
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.
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.
- Implementation of Parallel Dijkstra’s algorithm for pgRouting by parallel Boost Graph Library.
- Implementation of Bellman Ford_ shortest_path algorithm by BGL.
- Documentation and tests for the above-mentioned functionality.
https://github.com/pgRouting/pgrouting/tree/gsoc/bellford-pdijkstra
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
Task 1: Detailed Signature for Bellman Ford algorithm
Issue: https://github.com/pgRouting/pgrouting/issues/1030
- Create a Detailed Signature for the Bellman-Ford algorithm with all arguments specification.
- Verification with some standard relevant documents.
- Discuss and finalize it with mentors.
Task 2: Implement Basic Code Structure of the algorithm from the template
Local Branch: https://github.com/codeSG/pgrouting/tree/bellman_ford
PR:https://github.com/pgRouting/pgrouting/pull/1033
Task 1: Implement pgr_bellman_ford
- Src Directory
- Create
CMakeLists.txt&bellman_ford.c&bellman_ford_driver.cpp
- Create
- Include Directory
- Create
bellman_ford_driver.h
- Create
- Sql Directory
- Create
CMakeLists.txt&bellman_ford.sql
- Create
- Modified configurations.conf File
Task 2: Fix function's License
- Change developers name & email address.
Task 3: Testing for Assertions
PR: https://github.com/pgRouting/pgrouting/pull/1039
Task 1: Working Implementation for pgr_bellman_ford One-One Variant
- Include Directory
- Create
pgr_bellman_ford.hpp - Fix it to work correctly.
- Create
- Modified code to work for all variants
- Sql Directory (Signature Declaration for user end)
- Src Directory (bellman_ford.c and bellman_ford_driver.cpp file)
- Include Directory
Task 2: Fix Some Debug issues
- Recollect logs from .c and .cpp files.
- Retrive System/User's function calls for debugging.
PR: https://github.com/pgRouting/pgrouting/pull/1042
Task 1: Fix issues regarding ARRAY argument as input
- New branch created https://github.com/pgRouting/pgrouting/tree/gsoc/bellmanford-one-to-one
- Fix it to work correctly.
Task 2: Fix Code
- Sql Directory
- Create _pgr_bellman_ford.sql (To link .c file)
- Modify pgr_bellman_ford.sql (For calling all signature's variants)
- Src Directory
- Modify bellman_ford.c for array inputs
- Fix test counts in pgTap files.
| Tasks | Status |
|---|---|
| + Set up my project repository and development environment. | Done |
| + Set up a wiki page to maintain weekly progress and other information of the project. | Done |
| + Get in touch with the community, mentors, and introduce my project to them and receive early feedback. | Done |
| + Getting familiar with source code in depth and all the material that my mentors suggest. | Done |
| + Develop a better understanding of PostGIS, PostgreSQL and PL/pgsql. | Done |
| + Understand How non-parallel version of boost’s Dijkstra is implemented on pgRouting. | Done |
| + Implement pgr_funny_dijkstra, to understand implementation style in pgRouting. | Done |
| Time Period | Tasks | Status |
|---|---|---|
| Week 1 | → Design Detailed Signature for Bellman-Ford function. → Implement the basic code that reads and executes the queries from PostgreSQL. → Implement the structure for the output in the PostgreSQL database. |
Done Done Done |
| Week 2-3 | → Implement pgr_bellmanFord() function for all possible variants. | Done |
| Week 4 | → Create pgTap unit tests for pgr_bellmanFord. → Prepare report for Phase 1 Submission. |
Done |
- Deliver a implementation of the pgr_bellmanFord().
- Mentors evaluate me and I evaluate mentors for officially coding period phase 1.
| Time Period | Tasks | Status |
|---|---|---|
| Week 5 | → Work on the feedback as provided after the first evaluation. → Complete implementation of Bellman-Ford function. → Design the detailed signature for parallel Dijkstra’s algorithm. |
|
| Week 6-7 | → Setup classes and utility functions for communication among processors. → Implement pgr_parallelDijkstra() in pgRouting. |
|
| Week 8 | → Create unit tests for pgr_parallelDijkstra. → Prepare report for Phase 2 Submission. |
- Deliver a working implementation of the Parallel Dijkstra’s algorithm. and its documentation, test, pgTap.
- Mentors evaluate me and I evaluate the mentors for coding period phase 2.
| Time Period | Tasks | Status |
|---|---|---|
| Week 9 | → Work on the feedback as provided after the first evaluation. → Finalize the coding part(if remaining) to get the overall working implementations. |
|
| Week 10 | → Create units & internal tests(adding precondition, postcondition, class invariant, etc) for the above functions and fix bugs if found. |
|
| Week 11 | → Prepare final user documentation. | |
| Week 12 | → Prepare Final Phase submission along with a detailed final phase report. |
- Deliver a working implementation of Parallel Dijkstra’s and Sequential Bellman-Ford Shortest path algorithm with user documentation.
- Mentors evaluate me and I evaluate the mentors for final coding period phase 3.
-
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.
-
Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.
-
R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958
-
L. R. Ford and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.
-
The Parallel Boost graph library function for Crauser Dijkstra’s Algorithm dijkstra_shortest_path.
-
The Boost graph library function for Bellman-Ford Shortest path algorithm bellman_ford_algorithm
-
Detailed Signature of Bellman-Ford
-
T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.
-
Introduction to ALgorithms, Lecture17 Bellman-Ford, by Srini Devadas MIT Fall 2011 https://www.youtube.com/watch?v=ozsuci5pIso
