GSoC 2023 Implement pgr_KSP and Add All Overloads
- Proposal
- Participants
- Weekly Report and Plan
- Log of Pull Requests
- Final Report
- References
The implementation of a pgr_yen() function that can calculate K shortest paths for various scenarios is essential for many applications. This project aims to implement a pgr_yen function that can handle five different scenarios that are one-to-one, one-to-many, many-to-one, many-to-many, and combinations of (source, target). By implementing such a function, we can efficiently and accurately find multiple shortest paths for different scenarios and improve the performance of various applications that rely on this functionality. This also includes the deprecation of pgr_ksp by making migration documentation of this new function.
Signature of current pgr_KSP function:
pgr_KSP(Edges SQL, start vid, end vid, K, [options])
options: [directed, heap_paths]
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
As of now, the pgr_ksp function is already there in pgRouting but it doesn’t have the mentioned overloads. There are more functions based on pgr_ksp, so pgr_ksp acts as a base function for them. That’s why we need the implementation of pgr_yen with all the overloads: One-to-one, one-to-many, many-to-one, many-to-many, and combinations. Also, pgr_ksp is based on Yen’s algorithm and Postgres does not allow two functions with the same set of input parameters but with different output columns. So, it is more logical to rename it as pgr_yen.
Adding the pgr_yen function to pgRouting will be useful for various scenarios. A few are:
- It can calculate at most k shortest paths between two nodes.
- It will work in the single source and single target scenario.
- It will work in the single source and multiple targets scenario.
- It will work in multiple sources and single target scenarios.
- It will work in multiple sources and multiple target scenarios.
- It will work for combinations of sources and targets as well.
- These overloads will make the algorithm ready for more practical routing in real-world usage.
- Adding this algorithm to pgRouting will result in more functionalities in pgRouting which will help the current and future users and developers to use and integrate it with other algorithms.
The deliverables at the end of the GSoC period are:-
- Implementation of pgr_yen( ) function with all overloads.
- Code with detailed comments.
- User’s documentation.
- Return columns on all the overloads will be seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
- Documentation on how to migrate from pgr_ksp to pgr_yen.
- A wiki page for each week’s progress and product created.
- Basic pgTap tests for the mentioned function equivalence with pgr_dijkstra when
k=1.
Detailed Proposal in PDF format
| Title | GitHub Handle | Name |
|---|---|---|
| 1st Mentor | @krashish8 | Ashish Kumar |
| 2nd Mentor | @shobhit162 | Shobhit Chaurasia |
| Student Software Developer | @Aniket-debug | Aniket Agarwal |
- Task 1: Intent of application
- Task 2: Experience with GitHub & Git
- Task 3: Build locally pgRouting
- Task 4: Get familiar with C++
- Task 5: Get familiar with pgRouting
- 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.
- Create the new one-to-one renamed function
- Reuse code of pgr_ksp wherever possible
- Deeply study pgr_ksp code and all files
- Report Mail - SoC, pgRouting-dev
- The work I did in this week:
-
My Plans for next week:
- Discuss the Doubts with meteors.
- Understand the significance of Heap_Paths.
- Will do Some changes in the Code to create a structure for one-to-many if time allows.
- Create a basic skeleton for C, C++, SQL, and pgTap tests.
- Go through Dijkstra-related work implemented with overloads on pgRouting.
- Start creating the pgr_yen() function.
- Report Mail - SoC, pgRouting-dev
-
The work I did in this week:
- Watch Twitch about the simplification of bdAstar
- Added all the overloads in pgr_ksp and passed doc-queries
- PR Link: Link
-
My Plans for next week:
- Catch up on my week 2 work.
- fix pgtap cases.
- Read data from PostgreSQL.
- Create C++ containers for passing SQL data to C++ containers for data processing.
- Transfer data to C++ containers suitably for use with Yen.
- Creation of helper class, wrappers.
- Implementing one-to-many, many-to-one, many-to-many and combinations code.
- Transform result to C container for executing SQL queries.
- Creation of example queries using prRouting sample data.
- Work on the submissions required as a part of the first evaluation.
- Prepare user documentation.
- Prepare a report for the first evaluation.
- Submit a working pgr_yen( ) function with its documentation (without pgTap tests).
- Work on the feedback provided from the first evaluation.
- Learn to create pgTap tests.
- Fix all the bugs/problems and documentation details.
- Write meaningful pgTap tests for the function, equivalence with Dijkstra when k=1 and for all the edge cases and functionalities.
- Fix bugs in the unit test.
- Create queries for documentation using the pgRouting sample data.
- Review, Verify documentation
- Migration documentation work.
- Prepare PR to the main repository.
- Prepare the final report.
- Submit the complete project with all the required files and final report.
- Submit the mentor evaluation.
- Mentors will evaluate my work.
- Mentors will submit my final evaluations.
| Pull Request | Description | Date | Status |
|---|---|---|---|
| #290 | GSoC-2023: Aniket Agarwal Week 1 | June 6th, 2023 | opened |
- pgRouting GSoC Ideas
- pgRouting Documentation
- Algorithms Index for pgRouting
- pgRouting Sample Graph Data for pgTap testing
- [pgr_ksp() Documentation
- Wikipedia Yen’s Algorithm
- Boost Library
- pgr_dijkstra() Documentation
- OSGeo GSoC recommendation
- GSoC Program rules
