Skip to content

GSoC 2018 Parallel Dijkstra and Bellman Ford

Jump to bottom Edit New page
Sourabh Garg edited this page May 8, 2018 · 28 revisions

Content

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.

Deliverables

  1. Implementation of Parallel Dijkstra’s algorithm for pgRouting by parallel Boost Graph Library.
  2. Implementation of Bellman Ford_ shortest_path algorithm by BGL.
  3. Documentation and tests for the above-mentioned functionality.

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

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

Timeline

Community Bonding Period (April 23 - May 13 )

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. Ongoing
+ Develop a better understanding of PostGIS, PostgreSQL and PL/pgsql. Ongoing
+ Understand How non-parallel version of boost’s Dijkstra is implemented on pgRouting. Ongoing
+ Implement pgr_funny_dijkstra, to understand implementation style in pgRouting. Done

Official Coding Period ( May 14 - August 14 )

Phase 1 ( May 14 - June 11)

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.
Week 2-3 → Implement pgr_bellmanFord() function for both variants.
Week 4 → Create pgTap unit tests for pgr_bellmanFord.
→ Prepare report for Phase 1 Submission.

First evaluation period (June 11 to June 15, 2018)

  • Deliver a working implementation of the pgr_bellmanFord() and its documentation, test and pgTap.
  • Mentors evaluate me and I evaluate mentors for officially coding period phase 1.

Phase 2 (June 11 to July 8 )

Time Period Tasks Status
Week 5 → Work on the feedback as provided after the first evaluation.
→ 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.

Second evaluation period ( July 9 to July 13, 2018 )

  • 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.

Phase 3 ( July 9 to August 5 )

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.

Final evaluation period ( August 6 to August 14, 2018 )

  • 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.

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

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally