17 Replies  4699 Views  Last Post: 04 August 2010  09:02 AM
#1 Guest_Passer By*
[LUA] Munkres/Hungarian Algorithm
Posted 03 August 2010  02:13 AM
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
Replies To: [LUA] Munkres/Hungarian Algorithm
#2 Guest_Passer By*
Re: [LUA] Munkres/Hungarian Algorithm
Posted 03 August 2010  02:48 AM
#3 Guest_Passer By*
Re: [LUA] Munkres/Hungarian Algorithm
Posted 03 August 2010  03:41 AM
#4
Re: [LUA] Munkres/Hungarian Algorithm
Posted 03 August 2010  04:22 AM
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
I'll post the code soon.
#6 Guest_Passer By*
Re: [LUA] Munkres/Hungarian Algorithm
Posted 03 August 2010  06:48 AM
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[count1][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[count1][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
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
#9
Re: [LUA] Munkres/Hungarian Algorithm
Posted 03 August 2010  01:09 PM
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
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
#12 Guest_Passer By*
Re: [LUA] Munkres/Hungarian Algorithm
Posted 03 August 2010  04:57 PM
{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
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
 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
Perhaps I made a mistake working it out by hand, it's time for bed.
