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
For the input Graph, creates a MinimumSpanningTree
using a variation of Prim's algorithm.
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionMinimumSpanningForest
(Graph<V, E> graph, com.google.common.base.Supplier<Forest<V, E>> Supplier, V root, Map<E, Double> weights) Creates a Forest from the supplied Graph and supplied Supplier, which is used to create a new, empty Forest.Creates a minimum spanning forest from the supplied graph, populating the supplied Forest, which must be empty.Creates a minimum spanning forest from the supplied graph, populating the supplied Forest, which must be empty. -
Method Summary
Modifier and TypeMethodDescriptionprotected void
updateForest
(Collection<V> tv, Collection<E> unfinishedEdges)
-
Field Details
-
graph
-
forest
-
weights
-
-
Constructor Details
-
MinimumSpanningForest
public MinimumSpanningForest(Graph<V, E> graph, com.google.common.base.Supplier<Forest<V, E>> Supplier, V root, Map<E, 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
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
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
-
-
Method Details
-
getForest
- Returns:
- the generated forest
-
updateForest
-