Ron Fredericks writes: in this post I present revision 3 of a software class called visualizeTree, to draw and visualize a tree structure using Python 2.7, TK graphics modules, pyDot module with GraphViz, and FFmpeg. You can reuse the videos presented here as a teaching aid for common search algorithms: depth first search (DFS), breadth first search (BFS), and depth first ordered search (DFSOrdered). You can also use these examples to create and visualize your own trees and search methods.
For revision 3, I split the growing code into four .py files. Included is a new class called slideShow to animate search algorithms within the main python program itself using TK graphics. The original FFmpeg video animation method is fully supported and allows animations to be played from Internet hosts or from a teachers slide set as mpeg4 video to name a few examples. Only now, using my slideShow class, you can visualize and animate search tree operations without leaving the python interpreter.
Python IDE showing buildBalancedTree, searchTree, & playSlides results.
See the reference section below for details on the required support software used in this project, or check out the source code from GitHub
Binary Search Tree Overview
In this article I focus on the binary search tree (BST). BSTs are a fundamental data structure used to construct more abstract data structures such as sets and associative arrays.
The information represented by each node is usually a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records. In the demos presented here, the search key is simply an ascending integer or character for each node.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient. In the demos presented here, the search method DFSOrdered visually shows the value of in-order traversal.
Unbalanced Tree
A BST is sometimes also called an ordered or sorted binary tree. The structure has the following properties:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes.
The average number of nodes to search in a worst case example using the tree shown below is 2.65. This is the sum of each depth first search to leaves on the tree: 3, 3, 2 or 8/3
This tree was drawn using the buildUnbalancedTree() and sketchTree()
functions presented in this article
The information presented in this section came from the following wiki article: Binary search tree
Balanced Tree
A balanced BST includes two more provisions: All leaves in the tree must be at the same maximum depth, or one level above the maximum depth. And, nodes must have left and right branches, except for final level in the tree. These additional restrictions can shorten a search and offer more reliable complexity.
The average number of nodes to search in a worst case example is 2.25. This is the sum of each depth first search to leaves on the tree: 2, 2, 2, 4 or 9/4. An improvement over the unbalanced tree shown above.
This tree was drawn using the buildBalancedTree() and sketchTree()
functions presented in this article.
Videos Generated Using This Article’s Software
These videos were created with the python code and FFmpeg batch file listed below. This type of video could be used to research the behavior of a new search or tree creation algorithm integrated into this code – or the videos can be used in their current form as a teaching aid, perhaps as part of a ppt slide set.
Breadth First Search (BFS) Video
This video demonstrates the breath first search algorithm helper function BFS() associated with the visualizeTree class featured in the python code listing below. In this case we are searching for tree element “7”. The search goes from left to right, then top to bottom. The search needs to test each node in the tree since element “7” is the worst case location.
Youtube link
Depth First Search Video
This video demonstrates the depth first search algorithm as a helper function DFS() associated with the visualizeTree class featured in the python code listing below. In this case we are searching for the same tree element “7”. The search goes from top to bottom, starting from the left, then moving to right. The search needs to test each node in the tree since element “7” is the worst case location.
Youtube link
Ordered Depth First Search Video
This video demonstrates an improved depth first search algorithm based on the helper function DFSOrdered() as seen in the python code listing below. The search uses information about balanced trees, and the element to find, in order to make an intelligent search decision.
In this case we are searching for the same tree element “7” again. The search still goes from top to bottom, left to right, just like the DFS search video above. Yet, the search will also test for right branched children that are less than the element we are searching, element “7” in this case. So, the search path becomes much shorter.
Youtube link
Ordered Depth First Search Video – Balanced with 26 Nodes
This video demonstrates an improved tree structure since all nodes are balanced. The video was again generated using the tools supplied in this article. The pydot interface shows correct depth for each node with all edges pointing in the same direction aligned parallel to each other.
In this case we are searching for tree element “j”. The search still goes from top to bottom, left to right, just like the DFS search videos above. The tree was generated using the supplied function “buildBalancedTree() from a sorted list of 26 characters (a to z).
Youtube link
Layout of software and files for this demo
The image below shows the two files used to animate tree structures:
- The python code for creation of dot graphics with pyDot module, an interface to the GraphViz open source cross-platform graphic program.
- The FFmpeg utility in a batch file to automate conversion of png image sequences generated by the python code in the subdirectory vidImages
Read the python source code for comments and links to get the supporting software module: pyDot and cross-platform programs: GraphViz and FFmpeg
The image below shows the png image sequence created by the python code as well as videos generated with the FFmpeg video utility batch file. Using settings shown in the batch file, each png file represents one second of video, for a total of 21 seconds of mpeg-4 video content.
Main program: binarySearchTreeAnimationApp.py
The main program presented here walks you through all the steps to generate a tree, search a tree, and animate the results. Yet the actual tree, search visualization, and animation code are shown in the next sections.
Note: The source code highlighting tool for both the python and DOS Batch file listings include hyperlinks that are automatically generated to get more information about a given keyword, language element, or group of related topics. I suggest using the github version controlled software to get the software however, because “‘” single quote marks tend to get mangled into back-ticks in this tool.
code=python
-
"""
-
File: binarySearchTreeAnimationApp.py
-
-
Animate a Binary Search Tree using Python, pyDot, GraphViz, TK, and FFmpeg utility
-
-
Project home: http://www.embeddedcomponents.com/blogs/2013/12/visualizing-software-tree-structures/
-
-
Developed by Ron Fredericks, Video Technologist, at LectureMaker LLC, http://www.LectureMaker.com
-
MIT License, Copyright (c) 2013, Ron Fredericks
-
Free to use following these terms: http://opensource.org/licenses/MIT
-
-
Revision 3: 1/5/2014
-
-
Usage:
-
Input: A binary search tree to sketch (example provided).
-
A search algorithm to animate (examples provided).
-
Examples include all code needed to generate and visualize tree structures:
-
1) binaryTree.py includes binaryTree class,
-
functions to create unbalanced and balanced tree from a list, and
-
manual creation of a tree one node at a time.
-
2) visualizeTree.py includes visualizeTree class,
-
functions for breadth first, depth first, and ordered depth first search.
-
-
Output: This demo software presents two forms of graphic animation, using a series of png images:
-
1) Animate images using the supplied slideShow TK graphics python class
-
2) Animate images using mpeg4 video produced from supplied FFmpeg batch file
-
-
-
Inspired by MITx 6.00.1x "Introduction to Computer Science
and Programming
"
-
As taught by Professor Eric Grimson, Chairman of EECS Department, MIT
-
Fall 2013, http://www.edx.org
-
-
-
Required Software:
-
The following free open source programs should be installed on your computer:
-
GraphViz: Graph visualization tool: http://www.graphviz.org/
-
FFmpeg: Cross-platform solution to record, convert and stream audio and video: http://www.ffmpeg.org/
-
-
The following python module should be installed into your environment:
-
pydot: a python interface to Graphvize’s Dot language: https://code.google.com/p/pydot/
-
-
The following python modules are used for display of individual PNG images:
-
Tkinter: standard python GUI: https://wiki.python.org/moin/TkInter
-
Image and ImageTk: the python image library: http://www.pythonware.com/products/pil/
-
-
The following support modules are supplied with this project:
-
binaryTree.py – Used to create a binary search tree to visualize.
-
visualizeTree.py – Used to draw a binary search tree as well as to draw the steps during a search.
-
slideShow.py – Used to animate a series of graphic images,
-
in this case, the binary tree and the search process.
-
png2mpg4.bat – Used to generate mpg4 video from a series of png graphic images,
-
in this case, the binary tree and the search process.
-
"""
-
-
# Local python libraries supplied with this project
-
-
-
-
-
# import the graphics module used to launch supplied slideShow TK graphics python class
-
-
-
# History:
-
# Initial project published on 12/11/2013
-
#
-
# Rev 1: 12/16/2013
-
# 1) Improve comments for accuracy.
-
#
-
# Rev 2: 12/23/2013
-
# 1) Provide an initialization segment near the top of the code to simplify control of tree sketching and search animation
-
# 2) New FFmpeg command line to generate intelligently scaled video in HD from PNG image sequences:
-
# ffmpeg -f image2 -r 1 -start_number 00001 -i bst_graph%%05d.png -b:v 5000k -vcodec mpeg4 -r 30 -vf scale="’if(gt(a,4/3),1920,-1)’:’if(gt(a,4/3),-1,1280)’" -y movie.mp4
-
#
-
# Rev 3: 1/4/2014
-
# 1) Split program into seperate files:
-
# a) binaryTree.py – binary search tree
-
# b) visualizeTree.py – pydot/GraphViz package
-
# c) slideShow.py – TK graphics
-
# d) binary_tree_search_video – main program
-
#
-
-
#############################
-
# User Controlled Parameters
-
#############################
-
-
# Examples
-
-
# Build balanced trees from a sorted list and rootValue set to None
-
#————————————————————————————–
-
-
# Build a tree using an integer list. The root value is determined automatically
-
-
listForTree =
sorted([5,
2,
1,
4,
8,
6,
7,
3])
-
rootValue =
None # Note: None will be replaced by the midpoint of the sorted list
-
findValue = ‘1’
-
-
# build a tree using a character list. The root value is determined automatically
-
”‘
-
listForTree = [c for c in ‘abcdefghijklmnopqrstuvwxyz‘]
-
rootValue = None # Note: None will be replaced by the midpoint of the list
-
findValue = ‘j‘
-
‘”
-
-
# Build unbalanced trees using an unsorted list and rootValue set to a known value in list
-
#—————————————————————————————
-
-
# Build a tree using an integer list. The root value is determined manually
-
"""
-
listForTree = [5,2,1,4,8,6,7,3]
-
rootValue = 5 # Note: Select a root key from the list of elements in listForTree
-
findValue = ‘7’
-
"""
-
-
# Longer alpha demo with randomly shuffled tree data, and random choice for search value
-
"""
-
import random
-
listForTree = [c for c in ‘abcdefghijklmnopqrstuvwxyz’]
-
rootValue = listForTree[len(listForTree)/2] # Note: Select a root key from the list of elements in listForTree
-
random.shuffle(listForTree)
-
findValue = random.choice(listForTree)
-
"""
-
-
-
# Select a predefined search function from options described above (in overview)
-
#————————————————————————————
-
-
searchNameFcn = {‘DFSOrdered’: visualizeTree.DFSOrdered, ‘DFS’: visualizeTree.DFS, ‘BFS’: visualizeTree.BFS}
-
-
#searchName = ” # Don’t search
-
searchName = ‘BFS’ # Breadth-first Search
-
#searchName = ‘DFS’ # Depth-first Search
-
#searchName = ‘DFSOrdered’ # Ordered Depth-first Search
-
-
-
# Define path where image sequences will be stored (windows example)
-
#——————————————–
-
fileDir = "C:\\Users\\Ron Fredericks\\Documents\\LectureMaker\\Projects\\MOOC\\EDx\\cs600.1\\Video\\vidImages\\"
-
-
-
#####################################################################################
-
# Generate a Binary Tree using controls defined above and Print Out Animation Status
-
#####################################################################################
-
-
# Display ‘sketch tree’ and ‘animate search’ parameters
-
-
print "Generate a balanced tree with",
-
root = binaryTree.
buildBalancedTree(listForTree
[:
],
0,
len(listForTree
))
-
-
print "Generate an unbalanced tree with",
-
root = binaryTree.buildUnbalancedTree(listForTree[:], rootValue)
-
-
print "Error: tree not built",
-
-
print "root value:", root.
getValue()
-
-
print "List used to generate tree:",
str(listForTree
)
-
print "Search for a value of", findValue,
"using", searchName,
"search method"
-
-
# Demonstrate insert() and delete() binaryTree methods
-
nodeInserted = root.insert(1)
-
-
print "Node " +
str(nodeInserted.
getValue()) +
" was successfully inserted into tree"
-
-
-
print "Node not inserted"
-
-
-
##################################################################
-
# Draw and animate binary search tree during a BFS or DFS search
-
##################################################################
-
-
# Instantiate the visualizeTree object
-
vT = visualizeTree.visualizeTree(fileDir)
-
-
# Draw the initial binary search tree.
-
vT.searchTree(root, visualizeTree.sketchTree)
-
vT.setVidFrames(3)
-
vT.updateGraph()
-
vT.appendVisualizeList()
-
-
# Animate a search to find a node in the tree.
-
-
vT.setVidFrames(1)
-
vT.searchTree(root, searchNameFcn[searchName], findValue)
-
-
# extend the final segment of video for 3 more frames (or 3 seconds in video, based on FFmpeg settings)
-
vT.setVidFrames(3)
-
vT.updateGraph()
-
-
-
##################################################################
-
# Animate the search method using TK graphics
-
##################################################################
-
-
mainTitle = "Find " + ‘"’ + findValue + ‘"’ + " using " + searchName
-
-
playList = vT.visualizeList
-
sShow = slideShow.slideShow(rootTk)
-
sShow.setImageScaling(1280, 720)
-
sShow.
playSlides(playList, mainTitle,
"Quit",
True)
-
rootTk.destroy()
Python class: binaryTree.py
Use this code with the main program to create and operate on binary tree structures. Several sample trees are generated using this class from the main program. You can use your own class or use the methods I provide.
code=python
-
"""
-
File: binaryTree.py
-
-
Support Module for: Animate a Binary Search Tree using Python
-
-
Project home: http://www.embeddedcomponents.com/blogs/2013/12/visualizing-software-tree-structures/
-
-
Developed by Ron Fredericks, Video Technologist, at LectureMaker LLC, http://www.LectureMaker.com
-
MIT License, Copyright (c) 2013, Ron Fredericks
-
Free to use following these terms: http://opensource.org/licenses/MIT
-
-
Revision 3: 1/5/2014
-
-
###########################################
-
# Class binaryTree()
-
###########################################
-
-
Create a binary search tree
-
-
Public methods to interconnect nodes:
-
setLeftBranch()
-
setRightBranch()
-
setParent()
-
getValue()
-
getLeftBranch()
-
getRightBranch()
-
getParent()
-
-
Public methods to operate on nodes:
-
insert() – insert a node
-
lookup() – find a node
-
delete() – delete a node
-
children_count() – return number of children associated with a node
-
print_tree() – print a sorted list of nodes in the tree
-
-
External functions to build a tree:
-
manual method – highlighted example in comments
-
buildBalancedTree() – generate a balanced tree from a sorted list
-
buildUnbalancedTree() – generate an unbalanced tree from an unsorted list
-
"""
-
-
# History:
-
# Initial project published on 12/11/2013
-
#
-
# Rev 1: 12/16/2013
-
# 1) Improve comments for accuracy.
-
#
-
# Rev 2: 12/23/2013
-
# 1) Provide 3 tree generation options: manually create tree, generate random unbalanced tree, create balanced tree.
-
# 2) Improve draw method to include left, right, and middle "invisible" nodes and intelligent edge weights,
-
# now all edges in same direction are parallel, and every node of the same depth is displayed at the same depth.
-
# 3) Fix bug in DFSOrdered() search function
-
# 6) Improve video scaling:
-
# a) support large trees
-
# b) support HD video during graph generation and in FFmpeg for 1920 x 1080 pixel size
-
#
-
# Rev 3: 1/4/2014
-
# 1) Create (this) binaryTree.py module to clarify and shorten original project code
-
# 2) Fix bug in binaryTree.lookup() method: fix the case for lookup not found
-
# 3) Add new binaryTree.delete() method to delete a node, and helper function binaryTree.children_count() to return node’s number of children
-
# 4) Add new binaryTree.print_tree() method to list node values in sorted order to standard output
-
# 5) Improve insert recursive binaryTree.insert() method: a) detect when node already present, b) return inserted node object on success
-
#
-
-
-
-
# Reference: Structure and node naming convention came from edx.org’s mitX MOOC course 6.00.1x slides taught by professor Eric Grimson, Fall 2013.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
"""
-
Insert new node with data key set to value
-
Return inserted node object to caller, or None if node not inserted (when node was already present)
-
Modified from reference: http://www.laurentluce.com/posts/binary-search-tree-library-in-python/
-
"""
-
-
-
self.
setLeftBranch(binaryTree
(value
))
-
-
-
-
-
-
-
self.
setRightBranch(binaryTree
(value
))
-
-
-
-
-
-
-
"""
-
Lookup node containing data key set to value
-
Returns node object to caller, or None if not found
-
Modified from reference: http://www.laurentluce.com/posts/binary-search-tree-library-in-python/
-
"""
-
-
-
-
-
-
-
-
-
-
-
-
-
"""
-
Delete node containing data key set to value
-
Returns status text message
-
Modified from reference: http://www.laurentluce.com/posts/binary-search-tree-library-in-python/
-
"""
-
# get node containing value and its number of children | or return with node not found message
-
node =
self.
lookup(value
)
-
-
return "Error in delete method: node " +
str(value
) +
" not found"
-
-
children_count = node.children_count(node)
-
-
# if node has no children, just remove it
-
parent = node.getParent()
-
if parent.
getLeftBranch() is node:
-
parent.
setLeftBranch(None)
-
-
parent.
setRightBranch(None)
-
elif children_count ==
1:
-
# if node has 1 child, replace node by its child
-
-
n = node.getLeftBranch()
-
-
n = node.getRightBranch()
-
parent = node.getParent()
-
-
if parent.
getLeftBranch() is node:
-
parent.setLeftBranch(n)
-
-
parent.setRightBranch(n)
-
elif children_count ==
2:
-
# if node has 2 children, find its successor
-
parent = node
-
successor = node.getRightBranch()
-
while successor.
getLeftBranch():
-
parent = successor
-
successor = successor.getLeftBranch()
-
# replace node value by its successor value
-
node.value = successor.value
-
# fix successor’s parent’s child
-
if parent.
getLeftBranch() == successor:
-
parent.setLeftBranch(successor.getRightBranch())
-
-
parent.setRightBranch(successor.getRightBranch())
-
childMessageFrag = ("no children", "1 child", "2 children")
-
return "Node " +
str(value
) +
" has " +
str(childMessageFrag
[children_count
]) +
" and was successfully deleted"
-
-
-
"""
-
Returns the number of children of a tree node object: 0, 1, 2
-
"""
-
-
-
cnt = 0
-
-
cnt += 1
-
-
cnt += 1
-
-
-
-
"""
-
Print tree content inorder
-
"""
-
-
self.
getLeftBranch().
print_tree()
-
-
-
self.
getRightBranch().
print_tree()
-
-
-
-
-
-
"""
-
A Manual Method to Instantiate a Tree
-
————————————-
-
-
n5 = binaryTree(5)
-
n2 = binaryTree(2)
-
n1 = binaryTree(1)
-
n4 = binaryTree(4)
-
n8 = binaryTree(8)
-
n6 = binaryTree(6)
-
n7 = binaryTree(7)
-
n3 = binaryTree(3)
-
-
n5.setLeftBranch(n2)
-
n2.setParent(n5)
-
n5.setRightBranch(n8)
-
n8.setParent(n5)
-
n2.setLeftBranch(n1)
-
n1.setParent(n2)
-
n2.setRightBranch(n4)
-
n4.setParent(n2)
-
n8.setLeftBranch(n6)
-
n6.setParent(n8)
-
n6.setRightBranch(n7)
-
n7.setParent(n6)
-
n4.setLeftBranch(n3)
-
n3.setParent(n4)
-
-
# define sketch tree and animate search parameters
-
root = n5
-
findValue = ‘7’
-
listForTree = None
-
"""
-
-
-
# Helper functions to instantiate a tree from a list
-
# ————————————————–
-
-
def buildBalancedTree
(sortedList, start, end
):
-
"""
-
Build a balanced binary search tree from a sorted linked list.
-
-
This function uses class binaryTree, with methods:
-
‘getLeftBranch()’, ‘getRightBranch()’ and optionally setParent().
-
-
Input:
-
sortedList: sorted list, any data structure with ‘pop(0)’ method,
-
which removes and returns the leftmost element of the list. The
-
easiest thing to do is to use a list for the sorted
-
list.
-
start: int, start index, on initial call set to 0
-
end: int, on initial call should be set to len(sortedList)
-
Output:
-
root node of type binaryTree if the supplied list has 2 or more values,
-
or None.
-
-
Note:
-
The sortedList list is destroyed during the process.
-
-
References:
-
The original python implementation used a sorted "linked" list found here:
-
http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
-
Based on an original solution in C found here:
-
http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
-
"""
-
-
-
middle = (start + end) // 2
-
node = buildBalancedTree(sortedList, start, middle)
-
root = binaryTree(sortedList.pop(0))
-
root.setLeftBranch(node)
-
-
root.getLeftBranch().setParent(root)
-
root.setRightBranch(buildBalancedTree(sortedList, middle+1, end))
-
if root.
getRightBranch():
-
root.getRightBranch().setParent(root)
-
-
-
-
def buildUnbalancedTree
(unsortedList, rootValue
):
-
"""
-
Build an unbalanced binary search tree
-
Input: An unsorted list of key values to generate a tree,
-
The root key value, a member of the unsortedList.
-
Output: rootNode when rootValue was found in unsortedList, otherwise return None.
-
-
Notes:
-
The unsortedList list is destroyed during the process.
-
The nodes will be inserted into the tree using unsortedList list from left to right,
-
Uses the binaryTree.insert() method.
-
"""
-
-
-
rootIndex = unsortedList.index(rootValue)
-
rootNode = binaryTree(unsortedList[rootIndex])
-
unsortedList.remove(unsortedList[rootIndex])
-
-
rootNode.insert(unsortedList[0])
-
unsortedList.remove(unsortedList[0])
-
Python class: visualizeTree.py
The visualization is carried out using a class called visualizeTree along with its included three helper functions DFS(), DFSOrdered() and BFS() for searching with animation using depth first or breadth first. The code produces a series of PNG images as a sequence in a subdirectory called vidImages. The code ends with a visual display of the last PNG image.
The python code uses the pyDot module to interface with GraphViz: both free and open source software. More details are described in the reference section of this article.
code=python
-
"""
-
File: visualizeTree.py
-
-
Support Module for: Animate a Binary Search Tree using Python, pyDot, GraphViz
-
-
Project home: http://www.embeddedcomponents.com/blogs/2013/12/visualizing-software-tree-structures/
-
-
Developed by Ron Fredericks, Video Technologist, at LectureMaker LLC, http://www.LectureMaker.com
-
MIT License, Copyright (c) 2013, Ron Fredericks
-
Free to use following these terms: http://opensource.org/licenses/MIT
-
-
Revision 3: 1/5/2014
-
-
#############################################################
-
# Class visualizeTree
-
#############################################################
-
-
Graph tree as a png file, and generate a sequence of images to animate a search.
-
-
A tree node must provide these methods for this class to work:
-
getValue()
-
getLeftBranch()
-
getRightBranch()
-
-
A tree must provide the root node for this class to work.
-
-
External search functions included:
-
DFS() – animate a search using depth first search
-
DFSOrdered() – animate an ordered search using depth first search
-
BFS() – animate a search using breath first search
-
-
Public drawing methods:
-
sketchTree() – draw a tree
-
searchTree() – search a tree (using a search function as described above), with animated trail of search
-
setVidFrames() – number of png images to generate for each step in the video
-
updateGraph() – generate a png image
-
appendVisualizeList() – add a png image name to a list for use with "showVideo" class
-
"""
-
-
-
-
# History:
-
# Initial project published on 12/11/2013
-
#
-
# Rev 1: 12/16/2013
-
# 1) Improve automated tree graphic image design so that no node is displayed directly below its parent.
-
# a) add invisible nodes, and invisible edges as placeholders to replace leaves that are not in the tree definition,
-
# b) change the default weight of edges to zero, so that displayed trees have freedom to spread out on the canvas.
-
# 2) Redesign the draw() method to support automated inclusion of invisible nodes when a left or right sibling is missing from tree,
-
# remove automated display of "root", "node", and "leaf" in the node label.
-
# 3) Redesign search routines BFS, and DEF so that drawing of graphic image information is not mixed in.
-
# Now new search routines can be designed solely on the merits of search.
-
# 4) Add a new search routine: DFSOrdered.
-
# 5) Add a new drawing routine: sketchTree.
-
# This routine adds the drawing information previously mixed into the search routines.
-
# Use this routine once to draw the full tree image during initialization.
-
# 6) Change method blinkNodeTraversed color scheme to show a history of nodes searched in a new color
-
#
-
# Rev 2: 12/23/2013
-
# 1) Clean up PNG image display code.
-
# 2) Improve video scaling:
-
# a) support large trees,
-
# b) support HD video during graph generation for 1920 x 1080 pixel size (corresponding changes made to FFmpeg script).
-
#
-
# Rev 3: 1/4/2014
-
# 1) Create visualizeTree.py module to clarify and shorten original project code.
-
# 2) Include special case to support drawing a one node tree: see draw(), and sketchTree() for details.
-
# 3) Create new visualizeList[] list to hold a subset of images generated by visualizeTree() class,
-
# to display using a new interactive Tkinter Slideshow() class.
-
#
-
-
-
-
def __init__(self, fileDir, fileName=
‘bst_graph’, fileExt=
‘.png’, vidFrames=
1, fileCount=
0):
-
self.
fileDir = fileDir
# string, full directory path to where image sequence files will be stored
-
self.
fileName = fileName
# string, base name of the file
-
self.
fileExt = fileExt
# string, image file extension (currently ".png" is the only supported type)
-
self.
vidFrames = vidFrames
# integer, a counter used generate duplicate copies of the PNG image files,
-
# a way to stretch the video time line.
-
self.
fileCount = fileCount
# integer, first number to use with generate sequenced image files.
-
-
self.
treeList =
[] # storage for the DFS or BFS tree search as a queue or stack
-
self.
nodeNames =
{} # store each node name (key) with each node’s pyDot object (value), used by draw() method to ensure each node is drawn once
-
self.
fullFileName =
"" # store the current full file name for png images
-
-
self.
visualizeList =
[] # hold unique png files for Tkinter display
-
-
self.
initGraph(graph_type=
‘digraph’, nodesep=.
5, pad=.
3, size=
"19.2, 10.1")
-
self.
setNodeDefaults(style=
"filled", fillcolor=
"grey", shape=
"circle")
-
self.
setEdgeDefaults(color=
"blue", arrowhead=
"vee")
-
-
-
# Initialize a directional graph
-
# Dot attributes:
-
# graph_type = "graph" (edges drawn as lines)| "digraph" (edges drawn as arrows)
-
# rankdir= "TB", "LR", "BT", "RL", corresponding to directed graphs drawn from top to bottom, from left to right, from bottom to top, and from right to left, respectively.
-
# ranksep=float_value: rank separation in fraction of an inch 0.75 default, minimum vertical distance between nodes of equal rank
-
# nodesep=float_value: node separation in fraction of an inch 0.25 default, minimum horizontal distance between nodes of equal rank
-
# size = "string_value width, string_value height" in inches. Example: size="4, 8"
-
# dpi=300 for better image quality, or dpi=96 for default value
-
# optional layout="neato" | "sfpd" | "fpd" | "twopi" | "circo" to create a differently style for graph
-
# pad=float_value for both width and height of pad around graph margins, in inches (.3 seems to be a good value)
-
# bgcolor="red" set the background color
-
# label="hello" set a text label just below the graph
-
self.
graph = pydot.
Dot(**kwargs
)
-
-
def setNodeDefaults
(self, **kwargs
):
-
# Set default node attributes
-
# Node attributes:
-
# style = ‘filled’ | ‘invisible’
-
# Many more options here: http://www.graphviz.org/doc/info/attrs.html#d:peripheries
-
# shape = ‘box’ | ‘ellipse’ | ‘circle’ | ‘point’ | ‘triangle’
-
# Many more shapes here: http://www.graphviz.org/doc/info/shapes.html
-
# fillcolor = "grey" for example, the color of the shape inside
-
# color = "red" for example, the color of the shapes outer border (or borders with ‘doublecircle’)
-
# height and width float_value inches, for example: height=1.5, width=1.5
-
# text control: ‘fontcolor’, ‘fontsize’, ‘label’, ‘fontname’,
-
self.
graph.
set_node_defaults(**kwargs
)
-
-
def setEdgeDefaults
(self, **kwargs
):
-
# Set edge attributes
-
# Edge attributes:
-
# style = ‘dashed’ | ‘dotted’ | ‘solid’ | ‘invis’ | ‘bold’
-
# arrowhead = ‘box’ | ‘crow’ | ‘diamond’ | ‘dot’ | ‘inv’ | ‘none’ | ‘tee’ | ‘vee’
-
# place a label: label="and back we go again", labelfontcolor="#009933", fontsize="10.0"
-
# Adjust weighted flexibility in edge drawings: weight="0" for maximum flex, "3" for
-
# minlen=2 minimum edge length in inches (default is 1
-
# weight="0" to "100"
-
self.
graph.
set_edge_defaults(**kwargs
)
-
-
-
# Method to control the number of duplicate png images to generate (ie stretch or shrink video time)
-
self.
vidFrames = vidFrames
-
-
-
# Method to search a binary tree
-
# Input:
-
# searchMethod is a helper function that defines the type of search to perform,
-
# current examples implemented: DFS, BFS, and DFSOrdered
-
# find is string representing the node to search and highlight, or None to display full binary tree
-
# Output:
-
# True if node is found, or False if node is not found, or False when drawing the full tree (not searching)
-
-
-
node =
self.
treeList.
pop(0)
-
-
#print str(node) # activate to display nodes searched when debug needed
-
-
-
-
-
-
searchMethod
(node,
self.
treeList, find,
self.
draw)
-
-
-
def draw
(self, parent_name, child_name=
None, fill_color=
"grey", style_type=
‘filled’):
-
# Method to draw a node and an edge of a Binary Tree
-
# Input:
-
# parent_name is a string lable identifying the parent node to draw (if not drawn already)
-
# child_name is a string lable identifying the child node to draw (or None, for a one node tree)
-
# fill_color is the color to fill nodes drawn
-
# style_type is either "filled" for normal drawing of tree nodes, or "invisible" for drawing nodes not part of tree
-
-
# Draw a tree with only one node
-
self.
nodeNames[parent_name
] = pydot.
Node(parent_name, label=parent_name, fillcolor=fill_color, style=style_type
)
-
self.
graph.
add_node(self.
nodeNames[parent_name
])
-
-
-
if style_type==
"invisible":
-
# save original edge defaults
-
weight_ = "100"
-
saveEdgeDefaults =
self.
graph.
get_edge_defaults()[0]
-
self.
graph.
set_edge_defaults(style=style_type, color=
"white", arrowhead=
"none") # comment during debug
-
###fill_color="#6699cc" # debug, display invisible edges and nodes as light blue
-
###style_type="filled" # debug, display invisible edges and nodes as light blue
-
-
weight_ = "3"
-
edge = pydot.Edge(parent_name, child_name, style=style_type, weight=weight_)
-
self.
graph.
add_edge(edge
)
-
if style_type==
"invisible":
-
# restore original edge defaults
-
self.
graph.
set_edge_defaults(**saveEdgeDefaults
)
-
-
-
# root node identified (the top most tree element)
-
self.
nodeNames[parent_name
] = pydot.
Node(parent_name, label=parent_name, fillcolor=fill_color, style=style_type
)
-
self.
graph.
add_node(self.
nodeNames[parent_name
])
-
-
# node (a tree element with leaves) identified
-
self.
nodeNames[parent_name
] = pydot.
Node(parent_name, label=parent_name, fillcolor=fill_color, style=style_type
)
-
self.
graph.
add_node(self.
nodeNames[parent_name
])
-
-
# leaf element identified (a parent with no children)
-
self.
nodeNames[child_name
] = pydot.
Node(child_name, label=child_name, fillcolor=fill_color, style=style_type
)
-
self.
graph.
add_node(self.
nodeNames[child_name
])
-
-
def highlightNodeFound
(self, node
):
-
# Method to animate the found node in a search tree
-
self.
graph.
add_node(pydot.
Node(node, fillcolor=
"green"))
-
-
self.
appendVisualizeList()
-
-
-
self.
visualizeList.
append(self.
fullFileName)
-
-
def blinkNodeTraversed
(self, node
):
-
# Method to animate a node being traversed in a search tree
-
self.
graph.
add_node(pydot.
Node(node, fillcolor=
"red"))
-
-
self.
appendVisualizeList()
-
# use a redish grey color #cc9999 to show a breadcrumb to searched nodes in tree
-
self.
graph.
add_node(pydot.
Node(node, fillcolor=
"#cc9999"))
-
-
-
-
# Method to set the file name based on:
-
# directory, name, count and extension in support of our ffmpeg png to video batch file
-
-
-
-
-
# Method to get the current full file name
-
-
-
-
-
-
# Method to return maximum file count: the number of png images created
-
-
-
-
# Method to write multiple copies of the same png image in support of ffmpeg png to video batch file
-
-
-
-
-
-
-
# Helper search functions for use with visualizeTree’s method named "searchTree()"
-
# ——————————————————————————–
-
-
-
# Depth First Search helper function for binaryTree.searchTree():
-
# Start at root followed by all nodes from top to bottom, then left to right,
-
# until key value found or queue exhausted.
-
# Input:
-
# node: Current node in binary tree,
-
# queue: First in First out (FIFO) ,
-
# find and draw: Unused.
-
if node.
getRightBranch():
-
queue.insert(0, node.getRightBranch())
-
-
queue.insert(0, node.getLeftBranch())
-
-
def DFSOrdered
(node, queue, find, draw=
None):
-
# Ordered Depth First Search helper function for binaryTree.searchTree():
-
# Start at root followed by selected nodes from top to bottom, then left to right,
-
# that meet our find requirment, until key value found or leaf node examined.
-
# Input:
-
# node: Current node in binary tree,
-
# queue: First in First out (FIFO) ,
-
# find: the string value we are searching for in a tree,
-
# draw: Unused.
-
-
if node.
getRightBranch() and find >
str(node.
getValue()):
-
queue.insert(0, node.getRightBranch())
-
if node.
getLeftBranch() and find <
str(node.
getValue()):
-
queue.insert(0, node.getLeftBranch())
-
-
-
# Breadth First Search helper function for binaryTree.searchTree():
-
# Start at root followed by all nodes from left to right, then top to bottom,
-
# until key value found or queue exhausted.
-
# Input:
-
# node: Current node in binary tree,
-
# stack: Last in First out (LIFO) ,
-
# find and draw: Unused.
-
-
stack.append(node.getLeftBranch())
-
if node.
getRightBranch():
-
stack.append(node.getRightBranch())
-
-
# Sketch complete tree
-
# makes calls to visualizeTree’s draw() method to graph edge and node elements
-
# Input: node in binary tree, stack for depth first drawing
-
# Unused: find
-
-
-
draw
(str(node
),
str(node.
getLeftBranch()))
-
stack.append(node.getLeftBranch())
-
if node.
getRightBranch():
-
# insert invisible third node in-between left and right nodes
-
draw
(str(node
),
":"+
str(node
), style_type=
"invisible")
-
elif node.
getRightBranch():
-
# draw any missing left branches as invisible nodes/edges with dummy unique labels
-
draw
(str(node
),
":"+
str(node
), style_type=
"invisible")
-
if node.
getRightBranch():
-
draw
(str(node
),
str(node.
getRightBranch()))
-
stack.append(node.getRightBranch())
-
elif node.
getLeftBranch():
-
# draw any missing right branches as invisible nodes/edges with dummy unique labels
-
draw
(str(node
),
";"+
str(node
), style_type=
"invisible")
-
-
# special case: draw a tree with only one node
-
Plython class: slideShow.py
The slide show code is built around a TK update() loop with event driven buttons to control the presentation of png images located in the playSlides() method. Each cycle of the idle loop sleeps for a fraction of a second set by public attribute: idleTimeSlice. On my computer with a 0.05 second sleep state per idle loop, the fastest playback clocks in at around 0.09 seconds per image while running from my Canopy 64-bit development environment. This speed is more than enough to generate a flicker free “flip book” visual experience. I have found that a playback speed ranging from from .35 to 1. second per png image works well. The playback speed is not set with the idle loop time slice, instead a list of play times can be set using the setSpeedList() method. Perhaps other developers may find this stand-alone class useful for animation or photo slide show projects of their own.
Python 2.7 class slideShow() being used as an animation tool for this project.
code=python
-
"""
-
File: slideShow.py
-
-
Support Module for: Animate a Binary Search Tree using Python, and TK graphics
-
-
Project home: http://www.embeddedcomponents.com/blogs/2013/12/visualizing-software-tree-structures/
-
-
Developed by Ron Fredericks, Video Technologist, at LectureMaker LLC, http://www.LectureMaker.com
-
MIT License, Copyright (c) 2013, Ron Fredericks
-
Free to use following these terms: http://opensource.org/licenses/MIT
-
-
-
-
################################################
-
# Class slideShow
-
################################################
-
-
Animate a sequence of images in a TK window, assumes all images are the same size.
-
-
Public methods:
-
slideShow(rootTk) – instantiate slide show class
-
setImageScaling() – update default image scale factor
-
setSpeedList() – update default list of playback speeds
-
setColorScheme() – update default button color scheme
-
setIdleTimeSlice() – update defalut sleep time during idle loop
-
playSlides() – launch a slide show
-
"""
-
-
# Import TK graphics packages.
-
-
-
-
-
-
# History:
-
# Initial project published on 12/11/2013
-
#
-
# Rev 1: 12/16/2013
-
# 1) Improve comments for accuracy.
-
#
-
# Rev 2: 12/23/2013
-
# 1) Improve comments for accuracy.
-
#
-
# Rev 3: 1/4/2014
-
# 1) Create (this) slideShow.py module to clarify and shorten original project code.
-
# 2) Turn single image display into slideShow() class to display multiple images.
-
# Rev 3a: 1/10/2014
-
# 1) Improve clarity of idle loop
-
# 2) Improve clarity of performance display in main playback loop
-
-
-
-
-
-
# Root for TK graphics (example: rootTk = Tkinter.Tk())
-
-
# Text title for TK graphics playback window.
-
self.
mainTitle =
"Slide Show"
-
# List of images to play during slide show (example: playList = ["c:\tmp\im1.png", "c:\tmp\im2.png"…]).
-
-
# Activate (set True) to display performance of main timing loop to screen (standard output).
-
-
-
# Polling loop controls for playSlides() method…
-
self.
speedList =
[.
01, .
05, .
1, .
35, .
5,
1.,
2.
] # A sorted list of wait times between images to play during a slide show,
-
# where speedList pointer controlled by "Faster" and "Slower" buttons.
-
self.
speedPointerDefault =
3 # The default wait time (during startup and after a reset) index within speedList[].
-
# Recommended setting (integer): len(speedList)/2
-
self.
idleTimeSlice = .
01/
2.1 # Idle loop time slice between Tkinter updates.
-
# Recommend setting based on Nyquist Interval (float): min(.1, speedList[0]/2.1),
-
# and the need for python code associated with button activity to be responsive to user.
-
-
# Button colors…
-
self.
bg_color_f =
"#ccffff" # Background color for buttons.
-
self.
bg_color_r =
"#ffffcc" # Background color for play/pause button and reverse/normal buttons
-
# when user selects reverse playback option.
-
self.
fg_color_f =
"blue" # Text color for buttons.
-
self.
fg_color_r =
"black" # Text color for play/pause button and reverse/normal buttons
-
# when user selects reverse playback option.
-
self.
exitButtonText =
"Quit" # Text for use in exit button, use "Next" (for example),
-
# when cascading several slide shows together.
-
-
# Image scaling to fit within monitor…
-
self.
w_screen =
None # Width of screen: use None for auto-detection and auto-scaling,
-
# otherwise set to maximum png width in pixels plus 20 for borders (controller width only takes 420).
-
self.
h_screen =
None # Height of screen: use None for auto-detection and auto-scaling,
-
# otherwise set to maximum png height in pixels plus 70 for borders, title bar, and buttons (controller height only takes 66).
-
-
def setImageScaling
(self, wMax, hMax
):
-
# Set maximum width and height values in pixels for png images.
-
# Auto-scaling will take place when images are larger than these values.
-
-
-
-
def setSpeedList
(self, speedList, speedPointerDefault
):
-
# Update the default list of playback times offered by the "faster" / "slower" buttons
-
assert len(speedList
) >=
3,
"List should be 3 or floating point times. Example: speedList = [.01, .05, .1, .35, .5, 1., 2.]"
-
assert speedPointerDefault <
len(speedList
),
"Default time pointer should be an integer: between 0 and len(speedList) – 1"
-
self.
speedList = speedList
-
self.
speedPointerDefault = speedPointerDefault
-
-
def setIdleTimeSlice
(self, idleTimeSlice
):
-
# Update the default idle loop time slice. Use faster time for more responsive buttons. Use slower time for slower computers.
-
assert type(idleTimeSlice
) ==
float,
"Wait time between rootTk.update() calls should be a float. Example: idleTimeSlice = .05"
-
self.
idleTimeSlice = idleTimeSlice
-
-
def setColorScheme
(self, bg_color_f=
"#ccffff", bg_color_r=
"#ffffcc", fg_color_f=
"blue", fg_color_r=
"black"):
-
# Set text and background colors for buttons. The "_f" colors are used for initial buttons, and controller title.
-
# The "_r" colors are used for revere playback on "play/pause" and "normal" buttons.
-
self.
bg_color_f = bg_color_f
-
self.
bg_color_r = bg_color_r
-
self.
fg_color_f = fg_color_f
-
self.
fg_color_r = fg_color_r
-
-
-
-
# Exit play loop when user clicks operating system’s window exit button, or slideShow’s "Quit" button.
-
# manage WM_DELETE_WINDOW event
-
-
-
-
-
# Modify play loop for playback or pause. Auto pause when playback comes to an end.
-
-
-
self.
Play.
configure(text =
‘ Play ‘)
-
-
-
# forward play should only take place when imageCount (frame count) is not already at the end
-
self.
Play.
configure(text =
‘Pause’)
-
-
-
# reverse play should only take place when imageCount (frame count) is not already at the begining
-
self.
Play.
configure(text =
‘Pause’)
-
-
-
# Auto pause when playback comes to an end.
-
-
-
-
# Modify play loop for shorter delay between images.
-
self.
speedPointerCurrent =
max(0,
self.
speedPointerCurrent-1)
-
-
self.
updateSpeedButtons()
-
-
-
# Modify play loop for longer delay between images.
-
-
-
self.
updateSpeedButtons()
-
-
-
# Helper function for "faster" and "slower" buttons to display correct text with each button.
-
-
tmpText =
‘{:7.2f}’.
format(self.
setTime)
-
-
print "Update time:", tmpText
-
self.
Speed.
configure(text = tmpText
)
-
-
self.
Slower.
configure(text =
‘Slowest’)
-
-
self.
Slower.
configure(text =
‘Slower’)
-
if self.
speedPointerCurrent ==
0:
-
self.
Faster.
configure(text =
‘Fastest’)
-
-
self.
Faster.
configure(text =
‘Faster’)
-
-
-
# Modify play loop for forward or reverse playback.
-
# Update play/pause and reverse/normal button color scheme for improved user awareness of current state.
-
-
-
-
self.
Reverse.
configure(text =
‘Reverse’, bg=
self.
bg_color_f, fg=
self.
fg_color_f)
-
-
-
-
self.
Reverse.
configure(text =
‘Normal’, bg=
self.
bg_color_r, fg=
self.
fg_color_r)
-
-
-
-
# Modify play loop to initial state.
-
-
-
-
self.
speedPointerCurrent =
self.
speedPointerDefault
-
self.
updateSpeedButtons()
-
-
-
-
-
-
-
-
-
# Determine visual environment, and generate width/height scale dimensions as needed.
-
# Output: Return tuple: updated width and height, and flag to scale or not.
-
-
# Get screen size. Leave some room for boarders and buttons, use float values for scale calculations.
-
-
self.
w_screen =
self.
rootTk.
winfo_screenwidth() –
20
-
-
-
self.
h_screen =
self.
rootTk.
winfo_screenheight() –
70
-
# Get width, height, and then initialize display using initial png image in sequence
-
-
w = image.size[0]
-
h = image.size[1]
-
-
scaleFactorW = 1.
-
scaleFactorH = 1.
-
-
scaleFactorW = w /
self.
w_screen
-
-
scaleFactorH = h /
self.
h_screen
-
-
# Find largest scale factor, a scale factor below 1.0 would cause image to be magnified.
-
scaleFactor =
max(1. ,
max(scaleFactorW, scaleFactorH
))
-
-
-
-
# Determine if scaling should be done on images.
-
-
-
-
-
#Return tuple: updated width and height, and flag to scale or not.
-
-
-
-
def playSlides
(self, playList, mainTitle=
"Slide Show", exitButtonText=
"Quit", testPerformance=
False):
-
# Main playback loop
-
-
-
-
assert len(playList
) >
0,
‘Error: playList is a ist of images to play during slide show (example: playList = ["c:\tmp\im1.png", "c:\tmp\im2.png"…])’
-
-
-
self.
mainTitle = mainTitle
-
-
assert type(exitButtonText
) ==
str,
"Error: Exit button text should be passed as a string value"
-
self.
exitButtonText = exitButtonText
-
-
self.
testPerformance= testPerformance
-
-
assert self.
rootTk and self.
rootTk.
winfo_exists(),
"Error: Tkinter root not valid (initialization example: s = slideShow(Tkinter.Tk(), ‘Title’)"
-
-
self.
rootTk.
title(self.
mainTitle) # Place title in top window boarder.
-
self.
speedPointerCurrent =
self.
speedPointerDefault # Current playback speed set to default time index in speedList[].
-
self.
setTime =
self.
speedList[self.
speedPointerCurrent] # Initialize time to wait between images during playback.
-
self.
imageCountMax =
len(self.
playList) –
1 # Maximum image count [0 to n].
-
-
wScale, hScale, useScale =
self.
scaleFactor() # Calculate image scale details
-
-
# group buttons together tightly using this frame
-
-
frame.grid(row = 1, column=1)
-
-
# manage user buttons
-
#———————
-
-
# place menu name by the buttons
-
msg =
Tkinter.
Label(frame, text=
"Controller: ", font=
("Helvetica",
14), fg=
self.
fg_color_f)
-
msg.grid(row = 1, column = 0)
-
-
# define play/pause button
-
self.
Play =
Tkinter.
Button(frame, text =
" Play ", bg=
self.
bg_color_f, fg=
self.
fg_color_f, command =
self.
tooglePlayPause)
-
self.
Play.
grid(row =
1, column =
1)
-
-
# define play faster and slower buttons
-
self.
Faster =
Tkinter.
Button(frame, text =
"Faster", bg=
self.
bg_color_f, fg=
self.
fg_color_f, command =
self.
incrementFaster, width=
6)
-
self.
Faster.
grid(row =
1, column =
2)
-
self.
Speed =
Tkinter.
Label(frame, text =
‘{:7.2f}’.
format(self.
setTime), fg=
self.
fg_color_f, relief=
"sunken", borderwidth=
2)
-
self.
Speed.
grid(row =
1, column =
3)
-
self.
Slower =
Tkinter.
Button(frame, text =
"Slower", bg=
self.
bg_color_f, fg=
self.
fg_color_f, command =
self.
incrementSlower, width=
6)
-
self.
Slower.
grid(row =
1, column =
4)
-
-
# define reverse play button
-
self.
Reverse =
Tkinter.
Button(frame, text =
"Reverse", bg=
self.
bg_color_f, fg=
self.
fg_color_f, command =
self.
toogleReverse)
-
self.
Reverse.
grid(row =
1, column =
5)
-
-
# define reset button
-
Reset =
Tkinter.
Button(frame, text =
"Reset", bg=
self.
bg_color_f, fg=
self.
fg_color_f, command =
self.
doReset)
-
Reset.grid(row = 1, column = 6)
-
-
# define quit button, and link window exit button to it
-
self.
rootTk.
protocol("WM_DELETE_WINDOW",
self.
setExitFlag)
-
Exit =
Tkinter.
Button(frame, text =
self.
exitButtonText, bg=
self.
bg_color_f, fg=
self.
fg_color_f, command =
self.
setExitFlag)
-
Exit.grid(row = 1, column = 7)
-
-
# Initialize main polling loop.
-
-
-
startMeasureTime = 0. # measureValid will is initialized to False during doReset()
-
-
# Main polling loop.
-
-
-
-
deltaTime =
time.
clock() – startMeasureTime
-
print "deltaTime:",
‘{:2.5f}’.
format(deltaTime
),
"imageCount:",
"%02d" %
(self.
imageCount)
-
startMeasureTime =
time.
clock()
-
-
-
# Exit slide show if a quit button or exit window button was pressed.
-
-
-
-
# Display an image.
-
-
-
if useScale: image = image.
resize((wScale,hScale
),Image.
ANTIALIAS)
-
# Use alternate image storage to avoid flicker.
-
-
tkpi = ImageTk.PhotoImage(image)
-
label_image =
Tkinter.
Label(self.
rootTk, image=tkpi, relief=
"sunken")
-
label_image.grid(row=0, columnspan=6)
-
-
tkpi2 = ImageTk.PhotoImage(image)
-
label_image2 =
Tkinter.
Label(self.
rootTk, image=tkpi2, relief=
"sunken")
-
label_image2.grid(row=0, columnspan=6)
-
-
-
# Initialize wait time.
-
idleLoopTimeInit =
time.
clock()
-
-
# Idle polling loop. Wait for user controls, ellapsed time to next image, or end of slide show.
-
-
# update TK graphics thread.
-
-
-
# Exit idle loop on quit/close
-
-
-
# Exit idle loop on reset
-
-
-
-
# Skip idle loop on initial image.
-
-
-
-
-
-
-
-
-
if time.
clock() – idleLoopTimeInit >
self.
setTime:
-
# Re-initialize wait time unless playback is underway.
-
idleLoopTimeInit =
time.
clock()
-
-
# Update graphics display at least every idleTimeSlice seconds, even when we want to delay for a longer period of time.
-
-
-
-
# Stop normal playback, update play/pause button text, and wait in a loop.
-
-
# Toogle reverse playback so the user can play the png images in reverse direction.
-
-
-
-
# Stop reverse playback, update play/pause button text, and wait in a loop.
-
-
# Toogle reverse playback so the user can play the png images in forward direction.
-
-
-
-
# Normal playback by incrementing/decrementing the png image to display.
-
-
-
-
-
-
# clear reset flag and return to main playback loop with all attributes reset
-
-
-
-
# Private attributes for play loop and interactive button management.
-
-
-
-
-
-
-
-
-
-
-
DOS Batch File png2mpg4.bat
Use this batch file to convert the PNG image sequence into a mpeg-4 video using the FFmpeg utility. This is a DOS / Windows script. A similar script can be generated for Mac OS X or Linux since the FFmpeg utility is available for these operating systems too.
code=dos
-
-
echo Batch File encodes a sequence of png files into mpeg
-4 video using FFmpeg
-
:
-
REM File name: png2mpg4.bat
-
REM Ron Fredericks, LectureMaker LLC, http://www.LectureMaker.com
-
REM Revision 1 12/23/2013: Now auto-scales and supports HD video at 1920 x 1080 pixels
-
:
-
REM Files of the form: bst_graph00001.png, counting up.
-
REM Frame rate set to 1 seconds per frame on input and 12 fps on output.
-
REM Output video will reside in the same directory as the PNG sequence images.
-
REM Note the use of a double %% to encode sequence numbers in this batch file,
-
REM use only one % outside of the batch file.
-
:
-
REM ffmpg parameters used:
-
REM -f image2 forces input to image file demuxer, creating video from many images, following a pattern
-
REM -r 1 indicates reading input at 1 second for each png file
-
REM -start_number 00001 is the start number for the png file sequence
-
REM -i bst_graph%%05d.png is the input pattern for the png file image sequence (numbers are 5 digits long)
-
REM -b:v 5000k is a high quality bitrate for video on output
-
REM -vcodec mpeg4 is the video codec
-
REM -r 30 is the frame rate for the video on output
-
REM -vf scale=720:480 is a simple video filter to scale output to a normal size of 720×480
-
REM -vf scale="’if(gt(a,4/3),1920,-1)’:’if(gt(a,4/3),-1,1280)’" is a more advanced video filter to scale output to 1920×1080 (HD)
-
REM -y overides output file without asking
-
REM movie.mp4 is the output file name
-
:
-
-
-
ffmpeg -f image2 -r
1 -start_number
00001 -i bst_graph%%05d.png -b:v 5000k -vcodec mpeg4 -r
30 -vf scale="’
if(gt
(a,
4/
3),
1920,
-1)‘:’
if(gt
(a,
4/
3),
-1,
1280)‘" -y movie.mp4
-
-
:
-
ECHO.&ECHO.Press any key to end the application.&PAUSE>NUL&GOTO:EOF
Notes on Software Use
You can download the full source code from Github.com as a zip file, see reference section below.
To use this software, the pydot module must be installed into your python environment which is an interface to the popular GraphViz application. I recommend installing GraphViz before installing pydot because pydot installation will try to set up a path to GraphViz. I installed pydot first and had to configure my Windows path manually. These two modules are available for Windows, Mac OS and Linux.
Before running the main program, binarySearchTreeAnimationApp.py, create a subdirectory to store your temporary images. The variable name is “filedir”. There is a windows example and a Mac OS example in the main program.
If you run the program from the IDE, make sure you are using a graphics friendly environment for TK. I use Enthought’s Canaopy so I go into the Edit -> Preference -> Python tab and change PyLab backend from default of “interactive Qt” to “Inline (SVG)”. Without this change, the program will just hang without showing the TK slide show window.
If you run the program from the command line as:
“python binarySearchTreeAnimationApp.py” then the TK graphics will work without changing the graphics backend in the IDE.
On the Mac, the play and reverse buttons will not change color when the user clicks on the reverse button. This is a common issue for many graphics packages, not just TK, in the Mac OS environment.
References
Get the software described here on GitHub: The python source and batch file can be downloaded from GitHub: https://github.com/RonFredericks/visualizeTree
pydot: a python interface to Graphvize’s Dot language: https://code.google.com/p/pydot/
GraphViz: Graph visualization cross-platform program: http://www.graphviz.org/
Some more graphviz links:
graphviz gallery (crazy examples here!): http://www.graphviz.org/Gallery.php
graphviz documentation: http://www.graphviz.org/Documentation.php
graphviz documentation on attributes: http://www.graphviz.org/doc/info/attrs.html
Generating Graph Visualizations with pydot and Graphviz http://pythonhaven.wordpress.com/2009/12/09/generating_graphs_with_pydot/
FFmpeg: Cross-platform solution to record, convert and stream audio and video: http://www.ffmpeg.org/
Tkinter: standard python GUI: http://docs.python.org/2/library/tkinter.html
Image and ImageTk: the python image library: http://www.pythonware.com/products/pil/
align=”left”>GeSHi source code highlighting: An open source library: http://qbnz.com/highlighter/
The binaryTree class used in this software demo was taken from professor Eric Grimson’s lecture series as part of MITx course 6.00.1x: http://www.edx.org
RXPF2THP4RWE
Technorati Tags: Animation, Binary Search Tree, binaryTree, FFmpeg, graphViz, pyDot, Python, slideShow, Tkinter, Tree, video, visualizeTree
constant running time
logarithmic running time
gets larger, the complexity of the algorithm grows at a rate of 
.
linear running time
.
log-linear running time
for comparisons
for copy operations
number of calls to merge
as indicated in the code’s comment. The Big O combination of the two segments of Mergesort is 
polynomial running time
, or quadratic complexity.
exponential running time
, there are 
cases. Result is a Big O complexity of 
, or exponential complexity.
