Getting a dendrogram's branch lengths in a breadth-first-search order

Question

Is there any R function to retrieve the branch lengths of a dendrogram:

set.seed(1)
mat <- matrix(rnorm(100*10),nrow=100,ncol=10)
dend <- as.dendrogram(hclust(dist(t(mat))))

in a breadth-first-search order?

For dend I'd like to get this result:

c(16.38688,15.41441,15.99504,14.68365,13.52949,14.39275,12.96921,13.91157,13.15395)

which is node depths (excluding leaves) ordered by bps.

Thanks

Answer 1

The data:

set.seed(1)
mat <- matrix(rnorm(100*10),nrow=100,ncol=10)
dend <- as.dendrogram(hclust(dist(t(mat))))    

Using the data.tree package allows traversing trees in various orders. level will give what the question specifies:

require(data.tree)
dend.dt <- as.Node(dend)
sapply(Traverse(dend.dt,traversal = "level", pruneFun = isNotLeaf),function(x) x$plotHeight)
[1] 16.38688 15.41441 15.99504 14.68365 13.52949 14.39275 12.96921 13.91157 13.15395

Answer 2

You can easily code one like this:

dendro_depth <- function(dendro){
  if(!is.null(attributes(dendro)$leaf))
    0
  else
    max(dendro_depth(dendro[[1]]),dendro_depth(dendro[[2]])) +1
}

Answer 3

See get_branches_heights from dendextend.

set.seed(1)
mat <- matrix(rnorm(100*10),nrow=100,ncol=10)
dend <- as.dendrogram(hclust(dist(t(mat))))

library(dendextend)
get_branches_heights(dend, sort = F)

It does not seem to be exactly in the order youu want, but see if this is still useful:

> get_branches_heights(dend, sort = F)
[1] 16.38688 15.41441 14.68365 15.99504 13.52949
[6] 12.96921 14.39275 13.91157 13.15395

BTW, the recent github version of dendextend also comes with the highlight_branches function for coloring branches based on branch height (in case this is somehow related to your motivation):

plot(highlight_branches(dend))