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 inV
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
.