I have written from scratch (with Fortran) my own implementation of the Ward algorithm to perform HC. The output of the program consists of two elements: a vector with the distance after each step, and a square matrix in which each row shows the list of indices that indicates to which cluster the element belongs (when two clusters merge, all elements are labelled with the number of the lower label). For instance, the first row is 1, 2, 3, ... N, and the last one is 1, 1, ... 1.

Now, the algorithm seems to work so far, but I'd like to plot also the dendrogram. As I'm using basic tools that basically allow me to draw lines, my idea is to create an additional output file containing the coordinates of the N-1 lines that make up the tree. Obtaining the coordinates is rather easy once you know the right order of elements that lead to non-crossing trees and the distances. But what I miss is how to obtain such order.

I though this should be explained somewhere, as it seems a basic part of every HC method, but surprisingly Google just took me to webs where they explain how to read dendrograms, not how to build them. To be 100% honest, I found this link, but unfortunately I can not rebuild the algorithm from the code they post.

Can anyone help me to find a suitable algorithm to build the dendrogram?

  • $\begingroup$ I think "walking the hierarchical tree from top to bottom" in your linked post is close to equivalent to simply sorting your square matrix from your right most column to your left-most one. $\endgroup$ – Andy W Aug 11 '17 at 14:23