[SoC] GSoC 2023 - Final report: Implement-pgr_KSP-and-Add-All-Overloads

[Aniket Agarwal]

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](
https://developers.google.com/open-source/gsoc/help/work-product) and
[OSGeo GSoC Admins](
https://lists.osgeo.org/pipermail/soc/2023-August/005114.html).

1.(a) **Title:**

  - Implement pgr_KSP and Add All Overloads

1.(b) **Organisation:**

  - pgRouting under OSGeo

2. **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*

3. **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.

4. **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.

5. **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.

6. **Links:**

- **Tags:**

    - pgr_KSP (2023-aniket-KSP-overloads):
https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2023-aniket-KSP-overloads

- **Pull Requests:**

  - **Final Pull Request:**
https://github.com/pgRouting/pgrouting/pull/2547

  - **Intermediate pull requests:**
https://github.com/pgRouting/GSoC-pgRouting/pulls?q=is%3Apr+author%3AAniket-debug

- **Project Documentation (Wiki Page):**
https://github.com/pgRouting/pgrouting/wiki/GSoC-2023-Implement-pgr_KSP-and-Add-All-Overloads

7. **Images:**

   - Example Image:
https://drive.google.com/file/d/1BHN0w7t3_HCM6t_x0c_3IKVpj1GH_BBG/view?usp=sharing

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20230827/f0483aac/attachment.htm>