• (2 Pages)
• 1
• 2

Reputation:

# [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 02:13 AM

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

Is This A Good Question/Topic? 0

Reputation:

## 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.

Reputation:

## 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 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12305
• Posts: 45,400
• Joined: 27-December 08

## 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.

Reputation:

## 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.

Reputation:

## 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

```

Reputation:

## 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:

```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.

Reputation:

## 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 baavgai

• Dreaming Coder

Reputation: 7164
• Posts: 14,931
• Joined: 16-October 07

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 01:09 PM

You have a spare end in step 3:
```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} } )

```

Reputation:

## 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.

Reputation:

## 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.

Reputation:

## 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}
```

Reputation:

## 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.

Reputation:

## Re: [LUA] Munkres/Hungarian Algorithm

Posted 03 August 2010 - 05:05 PM

That constant is coming from this random value I used:

```	-- 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.

Reputation:

## 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.