jdsl.graph.algo
Class IntegerPrimTreeBuilder

java.lang.Object
  |
  +--jdsl.graph.algo.IntegerPrimTemplate
        |
        +--jdsl.graph.algo.IntegerPrimTreeBuilder

public abstract class IntegerPrimTreeBuilder
extends IntegerPrimTemplate

Constructs a full minimum spanning tree on a given graph and reports the tree as an iterator over the edges. The user must provide weight(e) as in IntegerPrimTemplate. Use the class by subclassing to provide weight(e), then calling executeAll(.). The tree built is accessed with treeEdges().

Version:
$Id: IntegerPrimTreeBuilder.java,v 1.1 1999/09/01 03:42:33 mdh Exp $
Author:
Mark Handy

Field Summary
protected  Sequence edges_
           
 
Fields inherited from class jdsl.graph.algo.IntegerPrimTemplate
G, INFINITY, locators, Q, source, treeWeight, ZERO
 
Constructor Summary
IntegerPrimTreeBuilder()
           
 
Method Summary
 void init(InspectableGraph g, Vertex src, int infinity)
          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.
protected  void treeEdgeFound(Vertex v, Edge vparent, int treeWeight)
          Can be overridden to give you a notification when a vertex is added to the minimum spanning tree.
 EdgeIterator treeEdges()
           
protected abstract  int weight(Edge e)
          Must be overridden to supply a way of getting a positive weight for every edge in the graph.
 
Methods inherited from class jdsl.graph.algo.IntegerPrimTemplate
allVertices, badWeight, destination, doOneIteration, executeAll, executeAll, getLocator, incidentEdges, initMap, newPQ, relaxingEdge, setLocator, shouldContinue, vertexNotReachable
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

edges_

protected Sequence edges_
Constructor Detail

IntegerPrimTreeBuilder

public IntegerPrimTreeBuilder()
Method Detail

treeEdges

public EdgeIterator treeEdges()
Returns:
Iterator over all edges of the minimum spanning tree produced by the previous call of executeAll(.)

weight

protected abstract int weight(Edge e)
Description copied from class: IntegerPrimTemplate
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.
Overrides:
weight in class IntegerPrimTemplate
Following copied from class: jdsl.graph.algo.IntegerPrimTemplate
Parameters:
e - Edge for which the algorithm needs to know a weight
Returns:
Your application's weight for e

treeEdgeFound

protected void treeEdgeFound(Vertex v,
                             Edge vparent,
                             int treeWeight)
Description copied from class: IntegerPrimTemplate
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.

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.

Overrides:
treeEdgeFound in class IntegerPrimTemplate
Following copied from class: jdsl.graph.algo.IntegerPrimTemplate
Parameters:
v - Vertex that the algorithm just finished
vparent - Edge leading into v in the minimum spanning tree
treeWeight - the total weight of all edges known to be in the tree at this point in the execution of the algorithm, including vparent

init

public void init(InspectableGraph g,
                 Vertex src,
                 int infinity)
Description copied from class: IntegerPrimTemplate
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.

Calls the following methods that can be overridden: newPQ(), initMap(), allVertices(), setLocator(.).

Overrides:
init in class IntegerPrimTemplate
Following copied from class: jdsl.graph.algo.IntegerPrimTemplate
Parameters:
g - Graph on which to execute the algorithm
src - Vertex at which to root the minimum spanning tree
infinity - Distance with which all other vertices will be labelled initially; must be greater than any edge weight