### 4 releases (stable)

Uses old Rust 2015

1.1.1 | Jun 15, 2020 |
---|---|

1.1.0 | Mar 16, 2018 |

1.0.0 | Mar 15, 2018 |

0.1.0 | Mar 14, 2018 |

#**988** in Algorithms

**143** downloads per month

**MIT**license

33KB

538 lines

# hungarian

**IMPORTANT**: The

crate has a significantly
faster implementation of this
algorithm (benchmarks below), uses traits to abstract over cost matrices, and is also better maintained.
I recommend using it instead.`pathfinding`

A simple Rust implementation of the Hungarian (or Kuhn–Munkres) algorithm.
Should run in

time and take `O (n^3)`

`O``(`m`*`n`)`

space, given an `m ``*` n

rectangular
matrix (represented as a 1D slice).Derived and modified from this great explanation.

## Usage

Add the following to your

file:`Cargo.toml`

`[``dependencies``]`
`hungarian ``=` `"`1.1.1`"`

Add the following to the top of your binary or library:

`extern` `crate` hungarian`;`
`use` `hungarian``::`minimize`;`

And you should be good to go! For more information, check out the documentation.

## Recent Changes

- 1.1.1
- Version bump so the

redirect appears on`pathfinding`

.`crates``.`io

- Version bump so the
- 1.1.0
- Greatly optimized performance (by a factor of 2-4 on benchmarks on matrices from 5x5 to 100x100)
- Now uses

to take generic integer weights`num-trait` - Now backed by

to scale better with larger inputs`ndarray`

- 1.0.0
- Greatly improved source code documentation
- Renamed

function to`hungarian``minimize` - Now handle arbitrary rectangular matrices
- Added more test cases to cover non-square matrices
- Now returns

to handle when not all columns are assigned to rows`Vec``<``Option``<`Usize`>``>`

- 0.1.0
- Initial release
- Working base algorithm, but only works for square matrices.
- Not well documented

## Notes

Instead of using splitting logic across files and helper functions, I tried to simplify and condense the above explanation into a single, simple function while maintaining correctness. After trawling the web for test cases, I'm reasonably confident that my implementation works, even though the end result looks fairly different.

Please let me know if you find any bugs!

## Performance

Benchmarks were obtained using Criterion.rs, with the following two types of cost matrices:

` Worst Case ``|` Generic Case
`|`
`-``-``-``-``-``-``-``-``-``-``-``-``-` `|` `-``-``-``-``-``-``-``-``-``-``-``-``-`
`|` `1` `|` `2` `|` `3` `|` `...` `|` `|` `1` `|` `2` `|` `3` `|`
`-``-``-``-``-``-``-``-``-``-``-``-``-` `|` `-``-``-``-``-``-``-``-``-``-``-``-``-`
`|` `2` `|` `4` `|` `6` `|` `...` `|` `|` `4` `|` `5` `|` `6` `|`
`-``-``-``-``-``-``-``-``-``-``-``-``-` `|` `-``-``-``-``-``-``-``-``-``-``-``-``-`
`|` `3` `|` `6` `|` `9` `|` `...` `|` `|` `7` `|` `8` `|` `9` `|`
`-``-``-``-``-``-``-``-``-``-``-``-``-` `|` `-``-``-``-``-``-``-``-``-``-``-``-``-`
`.` `.` `.` `|`
`.` `.` `.` `|`
`.` `.` `.` `|`
`|`
C`(`i`,` j`)` `=` `(`i `+` `1``)``(`j `+` `1``)` `|` C`(`i`,` j`)` `=` `(`i `*` width`)` `+` j

#### Criterion Results

Cost Matrix | Matrix Size | Average Runtime |
Average Runtime |
---|---|---|---|

Worst-Case | 5 x 5 | 2.42 us | 1.19 us |

Worst-Case | 10 x 10 | 20.38 us | 4.24 us |

Worst-Case | 25 x 25 | 546.88 us | 59.66 us |

Worst-Case | 50 x 50 | 6.97 ms | 422.05 us |

Generic | 5 x 5 | 1.75 us | 871.24 ns |

Generic | 10 x 10 | 7.49 us | 3.50 us |

Generic | 25 x 25 | 86.33 us | 33.91 us |

Generic | 50 x 50 | 556.48 us | 285.69 us |

Generic | 100 x 100 | 3.97 ms | 1.93 ms |

Measured on a quad-core 2.6GHz Intel(R) i7-6700HQ with 16GB RAM; using Ubuntu 16.04 Linux x86_64 4.8.0-53-generic

#### Dependencies

~1.5MB

~27K SLoC