Write a java program that will use warshalls algorithm to compute the transitive

Question

Write a java program that will use warshalls algorithm to compute the transitive closure of a given relation. the input to the program is a file cotaining the relation (the size of the of the matrix is at the top), and the output must be a file containing the transitive closure of the given relation.

for example:

4   

0 1 0 0

1 0 0 1

0 1 0 0

0 0 0 0 is inputted

4

1 1 0 1

1 1 0 1

1 1 0 1

0 0 0 0 is outputted

the pseudocode for warshalls algorithm is:

input:relation R on a set of n elements

output: transitive closure R*

A=M[R]

for (k=1 to n)

{

for (i = 1 to n)

for (j=1 to n)

B[i][j] = A[i][j] OR (A[i][j] AND A[k][j])

for (i=1 to n)

for(j=1 to n)

A[i][j] = B [i][j]

}

return A

Explanation / Answer

Program:

package warsall;

public class Graph {

final static int V = 4; //Number of vertices in a graph

// Prints transitive closure of graph[][] using Floyd Warshall algorithm

void transitiveClosure(int graph[][])

{

int reach[][] = new int[V][V];

int i, j, k;

for (i = 0; i < V; i++)

for (j = 0; j < V; j++)

reach[i][j] = graph[i][j];

for (k = 0; k < V; k++)

{  

for (i = 0; i < V; i++)

{  

for (j = 0; j < V; j++)

{

reach[i][j] = (reach[i][j]!=0) ||

((reach[i][k]!=0) && (reach[k][j]!=0))?1:0;

}

}

}

// Print the shortest distance matrix

printSolution(reach);

}

/* A utility function to print solution */

void printSolution(int reach[][])

{

System.out.println("Following matrix is transitive closure"+

" of the given graph");

for (int i = 0; i < V; i++)

{

for (int j = 0; j < V; j++)

System.out.print(reach[i][j]+" ");

System.out.println();

}

}

// Driver program to test above function

public static void main (String[] args)

{

int graph[][] = new int[][]{ {0, 1, 0, 0},{1, 0, 0, 1},{0, 1, 0, 0},{0, 0, 0, 0}};

Graph g = new Graph();

g.transitiveClosure(graph);

}

}

Output:

Following matrix is transitive closure of the given graph
1 1 0 1
1 1 0 1
1 1 0 1
0 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.