hierarchical-clustering-0.4.7: Fast algorithms for single, average/UPGMA and complete linkage clustering.

Safe Haskell | Safe-Inferred
Language | Haskell98

Data.Clustering.Hierarchical.Internal.Optimal

Description

Implementations that are optimal in space and time.

Synopsis

- singleLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a
- completeLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a

# Documentation

singleLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a Source #

O(n^2) time and O(n) space. Calculates a complete, rooted dendrogram for a list of items using single linkage with the SLINK algorithm. This algorithm is optimal in space and time.

Reference
  R. Sibson (1973). "SLINK: an optimally efficient algorithm for the single-link cluster method". The Computer Journal (British Computer Society) 16 (1): 30-34.

completeLinkage :: [a] -> (a -> a -> Distance) -> Dendrogram a Source #

O(n^2) time and O(n) space. Calculates a complete, rooted dendrogram for a list of items using complete linkage with the CLINK algorithm. This algorithm is optimal in space and time.

Reference
  D. Defays (1977). "An efficient algorithm for a complete link method". The Computer Journal (British Computer Society) 20 (4): 364-366.