[pgrouting-dev] GSoC 2023 : Implement pgr_withPointsKSP and Add Overloads

pgRouting pgrouting-dev
1

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.
  1. 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
  1. 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.

  1. 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.

  1. Links:
  1. Image:

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