Code from GitHub example fails

[lampretl]

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?

[etiennedeg]

You have maximum_weight_maximal_matching_hungarian for bipartite graphs, which should be more efficient. (negate weights to minimize instead of maximize).

[lampretl]

@etiennedeg Thank you for your suggestion. The documentation for this function is very sparse:

help?> GraphsMatching.maximum_weight_maximal_matching_hungarian
  No documentation found.

  GraphsMatching.maximum_weight_maximal_matching_hungarian is a Function.

  # 2 methods for generic function "maximum_weight_maximal_matching_hungarian" from GraphsMatching:
   [1] maximum_weight_maximal_matching_hungarian(g::SimpleGraph)
       @ ~/.julia/packages/GraphsMatching/f764e/src/hungarian.jl:1
   [2] maximum_weight_maximal_matching_hungarian(g::SimpleGraph, w::AbstractMatrix{T}) where T<:Real
       @ ~/.julia/packages/GraphsMatching/f764e/src/hungarian.jl:1

When M is the output of this function, it looks like:

 julia> M = GraphsMatching.maximum_weight_maximal_matching_hungarian(Γ, -W)
MatchingResult{Float64}(-56.979, [217, 237, 294, 148, 247, 106, 266, 169, 154, 199  …  -1, -1, 65, 3, 53, -1, -1, 41, -1, 70])

How come there are -1's in this list? And how do I get the weight? M[1] does not work. Would it be possible to document a bit more. Otherwise, it's quite hard to work with this package.

Also, to get an analog of scipy's implementation, if I have an mxn matrix W˙ representing the weights of a bipartite graphΓ`, do I pass it like this?

m, n = 10^2, 2*10^2;  
W = sprand(m, n, 0.1, s->rand(0:0.001:10,s));
Γ = Graphs.SimpleGraphs.SimpleGraph(m+n);   
for (i,j,_) ∈ zip(findnz(W)...)  add_edge!(Γ, i, m+j) end;   
W = vcat(hcat(spzeros(m,m), W), hcat(W', spzeros(n,n)));
M = GraphsMatching.maximum_weight_maximal_matching_hungarian(Γ, W);

Is hcat and vcat necessary? So among all the maximal matchings (no edge can be added to enlarge the matching), this returns the one with the largest total weight?

[etiennedeg]

I agree that this package is severely undocumented (and in bad shape overall), I will try to fix it.

help?> MatchingResult
search: MatchingResult

  struct MatchingResult{U}
      weight::U
      mate::Vector{Int}
  end

  A type representing the result of a matching algorithm.

  weight: total weight of the matching

  mate:    `mate[i] = j` if vertex `i` is matched to vertex `j`.
           `mate[i] = -1` for unmatched vertices.

There seems to be no accessors, I will add some. For the moment, you can do M.weight and M.mate to gather the results.

Also, to get an analog of scipy's implementation, if I have an mxn matrix W˙ representing the weights of a bipartite graph Γ`, do I pass it like this?

That should do it, but I will add convenience methods to deal better with bipartite graphs.

So among all the maximal matchings (no edge can be added to enlarge the matching), this returns the one with the largest total weight?

Correct

[lampretl]

I think this package has great potential, since optimization algorithms are often used in industry (3 years ago, I succeeded in a job interview because I used scipy's min_weight_full_bipartite_matching to improve an ML classification task).

If you could improve the ease of use of this package, that would be a big gain for the Julia ecosystem :). And I will try to help, by testing it out and opening issues when needed.