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

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

Type Parameters:

V -

E -

public class MinimumSpanningForest<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 Map<E,Double>	weights

Constructor Summary

MinimumSpanningForest(Graph<V,E> graph, org.apache.commons.collections15.Factory<Forest<V,E>> factory, V root, Map<E,Double> weights)
Creates a Forest from the supplied Graph and supplied Factory, which is used to create a new, empty Forest.

MinimumSpanningForest(Graph<V,E> graph, Forest<V,E> forest, V root)
Creates a minimum spanning forest from the supplied graph, populating the supplied Forest, which must be empty.

MinimumSpanningForest(Graph<V,E> graph, Forest<V,E> forest, V root, Map<E,Double> weights)
Creates a minimum spanning forest from the supplied graph, populating the supplied Forest, which must be empty.

Method Summary

Forest<V,E>	getForest() Returns the generated forest.
protected void	updateForest(Collection<V> tv, Collection<E> unfinishedEdges)

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 Map<E,Double> weights

Constructor Detail

MinimumSpanningForest

public MinimumSpanningForest(Graph<V,E> graph,
                             org.apache.commons.collections15.Factory<Forest<V,E>> factory,
                             V root,
                             Map<E,Double> weights)

Creates 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 arbitrary 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 input graph

factory - the factory to use to create the new forest

root - the vertex of the graph to be used as the root of the forest

weights - edge weights

MinimumSpanningForest

public MinimumSpanningForest(Graph<V,E> graph,
                             Forest<V,E> forest,
                             V root,
                             Map<E,Double> weights)

Creates a minimum spanning 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 arbitrary 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

root - first Tree root, may be null

weights - edge weights, may be null

MinimumSpanningForest

public MinimumSpanningForest(Graph<V,E> graph,
                             Forest<V,E> forest,
                             V root)

Creates a minimum spanning 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 arbitrary 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

root - first Tree root, may be null

Method Detail

getForest

public Forest<V,E> getForest()

Returns the generated forest.

updateForest

protected void updateForest(Collection<V> tv,
                            Collection<E> unfinishedEdges)