[Lemon-user] About Gomory-Hu tree

[Alpár Jüttner]

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