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 java.lang.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