Skip to content

GSoC 2023 Implementing Dijkstra’s Driving distance Function and its migration

Jump to bottom Edit New page
Aryan Gupta edited this page Aug 27, 2023 · 22 revisions

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

  • What do I plan on doing next week?

    • Catch up my week 1 work in week 2.
    • Create a basic structure for documentation, C, C++ and SQL.
    • Start developing the *pgr_drivingdistance() *function.

  • Am I blocked on anything?

    • Nothing MAJOR

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

  • What do I plan on doing next week?

    • Catch up my week 1 work in week 2.
    • plan on adding the depth column with reference to pgr_primDD/pgr_kruskalDD

  • Am I blocked on anything?

    • Nothing MAJOR

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Fixed Dijkstra issue 729 from week 2
    • Reverted back the pgtap tests and the docqueries
    • Created new docqueries
    • Brought back the all previous functions due to the issue of backward compatibility.

  • What do I plan on doing next week?

    • Catching up on week 3 pull request.
    • plan on adding the depth column with reference to pgr_primDD/pgr_kruskalDD

  • Am I blocked on anything?

    • Nothing MAJOR

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Read the whole code of prim_dd and kruskal_dd and tried to understand the working
    • Added a new structure path_rtdd
    • made some new v4 files
    • adjusted function names according to the new files

  • What do I plan on doing next week?

    • Catching up on week 3 pull request.
    • plan on adding the depth column with reference to pgr_primDD/pgr_kruskalDD

  • Am I blocked on anything?

    • think i need more info on the path structures i.e. basepath_ssec.cpp and basepath_ssec.hpp .It would be very helpful to everyone as all functions need it.

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Read and understood depth_first_search function from pgr_mst.hpp and prim_dd trying to understand the flow of programs.
    • Fixed the docqueries (according to the new one i made)
    • adjusted function names according to the new files

  • What do I plan on doing next week?

    • Catching up on week 5 pull request issues.
    • Updating the v4drivingDist.hpp and v4drivedist_driver.cpp with the help of pgr_mst.hpp and pgr_prim.hpplDD
    • Add Depth Column

  • Am I blocked on anything?

    • Nothing major

Week 6 (Jul 3 - Jul 9)

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

Week 6 report

  • Report Mail - [SoC], [pgrouting-dev]

  • 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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Did the changes suggested by @vicky ,that includes
    • Fixed all the pgtap testcases till now (except one )
    • Fixed all the docqueries till now
    • Removed the extraneous v4 files and combining them with the old files

  • What do I plan on doing next week?

    • Catching up on week 7 pull request issues.
    • Fix the issue_519 [pgtap] and optimise the hpp file
    • Fix the documentation of pgr_drivingdistance

  • Am I blocked on anything?

    • Nothing major

Week 8 (Jul 17 - Jul 23)

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

Week 8 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Fixed the pgtap test cases
    • Code Linting done
    • Signature fixed (was not in alphabetical order)

  • What do I plan on doing next week?

    • Update the function documentation and migration documentation.
    • Fix the pgtap testcases

  • Am I blocked on anything?

    • Nothing major

Week 9 (Jul 24 - Aug 30)

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

Week 9 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Fixed the pgtap test cases (not the update test)[pgtap tests after the update failing]
    • Made the migration Documentation for the pgr_drivingdistance
    • Updated the documentation of the function pgr_drivingdistance

  • What do I plan on doing next week?

    • Fix the update test
    • Follow up on the week ninth's pull request

  • Am I blocked on anything?

    • Nothing major

Week 10 (Jul 31 - Aug 6)

  • Creating Documentation on Migrating thenew function

Week 10 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Learnt and Implemented:
      • cherry-pick
      • created a tag [1]
      • rebase and resolve conflicting code [2]
    • Watched twitch video by Vicky to learn how to prepare for a PR.
    • Fixed the build update extension file

  • What do I plan on doing next week?

    • Meeting with mentors.
    • Start preparing for PR to the main repo.

  • Am I blocked on anything?

    • Nothing major

Week 11 (Aug 7 - Aug 13)

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

Week 11 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Attended meet with vicky on pgr_drivingdistance function
    • Attended meet with vicky on pgr_withpointsksp function
    • Attended meet with vicky on pgr_ksp function
    • Attended meet with vicky on pgr_withpointsdd function
    • removed redundant v4 files
    • fixed issue_1152 pgtap
    • worked on adding depth column on hpp file

  • What do I plan on doing next week?

    • Meeting with mentors.
    • Start preparing for PR to the main repo.
    • finishing adding the depth column and hence getting pgtap update test working

  • Am I blocked on anything?

    • Nothing major

Week 12 (Aug 14 - Aug 20)

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

Week 12 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Updated the migration queries and result
    • Updated the release notes and NEWS
    • Rebase my code with nice commit log and merged into develop-try1 for practicing
    • Created final Pull Request to the pgrouting develop branch

  • Am I blocked on anything?

    • Nothing major

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

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally