[pgrouting-dev] [GSoC] Introduction and Project Idea

[GVS Akhil]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20190319/4355eaf9/attachment.html>