GSoC 2023 Implement pgr_withPointsKSP and Add Overloads
- Proposal
- Participants
- Weekly Report and Plan
- Log of Pull Requests
- Final Report
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.
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.
- 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.
- 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 in PDF format
| Title | GitHub Handle | Name |
|---|---|---|
| 1st Mentor | @krashish8 | Ashish Kumar |
| 2nd Mentor | @cvvergara | Vicky Vergara |
| Student Software Developer | @Abhinj | Abhinav Jain |
-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
- Introductory mail [SoC], [pgRouting-dev]
- Community Bonding Period Report [SoC], [pgRouting-dev]
- Create new one-to-one renamed function
- Reuse and duplicate Code wherever possible
- Deeply study pgr_withPointsKSP
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.
- Create a basic skeleton for C, C++, SQL, and pgTap Tests
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.
- Create C++ containers for passing SQL data to C++ containers for data processing
- Refine the code
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.
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
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.
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.
- Submit a working pgr_yen_withPoints function with its documentation without pgTap tests
Report Mail - [SoC], [pgRouting-dev]
What did I get done this week?
- Discussed the meaning of
driving sidewith 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
- Testing against OpenStreetMap data
- Internal tests for “pgr_yen_withPoints”
- No server crash test
- pgTap Unit tests
- Write meaningful pgTap tests for the function, equivalence with Dijkstra when k = 1 and for all edge cases and functionalities
- Fix bugs in the unit test
- Create queries for documentation using pgRouting sample data
- Verify Documentation
- Migration Documentation work
- Verify documentation and migration documentation works Prepare final submission along with full documentation.
- Prepare PR to main repository
- Prepare final report
