Posted: Sun May 08, 2005 1:50 am Post subject: Biconnected Graphs in java
hi folks im doing an assignment here an im really stuck!
ive got this method that returns a boolean determining wheather a graph object is biconnected or not
biconnected: means there is no articulation(or cutoff) point where if it was removed the graph will not be connected anymore. like a vital bottleneck
DFS: depth first search traversal
can you tell me what im doing wrong, if you can see it please?
this is my method
Code:
public static boolean isBiconnected(Graph G){
int n=G.order(); // number or vertices
boolean biCon = true; // is G biconnected?
//Arrays needed for DFS
int preOrder[] = new int[n];
int postOrder[] = new int[n];
int low[] = new int[n]; //this stores info when a back arc is discovered
//Call DFS on G
GraphAlgs.DFS(G, 0, preOrder, postOrder);
//Compare the timestamps
for (int i=0;i<n;i++){
low[i]=preOrder[i];
for (int j=0;j<n;j++){
low[i]=Math.min(low[i],preOrder[j]);
if (low[j]<preOrder[i])
low[i]=Math.min(low[i],low[j]);
else if (low[j]>=preOrder[i]) { //found articulation point, set boolean and break
biCon = false;
break;
}
}
}
//a back arc
//(preOrder[i]<preOrder[j]&& postOrder[j]<postOrder[i])
return biCon;
}
<edit> ive done some work on paper as to why biCon is always false when this is called but i still cannot see it
why doesnt the Gbak object overwrite G in the for loop?
it removes the vertices in both G and Gbak and i cant see how Gbak is modified, it's assigned outside the loop?
the commented out lines can only make this algorithm work otherwise it throws out an ArrayOutOfBounds
Code:
public static boolean isBiconnected(Graph G){
int n=G.order();
int preOrder[] = new int[n];
int postOrder[] = new int[n];
boolean biCon = true;
Graph Gbak = G;
for (int i=0;i<n;i++){
GraphAlgs.DFS(G, 0, preOrder, postOrder);
G.removeVertex(i);
//n=n-1;
// preOrder = new int[n];
//postOrder = new int[n];
G = Gbak;
if (GraphAlgs.isConnected(G))
biCon=true;
else
biCon=false;
This is a Java "problem". Class variables in Java are references. Once you set GBak to G, you now have 2 variables that reference the same object. Anything you do go GBak will affect the object that G references. In order to make a copy and set it to GBak, you'd need to implement the Cloneable interface in your Graph class and call the clone() method. Check out this link, perhaps it can help:
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
