integerdijkstratemplate.java

Java数据结构开发包

/*
  Copyright (c) 1999, 2000 Brown University, Providence, RI
  
                            All Rights Reserved
  
  Permission to use, copy, modify, and distribute this software and its
  documentation for any purpose other than its incorporation into a
  commercial product is hereby granted without fee, provided that the
  above copyright notice appear in all copies and that both that
  copyright notice and this permission notice appear in supporting
  documentation, and that the name of Brown University not be used in
  advertising or publicity pertaining to distribution of the software
  without specific, written prior permission.
  
  BROWN UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR ANY PARTICULAR PURPOSE.  IN NO EVENT SHALL BROWN
  UNIVERSITY BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  PERFORMANCE OF THIS SOFTWARE.
*/

package jdsl.graph.algo;

import jdsl.core.api.*;
import jdsl.core.ref.ArrayHeap;
import jdsl.core.ref.IntegerComparator;
import jdsl.graph.api.*;



/**
 * Implementation of Dijkstra's algorithm using the template-method
 * pattern: the core functionality is coded in a few final methods
 * that call overridable methods to do some of the work.  The methods
 * of this class are in five categories:
 *
 * <ul>
 * 
 * <li>A method you must override to make the compiler happy: You must
 * override weight(Edge) to supply the algorithm with a weight for
 * every edge in the graph.  Note that Dijkstra's algorithm cannot
 * handle negative-weight edges.
 * 
 * <li>"Hook" methods that may be overridden to specialize the
 * algorithm to the application at hand: shortestPathFound(.),
 * edgeRelaxed(.), and vertexNotReachable(.).  For every vertex in the
 * graph (or every vertex you allow the algorithm to consider), either
 * shortestPathFound(.) or vertexNotReachable(.) will be called, and
 * will be called exactly once.  When that has occurred, the vertex is
 * considered to be "finished"; it will not be considered again by the
 * algorithm.  Finally, edgeRelaxed(.) will be called every time an
 * edge to an unfinished vertex is explored.
 * 
 * <li>Overridable methods that will need to be overridden more
 * rarely: See the comments for shouldContinue(), isFinished(.),
 * setLocator(.), getLocator(.), setEdgeToParent(.), newPQ(),
 * initMap(), incidentEdges(.), destination(.), vertices(), and
 * init(.) (which has a split role between this category of methods
 * and the next).
 *
 * <li>"Output" methods through which the user can test, after the
 * execution of the algorithm, whether a vertex is reachable from the
 * source, and retrieve the decorations of the vertices: See the
 * comments for isReachable(.), distance(.), and getEdgeToParent(.).
 * 
 * <li>Methods composing the core of the algorithm, which cannot be
 * overridden (or, in the case of init(.), should rarely be
 * overridden): You can run the algorithm in either of two ways.  If
 * you want to run the whole algorithm at once, use either version of
 * executeAll(.).  It will call doOneIteration() multiple times, and
 * doOneIteration() will call your overridden output methods as it
 * encounters vertices.  Instead of using executeAll(.), you can
 * single-step the algorithm by calling init(.) to initialize, then
 * calling doOneIteration() repeatedly.
 *
 * </ul>
 * 
 * Note that it is possible to confuse the algorithm by doing things
 * like modifying the graph, messing with the priority queue, or
 * changing edge weights while it is running.
 *
 * @version JDSL 2.1.1 
 * @author Mark Handy
 * @author Galina Shubina
 * @author Luca Vismara
 */
public abstract class IntegerDijkstraTemplate {

  // instance variables

  protected PriorityQueue pq_;
  protected InspectableGraph g_;
  protected Vertex source_;
  private final Integer ZERO = new Integer(0);
  private final Integer INFINITY = new Integer(Integer.MAX_VALUE);
  private final Object LOCATOR = new Object();
  private final Object DISTANCE = new Object();
  private final Object EDGE_TO_PARENT = new Object();

    
  // abstract instance method; must be overridden
    
  /** 
   * Must be overridden to supply a way of getting a positive weight
   * for every edge in the graph.  This method gets called by the
   * algorithm when the algorithm needs to know the weight of an
   * edge. Dijkstra's algorithm cannot handle negative weights.
   * Furthermore, although it works correctly with zero-weight edges,
   * some of the methods of this class make guarantees based on
   * assuming positive weights that they cannot make if there are
   * zero-weight edges.
   *
   * @param e Edge for which the algorithm needs to know a weight
   * @return Your application's weight for e
   */
  protected abstract int weight (Edge e);


  // instance methods that may be overridden for special applications

  /** 
   * Can be overridden to give you a notification when the shortest
   * path to a vertex is determined.  The algorithm calls this method
   * at most once per vertex, after the vertex has been "finished"
   * (i.e., when the path from s to the vertex is known).  The vertex
   * will never again be touched or considered by the algorithm.
   * <p>
   * Note that there is no corresponding get-method; the algorithm
   * does not need this information again, so the only constraints on
   * what you do with the information are those imposed by your
   * application.
   *
   * @param v Vertex that the algorithm just finished
   * @param vDist Distance of v from the source
   */
  protected void shortestPathFound (Vertex v, int vDist) {
    v.set(DISTANCE,new Integer(vDist));
  }
    
  /** 
   * Can be overridden in any application that involves unreachable
   * vertices.  Called every time a vertex with distance INFINITY
   * comes off the priority queue.  When it has been called once, it
   * should subsequently be called for all remaining vertices, until
   * the priority queue is empty.
   * <p>
   * Note that there is no corresponding get-method; the algorithm
   * does not need this information again, so the only constraints on
   * what you do with the information are those imposed by your
   * application.
   *
   * @param v Vertex which the algorithm just found to be unreachable
   * from the source
   */
  protected void vertexNotReachable (Vertex v) {
    v.set(DISTANCE,INFINITY);
    setEdgeToParent(v,Edge.NONE);
  }

  /** 
   * Can be overridden in any application where the edges considered
   * for the shortest-path tree matter.  Called every time an edge
   * leading to a vertex is examined (relaxed); this can happen many
   * times per vertex.  If udist + uvweight is less than vDist, there
   * is a shorter path to v, via u and uv, than the shortest path to v
   * previously known, so v is updated in the priority queue.  This
   * method notifies you before such a calculation is made, whether
   * the calculation results in an update or not.
   * <p>
   * For every vertex reachable from the source, except the source,
   * this method will be called at least once before the vertex is
   * finished.  Once a vertex has been finished, this method will
   * never be called for that vertex again.
   * <p>
   * Note that there is no corresponding
   * get-method; the algorithm does not need this information again,
   * so the only constraints on what you do with the information are
   * those imposed by your application.
   * @param u Vertex about to be finished, from which an edge to v
   * is being explored
   * @param uDist The final distance to u (will soon be passed as
   * svDist to shortestPathFound(.))
   * @param uv Edge being explored
   * @param uvWeight Weight of uv
   * @param v Vertex being investigated: the best-known-path to it
   * will be updated if the path via u and uv is better
   * @param vDist The present, possibly suboptimal, distance of v
   * from s
   */
  protected void edgeRelaxed (Vertex u, int uDist, Edge uv, int uvWeight,
			      Vertex v, int vDist) { }
    
    
  // instance methods that may be overridden for special applications,
  // but needn't be

  /** 
   * Can be overridden in any application where the full shortest-path
   * tree is not needed and the algorithm should terminate early.
   * executeAll(.) checks the return from this method before each call
   * to doOneIteration().  The default implementation just returns
   * <code>true</code>, so executeAll(.) continues until the full
   * shortest-path tree is built.  Notice that if you are calling
   * doOneIteration() manually, this method is irrelevant; only
   * executeAll(.) calls this method.
   *
   * @return Whether to continue running the algorithm
   */
  protected boolean shouldContinue () {
    return true;
  }

  /**
   * Tests whether a vertex has been reached.
   *
   * @param v a vertex
   * @return Whether v has been marked as finished
   */
  protected boolean isFinished (Vertex v) {
    return v.has(DISTANCE);
  }

  /** 
   * Can be overridden to supply a way of storing and retrieving one
   * locator per vertex.  Will be called only once per vertex, during
   * initialization.  The default implementation decorates each vertex
   * with its locator.
   *
   * @see #getLocator(Vertex)
   * @see Decorable#set(Object,Object)
   * @param v Vertex to decorate with a locator
   * @param vLoc the locator with which to decorate v
   */
  protected void setLocator (Vertex v, Locator vLoc) {
    v.set(LOCATOR,vLoc);
  }
    
  /** 
   * Can be overridden to supply a way of storing and retrieving one
   * locator per vertex.  This is the counterpart to setLocator(.)
   * 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 priority queue.
   *
   * @see #setLocator(Vertex,Locator)
   * @see Decorable#get(Object)
   * @param v Vertex previously decorated with a locator
   * @return Locator associated with v in the earlier setLocator(.) call
   */
  protected Locator getLocator (Vertex v) {
    return (Locator)v.get(LOCATOR);
  }

  /** 
   * Can be overridden to supply a way of storing and retrieving one
   * edge per vertex.  The default implementation decorates each vertex