Share on Google+Share on Google+

omar
please help me in a java program !!
0 Answer(s)      7 years 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

Ads

View Answers









Related Tutorials/Questions & Answers:
Tutorials   
Java Spring Hibernate Struts Training What does core Java include? java What are some way to learn Java quickly? Is it required to learn Java before learning Java Script? Is it necessary to learn java script before learning PHP? Are HTML5 and Java Script boosts Java career? Is Java object oriented? Fingerprint application with Java Uninstall Oracle Virtual Box JSON to HashMap Free Java online Training I want example of Control Statement in Java ANSI Color Codes with Python Create a Program that Calculates Input What is difference between JDK,JRE and JVM? How to see ubuntu version on server? How to get Page Source in Selenium (WebDriver) using Java? The path to the driver executable must be set by the webdriver.gecko.driver system property parse data from a link in java Java Program Qns using BlueJ How to fix HAX Kernel Module Is Not Installed error? Installing Audacity Looking for code Logic to check track changes & Coments in MSWord, MSWordx, MSExcel, MSExcelx is ON/OFF Installing JDK on Mac SAX Parser exception ERROR 601 (42P00): Syntax error. Encountered Thread java.lang.NoClassDefFoundError: org/apache/commons/fileupload/FileItemFactory How to install Ubuntu 16.04 LTS? HttpServletRequest cannot be resolved to a type in eclipse - Solved Unhandled event loop exception GC overhead limit exceeded Spring Data jpa with apache phoenix Caused by: java.lang.IllegalArgumentException: Not a host:port pair: PBUF o.a.h.h.z.RecoverableZooKeeper - Possibly transient ZooKeeper, quorum= com.thinkaurelius.titan.diskstorage.hbase.HBaseStoreManager class not found com.thinkaurelius.titan.diskstorage.hbase.HBaseStoreManager not found How to download and install Java 8 on Windows? How to uninstall JDK 7? How to install gtk-doc-tools package in Ubuntu? How to install Oracle JDK 8 on Ubuntu? ejabberd_ctl.beam not found - Solved How to convert date to UTC format in Java? How to install autoconf, automake and libtool in Ubuntu 15.10? How to convert current date to mm dd yyyy format in Java? How to convert current date to dd mm yyyy format in Java? How to stop window closing in "internalFrameClosing" event. How to find list of all index in Neo4j? neo4j-server.properties file location SASLError using PLAIN: not-authorized how to convert war file into .exe file using java code

Ads

 
Advertisement null

Ads