I got it. I'll try to identify that strange instance and send it back to you as soon as possible. Thank you for your advice on scaling the fractional number, they are very helpful. They also help me to solve the problem of some ignorable computational errors, e.g., up to 1e-5, now I have a way to get rid of this.<br>
<br>Best,<br><br><div class="gmail_quote">On Sun, May 27, 2012 at 10:38 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>
> Thanks a lot! I do have some computational errors in my experience<br>
> when the capacity is indeed a fractional number. Particularly<br>
> sometimes(very rare case) the function .runMinCut() never stops on one<br>
> computer, and it runs OK on another.<br>
<br>
</div>This is strange. Do you use the same architecture/os/compilers or<br>
different ones?<br>
<br>
Anyway, I believe .runMinCut() should always stop. I would be very<br>
grateful if you could show an example where it isn't.<br>
<div class="im"><br>
> The problem is that I use Lemon as a subroutine, and the input is a<br>
> solution of a linear program, which is very likely to be fractional.<br>
> Scaling the fractional number might make the scaled integer number<br>
> very big, which might make the algorithm less efficient I guess.<br>
<br>
</div>Don't worry about it. Preflow will not slow down just because of scaling<br>
up the capacities. In math terms, this algorithm is strongly polynomial,<br>
i.e. its worst case running time only depends on the number of edges in<br>
the graph.<br>
<br>
The only thing you have to take care of is to avoid integer overflow<br>
during the computations. A rough guideline, if the sum of all edge<br>
capacities is still representable (i.e. it is no more than about 2e9 or<br>
9e19 for 'int' or 'long long', resp.), then you are on the safe side.<br>
<br>
Regards,<br>
Alpar<br>
<div class="HOEnZb"><div class="h5">><br>
> Best,<br>
><br>
> On Sun, May 27, 2012 at 4:14 AM, Alpár Jüttner <<a href="mailto:alpar@cs.elte.hu">alpar@cs.elte.hu</a>><br>
> wrote:<br>
> Hi,<br>
><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<br>
> Gomory-hu<br>
> > instance.<br>
> ><br>
> ><br>
> > // Construct a lemon graph instance<br>
> > 697 SmartGraph g;<br>
><br>
> > 709 SmartGraph::EdgeMap<double> capacity(g);<br>
><br>
> > ...<br>
> > 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<br>
> matching<br>
> > function for the constructor GomoryHu(g, capacity), and<br>
> > the Problem is in line 709, when I change the type from<br>
> double to int,<br>
> > it then has no errors, but I don't think Lemon only supports<br>
> int type<br>
> > capacities.<br>
><br>
><br>
> The point is that the capacity map is also a template<br>
> parameter, which<br>
> defaults to EdgeMap<int>. You must explicitly give it<br>
> otherwise, like<br>
> this:<br>
><br>
> GomoryHu<SmartGraph,martGraph::EdgeMap<double> > gomoryhu(g,<br>
> capacity);<br>
><br>
> However, let me mention that floating point calculation is<br>
> always risky.<br>
> LEMON does its best to deal with the inevitable computational<br>
> errors,<br>
> still I strongly recommend using an integer type (int or long<br>
> long)<br>
> whenever you can. (And - by appropriately rescaling the input<br>
> - you<br>
> almost always can.)<br>
><br>
> > Also, in order to get a minimum k-cut heuristically, I may<br>
> need to go<br>
> > through all the edges in the gomory-hu tree and choose the<br>
> union of<br>
> > the k smallest edges, which corresponds to a heuristically<br>
> chosen<br>
> > k-cut. Is there any efficient way to do this?<br>
><br>
><br>
> Put the edges in an std::vector<Edge>, then use<br>
> std::nth_element() for<br>
> choosing the k smallest ones.<br>
><br>
> Regards,<br>
> Alpar<br>
><br>
><br>
><br>
><br>
><br>
><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>
<br>
<br>
</div></div></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>