Class 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.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected edu.uci.ics.jung.graph.Forest<V,​E> forest  
      protected edu.uci.ics.jung.graph.Graph<V,​E> graph  
      protected java.util.Map<E,​java.lang.Double> weights  
    • 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)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • graph

        protected edu.uci.ics.jung.graph.Graph<V,​E> graph
      • forest

        protected edu.uci.ics.jung.graph.Forest<V,​E> forest
      • weights

        protected java.util.Map<E,​java.lang.Double> weights
    • 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 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​(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 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​(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 in
        forest - the Forest to populate. Must be empty
        root - first Tree root, may be null
    • Method Detail

      • getForest

        public edu.uci.ics.jung.graph.Forest<V,​E> getForest()
        Returns the generated forest.
      • updateForest

        protected void updateForest​(java.util.Collection<V> tv,
                                    java.util.Collection<E> unfinishedEdges)