GSoC 2023 Implementing Dijkstra’s Driving distance Function and its migration - pgRouting/pgrouting GitHub Wiki

Table of Contents

proposal

Brief Description

The project aims to implement a new function called "pgr_dijkstraDD" that replaces the existing "pgr_drivingDistance" function. The new function will have all overloads,including single and multiple vertices as before. The function will return columns such as sequence, depth, start vertex ID, node, edge, cost, and aggregate cost for all overloads. The project will also include testing of the new function with pgTap Tests.Documentation for the new function and migration guides for users to switch to the new function will also be created.The Dijkstra’s Driving Distance algorithm is employed to extract all nodes that can be reached from the root node with cost of reaching not exceeding the given distance D. This algorithm is primarily based on Dijkstra's Algorithm.

State of the Project Before GSoC

Signature of current pgr_drivingDistance function:

pgr_drivingDistance(Edges SQL, Root vid, distance, [directed])
pgr_drivingDistance(Edges SQL, Root vids, distance, [options])
options: [directed, equicost]
RETURNS SET OF (seq, [from_v,] node, edge, cost, agg_cost)

Currently the function does not have a depth column which tells the distance of a particular node from the root node.Signatures, Column names, and its contents are not consistent.Other than the above two stated points, the function “pgr_drivingDistance” is accurate, stable and gives correct results.

Benefits to the Community

  • It is one of the widely used functions from all the pgRouting functions.Because it operates on dijkstra function which is of utmost importance in the pgRouting library.
  • Added extra Depth Column
  • Postgres does not allow two functions with the same set of input parameters but with different output columns.
  • While making changes to the function we don’t want to break other user’s code while it is in testing and is stable .So we make a renamed function side by side ,so that it doesn’t affect the stable function.
  • pgr_dijkstraDD is better because it uses the algorithm inventor’s name.
  • Completing the project would make the name and structure of the function similar to other functions https://docs.pgrouting.org/dev/en/pgr_primDD.html https://docs.pgrouting.org/dev/en/pgr_kruskalDD.html
  • Open source: “pgr_dijkstraDD” function is part of the open-source pgRouting extension, which means that it is free to use and can be customised by users to meet their specific needs.
  • Adding this algorithm to pgRouting will result in more functionalities in pgRouting which will help the current and future users and developers to use and integrate it with other algorithms.

Deliverables

The deliverables at the end of the GSoC period are:-

  • Make and implement “pgr_dijkstraDD” function with all overloads: ➔ Single Vertex ➔ Multiple Vertices
  • C, C++, SQL code related to that function
  • Return columns on both the overloads: Seq, depth, start_vid, node, edge, cost, agg_cost
  • Return columns on all the overloads will be seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
  • Basic pgTap Tests
  • Full weekly report of evaluations
  • Documentation of the new function

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor @shobhit162 Shobhit Chaurasia
2nd Mentor @robe2 Regina Obe
Student Software Developer @aryan1010 Aryan Gupta

Weekly Report And Plan

Pre-bonding-period

Community Bonding Period (May 4 - May 28)

  • I will engage with my mentors, participate more actively in discussions, and learn more about pgRouting.
  • Learn the pgRouting coding style from Google C++ Style Guide
  • Adopt the pgRouting-established standards for development, documentation, and testing.
  • Set up the wiki page to keep track of weekly progress.

Community Bonding report

  • Introduced myself and my project in the soc mailing list [1] and requested feedback or suggestions on the project.
  • Added the links to the wiki page and the public repository in the OSGeo Accepted Students' wiki page [2].
  • Created my GSoC project wiki page in the pgrouting repository, where I will be regularly updating the weekly reports [3].
  • Studied Google's GSoC students guide and the OSGeo's specific instructions.
  • Met with the mentors and the core developer of pgRouting, to discuss the final name of the function in this project [4], some possible additional works.

First Coding Period (May 29 - July 9)

Week 1 (May 29 - Jun 4)

  • Design “pgr_dijkstraDD” function
  • Create the new single vertex renamed function
  • Reuse and Duplicate Code when possible
  • Understanding and getting deep into previous code (“pgr_drivingdistance”)

Week 1 report

Week 2 (Jun 5 - Jun 11)

  • Design the detailed signature for the “pgr_dijkstraDD” function
  • Make Basic Code skeleton of SQL,C and C++ files

Week 2 report

Week 3 (Jun 12 - Jun 18)

  • Create C++ containers for passing SQL data to C++ containers for data processing
  • Refine the code

Week 3 report

Week 4 (Jun 19 - Jun 25)

  • Creation of helper class, wrappers.
  • Implementing Single vertex and Multiple Vertices
  • Test against OSM data
  • Make sure the eros are properly handled

Week 4 report

Week 5 (Jun 26 - Jul 2)

  • Write appropriate queries using the pgRouting documentation's sample data.
  • Work on the submissions required as part of the first evaluation.

Week 5 report

Week 6 (Jul 3 - Jul 9)

  • Prepare user documentation.
  • Prepare a report for the first evaluation

Week 6 report

  • Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2023-July/005072.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2023-July/002467.html)

  • What did I get done this week?

    • Added the depth column to the pgr_drivingdistance function
    • Used the path type = Mst_rt (it has depth in it ) for passing the tuples
    • Used boost:depth_first_search function for the returning depth
    • The function is working and returning all the columns

  • What do I plan on doing next week?

    • Catching up on week 6 pull request issues.
    • Do the changes suggested by @vicky ,that includes
    • Fixing all the pgtap testcases till now (except one )
    • Fixing all the docqueries till now
    • Removing the extraneous v4 files and combining them with the old files

  • Am I blocked on anything?

    • Nothing major

First Evaluation Period(July 10 - July 14)

  • Submit a working pgr_dijsktraDD( ) function with its documentation (without pgTap tests)

Second Coding Period(July 10 - Aug 20)

Week 7 (Jul 10 - Jul 16)

  • Work on the feedback provided from the first evaluation.
  • Bug fixing.
  • Preparing second coding period Synopsis

Week 7 report

Week 8 (Jul 17 - Jul 23)

  • Internal tests for “pgr_dijkstraDD”
  • No server crash test
  • pgTap Unit tests

Week 8 report

Week 9 (Jul 24 - Aug 30)

  • Create queries and results for documentation using the pgRouting sample data.

Week 9 report

Week 10 (Jul 31 - Aug 6)

  • Creating Documentation on Migrating thenew function

Week 10 report

Week 11 (Aug 7 - Aug 13)

  • Fix all the bugs/problems and documentation details.
  • Wiki Page

Week 11 report

Week 12 (Aug 14 - Aug 20)

  • Verify documentation and migration documentation works Prepare final submission along with full documentation.

Week 12 report

Final Evaluation Period(Aug 28 - Sep 4)

  • Submit the complete project with all the required functions, documentation and unit tests.

Log of Pull Requests

Pull Request Description Date Status
#293 GSoC-2023 Week-01: pgr_drivingdistance June 5th, 2023 Merged
#296 GSoC-2023 Week-02: pgr_drivingdistance June 11th, 2023 Merged
#305 GSoC-2023 Week-03: pgr_drivingdistance June 18th, 2023 Merged
#310 GSoC-2023 Week-04: pgr_drivingdistance June 25th, 2023 Merged
#311 GSoC-2023 Week-05: pgr_drivingdistance July 1st, 2023 Merged
#315 GSoC-2023 Week-06: pgr_drivingdistance July 8th, 2023 Merged
#321 GSoC-2023 Week-07: pgr_drivingdistance July 15th, 2023 Merged
#329 GSoC-2023 Week-08: pgr_drivingdistance July 22th, 2023 Merged
#331 GSoC-2023 Week-09: pgr_drivingdistance July 29th, 2023 Merged
#334 GSoC-2023 Week-10: pgr_drivingdistance August 6th,2023 Merged
#338 GSoC-2023 Week-11: pgr_drivingdistance August 13th,2023 Merged
#344 GSoC-2023 Week-12: pgr_drivingdistance August 20th,2023 Merged
#2548 Final Pull Request to Develop branch August 25th,2023 Merged

Final Report

Hello everyone,

I'm happy to give my final report, which includes a summary of the work I did throughout the past twelve weeks of GSoC. This time has been an amazing experience that has given me many opportunity to learn while working with the pgRouting community and mentors. The study follows the recommendations made by Google and OSGeo GSoC Admins.

  1. (a) Title: Implementing Dijkstra’s Driving distance Function and its migration for pgRouting (b) Organization: pgRouting under OSGeo

  2. Abstract: This project aims to enhance the functionality of the pgr_drivingdistance function in pgRouting adding a result column and normalizing the output. And all overloads will be implemented (Single vertex & Multiple vertices).

The Dijkstra’s Driving Distance algorithm is employed to extract all nodes that can be reached from the root node with cost of reaching not exceeding the given distance D. This algorithm is primarily based on Dijkstra's Algorithm.

The final outcome is as follows:

  • The function signatures have changed, incorporating new columns in the new signatures.
  • HERE IMPORTANT TO NOTE THAT -All the changes according to proposal are done and all the tests are passing except the Update test for the drivingdistance
  1. The state of the art before GSoC:
  • The function did not have a depth column which tells the distance of a particular node from the root node.
  • Signatures, Column names, and its contents were not consistent.

Previous Signature:

pgr_drivingDistance(Edges SQL, Root vid, distance, [directed])
pgr_drivingDistance(Edges SQL, Root vids, distance, [options])
options: [directed, equicost]
RETURNS SET OF (seq, [from_v,] node, edge, cost, agg_cost)
  1. The addition (added value) that your project brought to the software:

The deliverables include code, documentation, documentation tests, and the pgTAP tests of pgr_drivingdistance function:

Current Signature:

pgr_drivingDistance(Edges SQL, Root vids, distance, [options])
options: [directed, equicost]
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Standardize the output by adding a column to make the returns including the depth of node, so that it has a unified output with other DD functions and expand the usability of the function. Return columns on all overloads:

  • Before: seq, [start_vid], node, edge, cost, agg_cost
  • After: seq, depth, start_vid, node, edge, cost, agg_cost

Improve documentation on how to migrate to new features, making it easy for users and other developers to adapt to the new overloaded function.

  1. Potential Future Work:

Fixes can be applied for the failing of Update test for the pgr_drivingdistance function

Specifically, it would be beneficial to add an optional parameter 'equicost' to the pgr_kruskalDD and pgr_primDD functions, similar to other DD functions. This addition would enhance the functionality and consistency across these functions.

  1. Links:

  2. Image:

I feel incredibly fortunate to have gotten the chance to participate in the GSoC and OSGeo communities. My knowledge and talents from this wonderful time are priceless assets that will surely direct my future growth efforts. I feel enormous satisfaction in knowing that my programming has the ability to benefit the community. I want to sincerely thank everyone who has provided their steadfast support and wisdom. Here's to the effectiveness of teamwork and shared learning! I'm so grateful to you all!

Thanks and Regards,

Aryan Gupta

References