nz.ac.waikato.jdsl.graph.algo
Class IntegerPrimTemplate

java.lang.Object
  nz.ac.waikato.jdsl.graph.algo.IntegerPrimTemplate

public abstract class IntegerPrimTemplate
extends java.lang.Object

Implementation of the algorithm of Prim and Jarnik for finding a minimum spanning tree, using the template-method 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:

• a method you must override to make the compiler happy: You must override weight(Edge) to supply the algorithm with a weight for every edge in the graph. Note that the Prim-Jarnik algorithm cannot handle negative-weight edges.
• "output" methods that you must, realistically speaking, override in order to get useful information out of the algorithm and into your application domain: You will need to override at least one of treeEdgeFound(.), relaxingEdge(.), and vertexNotReachable(.). For every vertex in the graph (or every vertex you allow the algorithm to consider), either treeEdgeFound(.) or vertexNotReachable(.) will be called, and will be called exactly once. When that has occurred, the vertex is considered to be "finished"; it will not be considered again by the algorithm. Finally, relaxingEdge(.) will be called every time an edge to an unfinished vertex is explored.
• overridable methods that will need to be overridden only for special applications: See the comments for shouldContinue(), setLocator(.), getLocator(.), newPQ(), initMap(), incidentEdges(.), destination(.), allVertices(), and init(.) (which has a split role between this category of methods and the next).
• methods composing the core of the algorithm, which cannot be overridden (or, in the case of init(.), should rarely be overridden): You can run the algorithm in either of two ways. If you want to run the whole algorithm at once, use either version of executeAll(.). It will call doOneIteration() multiple times, and doOneIteration() will call your overridden output methods as it encounters vertices. Instead of using executeAll(.), you can single-step the algorithm by calling init(.) to initialize, then calling doOneIteration() repeatedly.

Note that it is possible to confuse the algorithm by doing things like modifying the graph, messing with the priority queue, or changing edge weights while it is running.

Author:

Mark Handy, Galina Shubina

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 single-step 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 finer-grained control of the algorithm is needed.
protected void	initMap() 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.
protected PriorityQueue	newPQ() Can be overridden to supply a priority queue of your choosing, but the default implementation, which gives an empty nz.ac.waikato.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

Q

protected PriorityQueue Q

G

protected InspectableGraph G

source

protected Vertex source

ZERO

protected java.lang.Integer ZERO

INFINITY

protected java.lang.Integer INFINITY

locators

protected java.util.Hashtable locators

treeWeight

protected int treeWeight

Constructor Detail

IntegerPrimTemplate

public IntegerPrimTemplate()

Method Detail

weight

protected abstract int weight(Edge e)

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.

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)

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.

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

vertexNotReachable

protected void vertexNotReachable(Vertex v)

Can be overridden in any application that involves unreachable vertices. Called every time a vertex with distance INFINITY comes off the priority queue. When it has been called once, it should subsequently be called for all remaining vertices, until the priority queue is empty.

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.

Parameters:

v - Vertex which the algorithm just found to be unreachable from the source

relaxingEdge

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. Called every time an edge leading to a vertex is examined (relaxed); this can happen many times per vertex. If uvweight is less than vdist, then uv is a better tree edge to v than the best edge to v previously known, so v is updated in the priority queue. This method notifies you before such a calculation is made, whether the calculation results in an update or not.

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

Parameters:

u - Vertex about to be finished, from which an edge to v is being explored

uv - Edge being explored

uvweight - Weight of uv

v - Vertex being investigated: the best-known-edge to it will be updated if the uv is a better edge

vdist - The present, possibly suboptimal, distance of v from the partially built spanning tree

shouldContinue

protected boolean shouldContinue()

Can be overridden in any application where the full minimum spanning tree is not needed and the algorithm should terminate early. executeAll(.) checks the return from this method before each call to doOneIteration(). The default implementation just returns 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.

Returns:

Whether to continue running the algorithm

setLocator

protected void setLocator(Vertex u,
                          Locator ulocInPQ)

Can be overridden to supply a way of storing and retrieving one locator per vertex. Will be called exactly once per vertex, during initialization. The default implementation uses the java.util.Hashtable initialized by initMap() to store one locator per vertex.

Parameters:

u - Vertex to label with a locator

ulocInPQ - the label

See Also:

getLocator(Vertex), initMap()

getLocator

protected Locator getLocator(Vertex u)

Can be overridden to supply a way of storing and retrieving one locator per vertex. This is the counterpart to setLocator(.) but may be called many times. The default implementation queries the java.util.Hashtable mentioned in setLocator(.). The algorithm calls this method whenever it needs to update the best distance it knows for a vertex, which requires updating the priority queue.

Parameters:

u - Vertex previously labeled with a locator

Returns:

Locator associated with u in the earlier setLocator(.) call

See Also:

setLocator(Vertex,Locator)

newPQ

protected PriorityQueue newPQ()

Can be overridden to supply a priority queue of your choosing, but the default implementation, which gives an empty nz.ac.waikato.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.

Returns:

PriorityQueue to be used by the algorithm

initMap

protected void initMap()

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.

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.

incidentEdges

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. 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
return G.incidentEdges( v, EdgeDirection.UNDIR );

Parameters:

v - Vertex soon to be finished by the algorithm

Returns:

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

destination

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. 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 origin and needs all its adjacent vertices.

Parameters:

origin - Vertex soon to be finished by the algorithm

e - Edge incident on origin according to incidentEdges(.)

Returns:

the vertex opposite origin along e

allVertices

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. Note that overriding this method will probably also require overriding incidentEdges(.), in order to avoid edges leading to vertices not in the subset.

Returns:

Iterator over all vertices to be initially put in the priority queue and eventually finished by the algorithm

badWeight

protected int badWeight(Vertex u,
                        Edge uv,
                        int uvweight)

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.

Parameters:

u - Vertex being finished when the bad weight was discovered

uv - Edge for which weight(uv) returned a zero or negative value

uvweight - The weight returned from weight(uv)

Returns:

Weight the algorithm should use for uv (can be equal to uvweight) (the default is to return 0 only if uvweight is 0)

Throws:

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)

init

public 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. 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(.).

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

doOneIteration

public final void doOneIteration()

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.

executeAll

public final void executeAll(InspectableGraph g,
                             Vertex src,
                             int infinity)

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.

executeAll

public final void executeAll(InspectableGraph g,
                             Vertex src)

Just like the other version of executeAll(.), but with infinity=Integer.MAX_VALUE