[Lemon-user] Nagamochi-Ibaraki

[Duraid Madina]

Hi Attila,

On Fri, Feb 22, 2013 at 10:53:33AM +0100, Attila Bernáth 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?

Practically speaking, you may find that it will "just work",
without you doing anything special. Have you tried? My
understanding is that Nagamochi-Ibaraki is correct for
real-weighted graphs, but I don't know if the same is true
for the LEMON implentation when using doubles.

If for some reason it doesn't work, perhaps there is a way to
scale your doubles to integers. One nice thing about LEMON is
that switching among different integer (or integer-like) types
is very easy. You can easily switch between using 32-, 64- or
even arbitrary precision integers, until you find whatever
works.

Putting practicality aside (i.e. if you want to have some fun),
you might want to read 'A Simple Min-Cut Algorithm' by Stoer and
Wagner. Implementing that algorithm in LEMON should be a fun
exercise!

	Hope this helps,

	Duraid

> 
> Attila

> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user