Class MinimumSpanningForest<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.shortestpath.MinimumSpanningForest<V,E>
-
- Type Parameters:
V
- the vertex typeE
- the edge type
public class MinimumSpanningForest<V,E> extends java.lang.Object
For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.- Author:
- Tom Nelson - tomnelson@dev.java.net
-
-
Constructor Summary
Constructors Constructor Description MinimumSpanningForest(Graph<V,E> graph, com.google.common.base.Supplier<Forest<V,E>> Supplier, V root, java.util.Map<E,java.lang.Double> weights)
Creates a Forest from the supplied Graph and supplied Supplier, 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, java.util.Map<E,java.lang.Double> weights)
Creates a minimum spanning forest from the supplied graph, populating the supplied Forest, which must be empty.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Forest<V,E>
getForest()
protected void
updateForest(java.util.Collection<V> tv, java.util.Collection<E> unfinishedEdges)
-
-
-
Constructor Detail
-
MinimumSpanningForest
public MinimumSpanningForest(Graph<V,E> graph, com.google.common.base.Supplier<Forest<V,E>> Supplier, V root, java.util.Map<E,java.lang.Double> weights)
Creates a Forest from the supplied Graph and supplied Supplier, 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 graphSupplier
- the Supplier to use to create the new forestroot
- the vertex of the graph to be used as the root of the forestweights
- edge weights
-
MinimumSpanningForest
public MinimumSpanningForest(Graph<V,E> graph, Forest<V,E> forest, V root, java.util.Map<E,java.lang.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 inforest
- the Forest to populate. Must be emptyroot
- first Tree root, may be nullweights
- 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 inforest
- the Forest to populate. Must be emptyroot
- first Tree root, may be null
-
-