Class PrimMinimumSpanningTree<V,​E>

  • Type Parameters:
    V - the vertex type
    E - the edge type
    All Implemented Interfaces:
    org.apache.commons.collections4.Transformer<edu.uci.ics.jung.graph.Graph<V,​E>,​edu.uci.ics.jung.graph.Graph<V,​E>>

    public class PrimMinimumSpanningTree<V,​E>
    extends java.lang.Object
    implements org.apache.commons.collections4.Transformer<edu.uci.ics.jung.graph.Graph<V,​E>,​edu.uci.ics.jung.graph.Graph<V,​E>>
    For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,​E>> treeFactory  
      protected org.apache.commons.collections4.Transformer<E,​java.lang.Double> weights  
    • Constructor Summary

      Constructors 
      Constructor Description
      PrimMinimumSpanningTree​(org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,​E>> factory)
      Creates an instance which generates a minimum spanning tree assuming constant edge weights.
      PrimMinimumSpanningTree​(org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,​E>> factory, org.apache.commons.collections4.Transformer<E,​java.lang.Double> weights)
      Creates an instance which generates a minimum spanning tree using the input edge weights.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected V findRoot​(edu.uci.ics.jung.graph.Graph<V,​E> graph)  
      edu.uci.ics.jung.graph.Graph<V,​E> transform​(edu.uci.ics.jung.graph.Graph<V,​E> graph)  
      protected void updateTree​(edu.uci.ics.jung.graph.Graph<V,​E> tree, edu.uci.ics.jung.graph.Graph<V,​E> graph, 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

      • treeFactory

        protected org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,​E>> treeFactory
      • weights

        protected org.apache.commons.collections4.Transformer<E,​java.lang.Double> weights
    • Constructor Detail

      • PrimMinimumSpanningTree

        public PrimMinimumSpanningTree​(org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,​E>> factory)
        Creates an instance which generates a minimum spanning tree assuming constant edge weights.
      • PrimMinimumSpanningTree

        public PrimMinimumSpanningTree​(org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,​E>> factory,
                                       org.apache.commons.collections4.Transformer<E,​java.lang.Double> weights)
        Creates an instance which generates a minimum spanning tree using the input edge weights.
    • Method Detail

      • transform

        public edu.uci.ics.jung.graph.Graph<V,​E> transform​(edu.uci.ics.jung.graph.Graph<V,​E> graph)
        Specified by:
        transform in interface org.apache.commons.collections4.Transformer<V,​E>
        Parameters:
        graph - the Graph to find MST in
      • findRoot

        protected V findRoot​(edu.uci.ics.jung.graph.Graph<V,​E> graph)
      • updateTree

        protected void updateTree​(edu.uci.ics.jung.graph.Graph<V,​E> tree,
                                  edu.uci.ics.jung.graph.Graph<V,​E> graph,
                                  java.util.Collection<E> unfinishedEdges)