[Lemon-user] problem with using HaoOrlin

[Balázs Dezső]

Hi,

With Hao-Orlin algorithm, you can fix either the source or the sink.

If you want to fix the source you need to use:
hao_orlin.init(n);
hao_orlin.calculateOut();

If you want to fix the target you need to use:
hao_orlin.init(n);
hao_orlin.calculateIn();

If you want to calculate the mimum cut between two nodes, then you need a
maximum flow algorithm where you can fix both the source and the sink.
http://en.wikipedia.org/wiki/Maximum_flow_problem

Balazs




On Wed, Feb 6, 2013 at 3:31 PM, Pierre Nancel-Penard <pnancel at gmail.com>wrote:

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