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 java.lang.Object
For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.
-
-
Constructor Summary
Constructors Constructor Description MinimumSpanningForest(edu.uci.ics.jung.graph.Graph<V,E> graph, edu.uci.ics.jung.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(edu.uci.ics.jung.graph.Graph<V,E> graph, edu.uci.ics.jung.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.MinimumSpanningForest(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections4.Factory<edu.uci.ics.jung.graph.Forest<V,E>> factory, V root, java.util.Map<E,java.lang.Double> weights)
Creates a Forest from the supplied Graph and supplied Factory, which is used to create a new, empty Forest.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description edu.uci.ics.jung.graph.Forest<V,E>
getForest()
Returns the generated forest.protected void
updateForest(java.util.Collection<V> tv, java.util.Collection<E> unfinishedEdges)
-
-
-
Constructor Detail
-
MinimumSpanningForest
public MinimumSpanningForest(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections4.Factory<edu.uci.ics.jung.graph.Forest<V,E>> factory, V root, java.util.Map<E,java.lang.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 graphfactory
- the factory 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(edu.uci.ics.jung.graph.Graph<V,E> graph, edu.uci.ics.jung.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(edu.uci.ics.jung.graph.Graph<V,E> graph, edu.uci.ics.jung.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
-
-