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

Class 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

    • Constructor Detail

      • 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