Function linear_assignment::solver [−] [src]

pub fn solver<T>(matrix: &mut T, size: &MatrixSize) -> HashSet<Edge> where
    T: IndexMut<Edge>,
    T::Output: Weight, 

Find a solution to the assignment problem in matrix.

Given a bipartite graph consisting of the sets U and V, matrix represents the weights of the edges E between each vertex represented by the elements of the set U and the set V.

matrix should be a rectangular matrix, where size.columns >= size.rows.

Here we are interested in finding some subset of the edges E of our bipartite graph, (represented by our matrix), where:

  • Every vertex in U and in V is connected via exactly a single edge (not more or less)

  • The sum of the weights of these edges are at least as small as any other subset that satisfies the first condition.

These two properties must hold for our result.

Warning: there is the potential for overflow if the values in matrix are larger than 1/2 the maximum representable value of type T::Output.