Non-integer solution in maximal_weight_maximal_matching

[pegger0709]

Hello, I am trying to turn a 78x693 matrix with mostly NaN values (all entries except 7381 are NaN) into a bigraph so that every real number entry corresponds to an edge. Specifically, let the matrix be M and I want the bigraph G such that there is an edge between i and size(M,1)+j iff M[i,j] is a real number. I then want to take the bigraph G and find its maximal matching. However, when I do that, I get an exception.

julia> G=Graph(size(M,1)+size(M,2)) {771, 0} undirected graph

julia> for i=1:size(M,1) for j=1:size(M,2) if !isnan(M[i,j]) add_edge!(G,i,j+size(M,1)) end end end

julia> G {771, 7381} undirected graph

julia> is_bipartite(G) true

julia> weights=Dict{Pair{Int64,Int64},Real}() Dict{Pair{Int64,Int64},Real} with 0 entries

julia> for edge in collect(edges(G)) weights[edge]=0.0 end

julia> maximum_weight_maximal_matching(G,weights) ERROR: Found non-integer solution. in maximum_weight_maximal_matching(::LightGraphs.Graph, ::Dict{Pair{Int64,Int64},Real}) at /home/pegger/.julia/v0.5/LightGraphsExtras/src/matching/lp.jl:88

The graph can be seen in the following gist: https://gist.github.com/pegger0709/79ef4e97870a8a9d6fdb922add20ed9c/revisions Seth Bromberger had a look at it and suggested that there is an issue between LightGraphsExtras and my solver. I tried the function maximum_weight_maximal_matching on a smaller bigraph, and it worked fine, so I wonder what the issue could be?

julia> Gsmall=Graph(10) {10, 0} undirected graph

julia> add_edge!(Gsmall,1,5), add_edge!(Gsmall,1,7), add_edge!(Gsmall,3,6), add_edge!(Gsmall,3,8),add_edge!(Gsmall,4,7),add_edge!(Gsmall,4,9) true

julia> Gsmall {10, 6} undirected graph

julia> is_bipartite(Gsmall) true

julia> weights_small=Dict{Pair{Int64,Int64},Real}() Dict{Pair{Int64,Int64},Real} with 0 entries

julia> for edge in collect(edges(Gsmall)) weights_small[edge]=0.0 end

julia> maximum_weight_maximal_matching(Gsmall,weights_small) LightGraphsExtras.Matching.MatchingResult{Float64}(0.0,[5,-1,6,9,1,3,-1,-1,4,-1])

Thanks so much for your help.

Philip Egger

[sbromberger]

Ref https://github.com/JuliaGraphs/LightGraphs.jl/issues/500.

[sbromberger]

@pegger0709 - did you ever get this resolved?

[pegger0709]

Oh yes I figured it out. Was I supposed to close the thread or something? My apologies if I was, I'm quite new to github.

On Mar 22, 2017 13:10, "Seth Bromberger" notifications@github.com wrote:

@pegger0709 https://github.com/pegger0709 - did you ever get this resolved?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/JuliaGraphs/LightGraphsExtras.jl/issues/21#issuecomment-288470566, or mute the thread https://github.com/notifications/unsubscribe-auth/AT4KrjRgryBOBxPB7phTxvelkeUBRCL7ks5roVYMgaJpZM4KymyY .

[sbromberger]

It's no problem; I can close it out. I just didn't want to leave things unresolved. Glad to hear you got it all sorted.