search

JuliaGraphs / GraphsMatching.jl

Matching algorithms for Graphs.jl
Other
16 stars 7 forks source link

2-node graphs and same-weight graphs error #5

Open thchr opened 1 year ago

thchr commented 1 year ago

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: https://github.com/JuliaGraphs/GraphsMatching.jl/blob/7d14c0b345eb701f86ff20236e26a8a050994932/src/blossomv.jl#L34-L41

thchr commented 1 year ago

I'm wondering if an acceptable fix to this could be changing the wnew line to:

    wnew[e] = round(Int32, (c-cmin) / max(cmax-cmin, 1) * tmax)

EDIT: An alternative could be to just short-circuit: if all weights are the same, a valid answer is:

mate = collect(reverse(vertices(g)))
weight = nv(g) * first(values(w)) / 2
MatchingResult(weight, mate)