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.

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