@graphty/algorithms / index / hierarchicalClustering
Function: hierarchicalClustering() ​
hierarchicalClustering(
s,options?):HierarchicalResult
Defined in: indexed/hierarchical.ts:138
Agglomerative hierarchical clustering over hop distances, the index-based port of the legacy hierarchicalClustering: every node starts as its own cluster and the closest pair is merged until one cluster remains or no remaining pair is linked by a path.
The distance between two nodes is the BFS hop count over out-arcs (weights are ignored, as the legacy function ignores them); an unreachable pair has none and is left out of every linkage. The distance between two clusters over the member pairs that have one is their minimum (single), maximum (complete), mean (average), or mean times |A| |B| / (|A| + |B|) (ward). A pair with no connected member pair is never merged. On a directed snapshot the distance is taken in one direction, and which one follows the legacy function exactly, as do the tie-breaks: the merges, their order and their distances equal the legacy function's.
One difference in what the result offers: cut descends into every root of a disconnected snapshot, where the legacy clusters map lists all nodes as one cluster at every height (its forest node has no children, so its cut never splits it).
O(n^2) memory for the distance aggregates and O(n^3) time for the pair search; the legacy function is the same order with Map and Set per step.
Parameters ​
s ​
AdjacencyView
Any snapshot or adjacency view
options? ​
HierarchicalOptions = {}
The linkage
Returns ​
The dendrogram