gnimuc / hungarian.jl Goto Github PK

M = kron(A,B)

using Hungarian
@time assignH, costH = hungarian(M)  
# => 44.816792 seconds (13.19 M allocations: 8.777 GB, 2.24% gc time)

using Munkres
@time assignM = munkres(M)
# =>  0.062191 seconds (20.06 k allocations: 25.378 MB, 3.27% gc time)

A = UInt8[ 49 107  64  23 232 139  21  72 124 125 197 226  45  99 106;
     152 106  95 138 109 171  45  11 173  57 129 223   6 242 116;
     191 197  43 224 105 229  85 225 163 118  99 207 195 194  14;
     239 225 216  48 127 252 234 114   6  64  81 116 161  90  19;
     209 122  84 187 200 150 229  21 115 154 203 252 221 238 131;
     172 247 161 255 102 128 176  63  67 105 107 194 217 226 109;
       5  49  90 126  45 211 168 198 211 200  42  88 117 224 172;
     205 250 117 234  75 251  80  28 121  67  87 106 172 111  54;
     157  99 233  70  80 196 237   3  77 137  32 143 100 117 149;
     221  80 132 251 233 238  44 212 204  41 158 124 113  17 252;
     171   9 138 170  15 190 149  15 190  58 252 248  21 210 223;
      97 240  45 200  53  45  94 122  77  12 114  84 155  94  21;
       6 209 214  15  58  59  60 232  40 210  93  63  80  86  95;
      11 184 129 159 130 171 181  41 164  65 171  55 164  72 132;
      30 225 231 144 209 203  30 202 195 221  70  38 220  48 203]

using Hungarian
using Munkres

n = 15
hh = Hungarian.munkres(A)
match_h = [findfirst(hh[i,:].==Hungarian.STAR) for i = 1:n]
match_m = munkres(A)
sum_h = sum(A[ii, match_h[ii]] for ii in 1:n) |> Int    #-> 712   
sum_m = sum(A[ii, match_m[ii]] for ii in 1:n) |> Int    #-> 456

    @inbounds for j in colUncoveredIdx, i in rowUncoveredIdx
        cost = costMat[i, j] + Δcol[j] + Δrow[i]
        if cost <= h
            if cost != h
                h = cost
                empty!(minLocations)
            end
            push!(minLocations, (i, j))
        end
    end

julia> weights_int = [1 missing; missing missing]
2×2 Matrix{Union{Missing, Int64}}:
 1         missing
  missing  missing

julia> hungarian(weights_int)
([1, 0], 1)

julia> weights_float = [1.0 missing; missing missing]
2×2 Matrix{Union{Missing, Float64}}:
 1.0       missing
  missing  missing

julia> hungarian(weights_float)