I'm working on an assignment for class where I have to read an adjacency matrix and output the bipartite matches in Java. I've been given two methods to fill out to accomplish this, and I've managed to get it working for one use case, but I'm having some trouble making it work for the other two. I will paste my source code below. There are 3 test cases at the beginning of the program with the expected output of each shown at the end.
I need to implement the matrix as a 2D character array. The problem I'm having seems to be with the backtracking portion of it. The second test case returns the correct result. If someone could help me understand what I'm doing wrong I would greatly appreciate it. My process for finding matches is:
Traverse the matrix, display matches
public class BiPartiteMatch
{
// **************** main ****************
public static void main(String[] args)
{
System.out.println("Case 1: No matching exists. \n");
// a b c d e No matching A, C, E
// ----------------------- will only take a & d
char [][]M = { /*E*/ {'y', 'n', 'n', 'y', 'n'},
/*D*/ {'n', 'y', 'n', 'y', 'n'},
/*C*/ {'y', 'n', 'n', 'y', 'n'},
/*B*/ {'y', 'n', 'y', 'y', 'y'},
/*A*/ {'y', 'n', 'n', 'y', 'n'} };
System.out.println("Case 2: Matching with no backtracking needed. \n");
// a b c d e Matching with no
// ----------------------- backtracking needed
char [][]M = { /*E*/ {'y', 'n', 'n', 'y', 'y'},
/*D*/ {'n', 'y', 'n', 'y', 'n'},
/*C*/ {'n', 'y', 'y', 'n', 'n'},
/*B*/ {'y', 'n', 'y', 'n', 'n'},
/*A*/ {'n', 'y', 'n', 'n', 'y'} };
System.out.println("Case 3: Matching with backtracking. \n");
// a b c d e Matching with
// ----------------------- backtracking
char [][]M = { /*E*/ {'n', 'y', 'n', 'n', 'y'},
/*D*/ {'y', 'n', 'y', 'n', 'n'},
/*C*/ {'n', 'y', 'y', 'n', 'n'},
/*B*/ {'n', 'y', 'n', 'y', 'n'},
/*A*/ {'y', 'n', 'n', 'y', 'y'} };
if (findMatch(M, M.length-1)) // Find matches starting with the last row
displayMatches(M);
else
System.out.println("There is no matching.");
}// end main
// **************** recursive findMatch ****************
public static boolean findMatch(char [][]M, int myRow)
{
if(myRow < 0)
return false;
for(int c = 0; c < M.length; c++)
{
if(M[myRow][c] == 'y' && !isTaken(M, myRow, c))
{
M[myRow][c] = 't';
break;
}
}
findMatch(M, myRow-1);
return true;
}// end findMatch
// **************** isTaken ******************
// *******is this column already taken? ********
public static boolean isTaken(char [][]M, int row_Im_In, int col_Im_In)
{
for(int r = row_Im_In+1; r < M.length; r++)
{
if(M[r][col_Im_In] == 't')
return true;
}
return false;
}// end isTaken
// **************** displayMatches ****************
public static void displayMatches(char [][]M)
{
final char []MatchFrom = {'E', 'D', 'C', 'B', 'A'};
final char []MatchTo = {'a', 'b', 'c', 'd', 'e'};
for(int r = M.length-1; r > -1; r--)
{
for(int c = 0; c < M.length; c++)
{
if(M[r][c] == 't')
{
System.out.println(MatchFrom[r] + " matches to " + MatchTo[c]);
}
}
}
}// end displayMatches
}// end class declaration
Expected Results:
Case 1: No mathing exists.
There is no matching.
Case 2: Matching with no backtracking needed.
A matches to b
B matches to a
C matches to c
D matches to d
E matches to e
Case 3: Matching with backtracking.
A matches to a
B matches to d
C matches to b
D matches to c
E matches to e
You need to replace findMatch with something like this:
public static boolean findMatch(char [][]M, int myRow)
{
if(myRow < 0)
return true;
for(int c = 0; c < M.length; c++)
{
if(M[myRow][c] == 'y' && !isTaken(M, myRow, c))
{
M[myRow][c] = 't';
if (findMatch(M, myRow-1))
return true;
M[myRow][c] = 'y';
}
}
return false;
}
at the moment, your code will only attempt to find the first possible match for each element.
To do proper backtracking you need to call the recursive function from inside the loop, then if it fails to find a complete match you need to test the next position.