[Lemon-user] Problems with Hao-Orlin algorithm

[Alpár Jüttner]

Hi,
> 
> I have just tested Hao-Orlin algorithm and met a problem. I applied
> the algorithm on the graph that gave in the hao_orlin_test.cc (in the
> test folder). That is the minimum cut value couldn't be equal 1. By
> calculating manually, the value equals 2 (the cut set is the set of
> (2,3); (4,1) edges). The total of weights corresponds with 2.

Your counterexample is wrong, and the result given by LEMON's Hao-Orlin
implementation is correct.

First of all, arc (4,1) is not in the graph. I guess you mean (4,0). But
even then, your counterexample is wrong. The arcset {(2,3),(4,1)} is not
even a cut. I feel you misunderstand the definition of the cut of a
directed graph. Consult e.g.
http://en.wikipedia.org/wiki/Maximum_flow/minimum_cut_theorem
for a correct definition.

A minimum cut in that graph is C=({0,1,2},{3,4,5}). This cut contains
the arc (2,3) only. Therefore its weight is 1.

> Are there anyone worked with Hao-Orlin algorithm so far?

Yes, it has extensively been used in more projects.

Regards,
Alpar