hungarian algorthim code

i need code in c# which implement the Hungarian algorithm

Hungarian algorithm
mea_talAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

jgordosCommented:
Is this a homework problem?

Can't directly answer homework problems, but I can provide tips and references...

Check out this article, I found it helpful myself.

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm

-john
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
keustermansCommented:
Found this on the net.  it was in java I converted it to C#.

I am not sure if it 100% correct but it should give you a good starting point.
using System;
using System.Collections.Generic;
using System.Text;
 
namespace ConsoleApplication2
{
    public class Program
    {
        //**********************************//
        //METHODS OF THE HUNGARIAN ALGORITHM//
        //**********************************//
 
        public static int[][] hgAlgorithm(int[][] array, String sumType)
	{
        int[][] cost = array;	//Create the cost matrix
		
		if (sumType.ToLower().Equals("max"))	//Then array is weight array. Must change to cost.
		{
			int maxWeight = findLargest(cost);
			for (int i=0; i<cost.Length; i++)		//Generate cost by subtracting.
			{
				for (int j=0; j<cost[i].Length; j++)
				{
					cost [i][j] = (maxWeight - cost [i][j]);
				}
			}
		}
		int maxCost = findLargest(cost);		//Find largest cost matrix element (needed for step 6).
		
		int[][] mask = new int[cost.Length][];
        for (int Array0 = 0; Array0 < cost.Length; Array0++)
        {
            mask[Array0] = new int[cost[0].Length];
        }	//The mask array.
        int[] rowCover = new int[cost.Length];					//The row covering vector.
        int[] colCover = new int[cost[0].Length];				//The column covering vector.
		int[] zero_RC = new int[2];								//Position of last zero from Step 4.
		int step = 1;											
		bool done = false;
		while (done == false)	//main execution loop
		{ 
			switch (step)
		    {
				case 1:
					step = hg_step1(step, cost);     
		    	    break;
		    	case 2:
		    	    step = hg_step2(step, cost, mask, rowCover, colCover);
					break;
		    	case 3:
		    	    step = hg_step3(step, mask, colCover);
					break;
		    	case 4:
		    	    step = hg_step4(step, cost, mask, rowCover, colCover, zero_RC);
					break;
		    	case 5:
					step = hg_step5(step, mask, rowCover, colCover, zero_RC);
					break;
		    	case 6:
		    	   	step = hg_step6(step, cost, rowCover, colCover, maxCost);
					break;
		  	    case 7:
		    	    done=true;
		    	    break;
		    }
		}//end while
 
        int[][] assignment = new int[array.Length][];
        for (int Array0 = 0; Array0 < array.Length; Array0++)
        {
	        assignment[Array0] = new int[2];
        }
        for (int i = 0; i < mask.Length; i++)
		{
            for (int j = 0; j < mask[i].Length; j++)
			{
				if (mask[i][j] == 1)
				{
					assignment[i][0] = i;
					assignment[i][1] = j;
				}
			}
		}
		
		//If you want to return the min or max sum, in your own main method
		//instead of the assignment array, then use the following code:
		/*
		int sum = 0; 
		for (int i=0; i<assignment.Length; i++)
		{
			sum = sum + array[assignment[i][0]][assignment[i][1]];
		}
		return sum;
		*/
		//Of course you must also change the header of the method to:
		//public static int hgAlgorithm (int[][] array, String sumType)
		
		return assignment;
	}
        public static int hg_step1(int step, int[][] cost)
        {
            //What STEP 1 does:
            //For each row of the cost matrix, find the smallest element
            //and subtract it from from every other element in its row. 
 
            int minval;
 
            for (int i = 0; i < cost.Length; i++)
            {
                minval = cost[i][0];
                for (int j = 0; j < cost[i].Length; j++)	//1st inner loop finds min val in row.
                {
                    if (minval > cost[i][j])
                    {
                        minval = cost[i][j];
                    }
                }
                for (int j = 0; j < cost[i].Length; j++)	//2nd inner loop subtracts it.
                {
                    cost[i][j] = cost[i][j] - minval;
                }
            }
 
            step = 2;
            return step;
        }
        public static int hg_step2(int step, int[][] cost, int[][] mask, int[] rowCover, int[] colCover)
        {
            //What STEP 2 does:
            //Marks uncovered zeros as starred and covers their row and column.
 
            for (int i = 0; i < cost.Length; i++)
            {
                for (int j = 0; j < cost[i].Length; j++)
                {
                    if ((cost[i][j] == 0) && (colCover[j] == 0) && (rowCover[i] == 0))
                    {
                        mask[i][j] = 1;
                        colCover[j] = 1;
                        rowCover[i] = 1;
                    }
                }
            }
 
            clearCovers(rowCover, colCover);	//Reset cover vectors.
 
            step = 3;
            return step;
        }
        public static int hg_step3(int step, int[][] mask, int[] colCover)
        {
            //What STEP 3 does:
            //Cover columns of starred zeros. Check if all columns are covered.
 
            for (int i = 0; i < mask.Length; i++)	//Cover columns of starred zeros.
            {
                for (int j = 0; j < mask[i].Length; j++)
                {
                    if (mask[i][j] == 1)
                    {
                        colCover[j] = 1;
                    }
                }
            }
 
            int count = 0;
            for (int j = 0; j < colCover.Length; j++)	//Check if all columns are covered.
            {
                count = count + colCover[j];
            }
 
            if (count >= mask.Length)	//Should be cost.Length but ok, because mask has same dimensions.	
            {
                step = 7;
            }
            else
            {
                step = 4;
            }
 
            return step;
        }
        public static int hg_step4(int step, int[][] cost, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC)
        {
            //What STEP 4 does:
            //Find an uncovered zero in cost and prime it (if none go to step 6). Check for star in same row:
            //if yes, cover the row and uncover the star's column. Repeat until no uncovered zeros are left
            //and go to step 6. If not, save location of primed zero and go to step 5.
 
            int[] row_col = new int[2];	//Holds row and col of uncovered zero.
            bool done = false;
            while (done == false)
            {
                row_col = findUncoveredZero(row_col, cost, rowCover, colCover);
                if (row_col[0] == -1)
                {
                    done = true;
                    step = 6;
                }
                else
                {
                    mask[row_col[0]][row_col[1]] = 2;	//Prime the found uncovered zero.
 
                    bool starInRow = false;
                    for (int j = 0; j < mask[row_col[0]].Length; j++)
                    {
                        if (mask[row_col[0]][j] == 1)		//If there is a star in the same row...
                        {
                            starInRow = true;
                            row_col[1] = j;		//remember its column.
                        }
                    }
 
                    if (starInRow == true)
                    {
                        rowCover[row_col[0]] = 1;	//Cover the star's row.
                        colCover[row_col[1]] = 0;	//Uncover its column.
                    }
                    else
                    {
                        zero_RC[0] = row_col[0];	//Save row of primed zero.
                        zero_RC[1] = row_col[1];	//Save column of primed zero.
                        done = true;
                        step = 5;
                    }
                }
            }
 
            return step;
        }
        public static int[] findUncoveredZero	//Aux 1 for hg_step4.
        (int[] row_col, int[][] cost, int[] rowCover, int[] colCover)
        {
            row_col[0] = -1;	//Just a check value. Not a real index.
            row_col[1] = 0;
 
            int i = 0; bool done = false;
            while (done == false)
            {
                int j = 0;
                while (j < cost[i].Length)
                {
                    if (cost[i][j] == 0 && rowCover[i] == 0 && colCover[j] == 0)
                    {
                        row_col[0] = i;
                        row_col[1] = j;
                        done = true;
                    }
                    j = j + 1;
                }//end inner while
                i = i + 1;
                if (i >= cost.Length)
                {
                    done = true;
                }
            }//end outer while
 
            return row_col;
        }
        public static int hg_step5(int step, int[][] mask, int[] rowCover, int[] colCover, int[] zero_RC)
	{
		//What STEP 5 does:	
		//Construct series of alternating primes and stars. Start with prime from step 4.
		//Take star in the same column. Next take prime in the same row as the star. Finish
		//at a prime with no star in its column. Unstar all stars and star the primes of the
		//series. Erasy any other primes. Reset covers. Go to step 3.
		
		int count = 0;												//Counts rows of the path matrix.
		int[][] path = new int[(mask[0].Length*mask.Length)][];
        for (int Array0 = 0; Array0 < (mask[0].Length*mask.Length); Array0++)
        {
	        path[Array0] = new int[2];
        }	//Path matrix (stores row and col).
		path[count][0] = zero_RC[0];								//Row of last prime.
		path[count][1] = zero_RC[1];								//Column of last prime.
		
		bool done = false;
		while (done == false)
		{ 
			int r = findStarInCol(mask, path[count][1]);
			if (r>=0)
			{
				count = count+1;
				path[count][0] = r;					//Row of starred zero.
				path[count][1] = path[count-1][1];	//Column of starred zero.
			}
			else
			{
				done = true;
			}
			
			if (done == false)
			{
				int c = findPrimeInRow(mask, path[count][0]);
				count = count+1;
				path[count][0] = path [count-1][0];	//Row of primed zero.
				path[count][1] = c;					//Col of primed zero.
			}
		}//end while
		
		convertPath(mask, path, count);
		clearCovers(rowCover, colCover);
		erasePrimes(mask);
		
		step = 3;
		return step;
		
	}
        public static int findStarInCol			//Aux 1 for hg_step5.
        (int[][] mask, int col)
        {
            int r = -1;	//Again this is a check value.
            for (int i = 0; i < mask.Length; i++)
            {
                if (mask[i][col] == 1)
                {
                    r = i;
                }
            }
 
            return r;
        }
        public static int findPrimeInRow		//Aux 2 for hg_step5.
        (int[][] mask, int row)
        {
            int c = -1;
            for (int j = 0; j < mask[row].Length; j++)
            {
                if (mask[row][j] == 2)
                {
                    c = j;
                }
            }
 
            return c;
        }
        public static void convertPath			//Aux 3 for hg_step5.
        (int[][] mask, int[][] path, int count)
        {
            for (int i = 0; i <= count; i++)
            {
                if (mask[(path[i][0])][(path[i][1])] == 1)
                {
                    mask[(path[i][0])][(path[i][1])] = 0;
                }
                else
                {
                    mask[(path[i][0])][(path[i][1])] = 1;
                }
            }
        }
        public static void erasePrimes			//Aux 4 for hg_step5.
        (int[][] mask)
        {
            for (int i = 0; i < mask.Length; i++)
            {
                for (int j = 0; j < mask[i].Length; j++)
                {
                    if (mask[i][j] == 2)
                    {
                        mask[i][j] = 0;
                    }
                }
            }
        }
        public static void clearCovers			//Aux 5 for hg_step5 (and not only).
        (int[] rowCover, int[] colCover)
        {
            for (int i = 0; i < rowCover.Length; i++)
            {
                rowCover[i] = 0;
            }
            for (int j = 0; j < colCover.Length; j++)
            {
                colCover[j] = 0;
            }
        }
        public static int hg_step6(int step, int[][] cost, int[] rowCover, int[] colCover, int maxCost)
        {
            //What STEP 6 does:
            //Find smallest uncovered value in cost: a. Add it to every element of covered rows
            //b. Subtract it from every element of uncovered columns. Go to step 4.
 
            int minval = findSmallest(cost, rowCover, colCover, maxCost);
 
            for (int i = 0; i < rowCover.Length; i++)
            {
                for (int j = 0; j < colCover.Length; j++)
                {
                    if (rowCover[i] == 1)
                    {
                        cost[i][j] = cost[i][j] + minval;
                    }
                    if (colCover[j] == 0)
                    {
                        cost[i][j] = cost[i][j] - minval;
                    }
                }
            }
 
            step = 4;
            return step;
        }
        public static int findSmallest		//Aux 1 for hg_step6.
        (int[][] cost, int[] rowCover, int[] colCover, int maxCost)
        {
            int minval = maxCost;				//There cannot be a larger cost than this.
            for (int i = 0; i < cost.Length; i++)		//Now find the smallest uncovered value.
            {
                for (int j = 0; j < cost[i].Length; j++)
                {
                    if (rowCover[i] == 0 && colCover[j] == 0 && (minval > cost[i][j]))
                    {
                        minval = cost[i][j];
                    }
                }
            }
 
            return minval;
        }
 
        //***********//
        //MAIN METHOD//
        //***********//
 
        public static void Main(String[] args) 
	{
		//Below enter "max" or "min" to find maximum sum or minimum sum assignment.
		String sumType = "max";		
				
		//Hard-coded example.
		//int[][] array =
		//{
		//		{1, 2, 3},
		//		{2, 4, 6},
		//		{3, 6, 9}
		//};
		
		//<UNCOMMENT> BELOW AND COMMENT BLOCK ABOVE TO USE A RANDOMLY GENERATED MATRIX
		 
        Console.WriteLine("How many rows for the matrix? ");
        int numOfRows=int.Parse(Console.ReadLine());
		 
        Console.WriteLine("How many columns for the matrix? ");
        int numOfCols=int.Parse(Console.ReadLine());
		int[][] array = new int[numOfRows][];
        for (int Array0 = 0; Array0 < numOfRows; Array0++)
        {
	        array[Array0] = new int[numOfCols];
        }
		generateRandomArray(array, "random");	//All elements within [0,1].
		//</UNCOMMENT>
		
		if (array.Length > array[0].Length)
		{
			Console.Write("Array transposed (because rows>columns).\n");	//Cols must be >= Rows.
			array = transpose(array);
		}
				
		//<COMMENT> TO AVOID PRINTING THE MATRIX FOR WHICH THE ASSIGNMENT IS CALCULATED
		
		Console.Write("The matrix is:");
		for (int i=0; i<array.Length; i++)
		{
			for (int j=0; j<array[i].Length; j++)
            { Console.Write("{0}\t", array[i][j]); }
			     Console.Write("");
		}
		Console.Write("");
		//</COMMENT>*/
		
		long startTime = DateTime.Now.Ticks;	
		int[][] assignment = new int[array.Length][];
        for (int Array0 = 0; Array0 < array.Length; Array0++)
        {
	        assignment[Array0] = new int[2];
        }
		assignment = hgAlgorithm(array, sumType);	//Call Hungarian algorithm.
        long endTime = DateTime.Now.Ticks;
						
		Console.Write("\n\nThe winning assignment (" + sumType + " sum) is:\n");	
		int sum = 0;
		for (int i=0; i<assignment.Length; i++)
		{
			//<COMMENT> to avoid printing the elements that make up the assignment
            
			Console.Write("array({0},{1}) = {2}\n", (assignment[i][0]+1), (assignment[i][1]+1),
					array[assignment[i][0]][assignment[i][1]]);
			sum = sum + array[assignment[i][0]][assignment[i][1]];
			//</COMMENT>
		}
 
        Console.Write("\nThe {0} is: {1}\n", sumType, sum);
        Console.Write("Time elapsed:");
        Console.Write((endTime - startTime) / 1000000000.0);
        Console.ReadLine();
		
	}
 
        //*******************************************//
        //METHODS THAT PERFORM ARRAY-PROCESSING TASKS//
        //*******************************************//
 
        public static void generateRandomArray	//Generates random 2-D array.
        (int[][] array, String randomMethod)
        {
            Random generator = new Random(1);
            for (int i = 0; i < array.Length; i++)
            {
                for (int j = 0; j < array[i].Length; j++)
                {
                        array[i][j] = generator.Next(); 
                }
            }
        }
        public static int findLargest		//Finds the largest element in a positive array.
        (int[][] array)
        //works for arrays where all values are >= 0.
        {
            int largest = 0;
            for (int i = 0; i < array.Length; i++)
            {
                for (int j = 0; j < array[i].Length; j++)
                {
                    if (array[i][j] > largest)
                    {
                        largest = array[i][j];
                    }
                }
            }
            Console.Write("\n\nLargest Value {0}: ", largest);
            return largest;
        }
        public static int[][] transpose		//Transposes a int[][] array.
        (int[][] array)	
	{
        int[][] transposedArray = new int[array[0].Length][];
        for (int Array0 = 0; Array0 < array[0].Length; Array0++)
        {
            transposedArray[Array0] = new int[array.Length];
        }
		for (int i=0; i<transposedArray.Length; i++)
		{
			for (int j=0; j<transposedArray[i].Length; j++)
			{transposedArray[i][j] = array[j][i];}
		}
		return transposedArray;
	}
        public static int[][] copyOf			//Copies all elements of an array to a new array.
        (int[][] original)	
	{
		int[][] copy = new int[original.Length][];
        for (int Array0 = 0; Array0 < original.Length; Array0++)
        {
	        copy[Array0] = new int[original[0].Length];
        }
		for (int i=0; i<original.Length; i++)
		{
			//Need to do it this way, otherwise it copies only memory location
            Array.Copy(original[i], 0, copy[i], 0, original[i].Length);
			
		}
		
		return copy;
	}
 
    }
        
}

Open in new window

0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
.NET Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.