integerprimtemplate.java

Java数据结构开发包

     * 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)
     * @param u Vertex previously labeled with a locator
     * @return Locator associated with u in the earlier setLocator(.) call
     */
    protected Locator getLocator( Vertex u ) {
	return (Locator) locators.get(u);
    }
    /** 
     * 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 jdsl.core.ref.ArrayHeap
	    ( new jdsl.core.ref.IntegerComparator() );
    }
    
    /** 
     * Can be overridden to initialize a locator-lookup data structure
     * of your choosing, but the default implementation, which uses a
     * java.util.Hashtable, 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 way other than a java.util.Hashtable to implement
     * set/getLocator(.).  In that case, override this method to
     * do any necessary initialization of your data structure.
     * <p>
     * Note that the algorithm never removes anything from
     * <code>locators</code>, so if you want to execute the algorithm
     * repeatedly, it is probably unwise to return the same data structure
     * repeatedly from this method.
     */
    protected void initMap() {
	locators = new java.util.Hashtable();
    }
    
    /** 
     * 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 edges from a given vertex, directed and undirected.
     * Example:  if you want to build an MST on just the undirected
     * edges of your graph, you should override this method to read<br>
     * <code> return G.incidentEdges( v, EdgeDirection.UNDIR );
     * </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 edges to vertices adjacent to v
     */
    protected EdgeIterator incidentEdges( Vertex v ) {
	return G.incidentEdges( v );
    }
    
    /** 
     * 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 allVertices() {
	return G.vertices();
    }

    /** 
     * Can be overridden to handle edges that have zero or
     * negative weights.  The Prim-Jarnik algorithm is not guaranteed
     * to work correctly in the presence of negative-weight edges.
     * In the present of zero-weight edges, the algorithm works
     * correctly, but some guarantees of other methods of this
     * override this method to throw an exception or to fix 
     * the problem and return the weight the algorithm should use for
     * edge uv.  Whatever weight you return the algorithm will use,
     * without checking it.  The default behavior is to throw an
     * InvalidEdgeException if uvweight is negative, and to
     * return 0 if uvweight is 0 -- that is, to allow zero-weight
     * edges. 
     * @param u Vertex being finished when the bad weight was
     * discovered 
     * @param uv Edge for which weight(uv) returned a zero or negative
     * value 
     * @param uvweight The weight returned from weight(uv)
     * @return Weight the algorithm should use for uv (can be equal to
     * uvweight) (the default is to return 0 only if uvweight is 0)
     * @exception RuntimeException Any exception you want to throw to
     * indicate a bad weight (the default is to throw an
     * InvalidEdgeException only if uvweight is negative)
     */
     protected int badWeight( Vertex u, Edge uv, int uvweight ) {
	if( uvweight < 0 ) throw new InvalidEdgeException
			       ( "negative weight on edge" );
	else return 0;
    }

    /** 
     * 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(), allVertices(), setLocator(.).
     * @param g Graph on which to execute the algorithm
     * @param src Vertex at which to root the minimum spanning tree
     * @param infinity Distance with which all other vertices will be
     * labelled initially; must be greater than any edge weight
     */
    public void init( InspectableGraph g,
		      Vertex src,
		      int infinity ) {
	G = g;
	source = src;
	ZERO = new Integer(0);
	INFINITY = new Integer(infinity);
	Q = newPQ();
	initMap(); // by default, initializes the "locators" variable
	treeWeight = 0;
	VertexIterator pv = allVertices();
	while( pv.hasNext() ) {
	    Vertex u = pv.nextVertex();
	    Integer ukey;
	    if( u==source ) ukey = ZERO;
	    else ukey = INFINITY;
	    Locator uloc = Q.insert( ukey, new VEPair(u,null) );
	    setLocator( u, uloc );
	}
    }
    



    // methods composing the core of the algorithm, cannot be changed
    
    /** 
     * 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 minimum spanning tree by
     * one vertex.
     */
    public final void doOneIteration() {
	    
	// from Q take u of minimum distance from tree
	Locator uloc = Q.min();  Q.removeMin();
	VEPair ue = (VEPair) uloc.element(); // u and its parent edge
	Vertex u = ue.vert;

	if( uloc.key()==INFINITY ) vertexNotReachable(u); // u is finished
	else { // the general case
	    
	    // examine all the neighbors of u and update their distances
	    EdgeIterator pe = incidentEdges(u);
	    while( pe.hasNext() ) {
		Edge uv = pe.nextEdge();
		int uvweight = weight(uv);
		if( uvweight < 1 ) uvweight = badWeight( u, uv, uvweight );
		Vertex v = destination( u, uv );
		Locator vloc = getLocator( v );
		if( Q.contains(vloc) ) { // relax
		    int vdist = ( (Integer)vloc.key() ).intValue();
		    relaxingEdge( u, uv, uvweight, v, vdist );
		    if( uvweight < vdist ) {
			Q.replaceKey( vloc, new Integer(uvweight) );
			( (VEPair) vloc.element() ).edge = uv;
		    }
		}
	    } // while u has more edges

	    if( ue.edge != null ) treeWeight += weight( ue.edge );
	    treeEdgeFound( u, ue.edge, treeWeight ); // u is finished

	}
    }

    /** 
     * 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.
     */
    public final void executeAll( InspectableGraph g,
				  Vertex src,
				  int infinity ) {
	init( g, src, infinity );
	while( ! Q.isEmpty() && shouldContinue() ) doOneIteration();
    }
    
    /** 
     * Just like the other version of executeAll(.), but with 
     * infinity=Integer.MAX_VALUE 
     */
    public final void executeAll( InspectableGraph g,
				  Vertex src ) {
	init( g, src, Integer.MAX_VALUE );
	while( ! Q.isEmpty() && shouldContinue() ) doOneIteration();
    }
    
} // class IntegerPrimTemplate