GSoC 2023 Improving Parameters and Standardizing Results in pgr_withPointsDD Function for pgRouting

proposal

Brief Description

This project aims to enhance the functionality of the pgr_withPointsDD function in pgRouting by improving the 'driver_side' optional parameter, adding a result column and normalizing the output. And all overloads will be implemented(Single vertex & Multiple vertices). The pgr_withPointsDD function modifies the graph to include points and using Dijkstra algorithm, extracts all the nodes and points that have costs less than or equal to the value from the starting point. The edges extracted will conform to the corresponding spanning tree.

State of the Project Before GSoC

Signature of current pgr_withPointsDD function:

pgr_withPointsDD(Edges SQL, Points SQL, root vid, distance, [options A])
pgr_withPointsDD(Edges SQL, Points SQL, root vids, distance, [options B])
options A: [directed, driving_side, details]
options B: [directed, driving_side, details, equicost]
RETURNS SET OF (seq, [start_vid], node, edge, cost, agg_cost)
OR EMPTY SET

While the pgr_withPointsDD function has been successfully implemented, further improvements are necessary. Specifically, the result columns need to include depth of node, and the 'driver_side' optional parameter requires refinement to enhance routing control and accuracy. Additionally, normalizing the output of all overloads will make the function more user-friendly.
The pgr_withPointDD function will likely officially be part of the next major release, so it is very important to overload and improve it.

Benefits to the Community

The pgr_withPointsDD function is, in fact, the pgr_drivingDistance function equipped to handle routing issues where the inputs are custom points rather than existing nodes in the graph. This makes it better suited for use in real-world scenarios, providing more practical routing solutions.
Standardize the output of the function pgr_withPointsDD by adding a column to make the returns including the depth of node, so that it has a unified output with other DD functions and expand the usability of the function.
Improve documentation on how to migrate to new features, making it easy for users and other developers to adapt to the new overloaded function.

Deliverables

pgr_withPointsDD with all overloads:
- single vertex
- multiple vertices
driving_side CHAR:
- Before:
  Value in [r, l, b] indicating if the driving side is:
  r for right driving side.
  l for left driving side.
  b for both.
- After: Value in [r, R, L, l] indicating if the driving side is:
  r,R for right driving side.br> l,L for left driving side.
  Any other value (including NULL) will be considered as r.
Return columns on all overloads:
- Before: seq, [start_vid], node, edge, cost, agg_cost
- After: seq, depth, start_vid, node, edge, cost, agg_cost
Users Documentation of the function.
Documentation on how to migrate to the new function.
pgTap test cases.

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title	GitHub Handle	Name
1st Mentor	@robe2	Regina Obe
2nd Mentor	@cvvergara	Vicky Vergara
Student Developer	@squarege	Yige Huang

Weekly Report And Plan

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.

Report//todo

Introductory Mail - [SoC], [pgrouting-dev]
Commmunity Bonding Period Report Mail - [SoC], [pgrouting-dev]

Tasks

Meetings

May 8th
- Clarified the content structure of osgeo wiki page and pgrouting GSoC wiki page
- Reviewed pgRouting GSoC wiki page
- Dealt with an issue New OSGeo users are unable to edit the wiki pages
May 15th
- Discussed whether should change or keep the function names.
May 29th
- Prepared branch on GSoC repository
- Made first PR to the prepared branch
- Got clarity on where to begin work.

First Coding Period (May 29 - July 10)

Week 1 (May 29 - Jun 4)

Basic skeleton for documentation and tests
Code skeleton of SQL , C and C++ code

Week 1 report

Report Mail - [SoC], [pgrouting-dev]
What did I get done this week?
- Created a branch in the GSoC-pgRouting repository.
- Follow mentor's guide: Watched video at: pr-2521-simplify-dijkstra-code, together with the PR: pgRouting/pgrouting#2521.
- Studied how to standardize the output columns of a function, adjust documentation queries results, and other related tasks by following PR: pgRouting/pgrouting#2516.
- Made a PR of adding my name to the contributor's list.
What do I plan on doing next week?
- Catch up on my week 1 work.
- Start standardizing the output columns of pgr_withPointsDD.
Am I blocked on anything?

Due to my final exams, I wasn't able to devote so much time to the project that there was no real progress in code. But I will catch up on my work in the coming week. I have already communicated about this and received approval from mentor.

Week 2 (Jun 5 - Jun 11)

Design and modify the acceptable values of the 'driving_side' parameter.

Week 2 report

Report Mail - [SoC], [pgrouting-dev]
What did I get done this week?
- Standardized the output columns of pgr_withPointsDD by adding a column start_vid in single vertex overload.
- Changed acceptable values of the optional parameter driving_side:
  - from: Value in [r, l, b] indicating if the driving side is:
    r for right driving side.
    l for left driving side.
    b for both.
  - to: 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.
- Updated pgTap.
What do I plan on doing next week?
- Work on adding a new column depth to pgr_withPointsDD.
- Reference pgr_primDD/pgr_kruskalDD to carry out the work.
Am I blocked on anything?
- No.

Week 3 (Jun 12 - Jun 18)

Design and implement the addition of a 'depth' column to the result columns.

Week 4 (Jun 19 - Jun 25)

Implementing pgr_withPointsDD() function with all overloads (Single Vertex & Multiple Vertices).

Week 5 (Jun 26 - Jul 2)

Prepare the test data and design SQL query.

Week 6 (Jul 3 - Jul 9)

Basic testing of the function.
Prepare First coding report.

First Evaluation Period(July 10 - July 14)

Submit working pgr_withPointsDD() function along with its documentation (without pgTap test).

Second Coding Period(July 14 - Aug 21)

Week 7 (Jul 14 - Jul 16)

Work on the feedback as provided from the First Evaluation.
Bug fixing.
Prepare second coding period Synopsis.

Week 8 (Jul 17 - Jul 23)

pgTap unit tests.

Week 9 (Jul 24 - Jul 30)

Migration documentation
Query test using sample data on pgRouting documentation.

Week 10 (Jul 31 - Aug 6)

Fixing bugs, test more.
Working on the details of the document.

Week 11 (Aug 7 - Aug 13)

Preparing for Final Delivery.
Integrating to develop branch in the main repository.

Week 12 (Aug 14 - Aug 20)

Review, complete and finalize all documentation and tests.
Create a detailed final report.

Final Evaluation Period(Aug 21 - 28)

Submit complete project with all required functions, documentation and unit pgTap test cases.
Submit final report and evaluation of mentors.