I need help with Part A and Part B In this project, you will use the Boolean mat
ID: 3869076 • Letter: I
Question
I need help with Part A and Part B
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.
Part B
Write a test program that uses BMat objects to do specified Boolean matrix calculations. The starting version of your program should be the sample file P4Test.java. Instance BMat objects for the matrices A, B, C, D, E, F, and G that are defined in P4Test . Using BMat methods, have your program calculate the following (X is an integer variable, and W is a work matrix):
a. W = (C' Ù (A Ú B)) Ù B' (M' = complement of M)
b. W = (BT B) Ù (C Ú CT)
c. W = C18 = C C ... C (18 C's)
d. W = (D Ú E)T Ù (DT Ú ET)
e. W = D1 Ú D2 Ú D3 Ú D4
f. X = maximum out-degree of all nodes in D
g. W = symmetric closure of D. Is D symmetric?
h. W = transitive closure of E. Is E transitive?
i. Show that matrix F represents a tree (has a candidate root node and has no cycles).
j. Show that matrix G does not represent a tree.
Turn in:
1. Source code for the functions you added to BMat.java.
2. Source code for your test program.
3. Output from the test program.
4. A drawing of the digraph for each of the Boolean matrices A, B, C, F, and G. Try to arrange the nodes so that the arrows cross each other as little as possible.
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
// Project #4 test program
public class P4Test
{
public static void main(String[] args)
{
// Boolean matrix definitions
int A[][] = new int[][]
{{1, 1, 0, 0, 1},
{1, 0, 1, 0, 0},
{0, 0, 0, 0, 0},
{1, 0, 0, 0, 0},
{0, 0, 1, 0, 1}};
int B[][] = new int[][]
{{0, 1, 0, 0, 1},
{0, 1, 1, 0, 0},
{1, 0, 1, 0, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 1}};
int C[][] = new int[][]
{{0, 1, 0, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 0},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0}};
int D[][] = new int[][]
{{1, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0},
{0, 1, 1, 1, 0, 0},
{0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 1}};
int E[][] = new int[][]
{{0, 1, 1, 0, 0, 1},
{0, 1, 1, 0, 0, 1},
{0, 0, 1, 0, 0, 1},
{0, 0, 0, 0, 1, 1},
{0, 0, 0, 1, 1, 1},
{0, 0, 0, 0, 0, 0}};
int F[][] = new int[][]
{{0, 0, 0, 0, 1, 0, 1, 0, 0},
{1, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}};
int G[][] = new int[][]
{{0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}};
BMat BMA = new BMat(A);
// Put code here...
} // end main
} // end class
Explanation / Answer
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
// Project #4 test program
public class P4Test
{
public static void main(String[] args)
{
// Boolean matrix definitions
int A[][] = new int[][]
{{1, 1, 0, 0, 1},
{1, 0, 1, 0, 0},
{0, 0, 0, 0, 0},
{1, 0, 0, 0, 0},
{0, 0, 1, 0, 1}};
int B[][] = new int[][]
{{0, 1, 0, 0, 1},
{0, 1, 1, 0, 0},
{1, 0, 1, 0, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 1}};
int C[][] = new int[][]
{{0, 1, 0, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 0},
{1, 0, 0, 0, 1},
{0, 1, 0, 0, 0}};
int D[][] = new int[][]
{{1, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0},
{0, 1, 1, 1, 0, 0},
{0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 1}};
int E[][] = new int[][]
{{0, 1, 1, 0, 0, 1},
{0, 1, 1, 0, 0, 1},
{0, 0, 1, 0, 0, 1},
{0, 0, 0, 0, 1, 1},
{0, 0, 0, 1, 1, 1},
{0, 0, 0, 0, 0, 0}};
int F[][] = new int[][]
{{0, 0, 0, 0, 1, 0, 1, 0, 0},
{1, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}};
int G[][] = new int[][]
{{0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0}};
BMat BMA = new BMat(A);
// Put code here...
} // end main
} // end class
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.