Re: [Edmonds-alg-users] A bug?

[Ali T. <ali...@gm...>]

Dear Luigi,

On Sun, Dec 6, 2009 at 11:02, Luigi Laura <la...@di...> wrote:

> Hi,
> sorry to bother you;
> I think I found a small bug in your program.
>

Indeed, you did find a bug, and a serious one at that! I have now added it
to the tracker on sourceforge. I believe that the problem has an easy
solution and will hopefully upload a new corrected version as soon as
possible. Thanks for reporting the bug!

Best wishes
/Ali Tofigh


> I slightly modified the "sparse-example.cpp" file into
> "sparse-example2.cpp", that I attach to this mail. Note that the the graph
> is the only change.
> Below I paste the output (where you can also see the graph):
> --------------------------------------------------
> This is the graph:
> (0, 6)  1
> (1, 0)  1
> (2, 1)  1
> (3, 1)  30
> (4, 5)  1
> (5, 3)  1
> (5, 4)  30
> (6, 3)  30
> (6, 4)  1
> (6, 5)  30
> This is the maximum branching
> (1, 0)  1
> (3, 1)  30
> (6, 3)  30
> (5, 4)  30
> (6, 5)  30
> (0, 6)  1
> --------------------------------------------------
>
> Note that vertex 2 is not in the branching, and, most important, the
> branching includes a cycle: 1 -> 0 -> 6 ->  3 -> 1 (therefore it is
> difficult to still call it a branching :-(
>
> Note also that, if the arc (2,1) would have been in the solution instead of
> the (3,1) one, that would have been a branching (probably the optimal, i
> didn't check).
>
> Thank you in advance for any answer.
> Best regards,
> Luigi Laura
>