<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">  </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">      </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"> </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">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="" width="1" height="1" src="https://gml.email/v3.2/t/image/MTU1Mjk5ODE1NzdkYTc1Mjk1MmZjNDA3NGMxMDFlNGEyNDllNDM1ODhjJmd2cy5ha2hpbDE5OTdAZ21haWwuY29tJnBncm91dGluZy1kZXZAbGlzdHMub3NnZW8ub3Jn.gif" id="_gml"></span></div>