Hi Alpar,<br><br>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.<br>
<br>Best,<br><br><div class="gmail_quote">On Sun, May 27, 2012 at 4:14 AM, Alpár Jüttner <span dir="ltr"><<a href="mailto:alpar@cs.elte.hu" target="_blank">alpar@cs.elte.hu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Hi,<br>
<div class="im"><br>
On Sat, 2012-05-26 at 21:02 -0500, Yongjia Song wrote:<br>
> Hi all,<br>
><br>
><br>
> I encounter a compiling error when I try to create a Gomory-hu<br>
> instance.<br>
><br>
><br>
> // Construct a lemon graph instance<br>
>  697     SmartGraph g;<br>
</div><div class="im">>  709     SmartGraph::EdgeMap<double> capacity(g);<br>
</div>>  ...<br>
<div class="im">>  717     GomoryHu<SmartGraph> gomoryhu(g, capacity);<br>
>  718     gomoryhu.run();<br>
>  719     exit(0);<br>
><br>
><br>
> The error that shoes up when compiling is that, there is no matching<br>
> function for the constructor GomoryHu(g, capacity), and<br>
> the Problem is in line 709, when I change the type from double to int,<br>
> it then has no errors, but I don't think Lemon only supports int type<br>
> capacities.<br>
<br>
</div>The point is that the capacity map is also a template parameter, which<br>
defaults to EdgeMap<int>. You must explicitly give it otherwise, like<br>
this:<br>
<br>
GomoryHu<SmartGraph,martGraph::EdgeMap<double> > gomoryhu(g, capacity);<br>
<br>
However, let me mention that floating point calculation is always risky.<br>
LEMON does its best to deal with the inevitable computational errors,<br>
still I strongly recommend using an integer type (int or long long)<br>
whenever you can. (And - by appropriately rescaling the input - you<br>
almost always can.)<br>
<div class="im"><br>
> Also, in order to get a minimum k-cut heuristically, I may need to go<br>
> through all the edges in the gomory-hu tree and choose the union of<br>
> the k smallest edges, which corresponds to a heuristically chosen<br>
> k-cut. Is there any efficient way to do this?<br>
<br>
</div>Put the edges in an std::vector<Edge>, then use std::nth_element() for<br>
choosing the k smallest ones.<br>
<br>
Regards,<br>
Alpar<br>
<br>
<br>
<br>
</blockquote></div><br><br clear="all"><br>-- <br>Sincerely:<br>SONG Yongjia（宋永佳）<br><br>Department of Industrial and Systems Engineering<br>College of Engineering, University of Wisconsin-Madison<br>3241 Mechanical Engineering Building<br>
1513 University Avenue, Madison, WI 53706<br>