[LUA] Munkres/Hungarian Algorithm

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 3385 Views - Last Post: 04 August 2010 - 09:02 AM Rate Topic: -----

#1 Guest_Passer By*


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

Replies To: [LUA] Munkres/Hungarian Algorithm

#2 Guest_Passer By*


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.
Was This Post Helpful? 0

#3 Guest_Passer By*


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.
Was This Post Helpful? 0

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 9027
  • View blog
  • Posts: 33,485
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 Guest_Passer By*


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.
Was This Post Helpful? 0

#6 Guest_Passer By*


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

Was This Post Helpful? 0

#7 Guest_Passer By*


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.
Was This Post Helpful? 0

#8 Guest_Passer By*


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.
Was This Post Helpful? 0

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 4881
  • View blog
  • Posts: 11,272
  • 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} } )

Was This Post Helpful? 0
  • +
  • -

#10 Guest_Passer By*


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.
Was This Post Helpful? 0

#11 Guest_Passer By*


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.

Posted Image
Was This Post Helpful? 0

#12 Guest_Passer By*


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}

Was This Post Helpful? 0

#13 Guest_Passer By*


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.
Was This Post Helpful? 0

#14 Guest_Passer By*


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.
Was This Post Helpful? 0

#15 Guest_Passer By*


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.
Was This Post Helpful? 0
  • (2 Pages)
  • +
  • 1
  • 2