Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Connectivity Problem
public class MainClass {
public static void main(String args[]){
String sampleData = "1-2,2-3,3-4,9-0,0-9,2-4,5-6,9-0,8-9,9-8,1-9,1-3,1-10,10-13,11-12,12-15,15-19,19-22,20-22,21-20,18-20,1-20,1-19,1-9,20-21,21-22,22-0,1-22,9-20,9-23,19-8,2-18,7-21,2-21,21-3";
// String sampleData2 = "3-4,4-9,8-0,2-3,5-6,2-9,5-9,7-3,4-8,5-6,0-2,6-1,6-1,0-2,5-6,4-8,7-3,5-9,2-9,5-6,2-3,8-0,4-9,3-4";
// String sampleData3 = "3-4,4-9,8-0,2-3,5-6,2-9,5-9,7-3,4-8,5-6,0-2,6-1,3-4,4-9,8-0,2-3,5-6,0-2,5-9,7-3,4-8,5-6,2-9,6-1,3-4,4-9,8-0,2-3,5-6,2-9,5-9,7-3,4-8,5-6,0-2,6-1";
ProblemMatrix matrix = new ProblemMatrix(new boolean[50][50]);
matrix.setUpMatrix();
String[] pairs = sampleData.split(",");
for(String pair : pairs){
String[] pairSplit = pair.split("-");
int rowNumber = Integer.parseInt(pairSplit[0]);
int columnNumber = Integer.parseInt(pairSplit[1]);
matrix.checkConnectivity(rowNumber,columnNumber);
}
}
}
public class ProblemMatrix {
private boolean[][] matrix;
private int lastVisited; //to avoid infinite loops
public ProblemMatrix(boolean [][] matrix){
this.matrix = matrix;
}
public boolean[][] getMatrix(){
return this.matrix;
}
public void updateMatrix(int row, int column, boolean tf){
this.matrix[row][column] = tf;
}
public void setUpMatrix(){
for (int i = 0; i < this.matrix.length; i++) {
for (int j = 0; j < this.matrix[0].length; j++) {
if (i == j) { //for similar indexes
matrix[i][j] = true;
} else {
matrix[i][j] = false;
}
}
}
}
public void checkConnectivity(int row, int column){
if(this.matrix[row][column] && this.matrix[column][row]){
System.out.print("--" + " ");
}else{
if(checkTransitivity(row, column)){
System.out.print("--" + " ");
}else{
updateMatrix(row,column,true);
updateMatrix(column,row,true);
System.out.print(row + "-" + column + " ");
}
lastVisited = row;
}
}
private boolean checkTransitivity(int row, int column){
// if(row == 1 && column == 19) System.out.println("start - "+lastVisited);
// if(column == 19) System.out.println(row + " " + lastVisited);
//base case
if(this.matrix[row][column]){
return true;
}else{
//go over the row
for(int i = 0; i < this.matrix[row].length; i++){
if(this.matrix[row][i] && i != row && i != lastVisited){
lastVisited = row;
return checkTransitivity(i, column); //column is your target
}
}
}
return false;
}
}
@MohamadAtieh

This comment has been minimized.

Copy link
Owner Author

MohamadAtieh commented Jan 8, 2015

The commented sample data in MainClass work fine, except for the one being used.

The problem occurs when a visited node no longer has neighbors and returns false.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.