rmatrixmaxpermutationhungarian-algorithm

Hungarian algorithm for change of matrix

I need to implement the realization of Hungarian algorithm for such task: I have any example of matrix(actually I need this for cluster analysis):

X<-matrix(c(-1,1,2,-1,2,3,1,2,3), nrow=3, ncol=3, byrow = TRUE)
X

I need to do some permutations of rows or columns in order to receive such result: all diagonal elements should be maximum. Here I will show some photos: example of matrix, where I have 3 rows and 3 columns and then I must have a result: change of matrix.

As is shown on picture, there is a permutation: first column become third column and after this, new first and second columns change positions. How can I do such thing using Hungarian algorithm?

Solution

  • I'll use this matrix from your question as an example:

     2  7  1
 0  0 10
 8  2  0

    First of all the Hungarian Algorithm finds a minimum, not a maximum, so we need to multiply all of the values by -1 so that when you run the algorithm and it finds a minimum, it will actually be the maximum from the original matrix.

    -2 -7  -1
-0 -0 -10
-8 -2  -0

    The Hungarian Algorithm only works with non-negative numbers, and while the code you're using for it should be able to handle them, you can get rid of them yourself by subtracting the smallest number in the matrix (-10 in this case) from every value in the matrix.

     8  3  9
10 10  0
 2  8 10

    Now we run the Hungarian Algorithm on this matrix and get a list of indices of the minimum matching found by the algorithm. We want to sort this list by the x indices.

    [(0,2), (1,0), (2,1)]

    This minimum matching is also the maximum matching for our original matrix. Since this matching is sorted by the x indices, we can use the y indices as indexes into our original matrix. That is, the first index pair is (0,2), so the first row of our final matrix will be the third row from the original matrix.

    (0,2) -> first row in final matrix is third row in original matrix
    (1,0) -> second row in final matrix is first row in original matrix
    (2,1) -> third row in final matrix is second row in original matrix

     8  2  0
 2  7  1
 0  0 10

    This doesn't exactly match the permutation you gave in your question, but it is still a valid permutation.