[Haskell-cafe] Right tree structure for complicated problem
Pierre Penninckx
ibizapeanut at gmail.com
Sun Jan 22 11:10:28 CET 2012
Not exactly: The aim is not to know which path must the water take to the
least time.
The fact is, the water can only take one path, due to the circuit
configuration, from the source to the exit, so there is no choice for the
water.
It's not a graph with multiple paths, it's a tree with leafs as water
sources and branches as tubes.
So the aim is to know what time, with this circuit configuration, will the
water take to exit.
Plus, the sources of water are finite.
But, I can maybe inspirate myself from the maximum flow problem.
I'll take a look, but it's not really the same problem (although the
algorithm could be the same).
Thanks !
Ibiz
2012/1/22 Twan van Laarhoven <twanvl at gmail.com>
> On 2012-01-22 00:39, Pierre Penninckx wrote:
>
>> So here is what I want to achieve:
>> I'd like a program that calculates the time needed for water to flow out
>> of a
>> circuit made out of tube.
>> The rules are :
>> - There are multiple sources of water and only one exit.
>> - The water can only take one path from a source to the exit.
>> - Of course, a source of water contains a certain amount of water at the
>> beginning.
>>
>
> Is this a maximum flow problem? If so, I would suggest using a standard
> algorithm to solve it. See wikipedia [1] for an explanation. The fgl
> library has a haskell implementation of such an algorithm [2].
>
>
> Twan
>
>
> [1] http://en.wikipedia.org/wiki/**Maximum_flow_problem<http://en.wikipedia.org/wiki/Maximum_flow_problem>
> [2] http://hackage.haskell.org/**packages/archive/fgl/5.4.2.4/**
> doc/html/Data-Graph-Inductive-**Query-MaxFlow.html<http://hackage.haskell.org/packages/archive/fgl/5.4.2.4/doc/html/Data-Graph-Inductive-Query-MaxFlow.html>
>
> ______________________________**_________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120122/a03f488a/attachment.htm>
More information about the Haskell-Cafe
mailing list