juliagraphs / graphsmatching.jl Goto Github PK

I would like to use this package's implementation of the Hungarian algorithm, but cannot build it as I cannot build the BlossomV dependency. This appears to be because the link to the BlossomV code that BlossomV.jl uses has been taken down (see mlewe/BlossomV.jl#23). Is there a way to make BlossomV an "optional dependency"?

MWE:

 minimum_weight_perfect_matching(Graph([Edge(1,2)]), Dict(Edge(1,2)=>2.0))
ERROR: InexactError: trunc(Int32, NaN)
Stacktrace:
 [1] trunc
   @ ./float.jl:760 [inlined]
 [2] round
   @ ./float.jl:359 [inlined]
 [3] minimum_weight_perfect_matching(g::SimpleGraph{Int64}, w::Dict{Graphs.SimpleGraphs.SimpleEdge{Int64}, Float64}; tmaxscale::Float64)
   @ GraphsMatching ~/.julia/packages/GraphsMatching/f764e/src/blossomv.jl:40
 [4] minimum_weight_perfect_matching(g::SimpleGraph{Int64}, w::Dict{Graphs.SimpleGraphs.SimpleEdge{Int64}, Float64})
   @ GraphsMatching ~/.julia/packages/GraphsMatching/f764e/src/blossomv.jl:33
 [5] top-level scope
   @ REPL[558]:1

This fails due to the rescaling of weights which assumes that there are different weights:

On Julia 1.9.2 with GraphsMatching 0.2.0, the code from the introductory example does not run:

julia> using Graphs, GraphsMatching
julia> g = complete_graph(3)
julia> w = zeros(3,3)
julia> w[1,2] = 1
julia> w[3,2] = 1
julia> w[1,3] = 1
julia> match = maximum_weight_matching(g, with_optimizer(Cbc.Optimizer, logLevel=0), w)
ERROR: UndefVarError: `with_optimizer` not defined

After digging around, I succeeded with:

julia> match = maximum_weight_matching(g, JuMP.optimizer_with_attributes(Cbc.Optimizer,"LogLevel"=>0), w)
Welcome to the CBC MILP Solver 
Version: 2.10.8 
Build Date: Jan  1 1970 

command line - Cbc_C_Interface -LogLevel 0 -solve -quit (default strategy 1)
MatchingResult{Float64}(1.0, [2, 1, -1])

On an unrelated note, I have a question: does the graph optimization ecosystem in Julia cover the functionality of scipy.sparse.csgraph.min_weight_full_bipartite_matching?

Currently, the minimum weight perfect matching (MWPM) algorithm relies on BlossomV.jl, a wrapper around Kolmogorov's BlossomV software, which has a research-only, non-commercial license. I'm wondering if there are any plans to use an open-source version, such as a pure julia rewrite or a different implementation with a similar performance like the MWPM algorithm in LEMON (http://lemon.cs.elte.hu/pub/doc/latest-svn/index.html), with a much more permissive license? I realize that this issue has been raised in the past (see https://discourse.julialang.org/t/should-we-consider-bindeps-abandoned/23616 and mlewe/BlossomV.jl#15), but I'm a new user and haven't found a follow-up on this issue. So, I figure it doesn't hurt to ask. Thanks a lot in advance!