bghungar

Hungarian algorithm to solve the square assignment problem.

"Hungarian algorithm" to solve the square assignment problem (original & pure MATLAB implementation). The Hungarian algorithm can also be used as a sub-solver in a B&B solver for the travelling salesman problem.

How to match N (e.g. N=6) pairs of signals from 2 experiments? Build full reordering lists based on the PERMS(1:N) MATLAB function? But the complexity of this approach would be N! = prod(1:6) = 720 for a single run! That of the Hungarian algorithm is just N^3 = 6^3 = 216
i.e. it is many times more efficient!

This code is similar in purpose to the central part of assignprob: hungarian.m, v1.0 96-06-14, adapted by Niclas Borlin, [e-mail].
Unlike latter code which is an adaptation from a 1980 ACM algorithm in Fortran IV, this is original code written directly according to [1], and specially for MATLAB (and very portable across different R's of MATLAB). It has only few, hence efficient lines.

» help bghungar

BGHUNGAR "Hungarian algorithm" to solve the square assignment problem

========
For:
--------
C = a square profit/cost matrix.

the call:
--------
[izSol, ifail, D] = bghungar(C);

Returns:
--------

izSol = the optimal assignment: MAXIMIZES total profit

ifail = 0: success;
> 0: various failure triggers, according to the algorithm's sub-section

D = the square matrix equivalent to C at the end of iteration [1]

========
*** Notes:
1) For assignments that MINIMIZE cost, just invert
the sign of the cost matrix:
... = bghungar(-C);

2) Coding decisions are annotated, and debugging commands are provided
(just remove the comments) to resolve intricate use cases.