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

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[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

  

 

_______________________________________________
pgrouting-dev mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev
Reply | Threaded
Open this post in threaded view
|

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

Vicky Vergara-2
Hello Akhill

I hope you already read:

We are open for new ideas also.

Please register to

And start working on the proposal.
Dont forget that the proposal has to meet google proposal requirements and OSGeo proposal requirements.

Regards
pgRouting team


On Tue, Mar 19, 2019 at 6:27 AM GVS Akhil <[hidden email]> wrote:
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

  

 
_______________________________________________
pgrouting-dev mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev


--
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44, 
81739 München, Germany

Vicky Vergara
Operations Research

eMail: vicky@georepublic.de
Web: https://georepublic.info

Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl


_______________________________________________
pgrouting-dev mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev