[Lemon-user] problem with using HaoOrlin

[Pierre Nancel-Penard]

Hi Balazs,

Thank you for the fast response!
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.

Its strange because for last example node 4 is not a sink in the graph.  
no arc ends on it.
So any node which has false value in the cutMap can be a sink ....
There is no way to fix the sink (ie to tell HaoOrlin method which node 
is the sink)?

regards,

Pierre

El 05-02-2013 18:51, Balázs Dezső escribió:
> Hi Pierre,
>
> 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).
>
> 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.
>
> Balazs
>
>
> On Tue, Feb 5, 2013 at 7:11 PM, Pierre Nancel-Penard 
> <pnancel at gmail.com <mailto:pnancel at gmail.com>> wrote:
>
>     Hi,
>
>     I ve tried to use  HaoOrlin Algorithm lemon implementation for a
>     SmartDigraph. I use the calculateOut() method.
>     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.
>     I use lemon-1.2.3 on ubuntu 10.04.4 and gcc to compile.
>
>     first here is a test of use that works good. Its a graph with 5
>     nodes: 0 is the source, 4 is the sink.
>     It finds the min cut 2 that correspond to the nodes 0 and 2. All
>     is good!
>
>     Here are the results of the compiled c++ attached files:
>
>     $ ./test_that_work
>     @nodes
>     label
>     0
>     1
>     2
>     3
>     4
>     @arcs
>             label    capacity
>     0    1    0    2
>     0    2    1    3
>     1    2    2    1000
>     1    3    3    1000
>     3    4    4    4
>     mincut=2
>     2
>     0
>
>     Then,
>
>     $ ./test_that_dont_work
>     @nodes
>     label
>     0
>     1
>     2
>     3
>     4
>     5
>     @arcs
>             label    capacity
>     0    1    0    2
>     0    2    1    3
>     1    2    2    1000
>     1    3    3    1000
>     3    5    4    4
>     4    5    5    4
>     mincut=0
>     5
>     3
>     2
>     1
>     0
>
>     This is same graph as before but now 5 is sink, and there is other
>     node 4 that is only connected to sink.
>     As this node is only connected to sink, it don't change the min
>     cut. but it did and find 0 and all nodes!
>     I have same problem if the node 4 is not connected to sink.
>     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.
>     So I want to know if its due to an error from my use or
>     understanding of calculateOut() method.
>     Because putting off all the only sink connected nodes and
>     unconnected nodes is too much time consumming for larger problem
>     instance,
>
>     Any help will be greatly apreciated!
>
>     Best regards,
>
>     Pierre Nancel-Penard
>     PostDoc in Advanced Mining Technology Center
>     Universidad de Chile
>
>     _______________________________________________
>     Lemon-user mailing list
>     Lemon-user at lemon.cs.elte.hu <mailto:Lemon-user at lemon.cs.elte.hu>
>     http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20130206/650d48ed/attachment.html>