[bstdnator]

Hello there! I have been trying hard for about a week to get this http://csclab.murray...45/munkres.html algorithm implimented in c++.
The idea of the algorithm is that it should find the optimum assignment rows to columns minimising the cost of the matrix. from what i can tell i've followed the code on the above website to the letter (apart from adding various debug stuff) while converting, however the code is getting stuck in an endless loop between steps 4 and 6. I am desperately in need of a solution to this so any help would be fantastic. The code is self contained including a main() to test if its working as it should.

If its working correctly it should assign row 1 to column 2, row 2 to column 4, row 3 to column 3 and row 4 to column 1. which i *think* will be shown in M, resulting with something like...
M= |0 1 0 0 |
| 0 0 0 1 |
| 0 0 1 0 |
| 1 0 0 0 |

anyway, have a look at the code (please) and see if you can help, or if you know anywhere where this algorithm is implimented already or have done it yourself that would be fantastic, but i'd really like to get this working myself if possible cos i've spent way too much time on this now, i hate to admit defeat so posting here is a last resort.

#include <iostream>
#include <String>
using namespace std;

class Munkrees {
public:
	float** C;
	int** M;
	int** path;

private:	
	int *row;
	int *col;
	bool *C_cov;
	bool *R_cov;
	int aRow;
	int aCol;
	int Z0_r; 
	int Z0_c;
	float minval;//should be right
	float minvalOld;
	int n;//todo remove n so algn works for rectangular arrays properly
public:
	int rows;
	int columns;
	Munkrees(int inRows,int inColumns, float** matrix) {
		//aRow=0;
		//aCol=0;
		rows = inRows;
		columns = inColumns;
		cout<<"rows = "<<rows<<", columns = "<<columns<<endl;
		if(!rows==columns) {
			cout<<"rows!=columns - Algorithm undetermined"<<endl;
		}
		else {
			n=rows;
		}
		cout<<"init"<<endl;
		cout<<endl;
		cout<<"rows = "<<rows<<", columns = "<<columns<<endl;
		printArray(matrix, rows, columns, "matrix");
		cout<<"rows = "<<rows<<", columns = "<<columns<<endl;
		C= new float* [rows]; 
		for (int i=0; i<rows; i++){
			C[i]= new float [columns]; 
		}
		for (int i = 0; i<rows;i++) { 
			for (int j = 0; j<columns; j++ ) {
				C[i][j] = matrix[i][j];
			}
		}

		printArray(C, rows,columns,"C");

		C_cov = new bool[columns];
		for (int i = 0; i<columns;i++) {
			C_cov[i] = false;
		}
		R_cov = new bool[rows];
		for (int i = 0; i<rows;i++) {
			R_cov[i] = false;
		}
		M = new int* [rows]; 
		for (int i=0; i<rows; i++){
			M[i]= new int [columns]; 
		}
		for (int i = 0; i<rows;i++) {
			for (int j = 0; j<columns;j++) {
				M[i][j] = 0;
			}
		}

		printArray(M, 4,4,"M");

		path = new int* [rows];
		for (int i=0; i<rows; i++){
			path[i]= new int [columns]; 
		}
		for (int i = 0; i<rows;i++) {
			for (int j = 0; j<columns;j++) {
				path[i][j] = 0;
			}
		}

		printArray(path, 4,4,"path");

		row = new int[rows];
		col = new int[columns];
		int stepnum=1;
		int aRow=0;
		int aCol=0;
		int Z0_r=0; 
		int Z0_c=0;
		minval=999;//should be right
		minvalOld=minval;//used in step6
		bool done=false;
		int* returnVal = new int[2];
		cout<<"End Init!"<<endl;
		while (!done) {
			switch(stepnum){
				case 1:
					stepnum=step1(stepnum);
					cout<<"Step1--------------------------------------------------"<<endl;
					printArray(C, 4,4,"C");
					printArray(M, 4,4,"M");
					printArray(path, 4,4,"path");
					break;
				case 2:
					stepnum=step2(stepnum);
					cout<<"Step2--------------------------------------------------"<<endl;
					printArray(C, 4,4,"C");
					printArray(M, 4,4,"M");
					printArray(path, 4,4,"path");
					break;
				case 3:
					stepnum=step3(stepnum);
					cout<<"Step3--------------------------------------------------"<<endl;
					printArray(C, 4,4,"C");
					printArray(M, 4,4,"M");
					printArray(path, 4,4,"path");
					break;
				case 4:
					stepnum=step4(stepnum);
					cout<<"Step4--------------------------------------------------"<<endl;
					printArray(C, 4,4,"C");
					printArray(M, 4,4,"M");
					printArray(path, 4,4,"path");
					break;
				case 5:
					stepnum=step5(stepnum);
					cout<<"Step5--------------------------------------------------"<<endl;
					printArray(C, 4,4,"C");
					printArray(M, 4,4,"M");
					printArray(path, 4,4,"path");
					break;
				case 6:
					stepnum=step6(stepnum);
					cout<<"Step6--------------------------------------------------"<<endl;
					printArray(C, 4,4,"C");
					printArray(M, 4,4,"M");
					printArray(path, 4,4,"path");
					break;
				default:
					done=true;
					cout<<"Step=Done--------------------------------------------------"<<endl;
					printArray(C, 4,4,"C");
					printArray(M, 4,4,"M");
					printArray(path, 4,4,"path");
					break;
			}
		}
		cout<<"Printing M"<<endl;
		for (int i = 0; i<rows;i++) {
			for (int j = 0; j<columns; j++ ) {
				matrix[i][j] = (float)M[i][j];
				cout << M[i][j]<<"\t";
			}
			cout<<endl;
		}
		delete C;
	}
private:
	int step1(int stepnum){
		//For each row of the matrix, find the smallest element and
		//subtract it from every element in its row.  Go to Step 2
		for (int i = 0; i < n; i++) {
			minval=C[i][0]; 
			for(int j = 0; j < n; j++) {
				if (minval>C[i][j]) {
					minval=C[i][j]; 
				}
			} 
			for (int j = 0; j < n; j++) {
				C[i][j] =C[i][j]-minval; 
			} 
		}
		return 2;
	}

	int step2(int stepnum){
		//Find a zero (Z) in the resulting matrix.  If there is no starred
		//zero in its row or column, star Z. Repeat for each element in the
		//matrix. Go to Step 3. 
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < columns; j++) {
				if ( C[i][j]==0 && C_cov[j]==0 && R_cov[i]==0 ){
					M[i][j]=1; 
					C_cov[j]=1; 
					R_cov[i]=1; 
				}
			}
		}
		for (int i = 0; i<n; i++) {//TODO: this line will fail for non square matricies
			C_cov[i]=0; 
			R_cov[i]=0; 
		}
		return 3;
	}

	int step3(int stepnum){
		//Cover each column containing a starred zero. 
		//If K columns are covered, the starred zeros describe a 
		//complete set of unique assignments. In this case, Go to DONE
		//otherwise, Go to Step 4. 
		int count; 
		for (int i = 0; i<rows; i++) {
			for (int j = 0; j<columns; j++){ 
				if (M[i][j]==1 ) {
					C_cov[j]=1; 
				} 
			}
		}
		count=0; 
		for (int j = 0; j<rows; j++){ 
			count=count + C_cov[j]; 
		}
		if (count>=rows) {
			//we're done here
			return 7;
		}
		else {
			return 4;
		}
	}

	int step4(int stepnum){
		//Find a noncovered zero and prime it.  If there is no starred 
		//zero in the row containing this primed zero, Go to Step 5.
		//Otherwise, cover this row and uncover the column containing
		//the starred zero. Continue in this manner until there are no 
		//uncovered zeros left. Save the smallest uncovered value and Go to Step 6
		int step;
		bool done=false; 
		while (!done){ 
			cout<<"aRow = "<<aRow;
			find_a_zero(); 
			cout<<", and after find_a_zero() aRow = "<<aRow<<endl;
			if (aRow==0) { 
				done=true; 
				step = 6;
			}
			else {
				M[aRow][aCol]=2; 
				if (starInRow(aRow)) { 
					aCol = findStarInRow(aRow); 
					R_cov[aRow]=1; 
					C_cov[aCol]=0; 
				}
				else {
					done=true; 
					Z0_r=aRow; 
					Z0_c=aCol; 
					step= 5; 
				} 				
			}
			return step;
		}
		//TODO: this shouldnt be here (return 6) ??
		cout<< "Step 4 returning 6 from a place where we shouldnt be?"<<endl;;
		return 6;
	}

	int step5(int stepnum){
		//Construct a series of alternating primed and starred zeros 
		//as follows.  Let Z0 represent the uncovered primed zero 
		//found in Step 4.  Let Z1 denote the starred zero in the 
		//column of Z0 (if any). Let Z2 denote the primed zero in 
		//the row of Z1 (there will always be one).  Continue 
		//until the series terminates at a primed zero that has
		//no starred zero in its column.  Unstar each starred zero 
		//of the series, star each primed zero of the series, erase 
		//all primes and uncover every line in the matrix. 
		int count=0;
		bool done=false;
		int r=0;
		int c=0;
		path[count][0]=Z0_r;
		path[count][1]=Z0_c;
		while (!done) {
			r=findStarInCol(path[count][1],r);
			if (r>0) {
				count++;
				path[count][0]=r;
				path[count][1]=path[count-1][1];
			}
			else{
				done=true;
			}
			if (!done) {
				c=findPrimeInRow(path[count][0],c);
				count++;
				path[count][0]=path[count-1][1];
				path[count][1]=c;
			}
		}
		convertPath(count, path);
		clearCovers();
		erasePrimes();
		return 3;
	}

	int step6(int stepnum){
		//Add the value found in Step 4 to every element of each covered
		//row, and subtract it from every element of each uncovered column.
		//Return to Step 4 without altering any stars, primes, or covered lines.
		minval = find_smallest(); 
		for (int i= 0; i < rows; i++) { 
			  for (int j = 0; j<columns;j++) {
				if (R_cov[i]==1) { 
					C[i][j]=C[i][j]+minval; 
				} 
				if (C_cov[j]==0) {
					C[i][j]=C[i][j]-minval; 
				} 
			  } 
		} 
		stepnum=4; 
		return stepnum;
	}

	float find_smallest()
	{
		float min;
		min=minvalOld; 
		for (int i= 0; i < rows; i++) { 
			for (int j = 0; j<columns;j++) {
				 if (R_cov[i]==0 && C_cov[j]==0){
					   if (min>C[i][j] ){ 
						min=C[i][j]; 
					   }
				 }
			}
		}
		minvalOld=min;
		return min;
	}

	int findStarInCol(int c, int r){ 
		r=0; 
		for (int i = 0; i<n; i++) { 
			if (M[i][c]==1){ 
				r=i; 
			} 
		}
		return r;
	}

	int findPrimeInRow (int r, int c) {
		for (int j = 0;j<=n;j++) {
			if (M[r][j]==2) {
				c=j;
			}
		}
		return c;
	}
	void convertPath (int count, int** path) {
		for (int i = 0; i < count; i++) {
			if (M[path[i][0]][path[i][1]]==1) {
				M[path[i][0]][path[i][1]]=0;
			}
			else {
				M[path[i][0]][path[i][1]]=1;
			}
		}
		return;
	}

	void clearCovers () {
		for (int i = 0; i < n; i++ ) {
			R_cov[i]=0;
			C_cov[i]=0;
		}
		return;
	}

	void erasePrimes () {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (M[i][j]==2) {
					M[i][j]=0;
				}
			}
		}
		return;
	}

	void find_a_zero() { 
		int i=0; 
		int j;
		bool done=false;
		aRow=0; 
		aCol=0; 
		while (!done) { 
			j=0; 
			while (j<rows){ 
				if ((C[i][j]==0) && (R_cov[i]==false) && (C_cov[j]==false)) { 
					aRow=i; 
					cout << "aRow changed to "<<i;
					aCol=j; 
					done=true; 
				}
				j++; 
			}
			i++; 
			if (i==rows ){
				done=true;
			}
		}	
		return;
	}
	//never used
	bool starInRow(int aRow) {
		bool tbool = false;
		for (int j = 0;j<rows;j++) {
			if (M[aRow][j]==1) {
				tbool = true;
			}
		}
		return tbool;
	}

	int findStarInRow (int aRow) {
		aCol=0;
		for (int j = 0; j < rows; j++) {
			if ( M[aRow][j]==1) {
				aCol=j;
			}
		}
		return aCol;
	}

	void printArray(float** anArray, int ro, int co, string arrayName) {
		cout<<"Printing "<<arrayName<<"["<<ro<<","<<co<<"]"<<endl;
		for (int i = 0; i<ro; i++ ) {
			for (int j = 0; j<co; j++ ){ 
				cout<<anArray[i][j]<<"\t";
			}	
			cout<<endl;
		}
	}
	void printArray(int** anArray, int ro, int co, string arrayName) {
		cout<<"Printing "<<arrayName<<"["<<ro<<","<<co<<"]"<<endl;
		for (int i = 0; i<ro; i++ ) {
			for (int j = 0; j<co; j++ ){ 
				cout<<anArray[i][j]<<"\t";
			}	
			cout<<endl;
		}
	}

};


void printArray(float** anArray, int ro, int co, string arrayName) {
	cout<<"Outside Munkres - Printing "<<arrayName<<"["<<ro<<","<<co<<"]"<<endl;
	for (int i = 0; i<ro; i++ ) {
		for (int j = 0; j<co; j++ ){ 
			cout<<anArray[i][j]<<"\t";
		}	
		cout<<endl;
	}
}

	int main () {
		cout<<"Init"<<endl;
		float ** A;
		A= new float* [4]; 
		for (int i=0; i<4; i++){
			A[i]= new float [4]; 
		}
		A[0][0] = 1.0f;
		A[0][1] = 2.0f;
		A[0][2] = 3.0f;
		A[0][3] = 4.0f;
		A[1][0] = 2.0f;
		A[1][1] = 4.0f;
		A[1][2] = 6.0f;
		A[1][3] = 8.0f;
		A[2][0] = 3.0f;
		A[2][1] = 6.0f;
		A[2][2] = 9.0f;
		A[2][3] = 12.0f;
		A[3][0] = 4.0f;
		A[3][1] = 8.0f;
		A[3][2] = 12.0f;
		A[3][3] = 16.0f;
		printArray(A, 4,4, "A");
		Munkrees* newMunkrees = new Munkrees(4, 4, A);
		cout<<"Done..."<<endl;
		printArray(A, 4,4, "A");
		//printArray(A, 4,4);
}

[bstdnator]

please help
i need this for one of my masters projects

[bstdnator]

Just wondering, is there anything glaringly wrong with my post? not one reply, im sad now
between steps 4 and 6 output follows:
Printing C[4,4]
0 0 1 2
0 1 3 5
0 2 5 8
0 3 7 11
Printing M[4,4]
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Printing path[4,4]
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
aRow = 0aRow changed to 0, and after find_a_zero() aRow = 0
Step4--------------------------------------------------
Printing C[4,4]
0 0 1 2
0 1 3 5
0 2 5 8
0 3 7 11
Printing M[4,4]
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Printing path[4,4]
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Step6--------------------------------------------------
<repeat>

to expain, C is the original cost matrix which has been modified by steps 1,2,3 and 4. see http://csclab.murray...45/munkres.html for a description of how. M is the chosen optimum assignment and i have no idea what path shows. as as you can see it has not yet been used for anything. From above website i found this

Quote

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.

now im sat here scratching my head thinking huh? so i fix that how??
please someone who likes a challenge, help me out.

[bstdnator]

please help me

[Cerolobo]

Interesting algorithm. I'll take a look...

[Cerolobo]

Just a quick heads up. I know there is a issue in Step 4. Namely, you are not priming the Zeros.

[Cerolobo]

Fix number 1:
in step4(), change

if (aRow==0) { 

to
if(aRow == -1) {

Then go to find_a_zero(), and initialize aRow to -1.

With the way the Ada code is written, you will get that infinate loop if the chosen row it row 0.

[Cerolobo]

Note: I'm am not 100% certain that these corrections are actually correct. I HIGHLY recommend you test them out, if you do implement them.

Fix number 1:
in step4()

initialize step to 6

change

if (aRow==0) {
to
if(aRow == -1) {

Then go to find_a_zero(), and initialize aRow to -1.

Fix number 2:
in step3()

if(M[i][j]==1 )

to

if(C[i][j] == 0)

Fix number 3:
I completely rewrote step5(), based on this comment

"Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix."

to this

int step5(int stepnum)
{
  int r;
  int c;

  for(r = 0; r < rows; ++r)
	for(c = 0; c < columns; ++c)
	  switch(M[r][c])
	  {
		case 0:
		  break;

		case 1:
		  M[r][c] = 0;  // unstar a star
		  break;

		case 2:
		  M[r][c] = 1; // convert a prime to a star
		  break;
	  }

  clearCovers();

  return 3;
}

This was the most straight forward method I could think of to do what the above quote wanted you to do.

The path variable was used in here; however, I wasn't quite sure what it was actually being used for...

Fix number 4:
in find_smallest()

initilze min to something really large (I used 99999). When this function was called, it would pick up a 0 every now and then. When this happened, minvalOld would then become 0. The caused each sequential call to find_smallest() to return 0.




I tested it on the main you provided, the matrix on the site you posted, and on the matrixes in this pdf

http://www.ams.jhu.e...s/hungarian.pdf

It did generate the correct coefficient matrix in all the above cases.

Again, I HIGHLY recommend you test this out, before accepting them a true corrections.

Edit: Added the disclaimer at the top and bottom.

This post has been edited by Cerolobo: 08 April 2008 - 09:59 PM

[bstdnator]

Ohh fantastic, thank you so much
i havent had a chance to try it yet but i wanted to say thanks
i'll give it a go now and report back how it pans out.

Again, Thank You, you have saved my bacon.

[bstdnator]

Cerolobo, on 8 Apr, 2008 - 09:15 PM, said:

Fix number 1:
in step4()
initialize step to 6

int step = 6;
this is causing an endless loop between 4 and 6 so i left this out, could be because of another error elsewhere

Cerolobo, on 8 Apr, 2008 - 09:15 PM, said:

change
if (aRow==0) {
to
if(aRow == -1) {

ok done

Cerolobo, on 8 Apr, 2008 - 09:15 PM, said:

Then go to find_a_zero(), and initialize aRow to -1.

by this do you mean call find_a_zero method or inside the body for find_a_zero at the top set aRow = -1
i am assuming the second

Cerolobo, on 8 Apr, 2008 - 09:15 PM, said:

Fix number 2:
in step3()
if(M[i][j]==1 )
to
if(C[i][j] == 0)

ok that was a simple change

Cerolobo, on 8 Apr, 2008 - 09:15 PM, said:

Fix number 3:
I completely rewrote step5(), ...<cut>

ok i copied &pasted your changes, much neater code than before, its readable ! lol

Cerolobo, on 8 Apr, 2008 - 09:15 PM, said:

Fix number 4:
initialize min to something really large (I used 99999).

i was using 999.0f but bigger wont hurt so i changed that also
int find_smallest() << my find_smallest is returning a float but the procedure is identical im sure.

with all of those changes you suggested (including initialise step to 6 inside step 4) i am getting an endless loop between steps 4 and 6.
without initialising step to 6 at the beginning of step 4, i am getting the following output at the end of the program;
I've taken out all of the printArray() statements for readability...

Outside Munkres - Printing A[4,4]
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16

Step1--------------------------------------------------
Step2--------------------------------------------------
Step3--------------------------------------------------
Step4--------------------------------------------------
Step6--------------------------------------------------
Step4--------------------------------------------------
Step=Done--------------------------------------------------
Printing C[4,4]
0 0 1 2
0 1 3 5
0 2 5 8
0 3 7 11
Printing M[4,4]
1 2 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Printing path[4,4]
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Done...
Outside Munkres - Printing M[4,4]
1 2 0 0
0 0 0 0
0 0 0 0
0 0 0 0

not sure what you've done differently to me but sadly the matrix M is not in a finished assignment format.
Also i had no idea the original code was in Ada, i've never before seen Ada in my life hehe just the only format i could find the algorithm in.

Thank you again for your help so far Cerolobo.

my full code as it stands after those changes follows...

#include <iostream>
#include <String>
using namespace std;

class Munkrees {
public:
	float** C;
	int** M;
	int** path;

private:	
	int *row;
	int *col;
	bool *C_cov;
	bool *R_cov;
	int aRow;
	int aCol;
	int Z0_r; 
	int Z0_c;
	float minval;//should be right
	float minvalOld;
	int n;//todo remove n so algn works for rectangular arrays properly
public:
	int rows;
	int columns;
	Munkrees(int inRows,int inColumns, float** matrix) {
		//aRow=0;
		//aCol=0;
		rows = inRows;
		columns = inColumns;
 //	   cout<<"rows = "<<rows<<", columns = "<<columns<<endl;
		if(!rows==columns) {
			cout<<"rows!=columns - Algorithm undetermined"<<endl;
		}
		else {
			n=rows;
		}
  //	  cout<<"init"<<endl;
		cout<<endl;
 //	   cout<<"rows = "<<rows<<", columns = "<<columns<<endl;
 //	   printArray(matrix, rows, columns, "matrix");
//		cout<<"rows = "<<rows<<", columns = "<<columns<<endl;
		C= new float* [rows]; 
		for (int i=0; i<rows; i++){
			C[i]= new float [columns]; 
		}
		for (int i = 0; i<rows;i++) { 
			for (int j = 0; j<columns; j++ ) {
				C[i][j] = matrix[i][j];
			}
		}

   //	 printArray(C, rows,columns,"C");

		C_cov = new bool[columns];
		for (int i = 0; i<columns;i++) {
			C_cov[i] = false;
		}
		R_cov = new bool[rows];
		for (int i = 0; i<rows;i++) {
			R_cov[i] = false;
		}
		M = new int* [rows]; 
		for (int i=0; i<rows; i++){
			M[i]= new int [columns]; 
		}
		for (int i = 0; i<rows;i++) {
			for (int j = 0; j<columns;j++) {
				M[i][j] = 0;
			}
		}

  //	  printArray(M, 4,4,"M");

		path = new int* [rows];
		for (int i=0; i<rows; i++){
			path[i]= new int [columns]; 
		}
		for (int i = 0; i<rows;i++) {
			for (int j = 0; j<columns;j++) {
				path[i][j] = 0;
			}
		}

  //	  printArray(path, 4,4,"path");

		row = new int[rows];
		col = new int[columns];
		int stepnum=1;
		int aRow=0;
		int aCol=0;
		int Z0_r=0; 
		int Z0_c=0;
		minval=9999999;//should be right
		minvalOld=minval;//used in step6
		bool done=false;
		int* returnVal = new int[2];
 //	   cout<<"End Init!"<<endl;
		while (!done) {
			switch(stepnum){
				case 1:
					stepnum=step1(stepnum);
					cout<<"Step1--------------------------------------------------"<<endl;
	   //			 printArray(C, 4,4,"C");
	 //			   printArray(M, 4,4,"M");
   //				 printArray(path, 4,4,"path");
					break;
				case 2:
					stepnum=step2(stepnum);
					cout<<"Step2--------------------------------------------------"<<endl;
	  //			  printArray(C, 4,4,"C");
	//				printArray(M, 4,4,"M");
  //				  printArray(path, 4,4,"path");
					break;
				case 3:
					stepnum=step3(stepnum);
					cout<<"Step3--------------------------------------------------"<<endl;
	 //			   printArray(C, 4,4,"C");
   //				 printArray(M, 4,4,"M");
 //				   printArray(path, 4,4,"path");
					break;
				case 4:
					stepnum=step4(stepnum);
					cout<<"Step4--------------------------------------------------"<<endl;
		  //		  printArray(C, 4,4,"C");
		//			printArray(M, 4,4,"M");
	  //			  printArray(path, 4,4,"path");
					break;
				case 5:
					stepnum=step5(stepnum);
					cout<<"Step5--------------------------------------------------"<<endl;
		//			printArray(C, 4,4,"C");
	  //			  printArray(M, 4,4,"M");
	//				printArray(path, 4,4,"path");
					break;
				case 6:
					stepnum=step6(stepnum);
					cout<<"Step6--------------------------------------------------"<<endl;
	//				printArray(C, 4,4,"C");
	  //			  printArray(M, 4,4,"M");
		//			printArray(path, 4,4,"path");
					break;
				default:
					done=true;
					cout<<"Step=Done--------------------------------------------------"<<endl;
					printArray(C, 4,4,"C");
					printArray(M, 4,4,"M");
					printArray(path, 4,4,"path");
					break;
			}
		}
  //	  cout<<"Printing M"<<endl;
		for (int i = 0; i<rows;i++) {
			for (int j = 0; j<columns; j++ ) {
				matrix[i][j] = (float)M[i][j];
	//			cout << M[i][j]<<"\t";
			}
  //		  cout<<endl;
		}
		delete C;
		delete M;
		delete path;
	}
private:
	int step1(int stepnum){
		//For each row of the matrix, find the smallest element and
		//subtract it from every element in its row.  Go to Step 2
		for (int i = 0; i < n; i++) {
			minval=C[i][0]; 
			for(int j = 0; j < n; j++) {
				if (minval>C[i][j]) {
					minval=C[i][j]; 
				}
			} 
			for (int j = 0; j < n; j++) {
				C[i][j] =C[i][j]-minval; 
			} 
		}
		return 2;
	}

	int step2(int stepnum){
		//Find a zero (Z) in the resulting matrix.  If there is no starred
		//zero in its row or column, star Z. Repeat for each element in the
		//matrix. Go to Step 3. 
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < columns; j++) {
				if ( C[i][j]==0 && C_cov[j]==0 && R_cov[i]==0 ){
					M[i][j]=1; 
					C_cov[j]=1; 
					R_cov[i]=1; 
				}
			}
		}
		for (int i = 0; i<n; i++) {//TODO: this line will fail for non square matricies
			C_cov[i]=0; 
			R_cov[i]=0; 
		}
		return 3;
	}

	int step3(int stepnum){
		//Cover each column containing a starred zero. 
		//If K columns are covered, the starred zeros describe a 
		//complete set of unique assignments. In this case, Go to DONE
		//otherwise, Go to Step 4. 
		int count; 
		for (int i = 0; i<rows; i++) {
			for (int j = 0; j<columns; j++){ 
				if (C[i][j]==0 ) {
					C_cov[j]=1; 
				} 
			}
		}
		count=0; 
		for (int j = 0; j<rows; j++){ 
			count=count + C_cov[j]; 
		}
		if (count>=rows) {
			//we're done here
			return 7;
		}
		else {
			return 4;
		}
	}

	int step4(int stepnum){
		//Find a noncovered zero and prime it.  If there is no starred 
		//zero in the row containing this primed zero, Go to Step 5.
		//Otherwise, cover this row and uncover the column containing
		//the starred zero. Continue in this manner until there are no 
		//uncovered zeros left. Save the smallest uncovered value and Go to Step 6
		//int step=6;
		int step;
		bool done=false; 
		while (!done){ 
   //		 cout<<"aRow = "<<aRow;
			find_a_zero(); 
  //		  cout<<", and after find_a_zero() aRow = "<<aRow<<endl;
			if (aRow==-1) { 
				done=true; 
				step = 6;
			}
			else {
				M[aRow][aCol]=2; 
				if (starInRow(aRow)) { 
					aCol = findStarInRow(aRow); 
					R_cov[aRow]=1; 
					C_cov[aCol]=0; 
				}
				else {
					done=true; 
					Z0_r=aRow; 
					Z0_c=aCol; 
					step= 5; 
				}				 
			}
			return step;
		}
		//TODO: this shouldnt be here (return 6) ??
		cout<< "Step 4 returning 6 from a place where we shouldnt be?"<<endl;;
		return 6;
	}

	int step5(int stepnum){
		//Construct a series of alternating primed and starred zeros 
		//as follows.  Let Z0 represent the uncovered primed zero 
		//found in Step 4.  Let Z1 denote the starred zero in the 
		//column of Z0 (if any). Let Z2 denote the primed zero in 
		//the row of Z1 (there will always be one).  Continue 
		//until the series terminates at a primed zero that has
		//no starred zero in its column.  Unstar each starred zero 
		//of the series, star each primed zero of the series, erase 
		//all primes and uncover every line in the matrix. 

		int r;
		int c;

		for(r = 0; r < rows; ++r)
			for(c = 0; c < columns; ++c)
				switch(M[r][c])
			{
				case 0:
					break;

				case 1:
					M[r][c] = 0;  // unstar a star
					break;

				case 2:
					M[r][c] = 1; // convert a prime to a star
					break;
			}

			clearCovers();
			return 3;
	}

	int step6(int stepnum){
		//Add the value found in Step 4 to every element of each covered
		//row, and subtract it from every element of each uncovered column.
		//Return to Step 4 without altering any stars, primes, or covered lines.
		minval = find_smallest(); 
		for (int i= 0; i < rows; i++) { 
			  for (int j = 0; j<columns;j++) {
				if (R_cov[i]==1) { 
					C[i][j]=C[i][j]+minval; 
				} 
				if (C_cov[j]==0) {
					C[i][j]=C[i][j]-minval; 
				} 
			  } 
		} 
		stepnum=4; 
		return stepnum;
	}

	float find_smallest()
	{
		float min;
		min=minvalOld; 
		for (int i= 0; i < rows; i++) { 
			for (int j = 0; j<columns;j++) {
				 if (R_cov[i]==0 && C_cov[j]==0){
					   if (min>C[i][j] ){ 
						min=C[i][j]; 
					   }
				 }
			}
		}
		minvalOld=min;
		return min;
	}

	int findStarInCol(int c, int r){ 
		r=0; 
		for (int i = 0; i<n; i++) { 
			if (M[i][c]==1){ 
				r=i; 
			} 
		}
		return r;
	}

	int findPrimeInRow (int r, int c) {
		for (int j = 0;j<=n;j++) {
			if (M[r][j]==2) {
				c=j;
			}
		}
		return c;
	}
	void convertPath (int count, int** path) {
		for (int i = 0; i < count; i++) {
			if (M[path[i][0]][path[i][1]]==1) {
				M[path[i][0]][path[i][1]]=0;
			}
			else {
				M[path[i][0]][path[i][1]]=1;
			}
		}
		return;
	}

	void clearCovers () {
		for (int i = 0; i < n; i++ ) {
			R_cov[i]=0;
			C_cov[i]=0;
		}
		return;
	}

	void erasePrimes () {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (M[i][j]==2) {
					M[i][j]=0;
				}
			}
		}
		return;
	}

	void find_a_zero() { 
		int i=0; 
		int j;
		bool done=false;
		aRow=-1; 
		aCol=0; 
		while (!done) { 
			j=0; 
			while (j<rows){ 
				if ((C[i][j]==0) && (R_cov[i]==false) && (C_cov[j]==false)) { 
					aRow=i; 
   //				 cout << "aRow changed to "<<i;
					aCol=j; 
					done=true; 
				}
				j++; 
			}
			i++; 
			if (i==rows ){
				done=true;
			}
		}	
		return;
	}
	//never used
	bool starInRow(int aRow) {
		bool tbool = false;
		for (int j = 0;j<rows;j++) {
			if (M[aRow][j]==1) {
				tbool = true;
			}
		}
		return tbool;
	}

	int findStarInRow (int aRow) {
		aCol=0;
		for (int j = 0; j < rows; j++) {
			if ( M[aRow][j]==1) {
				aCol=j;
			}
		}
		return aCol;
	}

	void printArray(float** anArray, int ro, int co, string arrayName) {
		cout<<"Printing "<<arrayName<<"["<<ro<<","<<co<<"]"<<endl;
		for (int i = 0; i<ro; i++ ) {
			for (int j = 0; j<co; j++ ){ 
				cout<<anArray[i][j]<<"\t";
			}	
			cout<<endl;
		}
	}
	void printArray(int** anArray, int ro, int co, string arrayName) {
		cout<<"Printing "<<arrayName<<"["<<ro<<","<<co<<"]"<<endl;
		for (int i = 0; i<ro; i++ ) {
			for (int j = 0; j<co; j++ ){ 
				cout<<anArray[i][j]<<"\t";
			}	
			cout<<endl;
		}
	}

};


void printArray(float** anArray, int ro, int co, string arrayName) {
	cout<<"Outside Munkres - Printing "<<arrayName<<"["<<ro<<","<<co<<"]"<<endl;
	for (int i = 0; i<ro; i++ ) {
		for (int j = 0; j<co; j++ ){ 
			cout<<anArray[i][j]<<"\t";
		}	
		cout<<endl;
	}
}

	int main () {
  //	  cout<<"Init"<<endl;
		float ** A;
		A= new float* [4]; 
		for (int i=0; i<4; i++){
			A[i]= new float [4]; 
		}
		A[0][0] = 1.0f;
		A[0][1] = 2.0f;
		A[0][2] = 3.0f;
		A[0][3] = 4.0f;
		A[1][0] = 2.0f;
		A[1][1] = 4.0f;
		A[1][2] = 6.0f;
		A[1][3] = 8.0f;
		A[2][0] = 3.0f;
		A[2][1] = 6.0f;
		A[2][2] = 9.0f;
		A[2][3] = 12.0f;
		A[3][0] = 4.0f;
		A[3][1] = 8.0f;
		A[3][2] = 12.0f;
		A[3][3] = 16.0f;
		printArray(A, 4,4, "A");
		Munkrees* newMunkrees = new Munkrees(4, 4, A);
		cout<<"Done..."<<endl;
		printArray(A, 4,4, "M");
		cout<<"press any key to continue..."<<endl;
		char c;
		cin>>c;
		//printArray(A, 4,4);
}

[Cerolobo]

Related to Fix 1:
in step4(), step needs to be initialized to 6.

Basically, when you call find_a_zero(), initializing aRow to -1, tells you if a uncovered 0 was found. IE, if a uncovered zero was found, aRow will not equal -1 when you return to step4().

This is why you needed to change

if (aRow==0) {
to
if(aRow == -1) {

So, useing your main(), the first time step4() is called, it will scan you matrix, and not find any uncovered zero (column 1 is all 0s, and it was covered in step3()).

This will cause aRow to be -1, which causes the above if statement to be true, sending you to step 6.

In step 6, you basically make a new 0, and then return back to step 4.

This time, find_a_zero() will return aRow = 1, since (1, 0) (row major) is a 0 and not covered.

This will cause this part of the if statment to execuate

if (starInRow(aRow)) {
	aCol = findStarInRow(aRow);
	R_cov[aRow]=1;
	C_cov[aCol]=0;
}

At this point, step is equal to garbage ("random" data left in the space that step occupies). This is where you program jumps to the "Done" step. What you want, is for step6() to be re run, so that's why you need to initialize step to 6, or you can set it to 6 in the above if statement.

Related to Fix number 4:
You still have the same issue. The issue is with

min=minvalOld;

So, following the part directly above "Related to Fix number 4:"

find_smallest() will search your matrix and find a 0 (what you want). At the end of the function, you set

minvalOld=min;

IE, minvalOld = 0;

So, the next time you call find_smallest(),

min=minvalOld;

is invoked, and you end up with min == 0. So, you enter a endless loop of you subtracting 0 from everything, and then searching for the 0 you were supposed to have generated.

That's why you need to initilize min to something other then minvalOld, such as minval.

[Cerolobo]

Quick correction, you should not initilize
min=minval;

in find_smallest(), since you overwrite minval in step6(). hard codeing 999.0f or something similar should work.

[bstdnator]

Cerolobo, on 9 Apr, 2008 - 07:11 AM, said:

So, the next time you call find_smallest(),

min=minvalOld;

is invoked, and you end up with min == 0. So, you enter a endless loop of you subtracting 0 from everything, and then searching for the 0 you were supposed to have generated.

That's why you need to initilize min to something other then minvalOld, such as minval.

come here so i can kiss you, thank you so much

[Cerolobo]

I hope you read my last post. Namely,

"Quick correction, you should not initilize
min=minval;

in find_smallest(), since you overwrite minval in step6(). hard codeing 999.0f or something similar should work."

I didn't notice you were overwriting minval until a few minutes after I suggested it...

[bstdnator]

Cerolobo, on 9 Apr, 2008 - 07:36 AM, said:

I hope you read my last post. Namely,

"Quick correction, you should not initilize
min=minval;

in find_smallest(), since you overwrite minval in step6(). hard codeing 999.0f or something similar should work."

I didn't notice you were overwriting minval until a few minutes after I suggested it...

Nope, but from what you had written about the endless loop i figured it out and hardcoded it as you later suggested
thank you veyr much for your help

Out of curiosity, how long did it take you to get it working?