In this project, you will use the Boolean matrix representation of directed graphs to perform various operations on the digraphs and to examine special properties of the digraphs. A Boolean matrix class file BMat.java will be given to you. This class contains various functions (methods) that operate on Boolean matrices. You will write additional functions and put them into this class file.

Part A

Add the following functions to the BMat class:

1. BM1.outdegree(K) - Returns the out-degree for node K in Boolean matrix BM1. Assume that the nodes are numbered 0,1,2,...,SIZE-1.

2. BM1.meet(M2) - Returns the logical AND of matrices BM1 and BM2.

3. BM1.transpose() - Returns the transpose of matrix BM1.

4. BM1.product(M2) - Returns the Boolean product of matrices BM1 and BM2.

5. BM1.tclosure() - Returns the transitive closure of matrix BM1 (use Warshall's algorithm).

6. BM1.rootnode() - Returns the root node number (0 to SIZE-1) of BM1 if a candidate root node exists. Returns -1 if there is no root node. For a root node to exist, there must be exactly one node with in-degree 0. All other nodes must have in-degree 1.

****BMAT.JAVA***

// Boolean Matrix Class public class BMat { // Instance variables public int M[][]; public int SIZE;

// Boolean matrix constructors

public BMat(int s) { SIZE = s; M = new int[SIZE][SIZE]; // Fill M with zeros for(int r = 0; r < SIZE; r++){ for(int c = 0; c < SIZE; c++){ M[r][c] = 0; } } }

public BMat(int[][] B) { SIZE = B.length; M = new int[SIZE][SIZE]; // Copy matrix B values into M for(int r = 0; r < SIZE; r++){ for(int c = 0; c < SIZE; c++){ if(B[r][c] == 0) M[r][c] = 0; else M[r][c] = 1; } } }

// Boolean matrix methods

public void show() { // Display matrix for(int r = 0; r < SIZE; r++){ for(int c = 0; c < SIZE; c++){ System.out.print(" " + M[r][c]); } System.out.println(); } return; }

public boolean isEqual(BMat M2) { // Check if current matrix equals matrix M2 for(int r = 0; r < SIZE; r++){ for(int c = 0; c < SIZE; c++){ if(this.M[r][c] != M2.M[r][c]) return false; } } return true; }

public int trace() { // Sum of main diagonal values int diag = 0; for(int r = 0; r < SIZE; r++) diag = diag + M[r][r]; return diag; }

public int arrows() { // No. of 1's in matrix int narrows = 0; for(int r = 0; r < SIZE; r++){ for(int c = 0; c < SIZE; c++){ narrows = narrows + M[r][c]; } } return narrows; }

public int indegree(int K) { // Number of arrows INTO node K of digraph // Nodes are numbered 0,1,2,...,SIZE-1 int colsum = 0; for(int r = 0; r < SIZE; r++) colsum = colsum + M[r][K]; return colsum; }

public BMat complement() { // Logical NOT of current matrix BMat W1 = new BMat(SIZE); for(int r = 0; r < SIZE; r++){ for(int c = 0; c < SIZE; c++){ if(this.M[r][c] == 0) W1.M[r][c] = 1; else W1.M[r][c] = 0; } } return W1; }

public BMat join(BMat M2) { // Logical OR of current matrix with matrix M2 BMat W1 = new BMat(SIZE); for(int r = 0; r < SIZE; r++){ for(int c = 0; c < SIZE; c++){ W1.M[r][c] = this.M[r][c] | M2.M[r][c]; } } return W1; }

public BMat power(int N) { // Raise current matrix to Boolean Nth power (N >= 1) BMat W1 = new BMat(this.M); BMat W2 = new BMat(this.M); for(int k = 2; k <= N; k++){ W1 = W1.product(W2); } return W1; }

public BMat rclosure() { // Reflexive closure of current matrix BMat W1 = new BMat(this.M); // Put 1's on main diagonal for(int r = 0; r < SIZE; r++) W1.M[r][r] = 1; return W1; }

public BMat sclosure() { // Symmetric closure of current matrix BMat W1 = new BMat(this.M); BMat W2 = W1.transpose(); W1 = W1.join(W2); return W1; }

// ********************************* // Project #4 functions to add // *********************************

public int outdegree(int K) { // Number of arrows FROM node K of digraph // Nodes are numbered 0,1,2,...,SIZE-1 // Put code here...

}

public BMat meet(BMat M2) { // Logical AND of current matrix with matrix M2 // Put code here...

}

public BMat transpose() { // Transpose of current matrix // Put code here...

}

public BMat product(BMat M2) { // Boolean product of current matrix with matrix M2 // Put code here...

}

public BMat tclosure() { // Transitive closure of current matrix (Warshall's algorithm) // Put code here...

}

public int rootnode() { // Root node number (if any) of current matrix // Nodes are numbered 0,1,2,...,SIZE-1 // Put code here...

}

} // end class