<div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Hello Akhill</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">I hope you already read:</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-Ideas%3A-2019">https://github.com/pgRouting/pgrouting/wiki/GSoC-Ideas%3A-2019</a></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">We are open for new ideas also.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Please register to<br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><a href="https://gitter.im/pgRouting/pgrouting">https://gitter.im/pgRouting/pgrouting</a><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">And start working on the proposal.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Dont forget that the proposal has to meet google proposal requirements and OSGeo proposal requirements.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Regards</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">pgRouting team</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"></div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Mar 19, 2019 at 6:27 AM GVS Akhil <<a href="mailto:gvs.akhil1997@gmail.com">gvs.akhil1997@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div>Dear pgRouting Developers, </div><div><br></div><div>I introduce myself as GVS Akhil, a junior from IIT Indore who is currently pursuing a B.Tech degree majoring in Computer Science and Engineering. </div><div><br></div><div>I come from a competitive programming background and have a strong foundation of algorithms and data structures. I have personally written and used many graph algorithms including almost all the algorithms currently implemented in pgRouting. In turn, I have developed a great interest in graph algorithms.</div><div><br></div><div>I have work experience in both C and C++. I had interned at Samsung during the last summer where I worked and contributed to a large C++ codebase. Before this, I had been a research assistant at CEERI, Pilani where I helped a team of researches port an ML algorithm written in MATLAB to C. </div><div><br></div><div>Project Idea: </div><div>I consider myself unlucky to have found this amazing community so late. </div><div>I have spent the past few days reading the codebase, the project ideas as well as previous GSoC projects. </div><div><br></div><div>The list has many ideas that I would love to work on! </div><div>But, I observed that a few algorithms have not yet been implemented either in the supported boost version or pgRouting.</div><div><br></div><div>Examples:</div><div>a) Shortest Path Faster Algorithm (SPFA) - It is an improvement of Bellman-Ford algorithms which can compute single-source shortest paths in weighted(including negative weights) directed graphs. </div><div>It has an average running time of O(E) and the same worst-case complexity as Bellman-Ford of O(V.E)</div><div><br></div><div>b) 0-1 BFS: This modification of BFS allows the algorithm to calculate Single Source Shortest Path in a graph where weights of all edges are 0 or 1 in linear time complexity O(V+E) compared to O(E + V log V) of Dijkstra.</div><div><br></div><div>c) Planar Graphs Algorithms - For planar graphs, a few improvements of standard algorithms can be made. </div><div><span style="white-space:pre-wrap"> </span>1)SSSP with non-negative weights - O(n), O(n loglogn) possible over Djikstra's O(nlogn). </div><div><span style="white-space:pre-wrap"> </span>2)Max-flow - O(n) algorithm if source and sink are in same face of the graph.</div><div><span style="white-space:pre-wrap"> </span>3)SSSP with negative edges - O( n^(4/3) log (nL) ) where L is absolute value of most negative path. </div><div><br></div><div>The theory can be found here for the above improvements - <a href="http://theory.stanford.edu/~virgi/cs267/papers/planar-sssp.pdf" target="_blank">http://theory.stanford.edu/~virgi/cs267/papers/planar-sssp.pdf</a> </div><div>Also, there exists an O(V+E) algorithm in the boost library which can be used to verify planarity of the graph.</div><div><br></div><div>I would like to hear your opinion on whether it is logical to implement some of the algorithms mentioned and if it would be a good GSoC project.</div><div><br></div><div>I look forward to your reply.</div><div><br></div><div>Thank you,</div><div>Gvs Akhil</div><div><br></div><div> </div><div><br></div><div> </div></div><div></div><span><img alt="" src="https://gml.email/v3.2/t/image/MTU1Mjk5ODE1NzdkYTc1Mjk1MmZjNDA3NGMxMDFlNGEyNDllNDM1ODhjJmd2cy5ha2hpbDE5OTdAZ21haWwuY29tJnBncm91dGluZy1kZXZAbGlzdHMub3NnZW8ub3Jn.gif" id="gmail-m_-8840873910015697057_gml" width="1" height="1"></span></div>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/pgrouting-dev" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a></blockquote></div><br clear="all"><br>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><pre>Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany
Vicky Vergara
Operations Research
eMail: vicky@<a href="http://georepublic.de" target="_blank">georepublic.de</a>
Web: <a href="https://georepublic.info" target="_blank">https://georepublic.info</a>
Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9
Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
<span></span></pre></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>