Dear pgRouting Developers,
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.
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.
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.
Project Idea:
I consider myself unlucky to have found this amazing community so late.
I have spent the past few days reading the codebase, the project ideas as well as previous GSoC projects.
The list has many ideas that I would love to work on!
But, I observed that a few algorithms have not yet been implemented either in the supported boost version or pgRouting.
Examples:
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.
It has an average running time of O(E) and the same worst-case complexity as Bellman-Ford of O(V.E)
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.
c) Planar Graphs Algorithms - For planar graphs, a few improvements of standard algorithms can be made.
1)SSSP with non-negative weights - O(n), O(n loglogn) possible over Djikstra’s O(nlogn).
2)Max-flow - O(n) algorithm if source and sink are in same face of the graph.
3)SSSP with negative edges - O( n^(4/3) log (nL) ) where L is absolute value of most negative path.
The theory can be found here for the above improvements - http://theory.stanford.edu/~virgi/cs267/papers/planar-sssp.pdf
Also, there exists an O(V+E) algorithm in the boost library which can be used to verify planarity of the graph.
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.
I look forward to your reply.
Thank you,
Gvs Akhil
