Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
thchr opened this issue Feb 28, 2023 · 1 comment
Open

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

thchr opened this issue Feb 28, 2023 · 1 comment

Comments

@thchr
Copy link
Contributor

thchr commented Feb 28, 2023

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:

wnew = Dict{E, Int32}()
cmax = maximum(values(w))
cmin = minimum(values(w))
tmax = typemax(Int32) / tmaxscale # /10 is kinda arbitrary,
# hopefully high enough to not occur in overflow problems
for (e, c) in w
wnew[e] = round(Int32, (c-cmin) / (cmax-cmin) * tmax)
end

@thchr
Copy link
Contributor Author

thchr commented Feb 28, 2023

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)

thchr added a commit to thchr/GraphsMatching.jl that referenced this issue Feb 28, 2023
etiennedeg added a commit that referenced this issue May 2, 2024
* fix same-weight bug (issue #5)

* Fix weight

* Fix typos

* change to first strategy

* revert to spaces

* correct formatting using blue style

---------

Co-authored-by: etienneINSA <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant