<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 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 href="mailto:Lemon-user@lemon.cs.elte.hu">Lemon-user@lemon.cs.elte.hu</a><br>
<a 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>