[pgrouting-dev] GSoc 2023 Final Report Standardizing pgr_drivingDistance

pgRouting pgrouting-dev
1

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 opportunities 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 willbe 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 the 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:
  1. 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