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

[Vicky Vergara]

Hello Akhill

I hope you already read:
https://github.com/pgRouting/pgrouting/wiki/GSoC-Ideas%3A-2019

We are open for new ideas also.

Please register to
https://gitter.im/pgRouting/pgrouting

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 <gvs.akhil1997 at gmail.com> 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
> pgrouting-dev at lists.osgeo.org
> 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 at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20190319/2c240a49/attachment.html>