[SoC] GSoC 2023 - Final report: Improving Parameters and Standardizing Results in pgr_withPointsDD Function for pgRouting

[Yige Huang]

Hello everyone,

As GSoC comes to a close, I am pleased to present my final report
summarizing the work I have accomplished over the past twelve weeks. This
period has been an incredible experience, providing me with valuable
learning opportunities while collaborating with the pgRouting community and
mentors. The report adheres to the guidelines outlined by Google [1] and
OSGeo GSoC Admins [2].

1. (a) *Title*: Improving Parameters and Standardizing Results in
pgr_withPointsDD Function for pgRouting
    (b) *Organization*: pgRouting under OSGeo

2. *Abstract*:
This project aims to enhance the functionality of the pgr_withPointsDD
function in pgRouting by improving the 'driver_side' optional parameter,
adding a result column and normalizing the output. And all overloads will
be implemented (Single vertex & Multiple vertices).

The pgr_withPointsDD function modifies the graph to include points and
using Dijkstra algorithm, extracts all the nodes and points that have costs
less than or equal to the value from the starting point. The edges
extracted will conform to the corresponding spanning tree.

During the project, after discussions, the expectations for this function
were somewhat different from the original proposal. The final outcome is as
follows:

   - The function signatures have changed, incorporating new columns in the
   new signatures.
   - The function primarily caters to driving cases, hence the
   'driver_side' parameter has transitioned from optional to mandatory.
   Moreover, the valid values for this parameter differ for directed and
   undirected graphs.


3. *The state of the art before GSoC:*

Signature of current pgr_withPointsDD function:

   - The `driving_side` parameter is optional.
   - Default value of `driving_side` is `b`.

Results of current pgr_withPointsDD function:

   - Depending on the overload used, the columns `start_vid` might be
   missing.
   - Overload pgr_withPointsDD (Single vertex) does not have `start_vid`.

While the pgr_withPointsDD function has been successfully implemented,
further improvements are necessary. Specifically, the result columns need
to include depth of node, and the 'driver_side' optional parameter requires
refinement to enhance routing control and accuracy. Additionally,
normalizing the output of all overloads will make the function more
user-friendly. The pgr_withPointDD function will likely officially be part
of the next major release, so it is very important to overload and improve
it.

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_withPointsDD function:

In all the overloads, the function signatures have been modified:

   - The `driving_side` parameter now is compulsory.
   - Valid values differ for directed and undirected graphs.
      - Does not have a default value.
      - In directed graph, valid values are [r, R, l, L]
      - In undirected graph, valid values are [b, B]

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.

5. *Potential Future Work*:
The work on the pgr_withPointsDD function has already been completed.
However, in line with the goal of standardizing similar functions, the
signatures of other relevant functions can also be improved.

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_withPointsDD (2023-squarege-withPointsDD-overloads):
      https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2023-squarege-withPointsDD-overloads
      - *Pull Request*
      - Final Pull Request: Modifying withpointsdd:
      https://github.com/pgRouting/pgrouting/pull/2544
      - Subsequent Pull Request: Modifying withpointsdd supplement:
      https://github.com/pgRouting/pgrouting/pull/2545
      - Intermediate weekly Pull Requests created in GSoC-pgRouting
      repository:
      https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3Asquarege+created%3A%3C2023-08-28+


   - *Wiki Page*
      -
      https://github.com/pgRouting/pgrouting/wiki/GSoC-2023-Improving-Parameters-and-Standardizing-Results-in-pgr_withPointsDD-Function-for-pgRouting


7. *Image*:

   - Example image:
   https://drive.google.com/file/d/1rQUkA5XaKqpIv5iG0OfYPsLTb7MHsh4_/view?usp=sharing

I am thrilled to be a part of the incredible GSoC and OSGeo communities.
This experience has been tremendously valuable. It would bring me immense
joy to see my code benefit the community. Lastly, thank you everyone for
the supports!

Thanks and Regards,

Yige Huang

[1]. https://developers.google.com/open-source/gsoc/help/work-product[2].
https://lists.osgeo.org/pipermail/soc/2023-August/005114.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20230827/5d27bd95/attachment.htm>