Skip to content

GSoC 2023 Implement pgr_withPointsKSP and Add Overloads

Jump to bottom Edit New page
Abhinav Jain edited this page Aug 27, 2023 · 21 revisions

Table of Contents

Proposal

Brief Description

The project aims implement pgr_withPointsKSP and all its overloads.
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 finds K shortest paths.

State of the Project Before GSoC

Currently, the pgRouting repository implements the pgr_withPointsKSP function with only single signature (one to one).

Current Signature

pgr_withPointsKSP(Edges SQL, Points SQL start vid, end vid, K, [options])
options: [directed, heap_paths, driving_side, details]
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

However, it is not an official pgRouting function but its available for users.

Benefits to the Community

  • Adding all overloads will refrain users from writing and executing multiple queries.
  • Proposed Signatures :-
pgr_yen_withPoints(Edges SQL, Points SQL, start vid, end vid, K,[options])
pgr_yen_withPoints(Edges SQL, Points SQL, start vid, end vids, K,[options])
pgr_yen_withPoints(Edges SQL, Points SQL, start vids, end vid, K,[options])
pgr_yen_withPoints(Edges SQL, Points SQL, start vids, end vids,K,[options])
pgr_yen_withPoints(Edges SQL, Points SQL, Combinations SQL, K,[options])
options: [directed, heap_paths, driving_side, details])
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMTPY SET
  • The proposed function will return the same set of columns for all overloads, reducing users' and developers’ developing time.
  • The function will help users to calculate the K Shortest Paths not only between two vertices but also between the points (such as restaurants, supermarkets, etc.) closer to the particular edge and combinations of two.
  • Why the name is to be changed:
    • using the algorithm's author name, which will generalize better with the users and will help them to look up for the function in documentation easily.
    • Postgres does not allow two functions with the same set of input parameters but with different output columns
    • Adding these algorithms to pgRouting will result in more functionalities in pgRouting which will help the current and future users and developers to use and integrate with other algorithms.

Deliverables

  • pgr_withPointsKSP => pgr_yen_WithPoints
  • Have pgr_yen_WithPoints with all overloads:
    • one to one
    • one to many
    • many to one
    • many to many
    • combinations
  • driving_side CHAR: Value in [r,R,L,l] indicating if the driving side is:
    • r,R for right driving side
    • l,L for left driving side
    • Any other value (including NULL) will be considered as r
  • Return columns on all overloads: seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
  • pgTap test equivalence with pgr_withPoints when K = 1 and the points are actual vertices on the graph
  • Documentation of the new function
  • Documentation on how to migrate to the new function

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor @krashish8 Ashish Kumar
2nd Mentor @cvvergara Vicky Vergara
Student Software Developer @Abhinj Abhinav Jain

Weekly Report And Plan

Community Bonding Period (May 4 - May 28)

-Introduce myself to the community, interact with mentors, and actively get involved in the discussion. -Setting up the Development Environment -Develop a better understanding of PostgreSQL, PostGIS and how they interact with pgRouting. -Set up the wiki page to keep track of weekly progress.

Report

First Coding Period (May 29 - July 9)

Week 1 (May 29 - Jun 4)

  • Create new one-to-one renamed function
  • Reuse and duplicate Code wherever possible
  • Deeply study pgr_withPointsKSP

Week 1 Report

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Created a branch where i will be working.
  • Tasks in the issue #289
  • Understand the working of the function and its calls.
  • Added my name in contributor's list and Made a PR.

Plans for the next week:-

  • Will try to replicate what vicky did in this for pgr_kspWithPoints.
  • Start standardizing columns of the function

Am I blocked on anything?

  • No, Currently I am not blocked to anything.

Week 2 (Jun 5 - Jun 11)

  • Create a basic skeleton for C, C++, SQL, and pgTap Tests

Week 2 Report

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Watch Twitch about the simplification of bdAstar.
  • Tried to simplify the withPoints_ksp function similar to dijkstra but getting errors in github actions.

Plans for the next week:-

  • Will resolve the issues facing during week 2.
  • Standardise the output columns.

Am I blocked on anything?

  • No, Currently I am not blocked to anything.

Week 3 (Jun 12 - Jun 18)

  • Create C++ containers for passing SQL data to C++ containers for data processing
  • Refine the code

Week 3 Report

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Had a meeting with mentors and identified a new function signature, which can be found #300
  • Standardised the output columns of withPointsKSP

Plans for the next week:-

  • I will start testing my implemented function and backward compatibility

Am I blocked on anything?

  • As my sister's wedding draws near, my focus and dedication will be centered around this occasion. However, rest assured that I am committed to reclaiming and fulfilling my work obligations in the forthcoming weeks.

Week 4 (Jun 19 - Jun 25)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Removed unused code
  • Worked on Backward compatibility

Plans for the next week:-

  • Catch up on my week 4 work.
  • Fix pgtap cases.

Am I blocked on anything?

  • Sister's Wedding

Week 5 (Jun 26 - Jul 2)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Bug fixes in output columns
  • Some testing with doc queries

Plans for the next week:-

  • Catch up on my week 5 work.
  • Will start working on documentation.
  • pgtap test cases

Am I blocked on anything? I currently do not have any blocking issues and can proceed with my tasks smoothly.

Week 6 (Jul 3 - Jul 9)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • added more docqueries
  • worked on feedback provided by vicky

Plans for the next week:-

  • Catch up on my week 6 work.
  • Have to more work on feed provided by vicky

Am I blocked on anything? I currently do not have any blocking issues and can proceed with my tasks smoothly.

First Evaluation Period(July 10 - July 14)

  • Submit a working pgr_yen_withPoints function with its documentation without pgTap tests

Second Coding Period(July 14 - Aug 27)

Week 7 (Jul 14 - Jul 16)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Discussed the meaning of driving side with mentors and other GSoC students.
  • Updated old Code for backward compatibility
  • Updated Docqueries for newer function
  • Changed SQL functions to v4

Plans for the next week:-

  • Work on feedback.
  • Fixing pgTap cases and docqueries

Week 8 (Jul 17 - Jul 23)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Inner_query and types_check are passing for v3.6
  • resolved linting and signature errors
  • Involved in the discussion for driving_side

Plans for the next week:-

  • Will work on pgtap tests to pass on every version of pgrouting.
  • Validating parameters according to discussion.

Week 9 (Jul 24 - Jul 30)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Validating parameters according to discussion[1].
  • Work according to the issue[2]
  • Updated User and migration documentation

What do I plan on doing next week?

  • Meeting with mentors.
  • Working on update tests

Week 10 (Jul 31 - Aug 6)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Now tests pgTap passes for v3.1.3.
  • Created a tag on my forked repo[1].
  • Update test passes. Latest can be [2] and previous on [3].

What do I plan on doing next week?

  • Start preparing PR to main repository.

Week 11 (Aug 7 - Aug 13)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Changes Suggested by vicky
  • Removed old driver file
  • Minor Changes in Migration queries
  • Practiced Rebase[1].

What do I plan on doing next week?

  • Meeting with mentors
  • Rebase to main repository

Week 12 (Aug 14 - Aug 20)

Report Mail - [SoC], [pgRouting-dev]

What did I get done this week?

  • Modifying code with vicky's suggestion.
  • Updating v3.6 release note and NEWS.
  • Rebase my code.

Final Evaluation Period(Aug 21 - Aug 28)

  • Prepare PR to main repository
  • Prepare final report

Log of Pull Requests

Link to all the Pull Requests I made in GSoC-pgRouting repository for GSoC 2023

Pull Request Description Date Status
#2546 GSoC-2023: Modifying - withpointsksp August 23rd, 2023 Merged
#350 GSoC-2023: Abhinav Jain Week 12 August 17th, 2023 Merged
#341 GSoC-2023: Abhinav Jain Week 11 August 13th, 2023 Merged
#335 GSoC-2023: Abhinav Jain Week 10 August 6th, 2023 Merged
#332 GSoC-2023: Abhinav Jain Week 9 July 30th, 2023 Merged
#325 GSoC-2023: Abhinav Jain Week 8 July 23rd, 2023 Merged
#324 GSoC-2023: Abhinav Jain Week 7 July 16th, 2023 Merged
#318 GSoC-2023: Abhinav Jain Week 6 July 9th, 2023 Merged
#313 GSoC-2023: Abhinav Jain Week 5 July 2nd, 2023 Merged
#309 GSoC-2023: Abhinav Jain Week 4 June 25th, 2023 Merged
#303 GSoC-2023: Abhinav Jain Week 3 June 18th, 2023 Merged
#299 GSoC-2023: Abhinav Jain Week 2 June 10th, 2023 Merged
#291 GSoC-2023: Abhinav Jain Week 1 June 6th, 2023 Merged

Final Report

Report Mail - [SoC], [pgRouting-dev]

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 ‘nd_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:

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

References

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally