DepthFirst Class

The DepthFirst class is a GraphAlgorithm extension that illustrates a recursive backtracking depth first search/traversal of a graph. This class uses two stacks to maintain the current state of the search. The stack of edges is used as is typical for nonrecursive implementations. The stack of vertices is used to keep track of the backtracking that would normally occur with recursive implementations.

package GraphStuff;

import java.util.*;
import MyUtil.*;

public final class DepthFirst extends GraphAlgorithm {

   private Stack estk, vstk;

   private boolean deliveredCannotFinish;

   private int orgC,treeC,curC,lookC,VCount;

   private Vertex v[], V, s;

   private Edge e[], E;

   private boolean p_completedInit=false;

   public int GraphType() {return GraphPanel.Simple;}

   public String title() {
     return  "Depth First Search/Traversal - directed";
   }

   static public final String failedInit = "Error: Cannot Initialize\n";

   static public final String noEdges = 
   "This network has no edges, so there are no paths.\n";

   static public final String noVertices = 
   "This network has no vertices, so there are no paths.\n";

   static public final String ready = 
   "Select a start vertex and press step to continue.\n";

   static public final String description =
   "This algorithm performs a depth-first traversal of a directed graph.  The "
   +"traversal will of \n"
   +"course fail if no path exists from the initial vertex to any other vertex "
   +"in the graph.\n";

   static public final String cannotFinish = 
   "Since we have visited every accessible vertex but have not visited all "
   +"vertices,\n"+" there are no paths to some vertices from `";

   public boolean showLabels() {return true;}

   public String init (GraphPanel gP) {
      if (gP==null)
         return failedInit;
      Graph g = gP.graph;
      if (g==null)
         return failedInit;
      if (g.numVertices()==0)
         return noVertices;
      if (g.numEdges()==0)
         return noEdges;
      deliveredCannotFinish=false;
      if (estk==null)
         estk=new Stack();
      else while (!estk.isEmpty()) estk.pop();
      if (vstk==null)
         vstk=new Stack();
      else while (!vstk.isEmpty()) vstk.pop();
      v = g.vertices();
      lookC=1+(curC=1+(treeC=1+(orgC=g.uncolor())));
      VCount=0;
      p_completedInit=true;
      return description + ready;
   }

   public String step(GraphPanel gP) {
      if (gP==null)
         return failedInit;
      Graph g = gP.graph;
      if (g==null || !p_completedInit)
         return failedInit;
      if (g.numVertices()==0)
         return noVertices;
      if (g.numEdges()==0)
         return noEdges;
      if (VCount>v.length || deliveredCannotFinish)
         return null;          // already finished, or delivered cannotFinish 
      if (VCount==0) {
         V=null;
         for(int i=0;i<v.length && V==null;i++) {
            if (v[i].beenSelected()) {
               V=v[i];
               V.beenSelected(false);
               break;
            }
         }
         if (V==null)
            V=v[0];
         VCount++;
         V.colorNum(curC);
         e=V.outEdges();
         if (e!=null) {
            for(int i=0;i<e.length;i++)
               estk.push(e[i]);
         }
         s=V;
         return "We begin at vertex `"+s.vName()+"'";
      } else {
        if (estk.isEmpty()) {
           if (vstk.isEmpty()) {
             if (VCount==v.length) {
                V.colorNum(treeC);
                VCount++;
                return "Now we have visited every vertex.";
             } else {
                V.colorNum(treeC);
                deliveredCannotFinish=true;;
                return cannotFinish + s.vName() + "'";
             }
           } else {
              Vertex oldV=V;
              V.colorNum(treeC);
              V=(Vertex)(vstk.pop());
              V.colorNum(curC);
              if (oldV.outDegree()==0)
                 return "Since `"+oldV.vName()+"' has no out-adjacent vertices,\n"
                        +"we backtrack to vertex `"+V.vName()+"'.";
              return "We have visited all out-adjacent vertices from `"
                    +oldV.vName() +"',\n"+"so we backtrack to vertex `"
                    +V.vName()+"'.";          
           }
        }
        E=(Edge)(estk.pop());
        if (E.U()!=V) {
           estk.push(E);
           Vertex oldV=V;
           V.colorNum(treeC);
           V=(Vertex)(vstk.pop());
           V.colorNum(curC);
           if (oldV.outDegree()==0)
              return "Since `"+oldV.vName()+"' has no out-adjacent vertices,\n"
                     +"we backtrack to vertex `"+V.vName()+"'.";
           return "We have visited all out-adjacent vertices from `"
                 +oldV.vName() +"',\n"
                 +"so we backtrack to vertex `"+V.vName()+"'.";
        }
        if (E.V().colorNum()==orgC) {
           VCount++;
           e=E.V().outEdges();
           if (e!=null)
              for(int i=0;i<e.length;i++)
                 estk.push(e[i]);
           V.colorNum(treeC);
           E.V().colorNum(curC);
           E.colorNum(treeC);
           String ret = "In considering vertices out-adjacent to `"+V.vName()
                       +"',\n"+"we move to vertex `"+E.V().vName()+"'.";
           vstk.push(V);
           V=E.V();
           return ret;
        } else {
           E.colorNum(lookC);
           return "In considering vertices out-adjacent to `"+V.vName()
                  +"',\n"+"we note that vertex `"+E.V().vName()
                  +"' has already been visited.";
        }
      }
   }
}