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

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.shortestpath.MinimumSpanningForest2<V,E>
Type Parameters:
V -
E -

public class MinimumSpanningForest2<V,E>
extends Object

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

Author:
Tom Nelson - tomnelson@dev.java.net

Field Summary
protected  Forest<V,E> forest
           
protected  Graph<V,E> graph
           
protected  org.apache.commons.collections15.Transformer<E,Double> weights
           
 
Constructor Summary
MinimumSpanningForest2(Graph<V,E> graph, org.apache.commons.collections15.Factory<Forest<V,E>> factory, org.apache.commons.collections15.Factory<? extends Graph<V,E>> treeFactory, org.apache.commons.collections15.Transformer<E,Double> weights)
          create a Forest from the supplied Graph and supplied Factory, which is used to create a new, empty Forest.
MinimumSpanningForest2(Graph<V,E> graph, Forest<V,E> forest, org.apache.commons.collections15.Factory<? extends Graph<V,E>> treeFactory, org.apache.commons.collections15.Transformer<E,Double> weights)
          create a forest from the supplied graph, populating the supplied Forest, which must be empty.
 
Method Summary
 Forest<V,E> getForest()
          Returns the generated forest.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

graph

protected Graph<V,E> graph

forest

protected Forest<V,E> forest

weights

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

MinimumSpanningForest2

public MinimumSpanningForest2(Graph<V,E> graph,
                              org.apache.commons.collections15.Factory<Forest<V,E>> factory,
                              org.apache.commons.collections15.Factory<? extends Graph<V,E>> treeFactory,
                              org.apache.commons.collections15.Transformer<E,Double> weights)
create a Forest from the supplied Graph and supplied Factory, which is used to create a new, empty Forest. If non-null, the supplied root will be used as the root of the tree/forest. If the supplied root is null, or not present in the Graph, then an arbitary Graph vertex will be selected as the root. If the Minimum Spanning Tree does not include all vertices of the Graph, then a leftover vertex is selected as a root, and another tree is created

Parameters:
graph -
factory -
weights -

MinimumSpanningForest2

public MinimumSpanningForest2(Graph<V,E> graph,
                              Forest<V,E> forest,
                              org.apache.commons.collections15.Factory<? extends Graph<V,E>> treeFactory,
                              org.apache.commons.collections15.Transformer<E,Double> weights)
create a forest from the supplied graph, populating the supplied Forest, which must be empty. If the supplied root is null, or not present in the Graph, then an arbitary Graph vertex will be selected as the root. If the Minimum Spanning Tree does not include all vertices of the Graph, then a leftover vertex is selected as a root, and another tree is created

Parameters:
graph - the Graph to find MST in
forest - the Forest to populate. Must be empty
weights - edge weights, may be null
Method Detail

getForest

public Forest<V,E> getForest()
Returns the generated forest.



Copyright © 2009. All Rights Reserved.