Module org.jgrapht.core
Package org.jgrapht.alg.clustering

Class KSpanningTreeClustering<V,E>

java.lang.Object
org.jgrapht.alg.clustering.KSpanningTreeClustering<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
ClusteringAlgorithm<V>
public class KSpanningTreeClustering<V,E> extends Object implements ClusteringAlgorithm<V>
The k spanning tree clustering algorithm.

The algorithm finds a minimum spanning tree $T$ using Prim's algorithm, then executes Kruskal's algorithm only on the edges of $T$ until $k$ trees are formed. The resulting trees are the final clusters. The total running time is $O(m + n \log n)$.

The algorithm is strongly related to single linkage cluster analysis, also known as single-link clustering. For more information see: J. C. Gower and G. J. S. Ross. Minimum Spanning Trees and Single Linkage Cluster Analysis. Journal of the Royal Statistical Society. Series C (Applied Statistics), 18(1):54--64, 1969.

Author:
Dimitrios Michail

  • Constructor Details

    • KSpanningTreeClustering

      public KSpanningTreeClustering(Graph<V,E> graph, int k)
      Create a new clustering algorithm.
      Parameters:
      graph - the graph (needs to be undirected)
      k - the desired number of clusters

  • Method Details