[Lemon-user] About Gomory-Hu tree

[Yongjia Song]

Hi Alpar,

Thanks a lot! I do have some computational errors in my experience when the
capacity is indeed a fractional number. Particularly sometimes(very rare
case) the function .runMinCut() never stops on one computer, and it runs OK
on another. The problem is that I use Lemon as a subroutine, and the input
is a solution of a linear program, which is very likely to be fractional.
Scaling the fractional number might make the scaled integer number very
big, which might make the algorithm less efficient I guess.

Best,

On Sun, May 27, 2012 at 4:14 AM, Alpár Jüttner <alpar at cs.elte.hu> wrote:

> Hi,
>
> On Sat, 2012-05-26 at 21:02 -0500, Yongjia Song wrote:
> > Hi all,
> >
> >
> > I encounter a compiling error when I try to create a Gomory-hu
> > instance.
> >
> >
> > // Construct a lemon graph instance
> >  697     SmartGraph g;
> >  709     SmartGraph::EdgeMap<double> capacity(g);
> >  ...
> >  717     GomoryHu<SmartGraph> gomoryhu(g, capacity);
> >  718     gomoryhu.run();
> >  719     exit(0);
> >
> >
> > The error that shoes up when compiling is that, there is no matching
> > function for the constructor GomoryHu(g, capacity), and
> > the Problem is in line 709, when I change the type from double to int,
> > it then has no errors, but I don't think Lemon only supports int type
> > capacities.
>
> The point is that the capacity map is also a template parameter, which
> defaults to EdgeMap<int>. You must explicitly give it otherwise, like
> this:
>
> GomoryHu<SmartGraph,martGraph::EdgeMap<double> > gomoryhu(g, capacity);
>
> However, let me mention that floating point calculation is always risky.
> LEMON does its best to deal with the inevitable computational errors,
> still I strongly recommend using an integer type (int or long long)
> whenever you can. (And - by appropriately rescaling the input - you
> almost always can.)
>
> > Also, in order to get a minimum k-cut heuristically, I may need to go
> > through all the edges in the gomory-hu tree and choose the union of
> > the k smallest edges, which corresponds to a heuristically chosen
> > k-cut. Is there any efficient way to do this?
>
> Put the edges in an std::vector<Edge>, then use std::nth_element() for
> choosing the k smallest ones.
>
> Regards,
> Alpar
>
>
>
>


-- 
Sincerely:
SONG Yongjia（宋永佳）

Department of Industrial and Systems Engineering
College of Engineering, University of Wisconsin-Madison
3241 Mechanical Engineering Building
1513 University Avenue, Madison, WI 53706
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20120527/49c87ae5/attachment.html>