/ Hungarian.jl Public

The Hungarian(Kuhn-Munkres) algorithm for Julia

# Gnimuc/Hungarian.jl

Switch branches/tags
Nothing to show

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

## Latest commit

`0d18af7`

## Files

Failed to load latest commit information.
Type
Name
Commit time

# 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

The Hungarian(Kuhn-Munkres) algorithm for Julia

v0.7.0 Latest
Jan 3, 2023

## Packages 0

No packages published