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 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

Modifier and Type	Method	Description
ClusteringAlgorithm.Clustering<V>	getClustering()	Computes a clustering.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

getClustering

public ClusteringAlgorithm.Clustering<V> getClustering()

Description copied from interface: ClusteringAlgorithm

Computes a clustering.

Specified by:

getClustering in interface ClusteringAlgorithm<V>

Returns:

a clustering