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 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 |
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
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 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 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 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