0 Replies - 18035 Views - Last Post: 29 December 2012 - 12:43 PM Rate Topic: -----

#1 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10565
  • View blog
  • Posts: 39,103
  • Joined: 27-December 08

Data Structures: Graph Theory- Hungarian Algorithm

Posted 29 December 2012 - 12:43 PM

The Hungarian algorithm is used to optimize a graph, represented as a bipartite cost matrix. As such, the Hungarian algorithm utilizes the bipartite matching algorithm. An application of the Hungarian algorithm is to find the best worker for the best job.

The matrix is set up in the following form:
X/Y | 1 | 2 | 3 | 4 | 5 
 A  | 4   5   5   4   6
 B  | 6   7   7   5   8
 C  | 6   5   2   5   4
 D  | 4   3   4   7   6
 E  | 9   7   7   6   10



The steps of the Hungarian algorithm are as follows:
-If the matrix isn't square, make it square by adding rows of 0's
-Reduce the matrix (note that this is NOT a Linear Algebra reduction)
-Pick a greedy matching on the 0's
-Find the optimal matching with the bipartite matching algorithm
-If the matching isn't optimal, find the minimal Cover (found X vertices + unfound Y vertices).
-Based on the cover, find the minimal uncovered entry (call it m). Subtract m from every uncovered entry and add m to every double-covered entry.
-Pick a new greedy matching on the 0's and repeat

Some Pseudo-Code:
function hungarianAlgorithm(SquareCostMatrix matrix)
    foreach row in matrix
        min = findMin(row)
 
        foreach element in row
             element <-- element - min
        end foreach
    end foreach
  
    foreach column in matrix
        min = findMin(col)
       
        if min > 0
            foreach element in column
               element <-- element - min
            end foreach
        end if
    end foreach

    while matrix.getNumberMatches() < matrix.getX().size()
        pickMatching(matrix)
        augmentMatching(matrix)
      
        minCover <-- matrix.getMinCover()          

        foreach element in minCover
             if matrix.x.contains(element)
                cover row at element
             end if

             else 
                cover column at element
             end else
        end foreach

        min <-- findMinUncovered(matrix)
        
        foreach row in matrix
            foreach element in row
                if isCovered(element) == FALSE
                    element <-- element - min
                end if

                else if isDoubleCovered(element) 
                    element <-- element + min
                end if
            end foreach
        end foreach
    end while
end function

function findMinUncovered(Matrix matrix)
 
   min <-- infinity

   foreach row in matrix
        foreach element in row
            if isCovered(element) == FALSE AND element < min
               min <-- element
        end foreach
   end foreach

   return min
end foreach

function pickMatching(Matrix matrix)
    foreach row in matrix
       foreach element in row, indexed i
           if element == 0 AND hasMatching(column[i]) == FALSE
              match(element)
           end if
       end foreach
    end foreach
end function



Now, let's work through an example with the following cost matrix:
X/Y | 1 | 2 | 3 | 4 | 5 
 A  | 4   5   5   4   6
 B  | 6   7   7   5   8
 C  | 6   5   2   5   4
 D  | 4   3   4   7   6
 E  | 9   7   7   6   10



Each row has the following minimums:
A- 4
B- 4
C- 2
D- 3
E- 6

After subtracting the row minimums from each row, the matrix reduces to:
X/Y | 1 | 2 | 3 | 4 | 5 
 A  | 0   1   1   0   2
 B  | 1   2   2   0   3
 C  | 4   3   0   3   2
 D  | 1   0   1   4   3
 E  | 3   1   1   0   4



The only non-zero column minimum is at column 5, where the min = 2. Reducing the matrix again, we get:
X/Y | 1 | 2 | 3 | 4 | 5 
 A  | 0   1   1   0   0
 B  | 1   2   2   0   1
 C  | 4   3   0   3   0
 D  | 1   0   1   4   1
 E  | 3   1   1   0   2



Picking a greedy matching (using a * to denote a matched edge) on the 0's, we get:
X/Y | 1 | 2 | 3 | 4 | 5 
 A  | 0*  1   1   0   0
 B  | 1   2   2   0*  1
 C  | 4   3   0*  3   0
 D  | 1   0*  1   4   1
 E  | 3   1   1   0   2



The bipartite matching algorithm produces the forest: E --- 4 -*- B, meaning the matching is maximal. So it is necessary to reduce the matrix yet again. The min cover for this matching is: {4, A, C, D}. The double-covered elements are A4, C4, and D4. The remaining elements in the A, C, and D rows are single covered, as are the remaining elements in column 4.

The minimum amongst the uncovered elements is 1, so subtract it from the uncovered elements and add it to the double-covered elements. The updated matrix is as follows, with the greedy matching the same as the last one:
X/Y | 1 | 2 | 3 | 4 | 5 
 A  | 0*  1   1   1   0
 B  | 0   1   1   0*  0
 C  | 4   3   0*  4   0
 D  | 1   0*  1   5   1
 E  | 2   0   0   0   1



Augmenting the matching leaves the final matrix:
X/Y | 1 | 2 | 3 | 4 | 5 
 A  | 0*  1   1   1   0
 B  | 0   1   1   0*  0
 C  | 4   3   0   4   0*
 D  | 1   0*  1   5   1
 E  | 2   0   0*  0   1



Looking at the original cost matrix, that leaves the final cost at:
3 + 2 + 6 + 4 + 3 = 18

Is This A Good Question/Topic? 0
  • +

Page 1 of 1