<div dir="ltr"><img width="0" height="0" class="mailtrack-img" alt="" style="display:flex" src="https://mailtrack.io/trace/mail/f1a823dda5a93d8916ef5e75a3580a563fb2150d.png?u=439451"><div><font face="arial, helvetica, sans-serif"><br></font></div><div></div> <font face="arial, helvetica, sans-serif"><div>Hello all,<br></div></font><div><font face="arial, helvetica, sans-serif"><br></font><div><font face="arial, helvetica, sans-serif">I am Sourabh Garg, and This is my final report for my GSoC project.</font></div><div><br></div><div><font face="arial, helvetica, sans-serif"><b>Title: </b>Implement Parallel Dijkstra’s and Bellman-Ford algorithm by the Boost Graph Library.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><b>Organization:<span> </span></b>PgRouting under OSGeo</font></div><div><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div><font face="arial, helvetica, sans-serif"><b>Abstract: </b><b><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-weight:400;display:inline">Graph Algorithms like Dijkstra’s single source shortest path algorithm is widely applied in many routing applications, but it is constrained by non-negative edge's weight and is more efficient to use DAG shortest path algorithm(topological sort) in case of Directed Acyclic Graph.</p></b></font></div><div><font face="arial, helvetica, sans-serif"><p style="font-weight:400;box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);display:inline">Finding the shortest path from a source vertex to target using the<span> </span><i>bellman-ford algorithm</i><span> </span>for Graphs with negative weighted edges and<span> </span><i>dag_shortest_path</i> <i>algorithm<span> </span></i>for<i><span> </span></i>the Directed<i><span> </span></i>acyclic graph are major</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);display:inline"> <span style="text-decoration-style:initial;text-decoration-color:initial"><span style="color:rgb(34,34,34);background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"></span></span></p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);display:inline"><span style="color:rgb(34,34,34);background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">deliverables.</span></p> Often such algorithms are applied over Large-scale graphs, where computation problem may arise. It may be beneficial to exploit the high-performance parallel computing system, by implementing distributed graph algorithms in pgRouting. I have developed the testing base for parallel Boost Graph algorithm.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><b><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);display:inline">Implemented functions</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-weight:400;display:inline">:</p></b></font></div><div><ul><li style="margin-left:15px"><font color="#24292e" face="arial, helvetica, sans-serif">pgr_bellmanFord()  - Returns the shortest path for the graph with negative weighted edges.</font></li><li style="margin-left:15px"><font color="#24292e" face="arial, helvetica, sans-serif">pgr_dagShortestPath() - Returns the shortest path for the Directed Acyclic Graph.</font></li></ul></div><div><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div><font face="arial, helvetica, sans-serif"><b>State of the art before the project:<span> </span></b>pgRouting didn't have above functionalities before my GSoC. </font></div><div><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);font-weight:400;display:inline"><font face="arial, helvetica, sans-serif"><br></font></pre></b></div><div><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><font face="arial, helvetica, sans-serif">Addition that my project brought to pgRouting: </font></pre></b><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><pre style="white-space:pre-wrap;font-weight:400;display:inline"><font face="arial, helvetica, sans-serif">The deliverables are code, full documentation, documentation tests, pgTap of above functions.</font></pre></pre></b><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><font face="arial, helvetica, sans-serif"><br></font><font face="arial, helvetica, sans-serif"><span style="font-weight:400"><br></span></font></pre></b></div><div><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><font face="arial, helvetica, sans-serif"><b>Pending Work:</b> I have done experimentation with boost parallel graph library to generate distributed graph and apply dijkstra's algorithm over it. It was quite challenging to integrate the parallel version of algorithms with pgRouting architecture.</font></pre></div><div><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><font face="arial, helvetica, sans-serif"><span style="font-weight:400">
</span>Future Directions:<span style="font-weight:400"> </span></font></pre></b></div><div><ul style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><li style="margin-left:15px"><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><font face="arial, helvetica, sans-serif"><span style="font-weight:400">Implement full functionality of parallel Dijkstra in pgrouting architecture.</span></font></pre></b><br></li><li style="margin-left:15px"><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><font face="arial, helvetica, sans-serif"><span style="font-weight:400">Implement the feature to include the negative weighted edges in pgRouting graphs.</span></font></pre></b></li></ul>

<div><div><font color="#000000" face="arial, helvetica, sans-serif"><span style="white-space:pre-wrap"><b>Links:</b></span></font></div></div><div><ul style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><li style="margin-left:15px"><b>Wiki: </b><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-Parallel-Dijkstra-and-Bellman-Ford" target="_blank" style="color:rgb(17,85,204)">https://github.com/<wbr>pgRouting/pgrouting/wiki/GSoC-<wbr>2018-Parallel-Dijkstra-and-<wbr>Bellman-Ford</a></li><li style="margin-left:15px"><b>Last Pull Request:</b> <a href="https://github.com/pgRouting/pgrouting/pull/1082" target="_blank" style="color:rgb(17,85,204)">https://github.com/<wbr>pgRouting/pgrouting/pull/1082</a><br></li><li style="margin-left:15px"><b>Slide: </b><a href="https://docs.google.com/presentation/d/1ESngDemJKLmvWCO6uisd1bmhXGYdjc5ERa-ZEWdqOx0/edit?usp=sharing" target="_blank" style="color:rgb(17,85,204)">https://docs.google.<wbr>com/presentation/d/<wbr>1ESngDemJKLmvWCO6uisd1bmhXGYdj<wbr>c5ERa-ZEWdqOx0/edit?usp=<wbr>sharing</a></li><li style="margin-left:15px"><b>Tag:</b> <a href="https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018-codeSG-lw" target="_blank" style="color:rgb(17,85,204)">https://github.com/<wbr>pgRouting/pgrouting/releases/<wbr>tag/gsoc2018-codeSG-lw</a></li></ul><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">Best Regards,</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><i>Sourabh Garg</i></div></div></div></div></div>