search

JuliaGraphs / LightGraphsFlows.jl

Flow algorithms on LightGraphs
Other
36 stars 11 forks source link

Bug introduced in BoykovKolmogorovAlgorithm #43

Open juliohm opened 3 years ago

juliohm commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

Git Blame shows a few commits on the file:

  1. 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?
  2. https://github.com/JuliaGraphs/LightGraphsFlows.jl/commit/eff807b2197fbf665bbb7178624ef4d4f64fb7d7 (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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

@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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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

matbesancon commented 3 years ago

just gave you access to make PRs