[pgrouting-dev] GSoc 2023 Final Report Standardizing pgr_drivingDistance

[Aryan Gupta]

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](
https://developers.google.com/open-source/gsoc/help/work-product) and
[OSGeo GSoC Admins](
https://lists.osgeo.org/pipermail/soc/2023-August/005114.html).

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


3. **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)
```

4. **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 vid, distance, [directed])
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.

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

6. **Links**:

   - **Tag:**
      - pgr_drivingdistance (2023-aryan-drivingdistance-overloads):

https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2023-aryan-drivingdistance-overloads

   - **Pull Request**
      - Final Pull Request: Modifying pgr_drivingdistance:
      https://github.com/pgRouting/pgrouting/pull/2548
      - Intermediate weekly Pull Requests created in GSoC-pgRouting
      repository:

https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+is%3Aclosed+author%3Aaryan1010

   - **Wiki Page:**
      -
https://github.com/pgRouting/pgrouting/wiki/GSoC-2023-Implementing-Dijkstra%E2%80%99s-Driving-distance-Function-and-its-migration


7. **Image**:

   - Example image:

https://docs.google.com/presentation/d/1mbdDV_fZr7VaxjbpBEQA-oq9I3FxdE_X6tLjSYlcUNM/edit#slide=id.g13ca40d287b_0_45

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20230827/3054757f/attachment.htm>