GSoC 2023 Implementing Dijkstra’s Driving distance Function and its migration
- Proposal
- Participants
- Weekly Report and Plan
- Log of Pull Requests
- Final Report
The project aims to implement a new function called "pgr_dijkstraDD" that replaces the existing "pgr_drivingDistance" function. The new function will have all overloads,including single and multiple vertices as before. The function will return columns such as sequence, depth, start vertex ID, node, edge, cost, and aggregate cost for all overloads. The project will also include testing of the new function with pgTap Tests.Documentation for the new function and migration guides for users to switch to the new function will also be created.The Dijkstra’s Driving Distance algorithm is employed to extract all nodes that can be reached from the root node with cost of reaching not exceeding the given distance D. This algorithm is primarily based on Dijkstra's Algorithm.
Signature of current pgr_drivingDistance function:
pgr_drivingDistance(Edges SQL, Root vid, distance, [directed])
pgr_drivingDistance(Edges SQL, Root vids, distance, [options])
options: [directed, equicost]
RETURNS SET OF (seq, [from_v,] node, edge, cost, agg_cost)
Currently the function does not have a depth column which tells the distance of a particular node from the root node.Signatures, Column names, and its contents are not consistent.Other than the above two stated points, the function “pgr_drivingDistance” is accurate, stable and gives correct results.
- It is one of the widely used functions from all the pgRouting functions.Because it operates on dijkstra function which is of utmost importance in the pgRouting library.
- Added extra Depth Column
- Postgres does not allow two functions with the same set of input parameters but with different output columns.
- While making changes to the function we don’t want to break other user’s code while it is in testing and is stable .So we make a renamed function side by side ,so that it doesn’t affect the stable function.
- pgr_dijkstraDD is better because it uses the algorithm inventor’s name.
- Completing the project would make the name and structure of the function similar to other functions https://docs.pgrouting.org/dev/en/pgr_primDD.html https://docs.pgrouting.org/dev/en/pgr_kruskalDD.html
- Open source: “pgr_dijkstraDD” function is part of the open-source pgRouting extension, which means that it is free to use and can be customised by users to meet their specific needs.
- Adding this algorithm to pgRouting will result in more functionalities in pgRouting which will help the current and future users and developers to use and integrate it with other algorithms.
The deliverables at the end of the GSoC period are:-
- Make and implement “pgr_dijkstraDD” function with all overloads: ➔ Single Vertex ➔ Multiple Vertices
- C, C++, SQL code related to that function
- Return columns on both the overloads: Seq, depth, start_vid, node, edge, cost, agg_cost
- Return columns on all the overloads will be seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost
- Basic pgTap Tests
- Full weekly report of evaluations
- Documentation of the new function
Detailed Proposal in PDF format
| Title | GitHub Handle | Name |
|---|---|---|
| 1st Mentor | @shobhit162 | Shobhit Chaurasia |
| 2nd Mentor | @robe2 | Regina Obe |
| Student Software Developer | @aryan1010 | Aryan Gupta |
- Task 1: Intent of application
- Task 2: Experience with GitHub & Git
- Task 3: Build locally pgRouting
- Task 4: Get familiar with C++
- Task 5: Get familiar with pgRouting
- I will engage with my mentors, participate more actively in discussions, and learn more about pgRouting.
- Learn the pgRouting coding style from Google C++ Style Guide
- Adopt the pgRouting-established standards for development, documentation, and testing.
- Set up the wiki page to keep track of weekly progress.
- Design “pgr_dijkstraDD” function
- Create the new single vertex renamed function
- ➔ Reuse and Duplicate Code when possible
- Understanding and getting deep into previous code (“pgr_drivingdistance”)
- Design the detailed signature for the “pgr_dijkstraDD” function
- Make Basic Code skeleton of SQL,C and C++ files
- Create C++ containers for passing SQL data to C++ containers for data processing
- Refine the code
- Creation of helper class, wrappers.
- I➔ Implementing Single vertex and Multiple Vertices
- Test against OSM data
- Make sure the eros are properly handled
- Write appropriate queries using the pgRouting documentation's sample data.
- Work on the submissions required as part of the first evaluation.
- Prepare user documentation.
- Prepare a report for the first evaluation
- Submit a working pgr_dijsktraDD( ) function with its documentation (without pgTap tests)
- Work on the feedback provided from the first evaluation.
- Bug fixing.
- Preparing second coding period Synopsis
- Internal tests for “pgr_dijkstraDD”
- No server crash test
- pgTap Unit tests
- Create queries and results for documentation using the pgRouting sample data.
- Creating Documentation on Migrating thenew function
- Fix all the bugs/problems and documentation details.
- Wiki Page
- Verify documentation and migration documentation works Prepare final submission along with full documentation.
- Submit the complete project with all the required functions, documentation and unit tests.
