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 typeE
- 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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ClusteringAlgorithm
ClusteringAlgorithm.Clustering<V>, ClusteringAlgorithm.ClusteringImpl<V>
-
-
Constructor Summary
Constructors Constructor Description KSpanningTreeClustering(Graph<V,E> graph, int k)
Create a new clustering algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description ClusteringAlgorithm.Clustering<V>
getClustering()
Computes a clustering.
-
-
-
Method Detail
-
getClustering
public ClusteringAlgorithm.Clustering<V> getClustering()
Description copied from interface:ClusteringAlgorithm
Computes a clustering.- Specified by:
getClustering
in interfaceClusteringAlgorithm<V>
- Returns:
- a clustering
-
-