Skip to content

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

Jump to bottom Edit New page
Yige Huang edited this page Aug 27, 2023 · 32 revisions

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Had a meeting with mentors and identified a new function signature, which can be found here.
    • Reverted last week's changes
    • Created new pgr_withPointsDD:
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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Work on the feedback last week.
    • Create basic skeleton for calculating depth, more details can be found here.

  • What do I plan on doing next week?

    • Continue the work of adding depth output column.

  • Am I blocked on anything?

    • Due to the lack of understanding of pgRouting's graph, edge, node and other related data structures and vistor, my coding work is somewhat difficult. But I will learn about them by reading the source code and constantly debugging experiments. Hope to finish the work of adding the new column next week without a hitch.

Week 5 (Jun 26 - Jul 2)

  • Prepare the test data and design SQL query.

Week 5 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Finished the work of adding new output column depth.
    • Tested locally and got expected results.

  • What do I plan on doing next week?

    • Catch up previous plans.
    • Design more SQL query test.

  • Am I blocked on anything?

    • NO.

Week 6 (Jul 3 - Jul 9)

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

Week 6 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Checked driving side parameter at SQL level instead of C/C++ level.
    • Updated docqueries for the old withPointsDD function.
    • Fixed bug.

  • What do I plan on doing next week?

    • Prepare for First Evaluation.
    • Discuss progress and something difficulties with mentor.
    • Work on feedback.

  • Am I blocked on anything?

    • Lack of knowledge about pgtap, it takes time to learn. I will ask mentor for guidance when necessary.

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

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Discussed the meaning of driving side with mentors and other GSoC students.
    • Updated documentation.
    • Fixed pgtap tests. The pgtap tests of pgr_withPointsDD now pass in both new & old versions.
    • Fixed a bug like issues979 for the new pgr_withPointsDD function.

  • What do I plan on doing next week?

    • Validate 'driving side' parameter.
    • Work on feedback.

  • Am I blocked on anything?

    • No this week.

Week 8 (Jul 17 - Jul 23)

  • pgTap unit tests.

Week 8 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Removed the extraneous files and combined them with the old files.
    • Validated driving side as mentioned in here:
      • if directed graph then valid values r & l.
      • if undirected graph then valid values b.
    • Adjusted pgtap tests and docqueries.
    • Made my code pass all the tests.

  • What do I plan on doing next week?

    • Update documentation.

  • Am I blocked on anything?

    • No.

Week 9 (Jul 24 - Jul 30)

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

Week 9 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Mentor's guidance issue

    • Documentation of pgr_withPointsDD.

    • Migration guide.

    • Link of update test CI (before handling the update tests).

  • What do I plan on doing next week?

    • Meeting with mentors.
    • Working on update tests.

  • Am I blocked on anything?

    • No.

Week 10 (Jul 31 - Aug 6)

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

Week 10 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Practiced:
      • Do cherry-pick to get the latest commit on the develop branch.
      • Try to create a new tag.
      • Do rebase, resolve all conflicting codes and save the result as a tag.
    • Improved documentation of pgr_withPointsDD.
    • Watched Twitch by Vicky to learn how to prepare for a PR.
    • Removed code that should have been removed before.

  • What do I plan on doing next week?

    • Meeting with mentors.
    • Start preparing for PR to the main repo.

  • Am I blocked on anything?

    • No.

Week 11 (Aug 7 - Aug 13)

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

Week 11 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Handled old and new code with just one function (aka simplify the code) in:
      • include/drivers/driving_distance/withPoints_dd_driver.h
      • src/driving_distance/many_to_dist_withPointsDD.c
      • src/driving_distance/withPoints_dd_driver.cpp
    • Removed duplicate code.

  • What do I plan on doing next week?

    • Meeting with mentors.
    • Verify documentation and migration documentation works.
    • Prepare final submission.

  • Am I blocked on anything?

    • No.

Week 12 (Aug 14 - Aug 20)

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

Week 12 report

  • Report Mail - [SoC], [pgrouting-dev]

  • What did I get done this week?

    • Modifying code with vicky's suggestion.
    • Fixing update test.
    • Updating v3.6 release note and NEWS.
    • Rebase my code with nice commit log and merged into develop-try1 branch

  • What do I plan on doing contributor evaluation period?

    • Submit final report on wiki and GSoC Dashboard

  • Am I blocked on anything?

    • No.

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]

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

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally