This is my implemintation of Munske's Algorithm. The problem is that it locks up around step 4 or 5, but I can't figure out why.
Code:
// Brad Galloway
// CSC 445 - Programming Assignment 4
// Munkre's Algorithm
#include<iostream>
#include<iomanip>
#include<fstream>
#include<string>
#include<climits>
using namespace std;
int const MAX_SIZE = 20; // size of matricies
int n; // the number of rows and columns the actual
// matrix has
int cost_matrix[MAX_SIZE][MAX_SIZE];// The cost matrix
int mask_matrix[MAX_SIZE][MAX_SIZE];// the mask matrix
int C_cover[MAX_SIZE]; // Array of column covers
int R_cover[MAX_SIZE]; // Array of row covers
int stepnum; // the step number
bool done; // Keeps track if the main program is done
int row = 0;
int col = 0;
int z0_r, z0_c;
int counter;
int path[MAX_SIZE][MAX_SIZE];
char outFilename[11] = "output.txt";
void read_file(char file[]){
ifstream inFile( file );
if(!inFile)
{
cerr << "File could not be opened. \n";
exit( 1 );
}
inFile >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
inFile >> cost_matrix[i][j];
for(int x = 0; x < n; x++){
C_cover[x] = 0;
R_cover[x] = 0;
}
}
void out_matrix(){
ofstream outFile( outFilename );
for(int x = 0; x < n; x++)
{
for(int y = 0; y < n; y++){
cout << setw(3);
outFile << setw(3);
if(mask_matrix[x][y] == 1){
cout << "*";
outFile << "*";
}
else if(mask_matrix[x][y] == 2){
cout << "'";
outFile << "'";
}
else if(C_cover[y] == 1 || R_cover[x] == 1){
cout << "X";
outFile << "X";
}
else{
cout << cost_matrix[x][y];
outFile << cost_matrix[x][y];
}
}
cout << "\n";
}
cout << "\n";
}
void find_a_zero(int &r, int &c){
int i = 1;
int j;
bool over = false;
while(!over){
j = 1;
while( j <= n ){
if(cost_matrix[i][j] == 0 && R_cover[i] == 0 && C_cover[j] == 0)
{
r = i;
c = j;
over = true;
}
j += 1;
}
if( i > n ){
over = true;
}
}
}
bool star_in_row(int r){
bool tbool = false;
for(int j = 0; j < n; j++){
if(mask_matrix[r][j] == 1){
tbool = true;
}
}
return tbool;
}
void find_star_in_row(int &r, int &c){
c = 0;
for(int j = 0; j < n; j++){
if(mask_matrix[r][j] == 1){
c = j;
}
}
}
void find_star_in_col(int c, int &r){
r = 0;
for(int i = 0; i < n; i++){
if(mask_matrix[i][c] == 1){
r = i;
}
}
}
void find_prime_in_row(int r, int &c){
for(int j = 0; j < n; j++){
if(mask_matrix[r][j] == 2){
c = j;
}
}
}
void convert_path(){
for(int i = 0; i < counter; counter++){
if(mask_matrix[path[i][1]][path[i][2]] == 1){
mask_matrix[path[i][1]][path[i][2]]=0;
}
else{
mask_matrix[path[i][1]][path[i][2]]=1;
}
}
}
void clear_covers(){
for(int i = 0; i < n; i++){
R_cover[i] = 0;
C_cover[i] = 0;
}
}
void erase_primes(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(mask_matrix[i][j] == 2){
mask_matrix[i][j] = 0;
}
}
}
}
void find_smallest(int minval){
minval = numeric_limits<int>::max();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(R_cover[i] == 0 && C_cover[j] == 0){
if(minval > cost_matrix[i][j]){
minval = cost_matrix[i][j];
}
}
}
}
}
void step_one(){
cout << "\nStep One\n";
int minval;
for(int i = 0; i < n; i++){
minval = cost_matrix[i][1];
for(int j = 0; j < n; j++){
if(minval > cost_matrix[i][j])
minval = cost_matrix[i][j];
}
for(int k = 0; k < n; k++)
cost_matrix[i][k] = cost_matrix[i][k] - minval;
}
out_matrix();
stepnum = 2;
}
void step_two(){
cout << "\nStep Two\n";
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(cost_matrix[i][j] == 0 && C_cover[j] == 0 && R_cover[i] == 0){
mask_matrix[i][j] = 1;
C_cover[j] = 1;
R_cover[i] = 1;
}
}
}
cout << "\nMask Matrix\n";
for(int x = 0; x < n; x++){
for(int y = 0; y < n; y++)
cout << setw(3) << mask_matrix[x][y];
cout << "\n";
}
cout << "\n";
out_matrix();
for(int x = 0; x < n; x++){
C_cover[x] = 0;
R_cover[x] = 0;
}
cout << "\nAfter Step Two\n";
out_matrix();
stepnum = 3;
}
void step_three(){
cout << "\nStep Three\n";
int counter = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(mask_matrix[i][j] == 1)
C_cover[j] = 1;
}
}
out_matrix();
for(int x = 0; x < n; x++)
counter += C_cover[x];
if(counter >= n)
stepnum = 7;
else
stepnum = 4;
}
void step_four(){
bool thru = false;
cout <<"\nStep Four\n";
while(!thru){
find_a_zero(row, col);
if(row == 0){
thru = true;
stepnum = 6;
}
else{
mask_matrix[row][col] = 2;
if(star_in_row(row)){
find_star_in_row(row, col);
R_cover[row] = 1;
C_cover[col] = 0;
}
else{
thru = true;
stepnum = 5;
z0_r = row;
z0_c = col;
}
}
}
out_matrix();
}
void step_five(){
cout << "\nStep Five\n";
counter = 1;
path[counter][1] = z0_r;
path[counter][2] = z0_c;
int r;
int c;
bool quit = false;
while(!quit){
find_star_in_col(path[counter][2], r);
if(r > 0){
counter += 1;
path[counter][1] = r;
path[counter][2] = path[counter-1][2];
}
else{
quit = true;
}
if(!quit){
find_prime_in_row(path[counter][1], c);
counter += 1;
path[counter][1] = path[counter-1][1];
path[counter][2] = c;
}
}
convert_path();
clear_covers();
erase_primes();
stepnum = 3;
out_matrix();
}
void step_six(){
cout << "\nStep six\n";
int minval;
find_smallest(minval);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(R_cover[i] == 1){
cost_matrix[i][j] = cost_matrix[i][j]-minval;
}
if(C_cover[j] == 0){
cost_matrix[i][j] = cost_matrix[i][j]-minval;
}
}
}
out_matrix();
stepnum = 4;
}
void finished(){
done = true;
}
int main(){
char filename[25];
char answer;
bool do_another = true;
while(do_another){
done = false;
stepnum = 1;
cout << "Enter filename containing cost matrix: ";
cin >> filename;
cout << endl;
read_file(filename);
out_matrix();
while(!done){
switch( stepnum ) {
case 1: step_one();
case 2: step_two();
case 3: step_three();
case 4: step_four();
case 5: step_five();
case 6: step_six();
default: finished();
break;
}
}
cout << "Would you like to do another file?(y or n): ";
cin >> answer;
if(answer == 'n' || 'N'){
do_another = false;
}
}
return 0;
}
Munske's Algorithm
Linear Mode
