Biconnected Graphs in java

Networking/Security Forums -> Programming and More

Author: sifi PostPosted: Sun May 08, 2005 1:50 am    Post subject: Biconnected Graphs in java
    ----
hi folks im doing an assignment here an im really stuck! Sad

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

Author: sifi PostPosted: Sun May 08, 2005 7:15 am    Post subject:
    ----
ok new algorithm

better question.. i think Very Happy

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;


      }
      return biCon;

   }

Author: brynoLocation: Texas PostPosted: Mon May 23, 2005 2:08 pm    Post subject:
    ----
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:

http://courses.dce.harvard.edu/~cscie160/Clone.htm

Author: sifi PostPosted: Wed May 25, 2005 12:21 pm    Post subject:
    ----
thanks Very Happy

actually there are a few problems with the code i posted, ive rectified them now and everything works!

i think



Networking/Security Forums -> Programming and More


output generated using printer-friendly topic mod, All times are GMT + 2 Hours

Page 1 of 1

Powered by phpBB 2.0.x © 2001 phpBB Group