## Hungarian.jl

The Hungarian(Kuhn-Munkres) algorithm for Julia
Popularity
36 Stars
Updated Last
12 Months Ago
Started In
October 2016

# Hungarian

The package provides one implementation of the Hungarian algorithm(Kuhn-Munkres algorithm) based on its matrix interpretation. This implementation uses a sparse matrix to keep tracking those marked zeros, so it costs less time and memory than Munkres.jl. Benchmark details can be found here.

## Installation

`pkg> add Hungarian`

## Quick start

Let's say we have 5 workers and 3 tasks with the following cost matrix:

```weights = [ 24     1     8;
5     7    14;
6    13    20;
12    19    21;
18    25     2]```

We can solve the assignment problem by:

```julia> using Hungarian

julia> assignment, cost = hungarian(weights)
([2, 1, 0, 0, 3], 8)

# worker 1 => task 2 with weights[1,2] = 1
# worker 2 => task 1 with weights[2,1] = 5
# worker 5 => task 3 with weights[5,3] = 2
# the minimal cost is 1 + 5 + 2 = 8  ```

Since each worker can perform only one task and each task can be assigned to only one worker, those `0`s in the `assignment` mean that no task is assigned to those workers.

If a job-worker assignment is not possible, use the special `missing` value to indicate which pairs are disallowed:

```julia> using Hungarian

julia> weights = [missing 1 1; 1 0 1; 1 1 0]
3×3 Matrix{Union{Missing, Int64}}:
missing  1  1
1         0  1
1         1  0

julia> assignment, cost = hungarian(weights)
([2, 1, 3], 2)```

NOTE: This package does not support `Inf` weights. All `Inf`s are converted to `prevfloat(typemax(T))` before running the munkres algorithm.

## Usage

When solving a canonical assignment problem, namely, the cost matrix is square, one can directly get the matching via `Hungarian.munkres(x)` instead of `hungarian(x)`:

```julia> using Hungarian

julia> matching = Hungarian.munkres(rand(5,5))
5×5 SparseArrays.SparseMatrixCSC{Int8, Int64} with 9 stored entries:
1  2  ⋅  ⋅  ⋅
⋅  ⋅  1  ⋅  2
2  ⋅  ⋅  ⋅  ⋅
1  ⋅  2  ⋅  ⋅
⋅  ⋅  ⋅  2  1

# 0 => non-zero
# 1 => zero
# 2 => STAR
julia> Matrix(matching)
5×5 Matrix{Int8}:
1  2  0  0  0
0  0  1  0  2
2  0  0  0  0
1  0  2  0  0
0  0  0  2  1

julia> [findfirst(matching[i,:].==Hungarian.STAR) for i = 1:5]
5-element Vector{Int64}:
2
5
1
3
4

julia> [findfirst(matching[:,i].==Hungarian.STAR) for i = 1:5]
5-element Vector{Int64}:
3
1
4
5
2```

If a job-worker assignment is not possible, use the special `missing` value to indicate which pairs are disallowed:

```julia> using Hungarian

julia> weights = [missing 1 1; 1 0 1; 1 1 0]
3×3 Matrix{Union{Missing, Int64}}:
missing  1  1
1         0  1
1         1  0

julia> matching = Hungarian.munkres(weights)
3×3 SparseArrays.SparseMatrixCSC{Int8, Int64} with 6 stored entries:
⋅  2  1
2  1  ⋅
1  ⋅  2```

## References

1. J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.

2. http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html