Function hungarian::minimize

pub fn minimize<N: NumAssign + PrimInt>(
    matrix: &[N], 
    height: usize, 
    width: usize
) -> Vec<Option<usize>>

Implementation of the Hungarian / Munkres Assignment Algorithm.

Given a rectangular cost matrix, this algorithm finds a maximal matching such that the total cost is minimized. Follows the general outline explained here. This implementation only works on integer costs (since checking if a float is 0 is not a great idea).

The function will automatically clamp all costs in the provided matrix to be greater or equal to zero, and as a result, won't correctly calculate the minimum assignment for a matrix with negative entries.

Requires

• matrix is rectangular (i.e. no ragged matrices)

Takes

• matrix: &[u64]: a 1D slice in row-major order, representing a 2D matrix
• height: height of matrix (i.e. number of rows)
• width: width of matrix (i.e. number of columns)

Returns

• v: A Vec where v[i] is:
  • Some(j) if row i should be assigned to column j
  • None if row i is not in the optimal assignment. Only possible if width < height.

Panics

This function uses unsafe array indexing directly in order to minimize, runtime costs, and will eventually panic with out-of-bounds if passed incorrect width or height arguments.

If given correct arguments, there is no way we can index out of bounds, even in unsafe blocks: we only ever iterate between 0 and width/height.

Examples

extern crate hungarian;

use hungarian::minimize;

fn main() {

    // Square matrix

    let width = 3;
    let height = 3;
    let matrix = vec![
        1, 2, 1,
        4, 5, 6,
        7, 8, 9,
    ];

    let assignment = minimize(&matrix, height, width);

    assert_eq!(&assignment, &vec![Some(2), Some(1), Some(0)]);

    let cost: u64 = assignment.iter()
        .enumerate()
        .filter_map(|(i, &a)| {
            a.map(|j| matrix[i*width + j])
        })
        .sum();

    assert_eq!(cost, 13);

    // Rectangular matrix (height < width)

    let height = 2;
    let width = 3;
    let matrix = vec![
        1, 0, 5,
        2, 3, 1,
    ];

    let assignment = minimize(&matrix, height, width);

    assert_eq!(&assignment, &vec![Some(1), Some(2)]);

    let cost: u64 = assignment.iter()
        .enumerate()
        .filter_map(|(i, &a)| {
            a.map(|j| matrix[i*width + j])
        })
        .sum();

    assert_eq!(cost, 1);

    // Rectangular matrix (width < height)

    let height = 3;
    let width = 2;
    let matrix = vec![
        5, 5,
        1, 0,
        2, 3,
    ];

    let assignment = minimize(&matrix, height, width);

    assert_eq!(&assignment, &vec![None, Some(1), Some(0)]);

    let cost: u64 = assignment.iter()
        .enumerate()
        .filter_map(|(i, &a)| {
            a.map(|j| matrix[i*width + j])
        })
        .sum();

    assert_eq!(cost, 2);

}