Skip to content

GSoC 2023 Implement pgr_KSP and Add All Overloads

Jump to bottom Edit New page
Aniket Agarwal edited this page Aug 27, 2023 · 22 revisions

Table of Contents

proposal

Brief Description

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.

State of the Project Before GSoC

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.

Benefits to the Community

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.

Deliverables

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

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor @krashish8 Ashish Kumar
2nd Mentor @shobhit162 Shobhit Chaurasia
Student Software Developer @Aniket-debug Aniket Agarwal

Weekly Report And Plan

Pre-bonding-period

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.

First Coding Period (May 29 - July 10)

Week 1 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • Created the base branch Aniket-2023
    • Understand the working of the function and its calls
    • Added some comments in the main pgr_ksp.hpp file where the yen algorithm works
    • Study the video: Link
    • With PR: Link
  • 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.

Week 2 Report

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

Week 3 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • Created new files: v6ksp.c, v6ksp_driver.cpp, and v6ksp_driver.h.
    • Removed all the changes made last week from ksp.c, ksp_driver.cpp, and ksp_driver.h.
    • Added docqueries for one-to-many, many-to-one, many-to-many, and combinations.
    • Made additional changes in several files to support the functionality of the newly added files.
    • PR Link: Link
  • My Plans for next week:
    • Catch up on my week 3 work.
    • Fix pgtap cases and some checks (the failing ones).

Week 4 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • Did changes suggested by @krashish8 in the previous pull request Link
    • Study migration guide Link
    • PR Link: Link
  • My Plans for next week:
    • Catch up on my week 4 work.
    • Fix pgtap cases.

Week 5 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • added start_vid and end_vid to the one-to-one overload
    • fixed pgtap tests (type_checks.pg)
    • PR Link: Link
  • My Plans for next week:
    • Catch up on my week 5 work.
    • Will start working on documentation.

Week 6 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • updated ksp doc
    • Added more docqueries
    • PR Link: Link
  • My Plans for next week:
    • Catch up on my week 6 work.
    • Will review my work with mentors and do the work accordingly.

First Evaluation Period(July 10 - July 14)

  • Submit a working pgr_ksp( ) function with its documentation (without pgTap tests).

Second Coding Period(July 14 - Aug 27)

Week 7 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • Fixed the pgtap test cases.
    • Fixed the documentation.
    • Removed the extraneous v4 files and combined them with the old files.
    • PR Link: Link
  • My Plans for next week:
    • Catch up on my week 7 work.

Week 8 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • updated following pagtap tests files:
    • no_crash_test.
    • inner_query.
    • PR Link: Link
  • My Plans for next week:
    • Catch up on my week 8 work.

Week 9 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • updated [doc][migration]
    • PR Link: Link
  • My Plans for next week:
    • Catch up on my week 9 work.

Week 10 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • updated inner_query.pg
    • updated no_crash.pg
    • updated types_check.pg
    • dropped pgr_ksp in build-extension-update-file
    • Create a tag link
    • Update tests before week 10 starts: link
    • Update tests at the end of week 10: link
    • PR Link: Link
  • My Plans for next week:
    • Catch up on my week 10 work.

Week 11 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • Get reviewed my work by @cvvergara.
    • [doc] changes suggested by @cvvergara.
    • [ksp] changes suggested by @cvvergara.
    • PR Link: Link
  • My Plans for next week:
    • Work on rebasing.

Week 12 Report

  • Report Mail - SoC, pgRouting-dev
  • The work I did in this week:
    • Practice rebasing
    • Created the tag
    • Practice Final Pull Request to develop-try1 branch
    • Created final Pull Request
    • PR Link: Link

Final Evaluation Period(Aug 28 - Sep 4)

  • Mentors will evaluate my work.
  • Mentors will submit my final evaluations.

Log of Pull Requests

Pull Request Description Date Status
#2547 GSoC-2023: Modifying KSP August 23rd, 2023 merged
#354 GSoC-2023: Aniket Agarwal Week 12 August 17th, 2023 Closed
#343 GSoC-2023: Aniket Agarwal Week 11 August 13th, 2023 merged
#336 GSoC-2023: Aniket Agarwal Week 10 August 6th, 2023 merged
#330 GSoC-2023: Aniket Agarwal Week 9 July 30th, 2023 merged
#326 GSoC-2023: Aniket Agarwal Week 8 July 23rd, 2023 merged
#322 GSoC-2023: Aniket Agarwal Week 7 July 16th, 2023 merged
#316 GSoC-2023: Aniket Agarwal Week 6 July 9th, 2023 merged
#312 GSoC-2023: Aniket Agarwal Week 5 July 2nd, 2023 merged
#307 GSoC-2023: Aniket Agarwal Week 4 June 25th, 2023 merged
#302 GSoC-2023: Aniket Agarwal Week 3 June 18th, 2023 merged
#295 GSoC-2023: Aniket Agarwal Week 2 June 10th, 2023 merged
#290 GSoC-2023: Aniket Agarwal Week 1 June 6th, 2023 merged

Final Report

Report Mail - [SoC], [pgrouting-dev] (sent to these two mailing lists of OSGeo).

Hello everyone,

With GSoC coming to an end, I hereby present my final report of the work I have done over the past three months. It has been an amazing experience and great learning, working with the pgRouting community and mentors. This report follows the guidelines set by Google and OSGeo GSoC Admins.

Title:

  • Implement pgr_KSP and Add All Overloads

Organisation:

  • pgRouting under OSGeo

Abstract:

  • This GSoC project deals with the implementation of the Overloads of the existing function pgr_KSP in pgRouting.
  • pgr_KSP This function is used to Calculate the K Shortest Paths between the source and target node of a graph.
  • The addition of Overloads will help to calculate the K Shortest Paths for the following scenarios.
    • single source and multiple targets
    • multiple sources and single target
    • multiple sources and multiple targets
    • combinations of sources and targets

The State of the Project Before GSoC:

  • The pgr_KSP function was already there in pgRouting but it didn’t have the following overloads One-to-Many, Many-to-One, Many-to-Many, and Combinations.

The addition that my project brought to pgRouting:

  • The pgr_ksp function has expanded its functionality and usability by incorporating various overload options. These options include:

  • One-to-Many Paths: Users can now find the k shortest paths from a single source to multiple target nodes. This is useful in scenarios where you have one starting location (source) and multiple potential destinations (targets).

  • Many-to-One Paths: Similarly, users can find the k shortest paths from multiple source nodes to a single target node. This could be used when you have several starting locations and want to reach a common destination.

  • Many-to-Many Paths: Your implementation allows users to find the k shortest paths between multiple source nodes and multiple target nodes. This covers more complex scenarios where there are multiple starting and ending locations.

  • Combinations of Sources and Targets: Your work enables users to mix and match different source and target combinations, creating a flexible solution that caters to a wide range of routing requirements.

  • By adding these overloads, the pgr_ksp function is more versatile and capable of addressing various routing needs. This expansion of functionality enhances the usefulness of pgRouting for real-world applications, making it more accessible and valuable to developers, researchers, and users who require advanced routing solutions.

Potential Future Work:

  • Performance Optimization: As the complexity of routing scenarios increases, the computation time for finding k shortest paths can also grow. There's potential to further optimize the algorithm, perhaps by exploring parallel processing, heuristics, or indexing techniques to speed up the computation of paths.
  • Documentation and Examples: Comprehensive documentation and usage examples are crucial for users to understand and utilize the function effectively. Improving documentation and providing practical examples would aid in the adoption of your enhancements.

Links:

Images:

  • Example Image: Link

I am absolutely thrilled to have had the incredible opportunity to be a part of both the GSoC and OSGeo communities. The knowledge and skills I've gained throughout this enriching period are invaluable assets that will undoubtedly shape my path in future development endeavours. Knowing that my code could potentially bring value to the community fills me with great satisfaction. I want to express my heartfelt gratitude to everyone who has offered their unwavering support and guidance. Here's to the power of collaboration and shared learning! Thank you all immensely!

Thanks and Regards,

Aniket Agarwal

References

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally