Skip to content

GSoC 2017 Rewrite TRSP

Jump to bottom Edit New page
Vidhan Jain edited this page Aug 23, 2017 · 71 revisions

Welcome to the PgRouting wiki for TRSP.

Contents of the Wiki

Abstract

In graph theory, the ​shortest path problem​ is the problem of finding a path between two vertices(or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. In real life scenario, the road network is modeled as a graph where the graph's vertices correspond to road junctions and the edges correspond to road segments, each weighted by the positive length of its road segment.

A turn models a movement from one edge element to another. Often turns are created to increase the cost of making the movement, or prohibit the turn entirely. For example, a turn feature representing a left-hand turn at an intersection could be assigned a cost of 30 seconds to model the average time it takes for the left-turn light to change to green. Similarly, a restriction attribute could read a field value from a turn feature to prohibit it. This is useful when the turning movement is posted as illegal (no left turns).

State of the project before GSoC

TRSP is implemented in PgRouting but the code has issues which are not fixed as yet. Wrappers are added to the codebase that enhance the functionality of TRSP but fail to fix the issues. The following functionality is added through the use of wrappers:-

  • pgr_dijkstraTRSP(one to one) (aka pgr_trsp)
  • pgr_withPointsTRSP(one to one) (aka pgr_trsp)
  • pgr_dijkstraViaTRSP() (aka pgr_trspViaVertices)
  • pgr_withPointsViaTRSP() (aka pgr_trspViaEdges)

Here​ is the link to a wiki page that describes the issues associated with the current implementation of the pgr_trsp code in PgRouting.

Project Goal

  • Complete pgr_lineGraph with code, tests and documentation.
  • Modify dijktra code to consider costs on the vertices.
  • pgr_dijkstraTRSP is out of scope.

Biography

  • Name: Vidhan Jain

  • Country: India

  • School: The LNM Institute of Information Technology

  • Degree: B Tech. in Computer Science & Engineering

  • Email: vidhanj1307@gmail.com

Project

Log Of Pull Requests

Pull request Description Date Status
#915 Add name and email-id to all the created files August 19, 2017 Merged
#913 Add newly created images and remove the previous ones August 18, 2017 Merged
#910 Graph to Line Graph (no weights) August 17, 2017 Merged
#904 Added queries in doc of line Graph for undirected graph August 14, 2017 Merged
#901 Add implementation of transformation of undirected graph to line graph August 12, 2017 Merged
#899 Add pgr_lineGraph to the proposed.rst August 10, 2017 Merged
#896 Add documentation for pgr_lineGraph August 7, 2017 Merged
#885 Integrating pgr_lineGraph with pgr_dijkstraTRSP July 28, 2017 Merged
#878 Implementation of pgr_lineGraph continued July 16, 2017 Merged
#876 Implement pgr_lineGraph July 10, 2017 Merged
#869 Update the gsoc/rewritetrsp branch with the develop branch code July 5, 2017 Merged
#868 Add pgtap tests July 5, 2017 Merged
#863 Logic to test whether graph conversion is required added June 26, 2017 Merged
#860 Create pgr_dijkstraTRSP.hpp file June 22, 2017 Merged
#859 Pass restriction parameter to dijkstraTRSP_driver.cpp June 22, 2017 Merged
#834 Input the data from the restrict table June 13, 2017 Merged
#833 Doc for pgr_dijkstraTRSP June 13, 2017 Merged
#831 Add pgr_dijkstraTRSP to proposed.rst. June 13, 2017 Merged
#827 Updating the upstream gsoc/rewriteTRSP branch June 11, 2017 Merged
#826 Fixing the lost CMakeLists.txt file June 11, 2017 Closed
#822 Merging pgr_dijkstraTRSP code in GsocDoc branch for documentation purposes June 9, 2017 Merged
#811 Relocating Documentation Files June 6, 2017 Merged
#806 Template code for pgr_dijkstraTRSP June 3, 2017 Merged
#802 Fixing the installation of POSTGIS on AppVeyor May 27, 2017 Merged
#136 Adding pgr_dijkstra for practice May 20, 2017 Merged
#792 Deleting pgr_path_t structure from pgr_types.h file May 19, 2017 Merged
#787 Linting the code for TRSP based on the C and C++ google guidelines. May 16, 2017 Merged
#740 Fix Warning in TRSP March 1, 2017 Merged

Reports

Week 12

1) TITLE

Rewrite of Turn Restricted Shortest Path Algorithm in PgRouting

2) SOFTWARE COMMUNITY

PgRouting, under OSGeo.

3) ABSTRACT

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. In real life scenario, the road network is modeled as a graph where the graph's vertices correspond to road junctions and the edges correspond to road segments, each weighted by the positive length of its road segment.

A turn models a movement from one edge element to another. Often in the real world scenario, turn restrictions such as no-left-turn, no-right-turn etc. are imposed on the road network.

The aim of the project was to come up with a solution for calculating the shortest path from a given source node to a destination node in the graph containing turn restrictions.

4) STATE BEFORE

TRSP is implemented in PgRouting but the code has issues which are not fixed as yet.

Wrappers are added to the codebase that enhance the functionality of TRSP but fail to fix the issues. The following functionality is added through the use of wrappers:-

  • pgr_dijkstraTRSP(one to one) (aka pgr_trsp)
  • pgr_withPointsTRSP(one to one) (aka pgr_trsp)
  • pgr_dijkstraViaTRSP() (aka pgr_trspViaVertices)
  • pgr_withPointsViaTRSP() (aka pgr_trspViaEdges)

Here is the link to a wiki page that describes the issues associated with the current implementation of the pgr_trsp code in PgRouting.

5) THE ADDITION

  • Pgr_dijkstraTRSP:

    • Implemented code that works when the resultant path from source to destination does not pass through restricted edges.
    • Some tests for the pgr_dijkstraTRSP for the working case have been done.
    • Some documentation has been done.

  • Pgr_lineGraph:

    • Implemented code for pgr_lineGraph for unweighted graphs
    • This functionality is to be used by the pgr_dijkstraTRSP.
    • Finished the user’s documentation
    • Finished the basic tests.

6) PENDING WORK

  • Pgr_lineGraphWeighted needs to be implemented.
  • Dijkstra algorithm needs to be applied on the weighted line graph.
  • The above functions need to be incorporated to pgr_dijstraTRSP to process the paths when they pass through a restriction.

7) LINKS

Week 11

  1. What did you get done this week?

    This week, I completed the implementation of pgr_lineGraph for undirected graphs.

    • Details along with the commit log can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    In the coming week, I'll be working on the implementation of pgr_weightedLineGraph.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    No, I am not blocked currently.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#third-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#official-coding-period-phase-3july-25---august-21

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 10

I along with the mentors have decided to change the scope of the project.

New Scope

  1. Complete pgr_lineGraph along with the tests and documentation.
  2. At an experimentation level, change the dijkstra code to also consider costs on vertices and/or work on supporting costs on vertices on dijkstra queries.
  3. pgr_dijkstraTRSP becomes out of scope.

Reasons

It turned out, that for making the proposal idea work, pgRouting needs some functionality that it does not have currently.

  • I already have code for pgr_dijkstraTRSP that work when the path does not pass through a restriction.
  • I am in the process of making pgr_lineGraph for unweighted graphs.
  • pgr_lineGraphWeighted which considers weights on graphs.
  • Currently pgRouting supports dijkstra queries where only edges have costs and is missing support on costs with vertices.

  1. What did you get done this week?

    This week, I completed the documentation of pgr_lineGraph. Also, fixed a major bug in its implementation.

    • Details along with the commit log can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    In the coming week, I'll be working on the implementation of Dijktra that considers costs on vertices.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    No, I am not blocked currently.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#third-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#official-coding-period-phase-3july-25---august-21

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 9

  1. What did you get done this week?

    This week, I completed the integration of pgr_lineGraph with pgr_dijkstraTRSP. I also added the code to remove the restricted edges of size 2 from the line Graph.

    • Details along with the commit log can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    In the coming week, I'll be working on the implementation of Dijktra in the Line Graph.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    No, I am not blocked currently.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#third-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#official-coding-period-phase-3july-25---august-21

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 8

  1. What did you get done this week?

    This week, I implemented the logic to convert the given graph into its corresponding Line Graph.

    • Details along with the commit log can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    I'll work on the integration of pgr_lineGraph and pgr_dijkstraTRSP as well as on the implementation of Dijktra on the Line Graph in the coming week.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    No, I am not blocked currently.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#second-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#official-coding-period-phase-3july-25---august-21

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 7

  1. What did you get done this week?

    This week, I started with the implementation to convert the given graph to Line graph as pgr_LineGraph function in PgRouting.

    • Details along with the commit log can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    I hope to complete the implementation of pgr_LineGraph and its integration with the pgr_dijkstraTRSP.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    No, I am not blocked currently.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#second-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#official-coding-period-phase-2june-27---july-24

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 6

  1. What did you get done this week?

    This week, I designed the pgtap tests using the sample test graph to test the dijkstraTRSP functionality.

    • Details along with the commit log can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    I hope to overcome the blockade and implement the Line graph conversion functionality.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    Currently I am blocked with this issue.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#second-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#official-coding-period-phase-2june-27---july-24

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 5

  1. What did you get done this week?

    This week, I debugged the logic that I created last week to verify the result of pgr_dijkstra of turn restrictions using unit tests. I also created a Restriction class in C++ that will act as a container to store the values of Restrict_t in C.

    • Details can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    I'll be implementing the main functionality to calculate the valid path in case pgr_dijkstra fails to find that.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    I have had issues with my laptop screen and I couldn't work for the past 2-3 days due to that. I think it will take 2-3 more days to fix that, so I am blocked due to that.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#second-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#official-coding-period-phase-2june-27---july-24

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 4

  1. What did you get done this week?

    This week, I created pgr_dijkstraTRSP.hpp file which will hold the main logic of the dijkstraTRSP. In certain scenarios, the result returned by dijkstra may not contain restriction. I had also implemented the logic to determine whether the result returned by dijkstra contains a turn restriction.

    • Details can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    I'll be implementing the functionality to convert a given graph into its corresponding Line graph in the coming week.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    Currently, I am not blocked on anything.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#first-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP#official-coding-period-phase-2june-27---july-24

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 3

I had been busy this week due to certain family issues so I couldn't achieve the desired goal for this week.

  1. What did you get done this week?

    I implemented the functionality to input the data from the restriction table implemented in postgresql into C/C++ data structures.

    • Details can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    I hope to implement the functionality to convert a given graph into its corresponding Line graph alongwith some unit tests in the coming week.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    Currently, I am not blocked on anything.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#first-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#official-coding-period-phase-1may-30---june-26

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 2

  1. What did you get done this week?

    I created the restrict table to store the restrictions in Postgresql. I also implemented a lot of pgtap tests that returned empty result in various scenarios.

    • Details can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    I hope to implement the functionality to convert a given graph into its corresponding Line graph alongwith some unit tests in the coming week.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    Currently, I am not blocked on anything.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#first-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#log-of-pull-requests

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#official-coding-period-phase-1may-30---june-26

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Week 1

  1. What did you get done this week? I generated the initial code for pgr_dijkstraTRSP using the template pgr_dijkstra code. I also learnt about the testing mechanism used in pgRouting. I learnt to use pgtap to create unit tests and also implemented pgtap tests for the pgr_dijkstraTRSP function.

    • Details can be found in [1]
    • Set of pull requests can be found in [2]

  2. What am I going to achieve for next week?

    I hope to complete the design of the restrictions table and implement the C code that reads and executes the queries from Postgresql.

    Details of possible sub tasks can be found in [3]

  3. Is there any blocking issue?

    I am currently blocked on designing the restrictions table since that needs to be as generic as possible.

    • The wiki page can be found in [4]
    • The repository can be found in [5]

    [1] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#first-evaluation-period

    [2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#project

    [3] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP/#official-coding-period-phase-1may-30---june-26

    [4] https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP

    [5] https://github.com/pgRouting/pgrouting/tree/gsoc/rewritetrsp

Third Evaluation Period

  • Aug 14 - Aug 21
    • Update queries to be used in Line Graph documentation(#904)
    • Update develop branch with all the changes implemented in gsoc/rewritetrsp branch(#910)
    • Update the images to be used in Line Graph documentation(#913)
    • Update all the files created with the name and e-mail(#915)
  • Aug 7 - Aug 13
    • Documentation for pgr_lineGraph(#896)
      • Fix errors in the documentation(Commit).
        • Create CMakeLists.txt for images
        • Add lineGraph queries to the queries directory
        • Remove footer
        • Remove handling costs section from the documentation.
        • Add reference to the site from where the images are taken.
      • Fix compilation errors resulted due to images(Commit).
      • Add reference to the site from where the images are taken(Commit).
    • Implement a separate function in pgr_lineGraph for generating the postgres results(Commit).
    • Lint the pgr_lineGraph and dijkstraTRSP code(Commit).
    • Add pgr_lineGraph to the proposed.rst(#899).
    • Add implementation of transformation of undirected graph to line graph(#901)
      • Implementation(Commit).
      • Remove unnecessary sql queries in pgr_lineGraph(Commit).
      • Skip dijkstraTRSP compilation and fix travis(Commit).
  • July 31 - Aug 6
    • Implementation of pgr_lineGraph
      • Modify the output table description of lineGraph(Commit).
      • Fixing a major in Line Graph implementation(Commit).
    • Added documentation of pgr_lineGraph(Commit).
  • July 24 - July 30
    • Implementation of pgr_lineGraph
      • Add cost and reverse_cost to the Line_graph_rt(Commit).
      • Fix the output returned by the pgr_lineGraph(Commit).
    • Integrating pgr_lineGraph with pgr_dijkstraTRSP(#885).
      • Create object of lineGraph in pgr_dijkstraTRSP(Commit).
      • Remove restricted edges of size 2 from the lineGraph(Commit).

Second Evaluation Period

  • July 17 - July 23
    • Implementation of pgr_lineGraph(#878)
      • Add insert_edges function(Commit).
      • Fixed error arising due to the constructor of Pgr_lineGraph class(Commit).
      • Create Line_vertex class(Commit).
      • Add the implementation(Commit).
      • Remove line_vertex.cpp and fix the creation of self-edges(Commit).
      • Add logic to display the lineGraph(Commit).
      • Add implementation of virtual nodes and virtual edges in the lineGraph(Commit).
  • July 10 - July 16
    • Create pgr_lineGraph(#876)
      • Comment out the tests of dijkstraTRSP resulting in failing of travis(Commit).
      • Generate the code for pgr_lineGraph using the template code of pgr_dijkstra(Commit).
      • Fix compilation problems and remove unnecessary comments(Commit).
      • Add CMakeLists.txt file in the doc of lineGraph(Commit).
      • Edit pg_prove_tests.sh to run the pgtap tests of pgr_lineGraph(Commit).
      • Remove lineGraph-compare-dijkstra.sql from pgtap tests directory(Commit).
      • Fix tests resulting in error in lineGraph-innerQuery.sql(Commit).
      • Added accidently deleted file doc-pgr_lineGraph.queries(Commit).
      • Create Line_graph_element_t structure to store output of Line graph(Commit).
      • Added Pgr_lineGraph class by extending Pgr_base_graph class(Commit).
      • Added logic for graph transformation(Commit).
  • July 3 - July 9
    • Create pgtap tests(#868)
      • Add pgtap test from source 2 to target 8 in the sample graph when turn restriction is from edge 4 - > edge 7(Commit).
      • Add comments to the sql query as well as indent it.(Commit).
      • Add id = 1 to all the current pgtap queries so that the tests only consider restriction with id 1 from edge 4 - > edge 7(Commit).
      • Implement more non-empty pgtap tests and update the sample graph network.(Commit).
      • Add test to compare the result returned by dijkstra with that of dijkstratrsp from all sources to all targets(Commit).
      • Modify the sql query so as to include the whole graph(Commit).
      • Add todo_start() and todo_end() to all the newly created pgtap tests(Commit).
    • Update the gsoc/rewritetrsp branch with the latest code changes introduced in the develop branch(#869).
    • Modify the sample graph after applying the following sql query:- UPDATE edge_table SET cost = cost + 0.001 * id * id, reverse_cost = reverse_cost + 0.001 * id * id(Issue).
    • Write about Line Graph Approach issues(Issue).
  • June 27 - July 2
    • Create a Restriction class in C++ that will act as a container to store the contents of the Restrict_t class.
    • Create has_restrictions and has_a_restriction functions.
    • Debug the logic implemented to verify the dijkstra solution whether that contains the restricted edges.
    • Create pgtap tests to verify the above logic.

First Evaluation Period

  • June 20 - June 26

    • Create pgr_dijkstraTRSP.hpp file(#860)
      • Create the file pgr_dijkstraTRSP.hpp using template pgr_ksp.hpp.
      • Modify function and constructor names to suit dijkstraTRSP.
      • Comment out unnecessary code.
      • Remove K parameter and fix the return type of the function.
      • Remove the irrelavant and commented out code.
      • Pass strict parameter to the function.
      • Convert restriction from pointer array to a C++ vector.
      • Pass restriction parameter to the function.
      • Create private variables such as m_restriction and m_strict.
      • Fix the function such that it returns the dijkstra result from the source and the destination.
    • Remove unnecessary comments and code from dijkstraTRSP.c.
    • Pass restrictions parameter from dijkstraTRSP.c to dijkstraTRSP_driver.h using do_pgr_dijkstraTRSP.(#859)

  • June 13 - June 19

    • Add pgr_dijkstraTRSP to proposed function list.
    • Created Restrict_t container to input data from restriction table.
    • Created pgr_get_restriction_data function.
    • Hardcode the sample data into the restrictions array.
    • Create ANY_INTEGER_ARRAY column for restricted_edges column.

  • June 6 - June 12

    • Move Documentation files(#811)
      • Create new branch test/merge from gsoc/rewriteTRSP
      • Fetch upstream changes and merge to the new branch
      • Create the directory dijkstraTRSP inside doc directory
      • Move documentation to new directory -> mv src/<directory>/doc/* doc/<directory>
      • Move query files to the doc/queries directory -> mv doc/<directory>/*.queries doc/queries
      • Edit doc/queries/CMakeLists.txt to include doc-pgr_dijkstraTRSP.queries
      • Create CMakeLists.txt in doc/ -> cp doc/allpairs/CMakeLists.txt doc/<directory>
      • Edit the new CMakeLists.txt file to include dijkstraTRSP documentation file pgr_dijkstraTRSP.rst
      • Uncomment the dijkstraTRSP line new configuration.conf file
      • Commit and Push
      • Merge in gsoc/dijkstraTRSP
      • Send PR to the upstream/gsoc/rewriteTRSP
    • Implement pgtap tests from empty set(#8)
      • Add tests from an non-existing starting vertex to a non-existing destination in directed graph with and without restriction.
      • Add tests from an non-existing starting vertex to a non-existing destination in undirected graph with and without restriction.
      • Add tests from an existing starting vertex to the same destination in directed graph with and without restriction.
      • Add tests from an existing starting vertex to the same destination in undirected graph with and without restriction.
      • Add tests from an existing starting vertex in one component to an existing destination in another component in directed graph with and without restriction.
      • Add tests from an existing starting vertex in one component to an existing destination in another component in undirected graph with and without restriction.
    • Add strict column in the restrictions table
    • Create an issue in the pgRouting repository for the discussion on the strict parameter(#813)
    • Design contents for the restrictions table(#9).
      • Serial Id
      • Array of Restricted edges in order
      • Turn Cost
    • Change restriction to restrict in all the queries.
    • Create style_dijkstraTRSP fixing all the errors that arise due to style_dijkstra in Travis.
    • Fix dijkstraTRSP-compare-dijkstra.sql file for comparison of results with Dijkstra in case of no restriction.

  • May 30 - June 5

    • Create database sample data.
    • Generated initial code for pgr_dijkstraTRSP using the template pgr_dijkstra code.
    • Fix documentation tests.
    • Create .pgpass file.
    • Fix tests resulting in failing of travis and appveyor.
    • Learn to integrate tests using pgtap in pgRouting.
    • Implement automated tests using pgplsql.
    • Look into the turn restriction data of osm.

Bonding Period

  • May 25 - May 29

    • Read tutorial on removing outdated branch in git.
    • Fix appveyor for branch gsoc/rewritetrsp(Issue #7)
    • Complete exercise to learn how to read/fix code.
    • Update branch gsoc/rewritetrsp with develop.
    • Make gsoc/rewritetrsp as the default branch.
    • Understand and play with the template generation code(tools/template/create.sh).

  • May 18 - May 24

    • The file include/pgr_types.h has pgr_path_t structure that needs to be in a separate file.
    • The structure pgr_path_t is not being used anywhere so remove that structure.
    • Create pgr_vidhanDijkstra for practice using mycreate.sh.
    • Send in a PR to Vicky's fork.
    • Pull changes and Fix conflicts.
    • Fix Appveyor build that is failing.

  • May 11 - May 17

    • Added the project wiki and the github project link on the OSGeo Wiki Page.
    • Compiled pgRouting. Here is the full compilation log.
    • Perform experiment to analyze the difference in time for compilation of the pgRouting Library after adding a blank line in pgr_contracted_blob in pgr_types.h file.

    Here is the result that i got:-

     206.20s user 13.22s system 70% cpu 5:11.07 total
 210.77s user 15.15s system 70% cpu 5:18.35 total # After addition of blank line.
    • Learn the basics of linting. Lint the following files based on the C/C++ standards by Google:-
      • src/trsp/src/trsp.c
      • src/trsp/src/GraphDefinition.cpp
      • src/trsp/src/trsp_core.cpp
      • src/trsp/src/trsp.h
      • src/trsp/src/utils.h

  • May 4 - May 10

    • Accept invitation to be part of the pgRouting organization on the github.
    • Set Up a wiki page with the following details:-
      • A brief introduction about your project.
      • Plan for the week.
      • A detailed list of tasks you need to accomplish during the week
      • Links to your weekly reports
    • Create Milestones.
    • Add current issues to the Bonding Period Milestone.
    • Introduced myself and my GSoc project to the OSGeo Community.

Pre Bonding Period

Timeline

Community Bonding Period(May 5 - May 29)

  • Create a wiki page for TODO tasks and weekly reports.
  • Look into the currently implemented code of TRSP.
  • Discuss the design and functionality of pgr_trsp with the mentors.
  • Get familiar with the PgRouting architecture.
  • Go through pgTap for creating unit tests for PostgreSQL.
  • Watch C++ videos for better understanding of C++ and STL.
  • Investigate the handling of costs while conversion of original graph to Line graph.
  • Discuss the design of restriction table with the mentors.

Official Coding Period(May 30 - August 21)

Official Coding Period Phase 1(May 30 - June 26)

  • Week 1(May 30 - June 5)

    • Implement the basic code required for connecting the pgr_dijkstraTRSP function to the postgreSQL.

  • Week 2(June 6 - June 12)

    • Implement the C code that reads and executes the queries from PostgreSQL.

  • Week 3(June 13 - June 19)

    • Design and implement the function that transforms a given graph into its corresponding Line graph.

  • Week 4(June 20 - June 26)

    • Create unit tests to test the transformed Line graph.
    • Implement a testing function that tests the graph transformation.
    • Fix bugs found in the implementation of the above function.
    • Work on the submissions required as part of the first evaluation.

First evaluation period(June 26 - June 30)

  • Mentors evaluate me and I evaluate the mentors of Coding Period Phase 1.
  • Deliver a working implementation of the transformation function into the Line Graph.

Official Coding Period Phase 2(June 27 - July 24)

  • Week 5-6(June 27 - July 10)

    • Work on the feedback as provided after the first evaluation.
    • Implement the dijkstra algorithm on the transformed Line Graph where some possibilities can be:-
      • Using the simplified version of pgRouting dijkstra directly.
      • Using boost library’s dijkstra directly.
      • Add additional functionality to the pgRouting simplified dijkstra.

  • Week 7-8(July 11 - July 24)

    • Implement unit tests to verify the result of the dijkstra algorithm on the transformed Line Graph.
    • Fix bugs found in the implementation of the dijkstra algorithm on the transformed Line graph.
    • Work on the submissions required as part of the second evaluation.

Second evaluation period(July 24 - July 28)

  • Mentors evaluate me and I evaluate the mentors of coding period phase 2.
  • Deliver a working implementation of the dijkstra on the Line graph.

Official Coding Period Phase 3(July 25 - August 21)

  • Week 9(July 25 - July 31)

    • Work on the feedback as provided after the second evaluation.
    • Implement the functionality that extracts the relevant result after applying dijkstra on the transformed Line graph.

  • Week 10(August 1 - August 7)

    • Create tests and rigorously test the above functions and fix bugs if found any.

  • Week 11(August 8 - August 14)

    • Create developer and user documentations.
    • Create documentation tests.

  • Week 12(August 15 - August 21)

    • Work on the final submission report.
    • Prepare for the final delivery.

Final evaluation period(August 21 - August 29)

  • Wrap up the project and submit final evaluation of my mentors of Coding Period Phase 3.
  • Deliver a working implementation of pgr_dijkstraTRSP.

And if time permits, implement:-

  • pgr_dijkstraTRSP(one to many)
  • pgr_dijkstraTRSP(many to one)
  • pgr_dijkstraTRSP(many to many)

Important Links

  1. Issues related to TRSP in PgRouting
  2. https://www.ordnancesurvey.co.uk/business-and-government/help-and-support/products/os-mastermap-highways-network.html
  3. https://www.ordnancesurvey.co.uk/docs/technical-specifications/os-mastermap-highways-network-routing-and-asset-management-technical-specification.pdf
  4. Git Tutorials
  5. C++ Tutorials
  6. C++ coding style standard
  7. Git cleanup outdated branch tutorial

References

  1. "Shortest path problem - Wikipedia." https://en.wikipedia.org/wiki/Shortest_path_problem.
  2. "Dijkstra's algorithm - Wikipedia." https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.
  3. "Line graph - Wikipedia." https://en.wikipedia.org/wiki/Line_graph
  4. "Turns in the network dataset—Help | ArcGIS Desktop." http://desktop.arcgis.com/en/arcmap/latest/extensions/network-analyst/turns-in-the-network-dataset.htm.
  5. "Is there a way to add turn restrictions in A* and ... - GIS StackExchange.", http://gis.stackexchange.com/questions/16411/is-there-a-way-to-add-turn-restrictions-in-a-and-dijkstra.
  6. "pgr_trsp - Turn Restriction Shortest Path (TRSP) — pgRouting Manual ....", http://docs.pgrouting.org/latest/en/pgr_trsp.html.
  7. "pgr_dijkstra — pgRouting Manual (2.4).", http://docs.pgrouting.org/latest/en/pgr_dijkstra.html.
  8. "Modeling Costs of Turns in Route Planning." http://geo.fsv.cvut.cz/gdata/2013/pin2/d/dokumentace/line_graph_teorie.pdf.
  9. "Notes on pgr_trsp (2.3.2 release) · pgRouting/pgrouting Wiki · GitHub.", https://github.com/pgRouting/pgrouting/wiki/Notes-on-pgr_trsp--(2.3.2-release).
  10. "Efficient Routing in Road Networks with Turn Costs - KIT." https://algo2.iti.kit.edu/1862.php.
  11. "Route Planning in Road Networks with Turn Costs." http://lekv.de/pub/lv-turns-2008.pdf.
  12. "Routino : Algorithm." https://www.routino.org/documentation/algorithm.html.
  13. "Combining turning point detection and Dijkstra's ... - SAGE Journals.", http://journals.sagepub.com/doi/full/10.1177/1687814016683353.
  14. "Graph Indexing of Road Networks for Shortest ... - VLDB Endowment." http://www.vldb.org/pvldb/vol4/p69-rice.pdf.
  15. "MODELLING TURNING RESTRICTIONS IN TRAFFIC ... - isprs." http://www.isprs.org/proceedings/XXXIV/part4/pdfpapers/410.pdf.
  16. "Smart Directions Powered by OSRM's Enhanced Graph Model | Mapbox.", https://www.mapbox.com/blog/smart-directions-with-osrm-graph-model/.
  17. "Route Planning in Road Networks with Turn Costs" http://algo2.iti.kit.edu/documents/routeplanning/volker_sa.pdf

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally