<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Hi Balazs,<br>
<br>
Thank you for the fast response!<br>
In fact, I don't need the min cut value but exactly the set of
nodes that should be set by the calculateOut() method in case the
sink is "my expected" sink of the graph.<br>
<br>
Its strange because for last example node 4 is not a sink in the
graph. no arc ends on it.<br>
So any node which has false value in the cutMap can be a sink ....<br>
There is no way to fix the sink (ie to tell HaoOrlin method which
node is the sink)?<br>
<br>
regards,<br>
<br>
Pierre<br>
<br>
El 05-02-2013 18:51, Balázs Dezső escribió:<br>
</div>
<blockquote
cite="mid:CAMNd4+XFX4dZ3YA5T-js0qjbJEGyZRLdY+Tt3E06NBGMy4ws4A@mail.gmail.com"
type="cite">
<div dir="ltr">
<div style="">Hi Pierre,</div>
<div style=""><br>
</div>
I think you misunderstand the Hao-Orlin algorithm. If you want
to find the minimum cut between two points (for example between
0 and 5), then you don't need to use this algorithm, but a
maximum flow algorithm (e.g., you can use Prelfow class).
<div>
<br>
</div>
<div style="">For the Hao-Orilin, you specify only a source, and
it finds the sink, for which node pair the cut is minimal. In
your case, 0 is source and the algorithm calculates node 4 for
the sink (you can choose any node for sink which has false
value in the cutMap). Because there is no directed path
between 0 and 4, the minimum is 0, which was calculated by the
lemon implementation, too.</div>
<div style=""><br>
</div>
<div style="">Balazs</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Tue, Feb 5, 2013 at 7:11 PM, Pierre
Nancel-Penard <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:pnancel@gmail.com" target="_blank">pnancel@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
I ve tried to use HaoOrlin Algorithm lemon implementation
for a SmartDigraph. I use the calculateOut() method.<br>
and I am facing a problem. As I didn't manage to register (I
had the "Environment not found" error message) to be able
to post a ticket, I post it here.<br>
I use lemon-1.2.3 on ubuntu 10.04.4 and gcc to compile.<br>
<br>
first here is a test of use that works good. Its a graph
with 5 nodes: 0 is the source, 4 is the sink.<br>
It finds the min cut 2 that correspond to the nodes 0 and 2.
All is good!<br>
<br>
Here are the results of the compiled c++ attached files:<br>
<br>
$ ./test_that_work<br>
@nodes<br>
label<br>
0<br>
1<br>
2<br>
3<br>
4<br>
@arcs<br>
label capacity<br>
0 1 0 2<br>
0 2 1 3<br>
1 2 2 1000<br>
1 3 3 1000<br>
3 4 4 4<br>
mincut=2<br>
2<br>
0<br>
<br>
Then,<br>
<br>
$ ./test_that_dont_work<br>
@nodes<br>
label<br>
0<br>
1<br>
2<br>
3<br>
4<br>
5<br>
@arcs<br>
label capacity<br>
0 1 0 2<br>
0 2 1 3<br>
1 2 2 1000<br>
1 3 3 1000<br>
3 5 4 4<br>
4 5 5 4<br>
mincut=0<br>
5<br>
3<br>
2<br>
1<br>
0<br>
<br>
This is same graph as before but now 5 is sink, and there is
other node 4 that is only connected to sink.<br>
As this node is only connected to sink, it don't change the
min cut. but it did and find 0 and all nodes!<br>
I have same problem if the node 4 is not connected to sink.<br>
So if there are unconnected nodes or nodes only connected to
sink, the method calculateOut() seems to not give the min
cut I want to obtain.<br>
So I want to know if its due to an error from my use or
understanding of calculateOut() method.<br>
Because putting off all the only sink connected nodes and
unconnected nodes is too much time consumming for larger
problem instance,<br>
<br>
Any help will be greatly apreciated!<br>
<br>
Best regards,<br>
<br>
Pierre Nancel-Penard<br>
PostDoc in Advanced Mining Technology Center<br>
Universidad de Chile<br>
<br>
_______________________________________________<br>
Lemon-user mailing list<br>
<a moz-do-not-send="true"
href="mailto:Lemon-user@lemon.cs.elte.hu">Lemon-user@lemon.cs.elte.hu</a><br>
<a moz-do-not-send="true"
href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user"
target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br>
<br>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</body>
</html>