Need help with Java program! Implement Warshall\'s Algorithm to the code provide
ID: 3914629 • Letter: N
Question
Need help with Java program!
Implement Warshall's Algorithm to the code provided to find the transitive closure for a graph. Use the graph below to test the code.
--------------------------------------------------------------------------
class StackX
{
private final int SIZE = 20;
private int[] st;
private int top;
public StackX()
{
st = new int[SIZE];
top = -1;
}
public void push(int j)
{ st[++top] = j; }
public int pop()
{ return st[top--]; }
public int peek()
{ return st[top]; }
public boolean isEmpty()
{ return (top == -1); }
}
class Vertex
{
public char label;
public boolean wasVisited;
public Vertex(char lab)
{
label = lab;
wasVisited = false;
}
}
class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[];
private int adjMat[][];
private int nVerts;
private StackX theStack;
public Graph()
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int y=0; y<MAX_VERTS; y++)
for(int x=0; x<MAX_VERTS; x++)
adjMat[x][y] = 0;
theStack = new StackX();
}
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
public void dfs()
{
vertexList[0].wasVisited = true;
displayVertex(0);
theStack.push(0);
while( !theStack.isEmpty() )
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex( theStack.peek() );
if(v == -1)
theStack.pop();
else
{
vertexList[v].wasVisited = true;
displayVertex(v);
theStack.push(v);
}
}
for(int j=0; j<nVerts; j++)
vertexList[j].wasVisited = false;
}
public int getAdjUnvisitedVertex(int v)
{
for(int j=0; j<nVerts; j++)
if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
return j;
return -1;
}
}
class DFSApp
{
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A');
theGraph.addVertex('B');
theGraph.addVertex('C');
theGraph.addVertex('D');
theGraph.addVertex('E');
theGraph.addEdge(0, 1);
theGraph.addEdge(1, 2);
theGraph.addEdge(0, 3);
theGraph.addEdge(3, 4);
System.out.print("Visits: ");
theGraph.dfs();
System.out.println();
}
}
Explanation / Answer
Solution:
import java.util.Scanner;
public class Warshall_Algorithm
{
private int V;
private boolean[][] tc;
/** Function to make the transitive closure **/
public void getTC(int[][] graph)
{
this.V = graph.length;
tc = new boolean[V][V];
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
if (graph[i][j] != 0)
tc[i][j] = true;
tc[i][i] = true;
}
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (tc[j][i])
for (int k = 0; k < V; k++)
if (tc[j][i] && tc[i][k])
tc[j][k] = true;
}
}
}
/** Funtion to display the trasitive closure **/
public void displayTC()
{
System.out.println(" Transitive closure : ");
System.out.print(" ");
for (int v = 0; v < V; v++)
System.out.print(" " + v );
System.out.println();
for (int v = 0; v < V; v++)
{
System.out.print(v +" ");
for (int w = 0; w < V; w++)
{
if (tc[v][w])
System.out.print(" * ");
else
System.out.print(" ");
}
System.out.println();
}
} /** Main function **/
public static void main (String[] args)
{
Scanner scan = new Scanner(System.in);
/** Make an object of Warshall_Algorithm class **/
Warshall_Algorithm w = new Warshall_Algorithm();
/** Accept number of vertices **/
System.out.println("Enter number of vertices ");
int V = scan.nextInt();
/** get graph **/
System.out.println(" Enter matrix ");
int[][] graph = new int[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
graph[i][j] = scan.nextInt();
w.getTC(graph);
w.displayTC();
}
}
Output:
Enter number of vertices
7
Enter matrix
0 1 1 0 0 1 0
0 0 0 0 1 1 0
0 0 0 0 0 0 0
0 0 1 0 0 0 1
0 0 0 0 0 1 0
1 0 0 0 0 0 1
0 0 0 1 1 0 0
Transitive closure :
0 1 2 3 4 5 6
0 * * * * * * *
1 * * * * * * *
2 *
3 * * * * * * *
4 * * * * * * *
5 * * * * * * *
6 * * * * * * *