GSoC 2023 Improving Parameters and Standardizing Results in pgr_withPointsDD Function for pgRouting - pgRouting/pgrouting GitHub Wiki

Table of Contents

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

Tasks

  • Create the OSGeo User ID，request writing access to the OSGeo wiki, for editing all info related to my project.
  • Set up the development environment.
  • Interact with mentors, introduce myself to the community, and actively get involved in the discussion.
  • Set up a wiki page to keep track of weekly progress.
  • Add a wiki link to OSGeo's accepted student's wiki page.
  • Studied GSoC students guide and the OSGeo recommendations for students.
  • Introduce myself and my project on OSGeo's SOC and pgrouting-dev mailing list.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Develop a better understanding of PostgreSQL, PostGIS, Pl/pgSQL, and how they interact with pgRouting.
  • Learn to create unit tests using pgTAP.
  • Learned how and where to create Pull Request, merge and how to commit, etc.
  • Created a public repository GSoC-pgRouting where all my works are reflected in the GSoC period.
  • Created a new branch named yige-2023 in the GSoC-pgRouting repository, where I will be merging all the Pull Requests.

Meetings

  1. May 8th
  2. May 15th
  3. 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

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(https://lists.osgeo.org/pipermail/soc/2023-June/005036.html), pgrouting-dev(https://lists.osgeo.org/pipermail/pgrouting-dev/2023-June/002447.html)

  • 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 3 report

pgr_withPointsDD([Edges SQL, Points SQL, root vid, distance, driving side, [options A])
pgr_withPointsDD([Edges SQL, Points SQL, root vid, distance, driving side, [options B])
options A: [directed,  details]
options B: [directed,  details, equicost]

RETURNS SET OF (seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

where: In driving side, "Both" is only valid on undirected graphs

  • What do I plan on doing next week?

    • adding depth output column to new pgr_withPointsDD.

  • Am I blocked on anything?

NO.

Week 4 (Jun 19 - Jun 25)

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

Week 4 report

Week 5 (Jun 26 - Jul 2)

  • Prepare the test data and design SQL query.

Week 5 report

Week 6 (Jul 3 - Jul 9)

  • Basic testing of the function.
  • Prepare First coding report.

Week 6 report

First Evaluation Period(July 10 - July 14)

  • Submit working pgr_withPointsDD() function along (without pgTap test and documentation).

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

Week 8 (Jul 17 - Jul 23)

  • pgTap unit tests.

Week 8 report

Week 9 (Jul 24 - Jul 30)

  • Migration documentation
  • Query test using sample data on pgRouting documentation.

Week 9 report

Week 10 (Jul 31 - Aug 6)

  • Fixing bugs, testing more.
  • Working on the details of the document.

Week 10 report

Week 11 (Aug 7 - Aug 13)

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

Week 11 report

Week 12 (Aug 14 - Aug 20)

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

Week 12 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

Link to all the Pull Requests I made in GSoC-pgRouting repository for GSoC 2023

Pull Request Description Date Status
#2545 GSoC-2023: Modifying - withpointsdd - supplement Aug 22th, 2023 Merged
#2544 GSoC-2023: Modifying - withpointsdd Aug 21th, 2023 Merged
#350 GSoC-2023: Yige Huang Week 12 Aug 20th, 2023 Merged
#341 GSoC-2023: Yige Huang Week 11 Aug 13td, 2023 Merged
#335 GSoC-2023: Yige Huang Week 10 Aug 7th, 2023 Merged
#332 GSoC-2023: Yige Huang Week 9 July 31st, 2023 Merged
#325 GSoC-2023: Yige Huang Week 8 July 23rd, 2023 Merged
#324 GSoC-2023: Yige Huang Week 7 July 16st, 2023 Merged
#318 GSoC-2023: Yige Huang Week 6 July 8th, 2023 Merged
#313 GSoC-2023: Yige Huang Week 5 July 1st, 2023 Merged
#309 GSoC-2023: Yige Huang Week 4 July 24th, 2023 Merged
#303 GSoC-2023: Yige Huang Week 3 July 15th, 2023 Merged
#299 GSoC-2023: Yige Huang Week 2 June 9th, 2023 Merged
#291 GSoC-2023: Yige Huang Week 1 June 4th, 2023 Merged
#278 Task 2: Experience with GitHub & Git March 23th, 2022 GSoC Task Pull Request - Not to Merge

Slides

https://drive.google.com/file/d/1rQUkA5XaKqpIv5iG0OfYPsLTb7MHsh4_/view?usp=sharing

Final Report

Report Mail - SoC(https://lists.osgeo.org/pipermail/soc/2023-August/005119.html)

Hello everyone,

As GSoC comes to a close, I am pleased to present my final report summarizing the work I have accomplished over the past twelve weeks. This period has been an incredible experience, providing me with valuable learning opportunities while collaborating with the pgRouting community and mentors. The report adheres to the guidelines outlined by Google and OSGeo GSoC Admins.

  1. (a) Title: Improving Parameters and Standardizing Results in pgr_withPointsDD Function for pgRouting (b) Organization: pgRouting under OSGeo

  2. Abstract: 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.

During the project, after discussions, the expectations for this function were somewhat different from the original proposal. The final outcome is as follows:

  • The function signatures have changed, incorporating new columns in the new signatures.
  • The function primarily caters to driving cases, hence the 'driver_side' parameter has transitioned from optional to mandatory. Moreover, the valid values for this parameter differ for directed and undirected graphs.
  1. The state of the art before GSoC:

Signature of current pgr_withPointsDD function:

  • The driving_side parameter is optional.
  • Default value of driving_side is b.

Results of current pgr_withPointsDD function:

  • Depending on the overload used, the columns start_vid might be missing.
  • Overload pgr_withPointsDD (Single vertex) does not have start_vid.

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.

  1. The addition (added value) that your project brought to the software:

The deliverables include code, documentation, documentation tests, and the pgTAP tests of pgr_withPointsDD function:

In all the overloads, the function signatures have been modified:

  • The driving_side parameter now is compulsory.
  • Valid values differ for directed and undirected graphs.
    • Does not have a default value.
    • In directed graph, valid values are [r, R, l, L]
    • In undirected graph, valid values are [b, B]

Standardize the output 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. Return columns on all overloads:

  • Before: seq, [start_vid], node, edge, cost, agg_cost
  • After: seq, depth, start_vid, node, edge, cost, agg_cost

Improve documentation on how to migrate to new features, making it easy for users and other developers to adapt to the new overloaded function.

  1. Potential Future Work:

The work on the pgr_withPointsDD function has already been completed. However, in line with the goal of standardizing similar functions, the signatures of other relevant functions can also be improved.

Specifically, it would be beneficial to add an optional parameter 'equicost' to the pgr_kruskalDD and pgr_primDD functions, similar to other DD functions. This addition would enhance the functionality and consistency across these functions.

  1. Links:

  2. Image:

I am thrilled to be a part of the incredible GSoC and OSGeo communities. This experience has been tremendously valuable. It would bring me immense joy to see my code benefit the community. Lastly, thank you everyone for the supports!

Thanks and Regards,

Yige Huang

Pre-Bonding Period (Mar 22 - Apr 4)

References