integerdijkstratemplate.java

Java数据结构开发包

   * with its edge.
   *
   * @see #getEdgeToParent(Vertex)
   * @see Decorable#set(Object,Object)
   * @param v Vertex to decorate with an edge
   * @param vEdge the with which to decorate v
   */
  protected void setEdgeToParent (Vertex v, Edge vEdge) {
    v.set(EDGE_TO_PARENT,vEdge);
  }
      
  /** 
   * Can be overridden to supply a priority queue of your
   * choosing, but the default implementation, which gives an empty   
   * jdsl.core.ref.ArrayHeap, is probably sufficient for most
   * purposes.  The priority queue must be able to accept keys of
   * type Integer.  If you choose to override the method, 
   * for typical applications you should return an empty priority
   * queue.  If necessary, it can be preinitialized, although you
   * will need to accommodate that fact in other methods.
   * @return PriorityQueue to be used by the algorithm
   */
  protected PriorityQueue newPQ () {
    return new ArrayHeap(new IntegerComparator());
  }

  /** 
   * Can be overridden to initialize a locator-lookup data structure
   * of your choosing, but the default implementation, which decorates
   * each vertex with its locator, is probably sufficient for most
   * purposes.  This method is called by the algorithm before any call
   * to setLocator(.).  The best reason to override this method is
   * that you have some other way to implement set/getLocator(.).  In
   * that case, override this method to do any necessary
   * initialization of your data structure.<p>
   */
  protected void initMap () { }
    
  /** 
   * Can be overridden in any application where the default choice of
   * edges to consider at any vertex is not satisfactory.  The default
   * is to consider all outgoing and all undirected edges from a given
   * vertex.  Example:  if you have a directed graph but want to view it
   * as undirected for purposes of building a shortest-path tree, you
   * should override this method to read<br>
   * <code> return G.incidentEdges(v, EdgeDirection.IN | EdgeDirection.OUT);
   * </code>
   * @param v Vertex soon to be finished by the algorithm
   * @return All the interesting edges of v -- i.e., all edges whose
   * weights you want the algorithm to inspect in considering
   * alternative routes to vertices adjacent to v
   */
  protected EdgeIterator incidentEdges (Vertex v) {
    return g_.incidentEdges(v,EdgeDirection.OUT | EdgeDirection.UNDIR);
  }
    
  /** 
   * Can be overridden to supply the destination of an edge, although I
   * can't think of any reason to do so.  Presently implemented with
   * opposite(.), so it works even if the edge is incoming to v (see the
   * example under incidentEdges(.)).  Called by the core algorithm when
   * it is about to finish <code>origin</code> and needs all its
   * adjacent vertices.
   * @param origin Vertex soon to be finished by the algorithm
   * @param e Edge incident on <code>origin</code> according to
   * incidentEdges(.) 
   * @return the vertex opposite <code>origin</code> along
   * <code>e</code> 
   */
  protected Vertex destination (Vertex origin, Edge e) {
    return g_.opposite(origin,e);
  }

  /** 
   * Can be overridden to consider a subset of the vertices in the
   * graph, although I can't think of any reason to do so.  Note that
   * overriding this method will probably also require overriding
   * incidentEdges(.), in order to avoid edges leading to vertices not
   * in the subset.
   * @return Iterator over all vertices to be initially put in the
   * priority queue and eventually finished by the algorithm
   */
  protected VertexIterator vertices () {
    return g_.vertices();
  }


  // output instance methods
  
  /**
   * Tests whether a vertex is reachable from the source.  The method
   * can be invoked at any time during the single-step execution of
   * the algorithm.
   *
   * @param v a vertex
   * @return whether v is reachable from the source
   */
  public final boolean isReachable (Vertex v) {
    return v == source_
      || (v.has(EDGE_TO_PARENT) && v.get(EDGE_TO_PARENT) != Edge.NONE);
  }

  /**
   * Returns the distance of a vertex from the source.
   *
   * @param v a vertex
   * @return the distance of v from the source
   * @exception InvalidQueryException if v has not been reached yet
   */
  public final int distance (Vertex v) throws InvalidQueryException {
    try {
      return ((Integer)v.get(DISTANCE)).intValue();
    }
    catch (InvalidAttributeException iae) {
      throw new InvalidQueryException(v+" has not been reached yet");
    }
  }
    
  /** 
   * Can be overridden to supply a way of storing and retrieving one
   * edge per vertex.  This is the counterpart to setEdgeToParent(.)
   * but may be called many times.  The default implementation uses
   * the decoration of each vertex.  The algorithm calls this method
   * whenever it needs to update the best distance it knows for a
   * vertex, which requires updating the edge to parent.
   *
   * @see #setEdgeToParent(Vertex,Edge)
   * @see Decorable#get(Object)
   * @param v Vertex previously labeled with an edge
   * @return Edge associated with v in the earlier setEdgeToParent(.)
   * call
   * @exception InvalidQueryException if v is the source or has not
   * been reached yet
   */
  public Edge getEdgeToParent (Vertex v) throws InvalidQueryException {
    try {
      return (Edge)v.get(EDGE_TO_PARENT);
    }
    catch (InvalidAttributeException iae) {
      String s = (v == source_)
	? " is the source vertex" : " has not been reached yet";
      throw new InvalidQueryException(v+s);
    }
  }

  
  // instance methods composing the core of the algorithm; cannot be
  // changed

  /** 
   * Called automatically by executeAll(); must be called by the client
   * prior to the first call to doOneIteration() if finer-grained
   * control of the algorithm is needed.  The method initializes
   * instance variables and then puts all vertices in the PQ with
   * initial distances, and records their respective locators.  Can be
   * overridden, although I can't think of any reason to do so.
   * <p>
   * Calls the following methods that can be overridden:  newPQ(),
   * initMap(), vertices(), setLocator(.).
   *
   * @param g Graph on which to execute the algorithm
   * @param source Vertex at which to root the shortest-path tree
   */
  public void init (InspectableGraph g, Vertex source) {
    g_ = g;
    source_ = source;
    pq_ = newPQ();
    initMap();
    VertexIterator vi = vertices();
    while (vi.hasNext()) {
      Vertex u = vi.nextVertex();
      Integer ukey = (u == source_) ? ZERO : INFINITY;
      Locator uLoc = pq_.insert(ukey,u);
      setLocator(u,uLoc);
    }
  }

  /**
   * Removes the decorations from the vertices.  Its invocation is the
   * user's responsibility.
   */
  public void cleanup () {
    VertexIterator vi = vertices();
    while (vi.hasNext()) {
      vi.nextVertex().destroy(LOCATOR);
      try {
	vi.vertex().destroy(EDGE_TO_PARENT);
	vi.vertex().destroy(DISTANCE);
      }
      catch(InvalidAttributeException iae) { }
    }
  }
    
  /** 
   * Can be called manually to single-step the algorithm, but you must
   * call init(.) before the first call to this method.  Finishes one
   * vertex and updates all adjacent vertices.  If the vertex that
   * gets finished was reachable from the source, this method expands
   * the shortest-path tree by one vertex.
   */
  public final void doOneIteration () throws InvalidEdgeException {
    // from Q take u of minimum distance from source
    Integer minKey = (Integer)pq_.min().key();
    // remove a vertex with minimum distance from the source
    Vertex u = (Vertex)pq_.removeMin();   

    if (minKey == INFINITY)
      vertexNotReachable(u);
    else {   // the general case
      int uDist = minKey.intValue();
      shortestPathFound(u,uDist);
      int maxEdgeWeight = INFINITY.intValue()-uDist-1;
      // examine all the neighbors of u and update their distances
      EdgeIterator ei = incidentEdges(u);
      while (ei.hasNext()) {   // while u has more edges
	Edge uv = ei.nextEdge();
	int uvWeight = weight(uv);
	if (uvWeight < 0 || uvWeight > maxEdgeWeight)
	  throw new InvalidEdgeException
	    ("The weight of "+uv+" is either negative or causing overflow");
	Vertex v = destination(u,uv);
	Locator vLoc = getLocator(v);
	if (pq_.contains(vLoc)) {   // v is not finished yet
	  int vDist = ((Integer)vLoc.key()).intValue();
	  int vDistViaUV = uDist+uvWeight;
	  if (vDistViaUV < vDist) {   // relax
	    pq_.replaceKey(vLoc,new Integer(vDistViaUV));
	    setEdgeToParent(v,uv);
	  }
	  edgeRelaxed(u,uDist,uv,uvWeight,v,vDist);
	}
      }
    }
  }

  /**
   * Repeatedly calls method doOneIteration() until either the
   * priority queue is empty or method shouldContinue() returns false.
   */
  protected final void runUntil () {
    while (!pq_.isEmpty() && shouldContinue())
      doOneIteration();
  }

  /** 
   * The easiest way to use the algorithm is to use this method.
   * Calls init(.) once, then doOneIteration() repeatedly until
   * either the PQ is empty or shouldContinue() returns false.
   *
   * @param g Graph on which to execute the algorithm
   * @param source Vertex at which to root the shortest-path tree
   */
  public final void execute (InspectableGraph g, Vertex source) {
    init(g,source);
    runUntil();
  }
  
}   // class IntegerDijkstraTemplate