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 Jul 1, 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.

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

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