<div dir="ltr"><div><div class="gmail_signature"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div style="font-size:12.8px"><span id="gmail-docs-internal-guid-63d2de7e-0d48-a5d1-8bc4-19066e04b841"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Hi everyone,</span></span><br></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:monospace,monospace;font-size:small"><br></span></div><div style="font-size:12.8px"><span style="color:rgb(0,0,0);font-family:monospace,monospace;font-size:small"><br></span></div><div><span id="gmail-docs-internal-guid-63d2de7e-0d48-1c7b-7e29-edc151d69a5b"><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">1) TITLE</span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">    Rewrite of Turn Restricted Shortest Path Algorithm in PgRouting</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span></p><br><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">2) SOFTWARE COMMUNITY</span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">    PgRouting, under OSGeo.</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">3) ABSTRACT</span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">    </span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap">In graph theory, the </span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);font-weight:700;vertical-align:baseline;white-space:pre-wrap">shortest path problem</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap"> 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.</span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap">    </span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:rgb(254,254,254);vertical-align:baseline;white-space:pre-wrap">A turn models a movement from one edge element to another. Often in the real world scenario, turn restrictions such as </span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:rgb(254,254,254);font-weight:700;vertical-align:baseline;white-space:pre-wrap">no-left-turn</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:rgb(254,254,254);vertical-align:baseline;white-space:pre-wrap">, </span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:rgb(254,254,254);font-weight:700;vertical-align:baseline;white-space:pre-wrap">no-right-turn </span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:rgb(254,254,254);vertical-align:baseline;white-space:pre-wrap">etc. are imposed on the road network.</span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:rgb(254,254,254);vertical-align:baseline;white-space:pre-wrap">    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.</span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">4) STATE BEFORE</span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">    TRSP is implemented in PgRouting but the code has issues which are not fixed as yet.   </span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">    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:-</span></p><ul style="font-size:12.8px;margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">pgr_dijkstraTRSP(one to one) (aka pgr_trsp)</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">pgr_withPointsTRSP(one to one) (aka pgr_trsp)</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">pgr_dijkstraViaTRSP() (aka pgr_trspViaVertices)</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:7pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">pgr_withPointsViaTRSP() (aka pgr_trspViaEdges)</span></p></li></ul><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:7pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap">    </span><a href="https://github.com/pgRouting/pgrouting/wiki/Notes-on-pgr_trsp--(2.3.2-release)" style="text-decoration-line:none"><span style="font-size:11pt;font-family:Arial;background-color:transparent;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">Here</span></a><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> is the link to a wiki page that describes the issues associated with the current implementation of the pgr_trsp code in PgRouting.</span></p><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">5) THE ADDITION</span></p><br><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">Pgr_dijkstraTRSP:</span></p><ul style="font-size:12.8px;margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Implemented code that works when the resultant path from source to destination does not pass through restricted edges.</span></p></li></ul><ul style="font-size:12.8px;margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Some tests  for the </span><span style="font-size:11pt;background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">pgr_dijkstraTRSP</span><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> for the working case have been done.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Some documentation has been done.</span></p></li></ul><br><br><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">Pgr_lineGraph:</span></p><ul style="font-size:12.8px;margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Implemented code for </span><span style="font-size:11pt;background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">pgr_lineGraph </span><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">for unweighted graphs </span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">This functionality is to be used by the </span><span style="font-size:11pt;background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">pgr_dijkstraTRSP.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Finished the user’s documentation</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Finished the basic tests.</span></p></li></ul><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"></span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">6) PENDING WORK</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"><br class="gmail-kix-line-break"></span></p><ul style="font-size:12.8px;margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;font-weight:400;vertical-align:baseline;white-space:pre-wrap">Pgr_lineGraphWeighted needs to be implemented.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;font-weight:400;vertical-align:baseline;white-space:pre-wrap">Dijkstra algorithm needs to be applied on the weighted line graph.</span></p></li><li dir="ltr" style="list-style-type:disc;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;font-weight:400;vertical-align:baseline;white-space:pre-wrap">The above functions need to be incorporated to pgr_dijstraTRSP to process the paths when they pass through a restriction.</span></p></li></ul><br><br><p dir="ltr" style="font-size:12.8px;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">7) LINKS</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><br class="gmail-kix-line-break"><br class="gmail-kix-line-break"></span></p><ol style="font-size:12.8px;margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">Pull request with all the commits:</span><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span><a href="https://github.com/pgRouting/pgrouting/pull/910" style="text-decoration-line:none"><span style="font-size:11pt;background-color:transparent;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">https://github.com/pgRouting/pgrouting/pull/910</span></a></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">Wiki Page:</span><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP" style="text-decoration-line:none"><span style="font-size:11pt;background-color:transparent;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">https://github.com/pgRouting/pgrouting/wiki/GSoC-2017-Rewrite-TRSP</span></a></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">Diff changes: </span><a href="https://github.com/vidhan13j07/GSOC17-RewriteTRSP/blob/master/contributions.diff" style="text-decoration-line:none"><span style="font-size:11pt;background-color:transparent;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">https://github.com/vidhan13j07/GSOC17-RewriteTRSP/blob/master/contributions.diff</span></a></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">Documentation:</span><span style="font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> </span><a href="http://docs.pgrouting.org/2.5/en/pgr_lineGraph.html" style="text-decoration-line:none"><span style="font-size:11pt;background-color:transparent;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">http://docs.pgrouting.org/2.5/en/pgr_lineGraph.html</span></a></p></li><li dir="ltr" style="list-style-type:decimal;font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;vertical-align:baseline"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;background-color:transparent;font-weight:700;vertical-align:baseline;white-space:pre-wrap">Slides: </span><span style="text-decoration-line:underline;font-size:11pt;background-color:transparent;vertical-align:baseline;white-space:pre-wrap"><a href="https://docs.google.com/presentation/d/1TTSvKvF-a6P1WD_Aezc541vUHsoCUAQXMOfnBX3orcU/edit?usp=sharing" style="text-decoration-line:none">https://docs.google.com/presentation/d/1TTSvKvF-a6P1WD_Aezc541vUHsoCUAQXMOfnBX3orcU/edit?usp=sharing</a></span></p></li></ol><div><font color="#000000" face="Arial"><span style="font-size:14.6667px"><br></span></font></div><div><font color="#000000" face="Arial"><span style="font-size:14.6667px">Best Regards,</span></font></div><div><font color="#000000" face="Arial"><span style="font-size:14.6667px">Vidhan Jain</span></font></div></span></div></div></div></div></div></div>
</div>