[pgrouting-dev] [GSOC Application] Flow Algorithms

pgRouting pgrouting-dev
1

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 (22.10).

  2. Research/write other possible implementations, such as the Ford-Fulkerson 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

2

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 (22.10).

  2. Research/write other possible implementations, such as the Ford-Fulkerson 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 list
[pgrouting-dev@lists.osgeo.org](mailto:pgrouting-dev@lists.osgeo.org)
[http://lists.osgeo.org/mailman/listinfo/pgrouting-dev](http://lists.osgeo.org/mailman/listinfo/pgrouting-dev)

-- 
Georepublic UG & Georepublic Japan
eMail: [daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: [https://georepublic.info](https://georepublic.info)
3

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@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&gt;
(22.10).
2) Research/write other possible implementations, such as the
Ford-Fulkerson
<https://en.wikipedia.org/wiki/Ford–Fulkerson_algorithm&gt;
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@lists.osgeo.orghttp://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: https://georepublic.info

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev