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.
- 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
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.
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
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.
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
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.
- Prepare PR to main repository
- Prepare final report
Link to all the Pull Requests I made in GSoC-pgRouting repository for GSoC 2023
| Pull Request | Description | Date | Status |
|---|---|---|---|
| #2545 | GSoC-2023: Modifying - withpointsdd - supplement | Aug 22th, 2023 | Merged |
| #2544 | GSoC-2023: Modifying - withpointsdd | Aug 21th, 2023 | Merged |
| #350 | GSoC-2023: Yige Huang Week 12 | Aug 20th, 2023 | Merged |
| #341 | GSoC-2023: Yige Huang Week 11 | Aug 13td, 2023 | Merged |
| #335 | GSoC-2023: Yige Huang Week 10 | Aug 7th, 2023 | Merged |
| #332 | GSoC-2023: Yige Huang Week 9 | July 31st, 2023 | Merged |
| #325 | GSoC-2023: Yige Huang Week 8 | July 23rd, 2023 | Merged |
| #324 | GSoC-2023: Yige Huang Week 7 | July 16st, 2023 | Merged |
| #318 | GSoC-2023: Yige Huang Week 6 | July 8th, 2023 | Merged |
| #313 | GSoC-2023: Yige Huang Week 5 | July 1st, 2023 | Merged |
| #309 | GSoC-2023: Yige Huang Week 4 | July 24th, 2023 | Merged |
| #303 | GSoC-2023: Yige Huang Week 3 | July 15th, 2023 | Merged |
| #299 | GSoC-2023: Yige Huang Week 2 | June 9th, 2023 | Merged |
| #291 | GSoC-2023: Yige Huang Week 1 | June 4th, 2023 | Merged |
| #278 | Task 2: Experience with GitHub & Git | March 23th, 2022 | GSoC Task Pull Request - Not to Merge |
