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.