

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: INNER  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object  +jdsl.graph.algo.IntegerPrimTemplate
Implementation of the algorithm of Prim and Jarnik for finding a minimum spanning tree, using the templatemethod 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:
Field Summary  
protected InspectableGraph 
G

protected java.lang.Integer 
INFINITY

protected java.util.Hashtable 
locators

protected PriorityQueue 
Q

protected Vertex 
source

protected int 
treeWeight

protected java.lang.Integer 
ZERO

Constructor Summary  
IntegerPrimTemplate()

Method Summary  
protected VertexIterator 
allVertices()
Can be overridden to consider a subset of the vertices in the graph, although I can't think of any reason to do so. 
protected int 
badWeight(Vertex u,
Edge uv,
int uvweight)
Can be overridden to handle edges that have zero or negative weights. 
protected Vertex 
destination(Vertex origin,
Edge e)
Can be overridden to supply the destination of an edge, although I can't think of any reason to do so. 
void 
doOneIteration()
Can be called manually to singlestep the algorithm, but you must call init(.) before the first call to this method. 
void 
executeAll(InspectableGraph g,
Vertex src)
Just like the other version of executeAll(.), but with infinity=Integer.MAX_VALUE 
void 
executeAll(InspectableGraph g,
Vertex src,
int infinity)
The easiest way to use the algorithm is to use this method. 
protected Locator 
getLocator(Vertex u)
Can be overridden to supply a way of storing and retrieving one locator per vertex. 
protected EdgeIterator 
incidentEdges(Vertex v)
Can be overridden in any application where the default choice of edges to consider at any vertex is not satisfactory. 
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 
initMap()
Can be overridden to initialize a locatorlookup data structure of your choosing, but the default implementation, which uses a java.util.Hashtable, is probably sufficient for most purposes. 
protected PriorityQueue 
newPQ()
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. 
protected void 
relaxingEdge(Vertex u,
Edge uv,
int uvweight,
Vertex v,
int vdist)
Can be overridden in any application where the edges considered for the minimum spanning tree matter. 
protected void 
setLocator(Vertex u,
Locator ulocInPQ)
Can be overridden to supply a way of storing and retrieving one locator per vertex. 
protected boolean 
shouldContinue()
Can be overridden in any application where the full minimum spanning tree is not needed and the algorithm should terminate early. 
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. 
protected void 
vertexNotReachable(Vertex v)
Can be overridden in any application that involves unreachable vertices. 
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 java.lang.Object 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 
protected PriorityQueue Q
protected InspectableGraph G
protected Vertex source
protected java.lang.Integer ZERO
protected java.lang.Integer INFINITY
protected java.util.Hashtable locators
protected int treeWeight
Constructor Detail 
public IntegerPrimTemplate()
Method Detail 
protected abstract int weight(Edge e)
e
 Edge for which the algorithm needs to know a weightprotected void treeEdgeFound(Vertex v, Edge vparent, int treeWeight)
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.
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
vparentprotected void vertexNotReachable(Vertex v)
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.
v
 Vertex which the algorithm just found to be
unreachable from the sourceprotected void relaxingEdge(Vertex u, Edge uv, int uvweight, Vertex v, int vdist)
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.
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.
u
 Vertex about to be finished, from which an edge to v
is being exploreduv
 Edge being exploreduvweight
 Weight of uvv
 Vertex being investigated: the bestknownedge to it
will be updated if the uv is a better edgevdist
 The present, possibly suboptimal, distance of v
from the partially built spanning treeprotected boolean shouldContinue()
true
, 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.protected void setLocator(Vertex u, Locator ulocInPQ)
u
 Vertex to label with a locatorulocInPQ
 the labelgetLocator(Vertex)
,
initMap()
protected Locator getLocator(Vertex u)
u
 Vertex previously labeled with a locatorsetLocator(Vertex,Locator)
protected PriorityQueue newPQ()
protected void initMap()
Note that the algorithm never removes anything from
locators
, so if you want to execute the algorithm
repeatedly, it is probably unwise to return the same data structure
repeatedly from this method.
protected EdgeIterator incidentEdges(Vertex v)
return G.incidentEdges( v, EdgeDirection.UNDIR );
v
 Vertex soon to be finished by the algorithmprotected Vertex destination(Vertex origin, Edge e)
origin
and needs all its
adjacent vertices.origin
 Vertex soon to be finished by the algorithme
 Edge incident on origin
according to
incidentEdges(.)origin
along
e
protected VertexIterator allVertices()
protected int badWeight(Vertex u, Edge uv, int uvweight)
u
 Vertex being finished when the bad weight was
discovereduv
 Edge for which weight(uv) returned a zero or negative
valueuvweight
 The weight returned from weight(uv)java.lang.RuntimeException
 Any exception you want to throw to
indicate a bad weight (the default is to throw an
InvalidEdgeException only if uvweight is negative)public void init(InspectableGraph g, Vertex src, int infinity)
Calls the following methods that can be overridden: newPQ(), initMap(), allVertices(), setLocator(.).
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 weightpublic final void doOneIteration()
public final void executeAll(InspectableGraph g, Vertex src, int infinity)
public final void executeAll(InspectableGraph g, Vertex src)


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: INNER  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 