Hello all,

Sorry for the thread necromancy but I have a very similar problem to the OP.

I am writing an implementation of the hungarian algorithm based on the same reference as the OP: http://csclab.murray...45/munkres.html

My implementation is in the lua scripting language. When I first implemented this I made some fairly significant changes to the layout of the code, thinking that the reference material was quite hard to follow.

I thought I had successfully implemented the algorithm, and it seemed to be giving optimal solutions. However, I notice now that in some cases the algorithm gets stuck in an infinite loop. Exactly like the OP, the infinite loop happens because the algorithm is looping between steps 4 and 6, never entering step 5.

I've been pouring over my code for two days now, trying to find the error. I've got rid of all my layout changes, just in case I had inadvertently introduced an error. My implementation now translates almost exactly to the reference, so I can easily compare them. I cannot find the problem.

Like the OP mentioned, the reference also says this:

"If your implementation is jumping between Step 4 and Step 6 without entering Step 5, you probably have not properly dealt with recognizing that there are no uncovered zeros in Step 4."

I've tried to have a look at what my algorithm is doing:

1. The algorithm enters step 4 a few times, finds a few zeros, eventually finds a zero which doesn't have a star in the same row, and goes on to step five and the algorithm continues. So far so good.

2. At some point though, the algorithm enters step 4, and finds an uncovered zero in every row, each zero with a starred zero in the same row. The result is that all rows end up covered, and the algorithm eventually can't find any more zeros, so goes to step six.

3. Because all the rows are covered, the code in step 6 to find the smallest uncovered value fails, simply returning infinity, so the algorithm goes back to step 4.

4. Because all the rows are covered, no uncovered zero is found and the algorithm goes back to step 6... etc etc.

That's how the loop forms.

Now I have a fairly good understanding of the written form of the Hungarian algorithm (essentially the pdfs posted above) but I don't have a very deep understanding of how this specific implementation works, so I'm a bit stuck at this point. I can see how the algorithm is failing, but I don't really understand why. At what point should the algorithm be doing something differently.

It would appear that other people have had the same problem, so perhaps there is someone out there familiar enough with the algorithm to point me on the right track. I can't exaggerate how grateful I would be.

In the meantime I'm going to test the algorithm on some small matrices to see what it produces.

Many thanks

## 17 Replies - 6621 Views - Last Post: 04 August 2010 - 09:02 AM

### #1 Guest_Passer By*

# [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 02:13 AM

##
**Replies To:** [LUA] Munkres/Hungarian Algorithm

### #2 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 02:48 AM

Hmm. After some tests it seems that the errors only start happening when I pad a rectangular matrix with zeros to make it square for the algorithm. It's strange because I'm sure I read that this was a perfectly valid way to work with non square matrices with the Hungarian algorithm.

### #3 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 03:41 AM

scratch that, it just failed in the same way for an unpadded matrix. How incredibly frustrating.

### #4

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 04:22 AM

Topic split into the Other Languages forum. Please avoid necroposting.

It might also help if you posted your code, as well as the result vs. expected result for your input.

It might also help if you posted your code, as well as the result vs. expected result for your input.

### #5 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 06:30 AM

Thanks for splitting the topic, for a while I thought my posts had simply been deleted.

I'll post the code soon.

I'll post the code soon.

### #6 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 06:48 AM

Ok so here's the code. I've added a couple of comments which will hopefully help. Lua is a pretty easy language to pick up, so don't worry too much if you haven't used it before.

function hungarian(icostMatrix) local max = #icostMatrix local maxj = #icostMatrix[1] local done = false if max ~= maxj then -- Non square matrix. Pad if max < maxj then print("too many tasks, not enough workers, adding " .. maxj - max .. " 'empty' worker slots") for i = max+1,maxj do icostMatrix[i] = {} for j = 1,maxj do icostMatrix[i][j] = 0 -- pad matrix with zeros end end max = maxj print("Cost matrix dimensions: " .. #icostMatrix .. "," .. #icostMatrix[1]) else return end end hungarianStep1(icostMatrix,max) -- Define and initialise variables to be used from now on local rowCovered = {} local columnCovered = {} local starred = {} for i = 1,max do rowCovered[i] = false columnCovered[i] = false starred[i] = {} for j = 1,max do starred[i][j] = 0 end end hungarianStep2(icostMatrix,max,rowCovered,columnCovered,starred) hungarianClearCovers(rowCovered,columnCovered,max) -- function to uncover all rows and columns local step = 3 local r,c local iterations = 0 local log = "3," -- log keeps a track of the order in which steps were called while step ~= 7 do if step == 3 then step = hungarianStep3(icostMatrix,max,rowCovered,columnCovered,starred) else if step == 4 then step,r,c = hungarianStep4(icostMatrix,max,rowCovered,columnCovered,starred) else if step == 5 then step = hungarianStep5(icostMatrix,max,rowCovered,columnCovered,starred,r,c) else if step == 6 then step = hungarianStep6(icostMatrix,max,rowCovered,columnCovered,starred) end end end end log = log .. step .. "," iterations = iterations + 1 if step == 7 then break end if iterations > 300 then print("ERROR possible infinite loop in hungarian") break end end print("hungarian finished in ".. iterations .. " iterations") print("log: " .. log ) --[[ DEBUG text print("Assignement matrix =") local line = " " for i = 1,#starred do line = "" for j = 1,#starred[i] do line = line .. starred[i][j] .. " " end print(line) end--]] local assigned = {} for i = 1,max do for j = 1,max do if starred[i][j] == 1 then assigned[i]=j break end end end return assigned end ------------------------------------------------------- -- STEP 1 -- function hungarianStep1(icostMatrix,max) local lowestCost for i = 1,max do lowestCost = icostMatrix[i][1] for j = 2,max do if icostMatrix[i][j] < lowestCost then lowestCost = icostMatrix[i][j] end end for j = 1,max do icostMatrix[i][j] = icostMatrix[i][j] - lowestCost end end end -- END of STEP 1 -- -- STEP 2 -- function hungarianStep2(icostMatrix,max,rowCovered,columnCovered,starred) for i = 1,max do for j = 1,max do if icostMatrix[i][j] == 0 and rowCovered[i] == false and columnCovered[j] == false then starred[i][j] = 1 rowCovered[i] = true columnCovered[i] = true end end end end -- END of STEP 2 -- -- STEP 3 -- function hungarianStep3(icostMatrix,max,rowCovered,columnCovered,starred) local count = 0 for i = 1,max do for j = 1,max do if starred[i][j] == 1 then columnCovered[j] = true end end end for j = 1,max do if columnCovered[j] then count = count + 1 end end if count >= max then print("Hungarian solution found!") end return 7 -- done! else return 4 -- do step 4 next end end -- END of STEP 3 -- -- STEP 4 -- function hungarianStep4(icostMatrix,max,rowCovered,columnCovered,starred) local done4 = false local step, check, scol local row,col local debugCount = 0 local log = "Log:" while done4 == false do debugCount = debugCount + 1 if debugCount > 300 then print("ERROR Infinite loop found in hungarianStep4") return 7 end row,col = hungarianFindZero(icostMatrix,rowCovered,columnCovered,max) ---[[ if row == 0 then done4 = true if log ~="Log:" then print(log) end step = 6 -- Do step 6 next else starred[row][col] = 2 log = log .." z="..row..","..col check = hungarianIsStarInRow(row,starred,max) if check then col = hungarianStarInRow(row,starred,max) log = log .." s="..row..","..col rowCovered[row] = true columnCovered[col] = false else done4 = true if log ~="AI:" then print(log) end step = 5 -- Do step 5 next end end end return step,row,col end -- END of STEP 4 -- -- STEP 5 -- function hungarianStep5(icostMatrix,max,rowCovered,columnCovered,starred,ZO_r,ZO_c) local r,c local count = 1 local path = {} path[count] = {} path[count][1] = ZO_r path[count][2] = ZO_c local done5 = false local debugCount = 0 while done5 == false do debugCount = debugCount + 1 if debugCount > 300 then print("ERROR: possible infinite loop found in hungarianStep5") return 7 -- note, there have been occassions where this get out has been used. --I don't know if that's a hint as to what the problem could be, or just a symptom of the problem end r = hungarianStarInColumn(path[count][2],starred,max) if r > 0 then count = count + 1 if path[count] == nil then path[count] = {} else print("ERROR, path[count] already exists") end path[count][1] = r path[count][2] = path[count-1][2] else done5 = true end if done5 == false then c = hungarianDoubleStarInRow(path[count][1],starred,max) count = count + 1 if path[count] == nil then path[count] = {} else print("ERROR, path[count] already exists") end path[count][1] = path[count-1][1] path[count][2] = c end end -- convert path for i = 1,count do if starred [path[i][1]] [path[i][2]] == 1 then starred [path[i][1]] [path[i][2]] = 0 else starred [path[i][1]] [path[i][2]] = 1 end end rowCovered,columnCovered = hungarianClearCovers(rowCovered,columnCovered,max) -- erase double starred for i = 1,max do for j = 1,max do if starred[i][j] == 2 then starred[i][j] = 0 end end end return 3 -- Do step 3 next end -- END of STEP 5 -- -- STEP 6 -- function hungarianStep6(icostMatrix,max,rowCovered,columnCovered,starred) local lowestValue = 9876543216433 for i = 1,max do for j = 1,max do if rowCovered[i] ~= true and columnCovered[j] ~= true then --print("This value is uncovered") -- This never gets printed when the program gets stuck in the loop if lowestValue > icostMatrix[i][j] then lowestValue = icostMatrix[i][j] end end end end --if lowestValue == 9876543216433 then -- -- ERROR, no lowest value found --end --print("Lowest Value = " .. lowestValue) for i = 1,max do for j = 1,max do if rowCovered[i] then icostMatrix[i][j] = icostMatrix[i][j] + lowestValue end if columnCovered[j] == false then icostMatrix[i][j] = icostMatrix[i][j] - lowestValue end end end return 4 -- Do step 4 next end -- END of STEP 6 -- -- hungarianFindZero(row,col) -- function hungarianFindZero(icostMatrix,rowCovered,columnCovered,max) for i = 1,max do for j = 1,max do if icostMatrix[i][j] == 0 and rowCovered[i] == false and columnCovered[j] == false then return i,j end end end return 0,0 end function hungarianIsStarInRow(row,starred,max) for j = 1,max do if starred[row][j] == 1 then return true end end return false end function hungarianStarInRow(row,starred,max) for j = 1,max do if starred[row][j] == 1 then return j end end return false end function hungarianStarInColumn(col,starred,max) for i = 1,max do if starred[i][col] == 1 then return i end end return 0 end function hungarianDoubleStarInRow(row,starred,max) for j = 1,max do if starred[row][j] == 2 then return j end end return 0 end function hungarianClearCovers(rowCovered,columnCovered,max) for i = 1,max do rowCovered[i] = false columnCovered[i] = false end return rowCovered,columnCovered end

### #7 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 08:33 AM

I've been looking at the steps of the algorithm in more detail, trying to see what they are supposed to achieve and how they achieve it.

In step five, the following code is supposed to switch primes (called double stars in my code) into stars and stars into zeros:

The logic is that 'path' should only contain stars or double stars, and so you can use 'else' here without making a second check. On a hunch, I edited the code as follows:

Printing the values to console and changing the else to an elseif. Interestingly, it appears I have some nil values appearing sometimes in [path[i][2]], in the last entry into path. Even more interestingly, the code seems now to be working. However, I'm not going to count my chickens, that nil value shouldn't be there. No smoke without fire.

In step five, the following code is supposed to switch primes (called double stars in my code) into stars and stars into zeros:

for i = 1,count do if starred [path[i][1]] [path[i][2]] == 1 then starred [path[i][1]] [path[i][2]] = 0 else starred [path[i][1]] [path[i][2]] = 1 end end

The logic is that 'path' should only contain stars or double stars, and so you can use 'else' here without making a second check. On a hunch, I edited the code as follows:

for i = 1,count do if starred [path[i][1]] [path[i][2]] ~= nil then log = log .. starred [path[i][1]] [path[i][2]] .. "," else log = log .. "nil," end if starred [path[i][1]] [path[i][2]] == 1 then starred [path[i][1]] [path[i][2]] = 0 elseif starred [path[i][1]] [path[i][2]] == 2 then starred [path[i][1]] [path[i][2]] = 1 end end

Printing the values to console and changing the else to an elseif. Interestingly, it appears I have some nil values appearing sometimes in [path[i][2]], in the last entry into path. Even more interestingly, the code seems now to be working. However, I'm not going to count my chickens, that nil value shouldn't be there. No smoke without fire.

### #8 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 08:41 AM

Ok so things still aren't working, and I still get an infinite loop sometimes. Still, that nil value might lead somewhere.

### #9

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 01:09 PM

You have a spare end in step 3:

Also, do you have an example of data it's failing on. e.g.

print("Hungarian solution found!") end

Also, do you have an example of data it's failing on. e.g.

hungarian({ {1,2,3,4},{2,4,6,8},{3,6,9,12},{4,8,12,16} } )

### #10 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 02:27 PM

Thanks for reading over it. I tidied up the code before posting it, clearing out some debugging stuff, and that end slipped through the net. I've deleted it.

The data it works on is generated by other parts of the program, but I can get it to output some examples for you.

The data it works on is generated by other parts of the program, but I can get it to output some examples for you.

### #11 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 04:52 PM

Here's an example of a matrix that fails, along with the log of which steps are being taken. The initial step 1 and 2 are not included because they happen every time.

### #12 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 04:57 PM

Text form:

{2,2,3,7,8,1,3,4,2,5,6,9}, {1,1,2,6,7,0,2,3,2,4,5,8}, {0,1,1,5,6,1,2,3,3,4,5,7}, {1,2,0,4,5,2,1,2,4,3,4,6}, {2,3,1,4,5,2,0,1,4,2,3,6}, {3,4,2,3,4,3,1,0,5,1,2,5}, {5,6,4,0,1,6,4,3,8,2,1,2}, {6,7,5,1,0,7,5,4,9,3,2,1}, {4,5,3,2,3,4,2,1,6,0,1,4}, {5,6,4,1,2,5,3,2,7,1,0,3}, {2,1,3,7,8,2,4,5,1,6,7,9}, {0,0,0,0,0,0,0,0,0,0,0,0}

### #13 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 05:03 PM

Looking at the state of the matrix when the while loop times out, this is what it looks like:

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

This is very weird stuff. Other matrices that fail also have the same constant for all values, 419023, so it doesn't seem to be random, and yet I have no idea where that's coming from.

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,419023,

This is very weird stuff. Other matrices that fail also have the same constant for all values, 419023, so it doesn't seem to be random, and yet I have no idea where that's coming from.

### #14 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 05:05 PM

That constant is coming from this random value I used:

At the beginning of step 6. If I change that value, I get a different constant appearing everywhere.

-- STEP 6 -- function hungarianStep6(icostMatrix,max,rowCovered,columnCovered,starred) local lowestValue = 9876543216433 for i = 1,max do for j = 1,max do

At the beginning of step 6. If I change that value, I get a different constant appearing everywhere.

### #15 Guest_Passer By*

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 05:48 PM

I've tried working through my algorithm in a spreadsheet using the matrix above, and comparing what happens with the algorithm log. After the first entry to step 4, I already have a different result in excel to what the algorithm is doing, and yet I followed the algorithm step by step.

Perhaps I made a mistake working it out by hand, it's time for bed.

Perhaps I made a mistake working it out by hand, it's time for bed.