[Lemon-user] About Gomory-Hu tree

[Yongjia Song]

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.

Best,

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

> Hi,
>
> > 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.
>
> This is strange. Do you use the same architecture/os/compilers or
> different ones?
>
> Anyway, I believe .runMinCut() should always stop. I would be very
> grateful if you could show an example where it isn't.
>
> >  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.
>
> Don't worry about it. Preflow will not slow down just because of scaling
> up the capacities. In math terms, this algorithm is strongly polynomial,
> i.e. its worst case running time only depends on the number of edges in
> the graph.
>
> The only thing you have to take care of is to avoid integer overflow
> during the computations. A rough guideline, if the sum of all edge
> capacities is still representable (i.e. it is no more than about 2e9 or
> 9e19 for 'int' or 'long long', resp.), then you are on the safe side.
>
> Regards,
> Alpar
> >
> > 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
>
>
>


-- 
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/e11bac73/attachment.html>