2
\$\begingroup\$

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.

Network Topologies

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());
}
\$\endgroup\$
  • \$\begingroup\$ Asking for alternative solutions isn't in the spirit of Code Review, and may also violate homework ethics. I've reworded your question. \$\endgroup\$ – 200_success Sep 29 '16 at 3:06
  • \$\begingroup\$ @200_success: While I agree with you there, the solution I have already works and fulfills the requirements of the assignment. Hence I could turn it in as is for full credit. Asking for alternate solutions doesn't impede this assignment as I already have the solution. It actually increases my learning because it shows me alternative means of solving the same problem. \$\endgroup\$ – Trojan404 Sep 29 '16 at 3:58
  • \$\begingroup\$ We also don't explicitly want alternative solutions, as it may just attract code snippet answers. \$\endgroup\$ – Jamal Sep 29 '16 at 6:29
  • \$\begingroup\$ @Jamal: If it does, then they aren't an answer. A question should not be held accountable for poor answers. I've explicitly stated that the point of this question is learn of alternate ways to accomplish the same method. If you think this is counterproductive, then delete question or place it on hold. \$\endgroup\$ – Trojan404 Sep 29 '16 at 14:05
  • \$\begingroup\$ Just a word of warning in the academic honesty department: if one of your classmates finds this solution, copies it and submits this as their own, you may be on the hook under your school's policy. \$\endgroup\$ – Joe C Sep 30 '16 at 21:23
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ See? It's never supposed to be easy. Easy just means you missed something. I've fixed isRing(). As for isStar(), would the best solution to that be to use a lookup table and then double back and check to make sure all limbs link to the center index? Or do you think since the question is asking about adjacency matrices we can assume that it is referencing digraphs? \$\endgroup\$ – Trojan404 Sep 28 '16 at 23:47
  • \$\begingroup\$ Your last suggestion about checking this.matrix[row][row] != false doesn't really make sense. Can you explain it further? Currently every test I run has the false count output correctly without that check. The only reason I have that check on the third one is that fully connected meshes cannot connect to themselves. Therefore, that value must be false. \$\endgroup\$ – Trojan404 Sep 29 '16 at 2:37
  • \$\begingroup\$ @Trojan404 For example, suppose you start with the star graph in the picture. But then you remove edge 1->2 and add edge 1->1. The falseCount for vertex one will be 1 still, even though the graph isn't a star any more. \$\endgroup\$ – JS1 Sep 29 '16 at 3:11
  • \$\begingroup\$ I see what you're talking about there, and that problem gets addressed by placing the row results into a lookup table and cross-referencing that on the center for validation. \$\endgroup\$ – Trojan404 Sep 29 '16 at 4:04
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks! Hope there's no hard feelings about how I responded, I just want to learn more and make sure that in the future I do things as efficiently as possible. \$\endgroup\$ – Trojan404 Sep 29 '16 at 4:37
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.