edu.uci.ics.jung.algorithms.shortestpath
Class PrimMinimumSpanningTree<V,E>

java.lang.Object
  edu.uci.ics.jung.algorithms.shortestpath.PrimMinimumSpanningTree<V,E>

Type Parameters:

V - the vertex type

E - the edge type

All Implemented Interfaces:

org.apache.commons.collections15.Transformer<Graph<V,E>,Graph<V,E>>

public class PrimMinimumSpanningTree<V,E>
extends Object
implements org.apache.commons.collections15.Transformer<Graph<V,E>,Graph<V,E>>

For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.

Author:

Tom Nelson - tomnelson@dev.java.net

Field Summary

protected org.apache.commons.collections15.Factory<? extends Graph<V,E>>	treeFactory
protected org.apache.commons.collections15.Transformer<E,Double>	weights

Constructor Summary

PrimMinimumSpanningTree(org.apache.commons.collections15.Factory<? extends Graph<V,E>> factory)
Creates an instance which generates a minimum spanning tree assuming constant edge weights.

PrimMinimumSpanningTree(org.apache.commons.collections15.Factory<? extends Graph<V,E>> factory, org.apache.commons.collections15.Transformer<E,Double> weights)
Creates an instance which generates a minimum spanning tree using the input edge weights.

Method Summary

protected V	findRoot(Graph<V,E> graph)
Graph<V,E>	transform(Graph<V,E> graph)
protected void	updateTree(Graph<V,E> tree, Graph<V,E> graph, Collection<E> unfinishedEdges)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

treeFactory

protected org.apache.commons.collections15.Factory<? extends Graph<V,E>> treeFactory

weights

protected org.apache.commons.collections15.Transformer<E,Double> weights

Constructor Detail

PrimMinimumSpanningTree

public PrimMinimumSpanningTree(org.apache.commons.collections15.Factory<? extends Graph<V,E>> factory)

Creates an instance which generates a minimum spanning tree assuming constant edge weights.

PrimMinimumSpanningTree

public PrimMinimumSpanningTree(org.apache.commons.collections15.Factory<? extends Graph<V,E>> factory,
                               org.apache.commons.collections15.Transformer<E,Double> weights)

Creates an instance which generates a minimum spanning tree using the input edge weights.

Method Detail

transform

public Graph<V,E> transform(Graph<V,E> graph)

Specified by:

transform in interface org.apache.commons.collections15.Transformer<Graph<V,E>,Graph<V,E>>

Parameters:

graph - the Graph to find MST in

findRoot

protected V findRoot(Graph<V,E> graph)

updateTree

protected void updateTree(Graph<V,E> tree,
                          Graph<V,E> graph,
                          Collection<E> unfinishedEdges)