Java Brute-Force Algorithms Homework

Question

I'm taking an algorithms class this semester and this homework seemed pretty easy. Easy usually means something is wrong. Not always, though. Through testing, this application successfully answered what was asked for by the professor. What I want to know is if there are any other solutions that fulfill the assignment from the professor based on the question from the book. Remember, it must be brute-force so there may be plenty of more efficient solutions, but they are irrelevant here. THIS HAS NOT BEEN GRADED YET.

Assignment from Professor

Do this as a Netbeans project. Create a class that can store a m x n matrix of boolean values. It should have a methods isaRing, isaStar and isaFullyConnectedMesh. Each method should examine the matrix and return true if the adjacency matrix represents a ring, star or fully connected mesh, respectively, and false if otherwise. The application should create the adjacency matrices for each of the 3 images in problem 5 and store them in objects of the class that you created. Then call all 3 methods on each object. The output should say that the ring is a ring, not a star and not a fully connected mesh, and likewise for the other two.

Base Question from the Book

A network topology specifies how computers, printers, and other devices are connected over a network. The figure below illustrates three common topologies of networks: the ring, the star, and the fully connected mesh.

You are given a boolean matrix A[0..n - 1, 0..n - 1], where n > 3, which is supposed to be the adjacency matrix of a graph modeling a network with one of these topologies. Your task is to determine which of these three topologies, if any, the matrix represents. Design a brute-force algorithm for this task and indicate its time efficiency class.

My Solution

My solution is divided into the main class and then a Matrix class that holds most of the logic. How'd I do?

Matrix

public class Matrix { private boolean[][] matrix; /** * Constructor * n x n matrix creation * * @param n */ public Matrix(int n) { this.matrix = new boolean[n][n]; this.setMatrixValue(); } /** * Constructor * n x m matrix creation * * @param n * @param m */ public Matrix(int n, int m) { this.matrix = new boolean[n][m]; this.setMatrixValue(); } /** * Constructor * matrix creation from a passed multidimensional array * * @param matrix */ public Matrix(boolean[][] matrix) { this.matrix = matrix; } /** * setMatrixValue * Instantiates the multidimensional array locations to randomly generated boolean values */ private void setMatrixValue() { if(this.matrix == null) { throw new IllegalStateException("Matrix is not defined."); } Random random = new Random(); for(int row = 0; row < this.matrix.length; row++) { for(int col = 0; col < this.matrix[0].length; col++) { this.matrix[row][col] = random.nextBoolean(); } } } /** * getMatrix * Getter for matrix * * @return */ public boolean[][] getMatrix() { return this.matrix; } /** * countRows * Returns the number of rows in the matrix * * @return */ public int countRows() { return this.matrix.length; } /** * countCols * Returns the number of columns in the matrix * * @return */ public int countCols() { return this.matrix[0].length; } /** * countFalseRow * Returns the number of false values within a provided row index * * @param row * @return */ private int countFalseRow(int row) { int count = 0; for(int col = 0; col < this.matrix[row].length; col++) { if(this.matrix[row][col] == false) { count++; } } return count; } /** * countFalseCol * Returns the number of false values within a provided column index * * @param col * @return */ private int countFalseCol(int col) { int count = 0; for(int row = 0; row < this.matrix.length; row++) { if(this.matrix[row][col] == false) { count++; } } return count; } /** * isRing * Checks whether the matrix is a Ring Topology * * @return */ public boolean isRing() { int row = 0; int col = 0; while(row < this.matrix.length && col < this.matrix[0].length) { int falseRowCount = countFalseRow(row); int falseColCount = countFalseCol(col); if(falseRowCount != this.matrix[0].length - 2) { return false; } if(falseColCount != this.matrix.length - 2) { return false; } row++; col++; } return true; } /** * isStar * Checks whether the matrix is a Star Topology * * @return */ public boolean isStar() { boolean center = false; int limbCount = 0; for(int row = 0; row < this.matrix.length; row++) { int falseCount = countFalseRow(row); if(falseCount == 1 && !center) { center = true; } else if(falseCount == this.matrix[0].length - 1 && limbCount < this.matrix[0].length - 1) { limbCount++; } else { return false; } } return true; } /** * isFullyConnectedMesh * Checks whether the matrix is a Fully Connected Mesh Topology * * @return */ public boolean isFullyConnectedMesh() { for(int row = 0; row < this.matrix.length; row++) { int falseCount = countFalseRow(row); if(falseCount != 1 || this.matrix[row][row] != false) { return false; } } return true; } } 

Main Class

public static void main(String[] args) { boolean[][] mdRing = { {false,true,false,false,false,true}, //1 - connects with 2 and 6 {true,false,true,false,false,false}, //2 - connects with 1 and 3 {false,true,false,true,false,false}, //3 - connects with 2 and 4 {false,false,true,false,true,false}, //4 - connects with 3 and 5 {false,false,false,true,false,true}, //5 - connects with 4 and 6 {true,false,false,false,true,false} //6 - connects with 1 and 5 }; boolean[][] mdStar = { {false,true,true,true,true,true}, //1 - connects with 2, 3, 4, 5, and 6 {true,false,false,false,false,false}, //2 - connects with 1 {true,false,false,false,false,false}, //3 - connects with 1 {true,false,false,false,false,false}, //4 - connects with 1 {true,false,false,false,false,false}, //5 - connects with 1 {true,false,false,false,false,false} //6 - connects with 1 }; boolean[][] mdFCM = { {false,true,true,true,true,true}, //1 - connects with 2, 3, 4, 5, and 6 {true,false,true,true,true,true}, //2 - connects with 1, 3, 4, 5, and 6 {true,true,false,true,true,true}, //3 - connects with 1, 2, 4, 5, and 6 {true,true,true,false,true,true}, //4 - connects with 1, 2, 3, 5, and 6 {true,true,true,true,false,true}, //5 - connects with 1, 2, 3, 4, and 6 {true,true,true,true,true,false} //6 - connects with 1, 2, 3, 4, and 5 }; //Matrices instantiation Matrix ring = new Matrix(mdRing); Matrix star = new Matrix(mdStar); Matrix fcm = new Matrix(mdFCM); //Topology checks System.out.println("True indicates that the matrix corresponds the the respective network topography."); System.out.println("\nChecking adjacency matrices for ring matrices..."); System.out.println("****Ring Matrix: " + ring.isRing()); System.out.println(" Star Matrix: " + star.isRing()); System.out.println(" Fully Connected Mesh Matrix: " + fcm.isRing()); System.out.println("\nChecking adjacency matrices for star matrices..."); System.out.println(" Ring Matrix: " + ring.isStar()); System.out.println("****Star Matrix: " + star.isStar()); System.out.println(" Fully Connected Mesh Matrix: " + fcm.isStar()); System.out.println("\nChecking adjacency matrices for fully connected mesh matrices..."); System.out.println(" Ring Matrix: " + ring.isFullyConnectedMesh()); System.out.println(" Star Matrix: " + star.isFullyConnectedMesh()); System.out.println("****Fully Connected Mesh Matrix: " + fcm.isFullyConnectedMesh()); } 

Answer 1

Bugs

Your isRing() function doesn't check that the whole graph is a single ring. If you had a graph with two disconnected rings, it would still return true.

Your isStar() function doesn't check that the limbs are connected to the center, only that they have one outgoing edge. If you construct a graph where the center connects outwards to all other vertices, but the other vertices connect to each other in a one-way ring, it would pass your test (although this graph would be have asymmetrical one-way edges).

For both cases, you probably need to check this.matrix[row][row] != false like you do with the third case. Otherwise your falseCount will be off by one.

Answer 2

Matrix class

The purpose of this class is to represent a graph, not to do operations like matrix multiplication. A better name might be AdjacencyMatrix (but read on for more thoughts on naming).

Note that only square matrices make sense. Therefore, I would avoid defining a Matrix(int, int) constructor. I would go even further and have Matrix(boolean[][]) validate that the matrix is square.

Furthermore, it looks like you are working with undirected graphs. Therefore, the matrix must be symmetric. (One axis represents inbound connections, the other represents outbound connections — and they must agree.) If you could get that validation out of the way in the constructor, then the topology examination algorithms wouldn't have to worry about both axes.

Note that your setMatrixValue() method disregards the square and symmetric limitations. The null check is a symptom of a problematic design that makes it possible to have a half-constructed object.

Alternative representation

In addition to the remarks above, consider a shift in terminology.

public class UndirectedGraph { public UndirectedGraph(boolean[][] adjacencyMatrix) { // Optional validation if (!isSymmetric(adjacencyMatrix)) { throw new IllegalArgumentException("Symmetric matrix required"); } this.matrix = adjacencyMatrix; } public static UndirectedGraph randomGraph(int nodeCount) { boolean[][] matrix = … … for (int i = 0; i < nodeCount; i++) { for (int j = i; j < nodeCount; j++) { matrix[i][j] = matrix[j][i] = random.nextBoolean(); } } return new UndirectedGraph(matrix); } private static boolean isSymmetric(boolean[][] matrix) { … } public int nodeCount() { return this.matrix.length; } public boolean hasEdge(int node1, int node2) { … } public int degree(int node) { … } } 

Then, your isRing() would translate to this:

 public boolean isRing() { for (int node = 0; node < nodeCount(); node++) { if (degree(node) != 2) { return false; } } return true; } 

Much more readable, isn't it? It would also be obvious that what you are verifying is that each node has degree 2 — a much less stringent condition than verifying that the entire graph is one ring.

Answer 3

I’ve found that I’ve used both of these answers. I didn’t want to give one person all the credit as both answers provided helpful insight. @JS1 helped me find a valid bug in my solution and solve it.

@200_success provided an excellent answer of alternative solutions. I completely understand the idea of separating the logic out of Matrix. I actually had an assignment a few weeks ago where I did this, I just pulled it inside this class for this assignment due to the reliance on access to the multidimensional array to calculate the topology check. That said, I don’t like calling the problem a topology check. I prefer to look at this as it is just an adjacency matrix. Unless it was called a topology, no one would know that this multidimensional array represents a network.

For that reason, it might be smarter to define the Matrix class and then a Topology class that holds the logic for isRing(), isStar(), and isFCM().

From here, I both agree and disagree with @200_success. I love the simplicity that he achieved, but I would probably go with the first suggested name of AdjacencyMatrix as UndirectedGraph is too specific in my opinion. This same problem could be solved using a DirectedGraph provided it was given the logic to check for it.

Having said this, both answers provide learning opportunities and helpful insights into my programming practices and I appreciate both of them and the time their authors took to write them. I’ll update this answer with any other insights or answers that I find helpful in the wait time to select this as the answer.