Latest Tutorials| Questions and Answers|Ask Questions?|Site Map



Home Answers Viewqa Java-Beginners please help me in a java program !!

Have Programming Question? Ask it here!
 
 
 


omar
please help me in a java program !!
0 Answer(s)      4 years and 7 months ago
Posted in : Java Beginners


the porgram should use kosaraju's algorithm to detect the strong connected components in a graph (http://en.wikipedia.org/wiki/Kosaraju_algorithm)
there are 4 classes in my program : Vertex , StackX, Graph , DFSApp
"DFSApp is the one from which i modify the graph and run the program"
i still need to modify the method kosaraju in the class Graph such that the program works ...
here are the classes
class Vertex
{
public char label; // label (e.g. 'A')
public boolean wasVisited;
// ------------------------------------------------------------
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// ------------------------------------------------------------
} // end class Vertex
class StackX
{
private final int SIZE = 8;
private int[] st;
private int top;
// ------------------------------------------------------------
public StackX() // constructor
{
st = new int[SIZE]; // make array
top = -1;
}
// ------------------------------------------------------------
public void push(int j) // put item on stack
{ st[++top] = j; }
// ------------------------------------------------------------
public int pop() // take item off stack
{ return st[top--]; }
// ------------------------------------------------------------
public int peek() // peek at top of stack
{ return st[top]; }
// ------------------------------------------------------------
public boolean isEmpty() // true if nothing on stack
{ return (top == -1); }
// ------------------------------------------------------------
} // end class StackX
class Graph
{
public final int MAX_VERTS = 8;
public Vertex vertexList[]; // list of vertices
public int adjMat[][]; // adjacency matrix
public int nVerts; // current number of vertices
public StackX theStack;
// ------------------------------------------------------------
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int y=0; y<MAX_VERTS; y++) // set adjacency
for(int x=0; x<MAX_VERTS; x++) // matrix to 0
adjMat[x][y] = 0;
theStack = new StackX();
} // end constructor
// ------------------------------------------------------------
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
// ------------------------------------------------------------
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;

}
// ------------------------------------------------------------
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
// ------------------------------------------------------------
public void dfs(int b) // depth-first search
{ // begin at vertex 0
vertexList[b].wasVisited = true; // mark it
displayVertex(b); // display it
theStack.push(b); // push it

while( !theStack.isEmpty() ) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex( theStack.peek() );
if(v == -1) // if no such vertex,
theStack.pop();
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
} // end while

// stack is empty, so we're done
for(int j=0; j<nVerts; j++) // reset flags
vertexList[j].wasVisited = false;
} // end dfs
// ------------------------------------------------------------
// returns an unvisited vertex adj to v
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;
} // end getAdjUnvisitedVertex()
// ------------------------------------------------------------



public void reverseGraph(Graph G){

int[][]L=new int[MAX_VERTS][MAX_VERTS];


for(int h = 0; h < MAX_VERTS; h++)
{
for(int i = 0; i < MAX_VERTS; i++)
{
L[i][h] = G.adjMat[h][i];
}
}
G.adjMat=L;


}

//End reverseGraph

public void Kosaraju(Graph G){
StackX S = new StackX();
G.dfs(0);

while(!theStack.isEmpty()){S.push(theStack.peek());theStack.pop();}

G.reverseGraph(G);
G.dfs(S.pop());


}
}
// end class Graph
class DFSApp
{


public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start for dfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('F'); // 5
theGraph.addVertex('G'); //6
theGraph.addVertex('H'); //7


theGraph.addEdge(0,1); // AB
theGraph.addEdge(1,3); // BD
theGraph.addEdge(3,0); //DA
theGraph.addEdge(3,6); //DG
theGraph.addEdge(6,7); // GH
theGraph.addEdge(7,2); //HC
theGraph.addEdge(2,6); //CG
theGraph.addEdge(4,2); //EC
theGraph.addEdge(4,5); //EF
theGraph.addEdge(5,4); //FE
theGraph.addEdge(0,5); //AF






// theGraph.reverseGraph(theGraph);
// System.out.print("Visits: ");
// theGraph.dfs(0);
// System.out.println();
// depth-first search


theGraph.Kosaraju(theGraph);


for (int i=0;i<theGraph.MAX_VERTS;i++){
for (int j=0;j<theGraph.MAX_VERTS;j++){
System.out.print(theGraph.adjMat[i][j]);

}}


}// end main()
} // end class DFSApp

Advertisement
View Answers

Related Tutorials/Questions & Answers:
 

 

 

DMCA.com