[Lemon-user] problem with using HaoOrlin

[Balázs Dezső]

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/20130205/2e7df8ed/attachment.html>