PyTree: A Generic Tree Object Viewer

PyTree A Generic Tree Object Viewer

Up to now, this chapter has been command-line-oriented. To wrap up, I want to show you a program that merges the GUI technology we studied earlier in the book with some of the data structure ideas we've met in this chapter.

This program is called PyTree, a generic tree data structure viewer written in Python with the Tkinter GUI library. PyTree sketches out the nodes of a tree on screen as boxes connected by arrows. It also knows how to route mouseclicks on drawn tree nodes back to the tree, to trigger tree-specific actions. Because PyTree lets you visualize the structure of the tree generated by a set of parameters, it's a fun way explore tree-based algorithms.

PyTree supports arbitrary tree types by "wrapping" real trees in interface objects. The interface objects implement a standard protocol by communicating with the underlying tree object. For the purposes of this chapter, PyTree is instrumented to display binary search trees ; for the next chapter, it's also set up to render expression parse trees. New trees can be viewed by coding wrapper classes to interface to new tree types.

The GUI interfaces PyTree utilizes were covered in depth earlier in this book, so I won't go over this code in much detail here. See Part II, for background details, and be sure to run this program on your own computer to get a better feel for its operation. Because it is written with Python and Tkinter, it should be portable to Windows, Unix, and Macs.

17.10.1 Running PyTree

Before we get to the code, let's see what PyTree looks like. You can launch PyTree from the PyDemos launcher bar (see the top-level of the examples distribution source tree at http://examples.oreilly.com/python2), or by directly running the treeview.py file listed in Example 17-27. Figure 17-2 shows PyTree in action displaying the binary tree created by the "test1" button. Trees are sketched as labels embedded in a canvas, and connected by lines with arrows. The lines reflect parent-to-child relationships in the actual tree; PyTree attempts to layout the tree to produce a more or less uniform display like this one.

Figure 17-2. PyTree viewing a binary search tree (test1)

PyTree's window consists of a canvas with vertical and horizontal scrolls, and a set of controls at the bottom -- radiobuttons for picking the type of tree you wish to display, a set of buttons that trigger canned tree drawing tests, and an input field for typing text to specify and generate a new tree. The set of test buttons changes if you pick the Parser radiobutton (you get one less test button); PyTree use widget pack_forget and pack methods to hide and show tree-specific buttons on the fly.

When you pick one of the canned test buttons, it displays in the input field the string you would type to generate the tree drawn. For binary trees, type a list of values separated by spaces and press the "input" button or the Enter key to generate a new tree; the new tree is the result of inserting the typed values from left to right. For parse trees, you input an expression string in the input field instead (more on this later). Figure 17-3 shows the result of typing a set of values into the input field and submitting; the resulting binary tree shows up in the canvas.

Figure 17-3. A binary tree typed manually with on-click pop-up

Notice the pop-up in this screen shot; left-clicking on a displayed tree node with your mouse runs whatever action a tree wrapper class defines, and displays its result in the pop-up. Binary trees have no action to run, so we get a default message in the pop-up, but parse tress use the mouseclick to evaluate the subtree rooted at the clicked node (again, more on parse trees later).

Just for fun, maximize this window and press the "test4" button -- it inserts 100 numbers from through 99 into a new binary tree at random, and displays the result. Figure 17-4 captures one portion of this tree; it's much too large to fit on one screen (or on one book page), but you can move around the tree with the canvas scrollbars.

Figure 17-4. PyTree viewing a large binary search tree (test4)

PyTree uses an algorithm to connect all parents to their children in this tree without crossing their connecting lines. It does some up-front analysis to try and arrange descendents at each level to be as close to their parents as possible. This analysis step also yields the overall size of a new tree -- PyTree uses it to reset the scrollable area size of the canvas for each tree drawn.

17.10.2 Pytree Source Code

Let's move on to the code. Similar to PyForm in the prior chapter, PyTree is coded as two modules; here, one module handles the task of sketching trees in the GUI, and another implements wrappers to interface to various tree types and extends the GUI with extra widgets.

17.10.2.1 Tree-independent GUI implementation

The module in Example 17-26 does the work of drawing trees in a canvas. It's coded to be independent of any particular tree structure -- its TreeViewer class delegates to its TreeWrapper class when it needs tree-specific information for the drawing (e.g., node label text, node child links). TreeWrapper in turn expects to be subclassed for a specific kind of tree; in fact it raises assertion errors if you try to use it without subclassing. In design terms, TreeViewer embeds a TreeWrapper; it's almost as easy to code TreeViewer subclasses per tree type, but that limits a viewer GUI to one particular kind of tree (see treeview_subclasses.py at http://examples.oreilly.com/python2 for a subclassing-based alternative).

Trees are drawn in two steps -- a planning traversal the builds a layout data structure that links parents and children, and a drawing step that uses the generated plan to draw and link node labels on the canvas. The two-step approach simplifies some of the logic required to layout trees uniformly. Study this listing for more details.

Example 17-26. PP2EDstructTreeView reeview_wrappers.py

#########################################################################
# PyTree: sketch arbitrary tree data structures in a scrolled canvas;
# this version uses tree wrapper classes embedded in the viewer gui 
# to support arbitrary trees (i.e.. composition, not viewer subclassing);
# also adds tree node label click callbacks--run tree specific actions;
# see treeview_subclasses.py for subclass-based alternative structure;
# subclassing limits one tree viewer to one tree type, wrappers do not;
# see treeview_left.py for an alternative way to draw the tree object;
# see and run treeview.py for binary and parse tree wrapper test cases;
#########################################################################

from Tkinter import *
from tkMessageBox import showinfo

Width, Height = 350, 350 # start canvas size (reset per tree)
Rowsz = 100 # pixels per tree row
Colsz = 100 # pixels per tree col

###################################
# interface to tree object's nodes
###################################

class TreeWrapper: # subclass for a tree type
 def children(self, treenode):
 assert 0, 'children method must be specialized for tree type'
 def label(self, treenode):
 assert 0, 'label method must be specialized for tree type'
 def value(self, treenode):
 return ''
 def onClick(self, treenode): # node label click callback
 return ''
 def onInputLine(self, line, viewer): # input line sent callback
 pass

###########$######################
# tree view gui, tree independent
##################################

class TreeViewer(Frame):
 def __init__(self, wrapper, parent=None, tree=None, bg='brown', fg='beige'):
 Frame.__init__(self, parent)
 self.pack(expand=YES, fill=BOTH)
 self.makeWidgets(bg) # build gui: scrolled canvas
 self.master.title('PyTree 1.0') # assume I'm run standalone
 self.wrapper = wrapper # embed a TreeWrapper object
 self.fg = fg # setTreeType changes wrapper 
 if tree:
 self.drawTree(tree)

 def makeWidgets(self, bg):
 self.title = Label(self, text='PyTree 1.0')
 self.canvas = Canvas(self, bg=bg, borderwidth=0)
 vbar = Scrollbar(self)
 hbar = Scrollbar(self, orient='horizontal')

 self.title.pack(side=TOP, fill=X)
 vbar.pack(side=RIGHT, fill=Y) # pack canvas after bars
 hbar.pack(side=BOTTOM, fill=X)
 self.canvas.pack(side=TOP, fill=BOTH, expand=YES)

 vbar.config(command=self.canvas.yview) # call on scroll move
 hbar.config(command=self.canvas.xview)
 self.canvas.config(yscrollcommand=vbar.set) # call on canvas move
 self.canvas.config(xscrollcommand=hbar.set)
 self.canvas.config(height=Height, width=Width) # viewable area size

 def clearTree(self):
 mylabel = 'PyTree 1.0 - ' + self.wrapper.__class__.__name__
 self.title.config(text=mylabel)
 self.unbind_all('')
 self.canvas.delete('all') # clear events, drawing

 def drawTree(self, tree):
 self.clearTree( )
 wrapper = self.wrapper
 levels, maxrow = self.planLevels(tree, wrapper)
 self.canvas.config(scrollregion=( # scrollable area
 0, 0, (Colsz * maxrow), (Rowsz * len(levels)) )) # upleft, lowright
 self.drawLevels(levels, maxrow, wrapper)

 def planLevels(self, root, wrap):
 levels = []
 maxrow = 0 # traverse tree to 
 currlevel = [(root, None)] # layout rows, cols
 while currlevel:
 levels.append(currlevel)
 size = len(currlevel)
 if size > maxrow: maxrow = size
 nextlevel = []
 for (node, parent) in currlevel:
 if node != None:
 children = wrap.children(node) # list of nodes
 if not children:
 nextlevel.append((None, None)) # leave a hole
 else:
 for child in children:
 nextlevel.append((child, node)) # parent link
 currlevel = nextlevel
 return levels, maxrow

 def drawLevels(self, levels, maxrow, wrap):
 rowpos = 0 # draw tree per plan
 for level in levels: # set click handlers
 colinc = (maxrow * Colsz) / (len(level) + 1) # levels is treenodes
 colpos = 0
 for (node, parent) in level:
 colpos = colpos + colinc
 if node != None:
 text = wrap.label(node)
 more = wrap.value(node)
 if more: text = text + '=' + more
 win = Label(self.canvas, text=text, 
 bg=self.fg, bd=3, relief=RAISED)
 win.pack( )
 win.bind('', 
 lambda e, n=node, handler=self.onClick: handler(e, n))
 self.canvas.create_window(colpos, rowpos, anchor=NW, 
 window=win, width=Colsz*.5, height=Rowsz*.5)
 if parent != None:
 self.canvas.create_line(
 parent.__colpos + Colsz*.25, # from x-y, to x-y
 parent.__rowpos + Rowsz*.5,
 colpos + Colsz*.25, rowpos, arrow='last', width=1)
 node.__rowpos = rowpos
 node.__colpos = colpos # mark node, private attrs
 rowpos = rowpos + Rowsz

 def onClick(self, event, node):
 label = event.widget
 wrap = self.wrapper
 text = 'Label = ' + wrap.label(node) # on label click
 value = wrap.value(node)
 if value: 
 text = text + '
Value = ' + value # add tree text if any
 result = wrap.onClick(node) # run tree action if any
 if result:
 text = text + '
' + result # add action result
 showinfo('PyTree', text) # popup std dialog

 def onInputLine(self, line): # feed text to tree wrapper
 self.wrapper.onInputLine(line, self) # ex: parse and redraw tree

 def setTreeType(self, newTreeWrapper): # change tree type drawn
 if self.wrapper != newTreeWrapper: # effective on next draw
 self.wrapper = newTreeWrapper
 self.clearTree( ) # else old node, new wrapper

17.10.2.2 Tree wrappers and test widgets

The other half of PyTree consists of a module that defines TreeWrapper subclasses that interface to binary and parser trees, implements canned test case buttons, and adds the control widgets to the bottom of the PyTree window.[4] These control widgets were split off into this separate module (in Example 17-27) on purpose, because the PyTree canvas might be useful as a viewer component in other GUI applications.

[4] If you're looking for a coding exercise, try adding another wrapper class and radiobutton to view the KeyedBinaryTree we wrote earlier in this chapter. You'll probably want to display the key in the GUI, and pop up the associated value on clicks.

Example 17-27. PP2EDstructTreeView reeview.py

# PyTree launcher script
# wrappers for viewing tree types in the book, plus test cases/gui

import string
from Tkinter import *
from treeview_wrappers import TreeWrapper, TreeViewer
from PP2E.Dstruct.Classics import btree
from PP2E.Lang.Parser import parser2

###################################################################
# binary tree wrapper
###################################################################

class BinaryTreeWrapper(TreeWrapper): # embed binary tree in viewer
 def children(self, node): # adds viewer protocols
 try: # to interface with tree
 return [node.left, node.right]
 except: 
 return None
 def label(self, node):
 try: 
 return str(node.data)
 except: 
 return str(node)
 def onInputLine(self, line, viewer): # on test entry at bottom
 items = string.split(line) # make tree from text input
 t = btree.BinaryTree( ) # draw resulting btree
 for x in items: t.insert(x) # no onClick handler here
 viewer.drawTree(t.tree)

###################################################################
# binary tree extension
###################################################################

class BinaryTree(btree.BinaryTree):
 def __init__(self, viewer): # embed viewer in tree
 btree.BinaryTree.__init__(self) # but viewer has a wrapper
 self.viewer = viewer
 def view(self):
 self.viewer.drawTree(self.tree)

###################################################################
# parse tree wrapper
###################################################################

class ParseTreeWrapper(TreeWrapper):
 def __init__(self): # embed parse tree in viewer
 self.dict = {} # adds viewer protocols
 def children(self, node):
 try:
 return [node.left, node.right]
 except:
 try:
 return [node.var, node.val]
 except: 
 return None
 def label(self, node):
 for attr in ['label', 'num', 'name']:
 if hasattr(node, attr):
 return str(getattr(node, attr))
 return 'set'
 def onClick(self, node): # on tree label click
 try: # tree-specific action
 result = node.apply(self.dict) # evaluate subtree
 return 'Value = ' + str(result) # show result in popup
 except:
 return 'Value = '
 def onInputLine(self, line, viewer): # on input line
 p = parser2.Parser( ) # parse expr text
 p.lex.newtext(line) # draw resulting tree
 t = p.analyse( )
 if t: viewer.drawTree(t)

###################################################################
# canned test cases (or type new nodelists/exprs in input field)
###################################################################

def shownodes(sequence):
 sequence = map(str, sequence) # convert nodes to strings
 entry.delete(0, END) # show nodes in text field
 entry.insert(0, string.join(sequence, ' '))

def test1_binary( ): # tree type is binary wrapper
 nodes = [3, 1, 9, 2, 7] # make a binary tree
 tree = BinaryTree(viewer) # embed viewer in tree
 for i in nodes: tree.insert(i) 
 shownodes(nodes) # show nodes in input field
 tree.view( ) # sketch tree via embedded viewer

def test2_binary( ):
 nodes = 'badce'
 tree = btree.BinaryTree( ) # embed wrapper in viewer
 for c in nodes: tree.insert(c) # make a binary tree
 shownodes(nodes)
 viewer.drawTree(tree.tree) # ask viewer to draw it

def test3_binary( ):
 nodes = 'abcde'
 tree = BinaryTree(viewer)
 for c in nodes: tree.insert(c)
 shownodes(nodes)
 tree.view( )

def test4_binary( ):
 tree = BinaryTree(viewer)
 import random # make a big binary tree
 nodes = range(100) # insert 100 nodes at random
 order = [] # and sketch in viewer
 while nodes:
 item = random.choice(nodes)
 nodes.remove(item)
 tree.insert(item)
 order.append(item)
 shownodes(order)
 tree.view( )

def test_parser(expr):
 parser = parser2.Parser( ) # tree type is parser wrapper
 parser.lex.newtext(expr) # subtrees evaluate when clicked
 tree = parser.analyse( ) # input line parses new expr
 entry.delete(0, END) # vars set in wrapper dictionary
 entry.insert(0, expr) # see lang/text chapter for parser
 if tree: viewer.drawTree(tree)

def test1_parser( ): test_parser("1 + 3 * (2 * 3 + 4)") 
def test2_parser( ): test_parser("set temp 1 + 3 * 2 * 3 + 4")
def test3_parser( ): test_parser("set result temp + ((1 + 3) * 2) * (3 + 4)")

###################################################################
# build viewer with extra widgets to test tree types
###################################################################

if __name__ == '__main__':
 root = Tk( ) # build a single viewer gui
 bwrapper = BinaryTreeWrapper( ) # add extras: input line, test btns
 pwrapper = ParseTreeWrapper( ) # make wrapper objects
 viewer = TreeViewer(bwrapper, root) # start out in binary mode

 def onRadio( ):
 if var.get( ) == 'btree':
 viewer.setTreeType(bwrapper) # change viewer's wrapper
 for btn in p_btns: btn.pack_forget( ) # erase parser test buttons
 for btn in b_btns: btn.pack(side=LEFT) # unhide binary buttons
 elif var.get( ) == 'ptree':
 viewer.setTreeType(pwrapper)
 for btn in b_btns: btn.pack_forget( )
 for btn in p_btns: btn.pack(side=LEFT)

 var = StringVar( )
 var.set('btree')
 Radiobutton(root, text='Binary', command=onRadio, 
 variable=var, value='btree').pack(side=LEFT)
 Radiobutton(root, text='Parser', command=onRadio, 
 variable=var, value='ptree').pack(side=LEFT)
 b_btns = []
 b_btns.append(Button(root, text='test1', command=test1_binary))
 b_btns.append(Button(root, text='test2', command=test2_binary))
 b_btns.append(Button(root, text='test3', command=test3_binary))
 b_btns.append(Button(root, text='test4', command=test4_binary))
 p_btns = []
 p_btns.append(Button(root, text='test1', command=test1_parser))
 p_btns.append(Button(root, text='test2', command=test2_parser))
 p_btns.append(Button(root, text='test3', command=test3_parser))
 onRadio( )

 def onInputLine( ):
 line = entry.get( ) # use per current tree wrapper type
 viewer.onInputLine(line) # type a node list or expression

 Button(root, text='input', command=onInputLine).pack(side=RIGHT)
 entry = Entry(root)
 entry.pack(side=RIGHT, expand=YES, fill=X)
 entry.bind('', lambda event: onInputLine( )) # button or enter key
 root.mainloop( ) # start up the gui

17.10.3 Pytree Does Parse Trees, Too

Finally, I want to show you what happens when you click the Parser radiobutton in the PyTree window. The GUI changes over to an expression parse tree viewer, by simply using a different tree wrapper class: the label at the top changes, the test buttons change, and input is now entered as an arithmetic expression to be parsed and sketched. Figure 17-5 shows a tree generated for the expression string displayed in the input field.

Figure 17-5. PyTree viewing an expression parse tree

PyTree is designed to be generic -- it displays both binary and parse trees, but is easy to extend for new tree types with new wrapper classes. On the GUI, you can switch between binary and parser tree types at any time by clicking the radiobuttons. Input typed into the input field is always evaluated according to the current tree type. When the viewer is in parse tree mode, clicking on a node in the tree evaluates the part of the expression represented by the parse tree rooted at the node you clicked. Figure 17-6 shows the pop-up you get when you click the root node of the tree displayed.

Figure 17-6. PyTree pop-up after clicking a parse tree node

When viewing parse trees, PyTree becomes a sort of visual calculator -- you can generate arbitrary expression trees and evaluate any part of them by clicking on nodes displayed. But at this point, there is not much more I can tell you about these kinds of trees until you move on to Chapter 18.