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

Table of Contents

• Proposal
  • Brief Description
  • State of the Project Before GSoC
  • Benefits to the Community
  • Deliverables
  • Detailed Proposal
• Participants
• Weekly Report and Plan
  • Community Bonding Period (May 4 - May 28)
  • First Coding Period (May 29 - July 10)
    • Week 1 (May 29 - Jun 4)
    • Week 2 (Jun 5 - Jun 11)
    • Week 3 (Jun 12 - Jun 18)
    • Week 4 (Jun 19 - Jun 25)
    • Week 5 (Jun 26 - Jul 2)
    • Week 6 (Jul 3 - Jul 9)
  • First Evaluation Period(July 10 - July 14)
  • Second Coding Period(July 14 - Aug 21)
    • Week 7 (Jul 14 - Jul 16)
    • Week 8 (Jul 17 - Jul 23)
    • Week 9 (Jul 24 - Jul 30)
    • Week 10 (Jul 31 - Aug 6)
    • Week 11 (Aug 7 - Aug 13)
    • Week 12 (Aug 14 - Aug 20)
  • Final Evaluation Period(Aug 21 - 28)
• Log of Pull Requests
• Slides
• Final Report

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

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 2 (Jun 5 - Jun 11)

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

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.

Log of Pull Requests

Slides

Final Report