Graphs.jl
Graphs.jl copied to clipboard
JuliaGraphs
Move code from GraphsFlows and GraphsMatching to Graphs
The LP-based algorithms of both packages are being migrated to GraphsOptim, but the combinatorial algorithms (with minimal dependencies) could and should probably go into the main library
See also #108
@gdalle I have opened a PR for the migration of GraphsFlows.jl to the main package. The only algorithm remaining is mincost.jl, which has a dependency on JuMP. I will create a separate PR for GraphsMatching.
I've accidentally tried to merge the wrong branch. I have created a new PR.
@gdalle Should we port the code from BlossomV as well? The minimum_weight_perfect_matching function in GraphsMatching.jl has a dependency on this package, but it seems to be very small, and it doesn't seem to be maintained. I guess that this would make sense for otherwise we would have to add another dependency.
It would be really great to port the BlossomV dependency since it has an awful licence: in practice, the GraphsMatching.jl package only works as long as the BlossomV code is hosted at the original URL (which it stopped being at one point)
Implementing BlossomV was part of a jsoc project in the past that did ultimately not succeed. The algorithm is not that trivial, and the paper omits some technical steps that have to be figured out - I had looked into implementing it myself in the past, but never found the time. It is doable though, for example the was implementation for JGraphT done for gsoc in the past.
Would it make sense to migrate just the Hungarian algorithm from GraphsMatching into Graphs.jl? I would like to use this implementation, but am hesitant to depend on GraphsMatching due to the dependency on BlossomV.
As a first step that would be good! Wanna give it a try? I can do my best to review it quickly.
@thchr I didn't find that second PR you mentioned? Did you ever get around to it?
I would be willing to give this a try. However, I just realized that GraphsMatching's Hungarian algorithm depends on Hungarian.jl. I am assuming that this is the kind of one-off dependency that Graphs.jl would like to avoid.