brede_mat_assignment

 brede_mat_assignment - Matching a bipartite graph'(Hungarian method)

       A = brede_mat_assignment(M)

       Input:    M   'Mat' structure or matrix

       Property  OptimizationType  [ MaxBruteForce | MaxGreedy |
                                   {MaxMunkres} ]
                 Output [ {AssignmentMatrix} | RowAndColumnIndices |
                        SortedInputMatrix ]

       Output:   A   'Mat' structure with assignment

       Solving of the "assignment problem" either by a non-optimal
       greedy algorithm, a brute force method or the so-called
       Munkres algorithm/Hungarian method/Hungarian
       algorithm/Kuhn-Munkres algorithm. The operation seems also to
       be referred to as "maximum weight perfect matching in a
       bipartite graph".    

       The brute force will take long time and use much memory for
       matrices with more than round 9 rows.

       Input should be a square rating matrix. The output is a
       assignment matrix if 'output' = 'AssignmentMatrix'. 

       Reference: 
         James Munkres, "Algorithms for the Assignment and
         Transportation Problems", J. Soc. Indust. Appl. Math,
         5(1):32+, 1957.

         Robert Pilgrim, Munkres' Assignment Algorithm,
         http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html 

       Example:
         M = rand(7)
         A = brede_mat_assignment(M); A.matrix

         % Kuhn (1955) example
         R = [ 8 7 9 9 ; 5 2 7 8 ; 6 1 4 9 ; 2 3 2 6 ];
         A = brede_mat_assignment(R, 'optimizationType', 'MaxMunkres'); A.matrix

       See also BREDE, BREDE_MAT, BREDE_MAT_MATCH.

 $Id: brede_mat_assignment.m,v 1.6 2006/07/21 11:18:32 fn Exp $