integerprimtemplate.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.graph.api.*;

/**
 * Implementation of the algorithm of Prim and Jarnik for finding a
 * minimum spanning tree, 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 four 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 the Prim-Jarnik
 * algorithm cannot handle negative-weight edges.
 * 
 * <li>"output" methods that you must, realistically speaking, override
 * in order to get useful information out of the algorithm and into
 * your application domain:  You will need
 * to override at least one of treeEdgeFound(.), relaxingEdge(.),
 * and vertexNotReachable(.).  For every vertex in the graph (or
 * every vertex you allow the algorithm to consider), either
 * treeEdgeFound(.) 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, relaxingEdge(.) will be
 * called every time an edge to an unfinished vertex is explored.
 * 
 * <li>overridable methods that will need to be overridden only
 * for special applications:  See the comments for shouldContinue(),
 * setLocator(.), getLocator(.), newPQ(), initMap(), incidentEdges(.),
 * destination(.), allVertices(), and init(.) (which has a split role
 * between this category of methods and the next).
 * 
 * <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.
 *
 * @author Mark Handy
 * @author Galina Shubina
 */

public abstract class IntegerPrimTemplate {
    public IntegerPrimTemplate() { }
    
    protected PriorityQueue Q;
    protected InspectableGraph G;
    protected Vertex source;
    protected Integer ZERO;
    protected Integer INFINITY;
    protected java.util.Hashtable locators;
    protected int treeWeight;

    private static class VEPair { // v and its best-so-far incoming e
	VEPair( Vertex v, Edge e ) { vert=v; edge=e; }
	private Vertex vert;
	private Edge edge;
    }
    
    
    
    // method that must be overridden to satisfy the compiler
    
    /** 
     * 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. Prim'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 );



    

    // "output" methods, at least one of which must, realistically speaking,
    // be overridden in order to get output from the algorithm

    /** 
     * Can be overridden to give you a notification when a vertex is
     * added to the minimum spanning tree.  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 vparent Edge leading into v in the minimum spanning tree
     * @param treeWeight the total weight of all edges known to be
     * in the tree at this point in the execution of the algorithm, including
     * vparent
     */
    protected void treeEdgeFound( Vertex v, Edge vparent, int treeWeight ) { }
    
    /** 
     * 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 ) { }
    
    /** 
     * Can be overridden in any application where the edges considered
     * for the minimum spanning tree matter.  Called every time an edge
     * leading to a vertex is examined (relaxed); this can happen many
     * times per vertex.  If uvweight is less than vdist, then uv is a
     * better tree edge to v than the best edge 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 uv Edge being explored
     * @param uvweight Weight of uv
     * @param v Vertex being investigated: the best-known-edge to it
     * will be updated if the uv is a better edge
     * @param vdist The present, possibly suboptimal, distance of v
     * from the partially built spanning tree
     */
    protected void relaxingEdge( Vertex u, 
				 Edge uv, int uvweight,
				 Vertex v, int vdist ) { }

    
    
    
    
    
    // methods that may be overridden for special applications,
    // but needn't be

    /** 
     * Can be overridden in any application where the full
     * minimum spanning 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 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;
    }

    /** 
     * Can be overridden to supply a way of storing and retrieving
     * one locator per vertex.  Will be called exactly once per vertex,
     * during initialization.  The default implementation uses the
     * java.util.Hashtable initialized by initMap() to store one locator per vertex. 
     * @see #getLocator(Vertex)
     * @see #initMap()
     * @param u Vertex to label with a locator
     * @param ulocInPQ the label
     */
    protected void setLocator( Vertex u, Locator ulocInPQ ) {
	locators.put( u, ulocInPQ );
    }
    
    /** 
     * 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
     * queries the java.util.Hashtable mentioned in setLocator(.). The