Class MinimumSpanningForest<V,E>

java.lang.Object
edu.uci.ics.jung.algorithms.shortestpath.MinimumSpanningForest<V,E>
Type Parameters:
V - the vertex type
E - the edge type

public class MinimumSpanningForest<V,E> extends Object
For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.
  • Field Details

    • graph

      protected Graph<V,E> graph
    • forest

      protected Forest<V,E> forest
    • weights

      protected com.google.common.base.Function<E,Double> 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 graph
      Supplier - the Supplier 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 Details

    • getForest

      public Forest<V,E> getForest()
      Returns:
      the generated forest
    • updateForest

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