Skip to content

GSoC 2023 Implement pgr_KSP and Add All Overloads

Jump to bottom Edit New page
Aniket Agarwal edited this page Jul 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

  • Update tests before Week 9 starts: Link
  • Update tests at the end of Week 9:

Week 10 Report

  • Fix bugs in the unit test.
  • Create queries for documentation using the pgRouting sample data.

Week 11 Report

  • Review, Verify documentation
  • Migration documentation work.

Week 12 Report

  • Prepare PR for the main repository.
  • Prepare the final report.
  • Submit the complete project with all the required files and final report.
  • Submit the mentor evaluation.

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
#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

References

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally