dfs.java

Java数据结构开发包

    * Stores the parent Vertex of another Vertex
    */
  private void setParent(Vertex v, Vertex par) {
    v.set(PARENT, par);
  }

   /**
    * Stores an index representing a DFS tree.
    */
  private void setTreeNumber(Vertex v, Integer treeNum) {
    v.set(TREE_NUMBER, treeNum);
  }

   /**
    * Called when a vertex's status changes.
    */
  private void mark(Vertex v, Object state) {
    v.set(VERTEX_STATUS, state);
  }

   /**
    * Marks an edge as traversed.
    */
  private void mark(Edge e, Object type) {
    e.set(EDGE_TYPE, type);
  }

  /**
   * Ensures that a given Edge is valid (i.e. incident on a given
   * Vertex v).
   */
  private void checkEdge(Edge e, Vertex v) {
    Vertex[] ends = graph_.endVertices(e);
    if ( !((ends[0] == v) || (ends[1] == v)) )
      throw new InvalidEdgeException("Edge "+e+" not incident on Vertex "+v);
  }

  /********************************************
   * PUBLIC IMPLEMENTATION-INDEPENDENT METHODS
   ********************************************/

  /**
   * Returns the "Start time" of a Vertex.
   * @param v - the Vertex to check.
   */
  public Integer startTime(Vertex v) {return (Integer)v.get(START_TIME);}
  
  /**
   * Returns the "Finish time" of a Vertex.
   * @param v - the Vertex to check.
   */
  public Integer finishTime(Vertex v) {return (Integer)v.get(FINISH_TIME);}

  /**
   * Retrieves the parent Vertex of a Vertex
   * @param v - the Vertex whose parent to find.
   */
  public Vertex parent(Vertex v) {
    return (Vertex)v.get(PARENT);
  }

  /**
   * Retrieves an index representing a connected DFS component. These
   * numbers start at 0 and are incremented after a component is
   * fully traversed. If a certain start Vertex is specified, it will
   * be the root of a DFS tree (defined be Vertices and Tree Edges)
   * with number 0.
   * @param v - the Vertex to check.
   */
  public Integer treeNumber(Vertex v) {
    return (Integer)v.get(TREE_NUMBER);
  }
  
  /**
   * Accesses the current status of the given Vertex. If the Vertex
   * has no status, <code>null</code> is returned.  
   * @param v - the Vertex to check.
   */
  public Object status(Vertex v) {
    if (v.has(VERTEX_STATUS))
      return v.get(VERTEX_STATUS);
    return null;
  }
  
  /**
   * Tests if a vertex has not been visited.
   * @param v - the Vertex to check.
   */
  public boolean isUnvisited(Vertex v) {
    if ((v.has(VERTEX_STATUS)) &&
	(v.get(VERTEX_STATUS) == UNVISITED))
      return true;
    return false;
  }

  /**
   * Tests if a vertex is being visited.
   * @param v - the Vertex to check.
   */
  public boolean isVisiting(Vertex v) {
    if ((v.has(VERTEX_STATUS)) &&
	(v.get(VERTEX_STATUS) == VISITING))
      return true;
    return false;
  }

  /**
   * Tests if a vertex has been visited.
   * @param v - the Vertex to check.
   */
  public boolean isVisited(Vertex v) {
    if ((v.has(VERTEX_STATUS)) &&
	(v.get(VERTEX_STATUS) == VISITED))
      return true;
    return false;
  }

  /**
   * Accesses the current type of the given Edge. If the Edge
   * has no type, <code>null</code> is returned.  
   * @param e - the Edge to check.
   */
  public Object type(Edge e) {
    if (e.has(EDGE_TYPE))
      return e.get(EDGE_TYPE);
    return null;
  }
 

  /**
   * Tests if an edge has been seen yet.
   * @param e - the Edge to check.
   */
  public boolean isUnseen(Edge e) {
    if ((e.has(EDGE_TYPE)) && 
	(e.get(EDGE_TYPE) == UNSEEN))
      return true;
    return false;
  }

  /**
   * Tests if an edge is a tree edge.
   * @param e - the Edge to check.
   */
  public boolean isTreeEdge(Edge e) {
    if ((e.has(EDGE_TYPE)) && 
	(e.get(EDGE_TYPE) == TREE_EDGE))
      return true;
    return false;
  }

  /**
   * Tests if an edge is a back edge.
   * @param e - the Edge to check.
   */
  public boolean isBackEdge(Edge e) {
    if ((e.has(EDGE_TYPE)) && 
	(e.get(EDGE_TYPE) == BACK_EDGE))
      return true;
    return false;
  }

  /**
   * Tests if an edge is a forward edge.
   * @param e - the Edge to check.
   */
  public boolean isForwardEdge(Edge e) {
    if ((e.has(EDGE_TYPE)) && 
	(e.get(EDGE_TYPE) == FORWARD_EDGE))
      return true;
    return false;
  }

  /**
   * Tests if an edge is a cross edge.
   * @param e - the Edge to check.
   */
  public boolean isCrossEdge(Edge e) {
    if ((e.has(EDGE_TYPE)) && 
	(e.get(EDGE_TYPE) == CROSS_EDGE))
      return true;
    return false;
  }

  /** 
    * Cleans up all decorations stored in the provided graph.  This
    * should be called after the user has completely finished
    * everything resulting from a single DFS execution.  
    */
  public void cleanup() {
    //remove all level numbers from the graph.
    VertexIterator vertices = graph_.vertices();
    while( vertices.hasNext() ) {
      Vertex currentVertex = vertices.nextVertex();
      //Test if the vertex is decorated, because if the graph is
      //functionally disconnected (i.e. interestingEdges isn't very
      //smart), all vertices may not be visited.
      if(currentVertex.has(VERTEX_STATUS))
	currentVertex.destroy(VERTEX_STATUS);

      if (currentVertex.has(PARENT))
	currentVertex.destroy(PARENT);

      if (currentVertex.has(START_TIME))
	currentVertex.destroy(START_TIME);

      if (currentVertex.has(FINISH_TIME))
	currentVertex.destroy(FINISH_TIME);

      if (currentVertex.has(TREE_NUMBER))
	currentVertex.destroy(TREE_NUMBER);
    }
    //remove all edge classifications from edges
    EdgeIterator edges = graph_.edges();
    while(edges.hasNext()) {
      Edge currentEdge = edges.nextEdge();
      //Test if the edge is decorated, because if the graph is
      //functionally disconnected (i.e. interestingEdges isn't very
      //smart), all vertices may not be visited.
      if(currentEdge.has(EDGE_TYPE))
	currentEdge.destroy(EDGE_TYPE);
    }  
  }

  /*************************************
   * IMPLEMENTATION-SPECIFIC METHODS
   *************************************/

   /**
    * Called when a vertex is visited.  Can be overridden by a subclass.
    */
  protected void startVisit(Vertex v) {}

   /**
    * Called when a discovery edge is traversed.  Can be overridden by a
    * subclass.
    */
  protected void traverseTreeEdge(Edge e, Vertex from) {}

   /**
    * Called when a back edge is traversed.  Can be overridden by a
    * subclass.  
    */
  protected void traverseBackEdge(Edge e, Vertex from) {}

   /**
    * Called when a forward edge is traversed.  Can be overridden
    * by a subclass.  
    */
  protected void traverseForwardEdge(Edge e, Vertex from) {}

   /**
    * Called when a cross edge is traversed.  Can be overridden by a
    * subclass.
    */
  protected void traverseCrossEdge(Edge e, Vertex from) {}

   /**
    * Tests if the depth first search is done.  Can be overridden by a
    * subclass.
    */
  protected boolean isDone() { return false; }

   /**
    * Called when the search has finished with the vertex.  Can be
    * overridden by a subclass.
    */
  protected void finishVisit(Vertex v) {}

  /**
   * A method that returns an iterator over those edges incident
   * to the parameter vertex in the graph which should be considered for
   * exploration.  Subclasses of DFS may implement this method so as to
   * traverse edges as though they were undirected or to traverse the
   * directed edges in the forward or reverse directions, or to in some
   * other way hand pick which edges were of interest for exploration.
   *
   * @param v The vertex for which interesting incident edges shouldbe
   * returned
   * @return EdgeIterator An Iterator over interesting edges incident to the
   * parameter Vertex
   */
  protected EdgeIterator interestingIncidentEdges(Vertex v) 
    { return graph_.incidentEdges(v);}
}