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 Jul 19, 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 14 - Aug 27)

Week 7 (Jul 14 - Jul 22)

  • 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 23 - Jul 30)

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

Week 9 (Jul 31 - Aug 6)

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

Week 10 (Aug 7 - Aug 13)

  • Creating Documentation on Migrating thenew function

Week 11 (Aug 14 - Aug 20)

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

Week 12 (Aug 21 - Aug 27)

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

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
GSoC-2023 Week-08: pgr_drivingdistance Merged
GSoC-2023 Week-08: pgr_drivingdistance Merged
GSoC-2023 Week-08: pgr_drivingdistance Merged
GSoC-2023 Week-08: pgr_drivingdistance Merged
GSoC-2023 Week-08: pgr_drivingdistance Merged

Final Report

References

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally