[pgrouting-dev] [GSOC Application] Flow Algorithms

[Andrea Nardelli]

Thanks for your feedback!

I saw that the Dijkstra implementation in pgRouting utilizes Boost, so I
thought that it would be better (and probably much better code than what I
would write, it's pointless to reinvent the wheel) to just simply utilize
the algorithms provided by Boost for the maximum flow problem.

I knew about pgRouting but never got around to using it until now. My
interest in the project sparked after following an Algorithms & Data
Structures course in the last semester which completely enlightened me on
just how many problems can be modeled and solved on graphs. I ran some
algorithms on the sample data, visualized it and decided I wanted to
contribute: so far I am still familiarizing with the code base and got one
pull request in.

Andrea



2016-03-16 0:50 GMT+01:00 Daniel Kastl <daniel at georepublic.de>:

> Hi Andrea,
>
> Welcome to this list and thank you for your interest to participate in
> GSoC and pgRouting!
> You probably read our Wiki page on Github:
> https://github.com/pgRouting/pgrouting/wiki/GSoC-Ideas
> It should answer the basic questions, but if something isn't clear, please
> ask.
>
> I think, that it's a good idea to start with using Boost Graph Library
> first.
> It's also better not to make too ambitious plans, especially if you are
> new to pgRouting.
> Have you used pgRouting already?
>
> Best regards,
> Daniel
>
>
>
> On 16/03/16 00:48, Andrea Nardelli wrote:
>
> Hello,
>
> I would like to contribute on pgrouting during the GSoC program.
> My project idea is implementing algorithms to solve the maximum flow
> problem, here is what I got so far:
> 1) Create new pgrouting functions that utilize the implementations already
> present in the Boost Graph library
> <http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/table_of_contents.html>
> (22.10).
> 2) Research/write other possible implementations, such as the
> Ford-Fulkerson
> <https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm>
> algorithm, which may yield better results on some particular graphs.
> 3) Extend the problem to include multiple sources and/or multiple sinks
> and implement solutions.
>
> My application will come soon, but I wanted to get in touch with you to
> discuss a bit and see if there are any other possible ideas.
> Thank you for your time!
>
> Andrea Nardelli
>
>
> _______________________________________________
> pgrouting-dev mailing listpgrouting-dev at lists.osgeo.orghttp://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
> --
> Georepublic UG & Georepublic Japan
> eMail: daniel.kastl at georepublic.de
> Web: https://georepublic.info
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20160316/72f71345/attachment.html>