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
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 finergrained
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 
edges_
protected Sequence edges_
IntegerPrimTreeBuilder
public IntegerPrimTreeBuilder()
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
zeroweight edges, some of the methods of this class make
guarantees based on assuming positive weights that they cannot
make if there are zeroweight 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 getmethod; 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 finishedvparent
 Edge leading into v in the minimum spanning treetreeWeight
 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 finergrained
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 algorithmsrc
 Vertex at which to root the minimum spanning treeinfinity
 Distance with which all other vertices will be
labelled initially; must be greater than any edge weight