Bug introduced in BoykovKolmogorovAlgorithm

[juliohm]

I've implemented this algorithm a long time ago in LightGraphs.jl and it was moved to this separate repository here after some discussion about heavy dependencies. This migration apparently didn't include the tests I had written for this algorithm specifically and now I am using this code in production with a major bug somewhere. Can you please point to the exact commit in LightGraphs.jl where you copied the code and tests?

I appreciate if you can help me fix this quickly, there are people trying to use downstream code as we speak.

[juliohm]

This file in the test suite for example was removed in the migration: https://github.com/JuliaGraphs/LightGraphs.jl/pull/815/files#diff-19895fa77080a2c9ef721245a44d805070debe3f6a94ddc071f5d827f7b4d8e1

[juliohm]

Git Blame shows a few commits on the file:

1. 3286885 (by @matbesancon) which seems to be the original migration commit. @matbesancon can you please confirm that the code was copied from LG.jl without modifications?
2. eff807b (by @simonschoelly) which introduces changes in a few places like replacing unshift! by pushfirst! and ctranspose by adjoint.

I appreciate if you can confirm these changes did not break the original tests in LG.jl

[juliohm]

Perhaps this has to do with the fact that I am using spzeros as the capacity matrix? I will try to investigate it further when I find some time. The adjoint should work fine with sparse matrices too I suppose.

[simonschoelly]

It looks like this test file: https://github.com/JuliaGraphs/LightGraphsFlows.jl/blob/master/test/boykov_kolmogorov.jl is still here, are you perhaps referring to some other tests?

Also, do you have a simple example where the code fails at the moment?

[juliohm]

Interesting. Thanks for sharing the test, it is indeed the same one we had in LG.jl. I should have added more tests with less trivial capacity matrices.

I will try to share a reproducible example soon.

[juliohm]

@simonschoelly can you please give me push access so that I can submit a PR directly in the repo without needing to fork?

I have added a couple more tests for the BoykovKolmogorov algorithm.

[simonschoelly]

I thin @matbesancon should do that, he also just made me admin a few days ago.

But what would be the problem with adding the tests in a fork and then making a pr?

[juliohm]

But what would be the problem with adding the tests in a fork and then making a pr?

It is just more inconvenient. And since I am a member of JuliaGraphs already and have written some of the algorithms here I think it makes sense to be a member in case I need to help fix something in the future.

[simonschoelly]

I just checked, I think somebody already made you admin here.

[matbesancon]

just gave you access to make PRs