[SoC] GSoC 2023 : Implement pgr_withPointsKSP and Add Overloads

[Abhinav Jain]

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: Implement pgr_withPointsKSP function and Add Overloads
(b) Organization: pgRouting under OSGeo

2. Abstract: This project aims to enhance the functionality of the
pgr_withPointsKSP function in pgRouting by making the ‘driver_side’
parameter compulsory, standardizing the result columns according to
Dijkstra function, and adding all overloads like one-to-many, many-to-one,
many to many and combinations.

Yen's algorithm computes single-source K-shortest loopless paths for a
graph with non-negative edge cost. It employs any shortest path algorithm
to find the best path, then proceeds to find K − 1 deviations of the best
path. Sometimes the applications work “on the fly” starting from a location
that is not a vertex in the graph. Those locations, in pgRouting, are
called points of interest.So this function will modify the graph to include
these points of interest and, using Yen’s Algorithm find K Shortest
Paths(KSP).

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


   -

   Only one-to-one overload exists
   -

   The driving_side parameter is optional
   -

   The default value of driving_side is `b`


Results of current pgr_withPointsKSP function:

   - Start_vid and end_vid columns don’t exist

4. The addition (added value) that your project brought to the software:

The deliverables include code, documentation, documentation tests, and the
pgTAP tests of the pgr_withPointsKSP function:


   -

   In one-to-one overload, 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 a directed graph, valid values are [r, R, l, L]
      -

      In an undirected graph, valid values are [b, B]
      -

      Standardize the output by adding columns like ‘start_vid’ and
      ‘end_vid’ to make the return columns similar to that of Dijkstra, hence
      increasing the usability of the function.
      -

   Adding more proposed functions:
   -

      pgr_withPointsKSP (One to Many)
      -

      pgr_withPointsKSP (Many to One)
      -

      pgr_withPointsKSP (Many to Many)
      -

      pgr_withPointsKSP (Combinations)


Return columns on all overloads:

Before: seq, path_id, path_seq, node, edge, cost, agg_cost

After: seq, path_id, path_seq, start_vid, end_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_withPointsKSP 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.

6. Links:


   - Tag:
   https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2023-abhinj-withPointsKSP-overloads
   - Pull Request:
      - Final Pull Request: https://github.com/pgRouting/pgrouting/pull/2546
      - Intermediate weekly Pull Requests created in GSoC-pgRouting
      repository:
      https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+is%3Aclosed+label%3AAbhinj-2023
      - Wiki Page:
      https://github.com/pgRouting/pgrouting/wiki/GSoC-2023-Implement-pgr_withPointsKSP-and-Add-Overloads

7. *Image:*


   - *Example image: *
   https://docs.google.com/https://lists.osgeo.org/pipermail/soc/2023-August/005114.htmlpresentation/d/1pFb62mAvWLQsvADJGzPxWSU8-k5z9UrTnImotis6cRA/edit?usp=sharing
   <https://docs.google.com/presentation/d/1pFb62mAvWLQsvADJGzPxWSU8-k5z9UrTnImotis6cRA/edit?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,

Abhinav Jain
[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/721c7901/attachment-0001.htm>