[Lemon-user] Nagamochi-Ibaraki

[Balázs Dezső]

I think you can use the algorithm with double values, but it's numerically
unstable.

In a substep of the algorithm, we have a list of nodes, and we need to
calculate the cut value by splitting the sequence at each possible
position. In order to do that, we iterate over the sequence, and we always
update the cut value when step to the next node. This step can cause
serious numerical errors, therefore I don't recommend to use double.

I recommend one of the following solutions:
 - If it's possible, use fixed point values (it's important that the
highest cut value in the graph should not overflow), or use fractional
values.
 - You can use HaoOrlin algorithm (you need to use only in one direction).
 - You can extend the algorithm with floating point support (patch is
welcomed)
 - The easy solution can be to recalculate the cut value in every step.
 - Or you can adaptively recalculate the cut, if the numerical error can be
high (e.g. if the current value is significantly less than the highest
value stored in that variable, then recalculate the cut value from scratch)

Balazs


On Fri, Feb 22, 2013 at 10:53 AM, Attila Bernáth <bernath.athos at gmail.com>wrote:

> Hi!
>
> I want to find the minimum cut in an undirected graph with nonnegative
> real (that is, double) capacities on the edges. Can I use Nagamochi-Ibaraki
> for that? The documentation seems to say that I cannot:
>
> http://lemon.cs.elte.hu/pub/doc/latest/a00233.html
> Note:
> This capacity is supposed to be integer type.
>
> What to do about this?
>
> Attila
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20130222/c6408d76/attachment.html>