Solved

# hungarian algorthim code

Posted on 2008-11-18
1,839 Views
i need code in c# which implement the Hungarian algorithm

Hungarian algorithm
0
Question by:mea_tal

LVL 11

Accepted Solution

Is this a homework problem?

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

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

-john
0

LVL 7

Expert Comment

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

for (int Array0 = 0; Array0 < cost.Length; Array0++)

{

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:

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++)

{

{

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

{

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++)

{

{

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.

{

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)

{

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)

{

count = count+1;

path[count][0] = path [count-1][0];	//Row of primed zero.

path[count][1] = c;					//Col of primed zero.

}

}//end while

clearCovers(rowCover, colCover);

step = 3;

return step;

}

public static int findStarInCol			//Aux 1 for hg_step5.

{

int r = -1;	//Again this is a check value.

for (int i = 0; i < mask.Length; i++)

{

{

r = i;

}

}

return r;

}

public static int findPrimeInRow		//Aux 2 for hg_step5.

{

int c = -1;

for (int j = 0; j < mask[row].Length; j++)

{

{

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++)

{

{

}

else

{

}

}

}

public static void erasePrimes			//Aux 4 for hg_step5.

{

for (int i = 0; i < mask.Length; i++)

{

for (int j = 0; j < mask[i].Length; j++)

{

{

}

}

}

}

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? ");

Console.WriteLine("How many columns for the matrix? ");

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);

}

//*******************************************//

//*******************************************//

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;

}

}

}
``````
0

## Featured Post

### Suggested Solutions

Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Entity Framework is a powerful tool to help you interact with the DataBase but still doesn't help much when we have a Stored Procedure that returns more than one resultset. The solution takes some of out-of-the-box thinking; read on!
how to add IIS SMTP to handle application/Scanner relays into office 365.
This video discusses moving either the default database or any database to a new volume.