GSoC 2018 Parallel Dijkstra and Bellman Ford

Content

Proposal
Tag
Presentation
Log of Pull requests
Reports
Timeline
References

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

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.

Proposal-pdf

Project Proposal

Tag

https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018-codeSG-lw

Presentation

https://docs.google.com/presentation/d/1ESngDemJKLmvWCO6uisd1bmhXGYdjc5ERa-ZEWdqOx0/edit#slide=id.g35f391192_00

Log of Pull Requests

Pull Request	Description	Date	Status
#1082	GSoC'18 Implemented functions(merged to develop)	02 August 2018	Merged
#1081	Fix issues with new functionalities	01 August 2018	Merged
#1078	Compile my project work with gcc7	31 July 2018	Merged
#1073	[WIP] Implemention of pgr_dagShortestPath	27 July 2018	Merged
#1068	[WIP] DAG Shortest Path Algorithm	20 July 2018	Merged
#1064	Implement Parallel dijkstra on distributed graph	12 July 2018	Merged
#1061	Experimentation of parallel boost graph	8 July 2018	Merged
#1060	Fix Compile and Documentation Warnings	4 July 2018	Merged
#1053	[WIP] Implementation of pgr_bellmanFord (Reading negative weightd edges)	29 June 2018	Merged
#1049	[WIP] Implementation of pgrBellmanFord(changed function's name)	18 June 2018	Merged
#1043	[WIP] Full Implementation of pgr_bellman_ford with Documentation	12 June 2018	Merged
#1042	[WIP]Implementation of pgr_bellman_ford (Many-to-many function)	7 June 2018	Merged
#1039	[WIP] Implementation of pgr_bellman_ford (One-to-one function)	30 May 2018	Merged
#1033	[WIP]Implementation of Bellman-Ford (Initial code structure)	24 May 2018	Merged

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

Official Coding Period (Phase 1)

Week 1 (14 May - 20 May)

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

Week 2 (21 May - 27 May)

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
Include Directory
- Create bellman_ford_driver.h
Sql Directory
- Create CMakeLists.txt & bellman_ford.sql
Modified configurations.conf File

Task 2: Fix function's License

Change developers name & email address.

Task 3: Testing for Assertions

Week 3 (28 May - 3 June)

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

Week 4 (4 June - 10 June)

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.

Official Coding Period (Phase 2)

Week 5 (11 June - 17 June)

PR: https://github.com/pgRouting/pgrouting/pull/1043

Task 1: Working Implementation for pgr_bellman_ford For all variants

One to One
One to Many
Many to One
Many to Many

Query and Results: https://github.com/pgRouting/pgrouting/pull/1043#issuecomment-396654667

Task 2: Documentation Files Modified

Update doc-pgr_bellman_ford.queries
Update pgr_bellman_ford.rst

Week 6 (18 June - 24 June)

PR: https://github.com/pgRouting/pgrouting/pull/1049

Task 1: Change Function's name

function's name changed from pgr_bellman_ford to pgr_bellmanFord

Task 2: Reading negative weighted edge in graph

Create functions for reading all edges(edge.cost >=0 or edge.cost< 0)
Debugging inside the code

Task 3: Testing code for boost's bellman-ford algorithm

Week 7 (25 June - 1 July)

PR: https://github.com/pgRouting/pgrouting/pull/1053

Task 1: Clean and Working pgr_bellmanFord for positive edges
Issue: https://github.com/codeSG/pgrouting/issues/6

Clean code files (bellman_ford.c , bellman_ford_driver.cpp, pgr_bellman_ford.hpp)
Remove debug statements
Remove unnecessary code

Task 2: Create function's signature for allowing negative edge sql query
Issue: https://github.com/codeSG/pgrouting/issues/7

Created bellman_ford_neg.sql
Created _bellman_ford_neg.sql

Task 3: Building graph and applying algorithm with negative edges
Issue: https://github.com/codeSG/pgrouting/issues/8

Create src & include files for dealing negative edges with pgr_bellmanFord
- Create src/bellman_ford_neg.c
- Create src/bellman_ford_neg_driver.cpp
- Create include/drivers/bellman_ford_neg_driver.h
Function to read negative_edge_sql
- Function to add a negative cost edge : graph_add_neg_edge()
- Function called by pgr_bellman_hpp (Here) : insert_negative_edges()

Week 8 (2 July - 8 July)

Task 1: Fix Compile and Documentation warnings in pgr_bellmanFord
PR: https://github.com/pgRouting/pgrouting/pull/1060

Updated Documentation
Fix warnings

Task 2: Experimentation of parallel boost graphs
PR: https://github.com/pgRouting/pgrouting/pull/1061

Set up the environment for working with MPI and Parallel boost.
Testing on Parallel boost graph library.
Added small graph examples for future testing.

Official Coding Period (Final Phase)

Week 9 (9 July - 15 July)

PR: https://github.com/pgRouting/pgrouting/pull/1064

Task 1: More Experimentation on parallel boost graphs

Reading graph(.gr file) from boost metis file reader
Applying dijkstra's shortest path algorithm.

Task 2: Visualization of Distributed graph

Read and tried various boost graph property_map.
Added small graph test and the corresponding output.

Week 10 (16 July - 22 July)

PR: https://github.com/pgRouting/pgrouting/pull/1068

Task 1: Implement Basic Code Structure of the dag shortest_path algorithm

Src Directory
- Create CMakeLists.txt & dagShortestPath.c & dagShortestPath_driver.cpp
Include/drivers Directory
- Create dagShortestPath_driver.h
Include Directory
- Create pgr_dagShortestPath.hpp
Sql Directory
- Create CMakeLists.txt, dagShortestPath.sql
Modified configurations.conf File

Task 2: Changed function's Signature to consider only directed graph

 pgr_dagShortestPath (edge_sql, start_vid, end_vid)
  RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost) OR EMPTY SET

Task 3: Working Implementation for dag_shortest_path for One-to-One source-target pair.

Week 11 (23 July - 29 July)

PR: https://github.com/pgRouting/pgrouting/pull/1073

Task 1: All possible function's signature added

 pgr_dagShortestPath (edge_sql, start_vid, end_vid)
 pgr_dagShortestPath (edge_sql, start_vids, end_vid)
 pgr_dagShortestPath (edge_sql, start_vid, end_vids)
 pgr_dagShortestPath (edge_sql, start_vids, end_vids)

  RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost) OR EMPTY SET

Created _dagShortestPath.sql
Updated CMakeLists.txtand dagShortestPath.sql

Task 2: Added function's documentation files

Created pgr_dagShortestPath.rst and doc-pgr_dagShortestPath.queries.
Updated proposed(Experimental) functions

Task 3: Added function's test files

Week 12 (30 July - 06 August)

Tag: https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018-codeSG-lw
PR: https://github.com/pgRouting/pgrouting/pull/1078
PR: https://github.com/pgRouting/pgrouting/pull/1082

Task 1: Check and Fix issues related to new functionalities

Fix pgr_dagShortestPath test files.

Task 2: Make the code compatible with some changes in develop branch

Make this project compiled with C++7.

Task 3: Merged work from all project branches to the develop branch

Task 4: Write a Google presentation about this project

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

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

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

Deliver a implementation of the pgr_bellmanFord().
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. → Complete implementation of Bellman-Ford function. → Design the detailed signature for parallel Dijkstra’s algorithm.	Done
Week 6-7	→ Setup classes and utility functions for communication among processors. → Implement pgr_parallelDijkstra() in pgRouting.	Done
Week 8	→ Create unit tests for pgr_parallelDijkstra. → Prepare report for Phase 2 Submission.	Done

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.	Done
Week 10	→ Create units & internal tests(adding precondition, postcondition, class invariant, etc) for the above functions and fix bugs if found.	Done
Week 11	→ Prepare final user documentation.	Done
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

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
The Boost graph library function for Directed acyclic shortest path algorithm dag_shortest_path

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

pgRouting Project