Welcome, guest | Sign In | My Account | Store | Cart

This recipe draws a dendrogram (horizontal format used for evolutionary trees), as ASCII text, given as input a binary tree in the form of a tuple for each tree node. Tree leaves can be any Python object other than a length-2 tuple, and are converted to strings in the output. Tree nodes at the same distance from the root will line up at the same column, with the distance between tree levels controlled by an optional "sep" parameter. The algorithm works by a straightforward inorder traversal, keeping some simple data structures to keep track of the tree edges that need to be drawn on each output line. Its output is via print statements but it could easily be modified to send its output lines to any other kind of stream.

Python, 48 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def printDendrogram(T, sep=3):
    """Print dendrogram of a binary tree.  Each tree node is represented by a length-2 tuple."""
	
    def isPair(T):
        return type(T) == tuple and len(T) == 2
    
    def maxHeight(T):
        if isPair(T):
            h = max(maxHeight(T[0]), maxHeight(T[1]))
        else:
            h = len(str(T))
        return h + sep
        
    activeLevels = {}

    def traverse(T, h, isFirst):
        if isPair(T):
            traverse(T[0], h-sep, 1)
            s = [' ']*(h-sep)
            s.append('|')
        else:
            s = list(str(T))
            s.append(' ')

        while len(s) < h:
            s.append('-')
        
        if (isFirst >= 0):
            s.append('+')
            if isFirst:
                activeLevels[h] = 1
            else:
                del activeLevels[h]
        
        A = list(activeLevels)
        A.sort()
        for L in A:
            if len(s) < L:
                while len(s) < L:
                    s.append(' ')
                s.append('|')

        print ''.join(s)    
        
        if isPair(T):
            traverse(T[1], h-sep, 0)

    traverse(T, maxHeight(T), -1)

Example: <pre>

>>> printDendrogram( ( ( ( 'a' , 'b') , 'c'), ( ( 'd' , 'e' ), ( 'f', 'g' ) ) ) )
</pre>

produces: <pre> a --+ |--+ b --+ | |--+ c -----+ | |-- d --+ | |--+ | e --+ | | |--+ f --+ | |--+ g --+ </pre>

Created by David Eppstein on Sat, 13 Jul 2002 (PSF)
Python recipes (4591)
David Eppstein's recipes (14)

Required Modules

  • (none specified)

Other Information and Tasks