Skip to content

GSoC 2017 Rewrite TRSP

Jump to bottom Edit New page
Vidhan Jain edited this page Aug 1, 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
#885 Integrating pgr_lineGraph with pgr_dijkstraTRSP July 28, 2017 Open
#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

Week 11

Week 10

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

  • 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)

Meetings

  1. Meeting regarding the administration of code and wiki(May 4)
  2. Meeting to perform a guided experiment for understanding good design principles(May 12)
  3. Meeting regarding the organization of files in pgRouting(May 13)
  4. Tutorial for creating a new function(May 19)
  5. Meeting regarding keeping branch up to date(May 26)
  6. Meeting regarding the documentation structure(June 2)

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