LightGraphsFlows.jl
LightGraphsFlows.jl copied to clipboard
JuliaGraphs
Bug introduced in BoykovKolmogorovAlgorithm
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.
This file in the test suite for example was removed in the migration: https://github.com/JuliaGraphs/LightGraphs.jl/pull/815/files#diff-19895fa77080a2c9ef721245a44d805070debe3f6a94ddc071f5d827f7b4d8e1
Git Blame shows a few commits on the file:
- https://github.com/JuliaGraphs/LightGraphsFlows.jl/commit/328688531ff05372f36a3881127701d61f9d7dc1 (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?
- https://github.com/JuliaGraphs/LightGraphsFlows.jl/commit/eff807b2197fbf665bbb7178624ef4d4f64fb7d7 (by @simonschoelly) which introduces changes in a few places like replacing
unshift!bypushfirst!andctransposebyadjoint.
I appreciate if you can confirm these changes did not break the original tests in LG.jl
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.
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?
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.
@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.
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?
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.
