Class PrimMinimumSpanningTree<V,E>

java.lang.Object
edu.uci.ics.jung.algorithms.shortestpath.PrimMinimumSpanningTree<V,E>
Type Parameters:
V - the vertex type
E - the edge type
All Implemented Interfaces:
com.google.common.base.Function<Graph<V,E>,Graph<V,E>>, Function<Graph<V,E>,Graph<V,E>>

public class PrimMinimumSpanningTree<V,E> extends Object implements com.google.common.base.Function<Graph<V,E>,Graph<V,E>>
For the input Graph, creates a MinimumSpanningTree using a variation of Prim's algorithm.
  • Field Details

    • treeFactory

      protected com.google.common.base.Supplier<? extends Graph<V,E>> treeFactory
    • weights

      protected com.google.common.base.Function<? super E,Double> weights
  • Constructor Details

    • PrimMinimumSpanningTree

      public PrimMinimumSpanningTree(com.google.common.base.Supplier<? extends Graph<V,E>> supplier)
      Creates an instance which generates a minimum spanning tree assuming constant edge weights.
      Parameters:
      supplier - used to create the tree instances
    • PrimMinimumSpanningTree

      public PrimMinimumSpanningTree(com.google.common.base.Supplier<? extends Graph<V,E>> supplier, com.google.common.base.Function<? super E,Double> weights)
      Creates an instance which generates a minimum spanning tree using the input edge weights.
      Parameters:
      supplier - used to create the tree instances
      weights - the edge weights to use for defining the MST
  • Method Details

    • apply

      public Graph<V,E> apply(Graph<V,E> graph)
      Specified by:
      apply in interface com.google.common.base.Function<V,E>
      Specified by:
      apply in interface Function<V,E>
      Parameters:
      graph - the Graph to find MST in
    • findRoot

      protected V findRoot(Graph<V,E> graph)
    • updateTree

      protected void updateTree(Graph<V,E> tree, Graph<V,E> graph, Collection<E> unfinishedEdges)