# Algorithm Visualizer

By Zhongkai Liu (zl777) and Yefei Si (ys948)

## Introduction

The goal of this project is to build an algorithm visualizer using Raspberry Pi and a 16x32 RGB LED panel. The implemented algorithms in the project include tree pre-order, in-order, post-order, level-order traversal, and Graph BFS and DFS. Nodes and edges are represented by different colors on the LED panel. The user interacts with the user interface to select one algorithm to run and also can choose the speed of the process and the shape of nodes on the panel.

## Project Objective:

The purpose of this project is to develop an education tool to help programming beginners understand algorithms.

• Develop the programs of the following algorithms:
• Tree Traversal:
• Pre-order
• In-order
• Post-order
• Level-order
• Graph Traversal:
• BFS
• DFS
• Display the process of algorithms on the LED panel
• Build a User Interface to select algorithms and control the process

## Design and Testing

### Big Picture

Figure 1: Project Design

The project has three main parts, connecting the LED panel to the Raspberry Pi, developing the programs of algorithms and building a user interface that allows users to select and control an algorithm. As shown in Figure 1, the user only interacts with the user interface to select the algorithm. The user interface calls the corresponding algorithm program. The program runs the algorithm and uses LED control program to send signals through GPIO pins to the LED panel to display.

### LED Panel Connection

The connection between LED panel and Raspberry Pi was finished by following the Guide for Connecting 16x32 RGB LED Panel to a Raspberry Pi. Those jumping wires are flexible and the connection is not very stable. Therefore, a ribbon cable was used to extend the connection and make it more robust. However, it is noticeable that when the ribbon cable was connected to the LED, the position of the pin was actually flipped on the other end of the ribbon cable.

After wiring up the Pi and LED panel, we did a small test of the connection. However, we found that red LED and green LED were not working on the half of the panel, which means R1 and G1 pins are not working or R2 and G2 pins are not working properly. Therefore, we switched pin and the panel displayed correct patterns as we wanted.

### Algorithm Programs

The programs are developed by applying the principles of Object-Oriented Programming (OOP). These programs are divided into four levels.

#### Panel

The python module “panel.py” define a class `Panel`, which represents the LED panel and includes all the information and behaviors of the panel. The class `Panel` setups all pins and determines how to send signals to the pins to control the display on the physical LED panel. An instance of class `Panel` maintains a 16 by 32 matrix (2-D array) variable `screen`, of which each element represents the color of the corresponding LED on the physical panel. The Panel class provides four useful methods for programs on higher levels to call.

#### Node and Line

The python modules “node_point.py” and “node_cross.py” define classes `Node`, `TreeNode` and `GraphNode`. The class `Node` represents a general node, and `TreeNode` and `GraphNode` are inherited from `Node`, which represent node in tree or graph repectively. The difference between “node_point.py” and “node_cross.py” is the shape of the node shown on the panel. “node_point.py” uses a single LED to represent the node, and “node_cross.py” one uses a cross formed by five LEDs. The python module “line.py” defines a class `Line` that represents an abstract line. These classes are abstractions of nodes and lines on the panel. They must call the methods provided by “panel.py” to draw and display them on the panel.

#### Tree and Graph

The python modules “tree_point.py” and “tree_cross.py” define the class `Tree`, which is the data structure tree. A tree is constructed a list of connected nodes with no loop connection. They import python module “node_point.py” and “node_cross.py” respectively to use different representations of node. Besides, they are identical to each other, which shows an advantage of OOP. The class `Tree` contains the method to select a random tree from a group of trees. It also has methods of traversal algorithms including “pre-order”, “in-order”, “post-order”, “level-order”. Similarly, the python modules “graph_point.py” and “graph_cross.py” define the class `Graph`, which is the data structure graph. A graph is a list of nodes and edges. Except for using different representations of node, they are identical. The class `Graph` contains the method to select a random graph. It also has methods of algorithms of “BFS” and “DFS”.

#### Tree and Graph Algorithm

The python modules “tree_algorithm” and “graph_algorithm” are encapsulations of algorithms implemented in class `Tree` and class `Graph`. They encapsulate the necessary steps of each algorithm into one method, which allows the User Interface to run an algorithm by calling one single method.

#### Programs Summary

As discussed in this section, these programs are clearly divided into four levels. For each level, it only needs to call certain methods provided by the lower level, and does not depend on the implementations on any lower level. The details of implementations on any lower level are hid. In addition, it also provides methods for programs on the higher level to call. The lowest level, Panel, deals with the sending signals to the GPIO pins. The highest level, Tree and Graph Algorithm, provides methods for each algorithm for User Interface program to call. It is shown how these algorithm programs connect the physical LED panel display and the User Interface.

### User Interface

User interface is an essential part of this project, since it is the only way that users can interact with and it should be user-friendly. There are five levels of interfaces in total.

Shown in Figure 2, the first level allows users to choose to quit or enter into the second level.

Shown in Figure 3, the second level, which is the algorithm choosing level, allows users to select “Tree” and “Graph” to run.

Shown in Figure 4 and 5, after the algorithm is selected, the interface of “Tree algorithm” allows user to select four traversal methods: preorder, inorder, postorder and levelorder. The interface of “Graph algorithm” has “BFS” and “DFS” button.

Shown in Figure 6 and 7, Each traversal method button leads to a control panel, which is the fourth level interface, so that users can select the speed and node shape. There are two node shapes: cross node and point node. The selected shape and speed icons will be enlarged to make users realize what choice they just made.

The final level is used to indicate that the algorithm is running. When the program traverses the tree or graph, it takes approximately 30 seconds to finish. Therefore, instead of freezing the screen, it is better to tell the user that the LED panel is running and he needs to wait until the process finishes.

The interface was implemented with pygame and the button class is created and it has a draw function and highlight function. Both draw and highlight function take self as input and draw a desired button on the interface, but the latter is used when icons needs to be enlarged.

Before the first testing, we didn’t have the fifth level interface. We found that it is wield when we ran the algorithm, the interface just froze at control panel interface. Therefore, we decided to add the fifth level to tell users to wait. Another bug occurred when we first implemented the control panel, the algorithm could run without speed and node shape being chosen. Therefore, we required users select speed and node shape before running the algorithm.

Figure 2: User Interface: Level 1

Figure 3: User Interface: Level 2

Figure 4: User Interface: Level 3 Tree

Figure 5: User Interface: Level 3 Graph

Figure 6: User Interface: Level 4 Tree

Figure 7: User Interface: Level 4 Graph

## Result and Conclusion

Although we had some issues with the LED panel and some bugs in User Interface program, after fixing them, everything works well as expected in the initial project description. The user can use the user interface to select an algorithm to run and also choose the speed and shape of nodes on the panel.

## Future Work

In our current program, every time users run the program, it will create a random tree or graph, it is helpful to add a replay function to allow users to watch the process again.

We could develop more algorithms in this project, like shortest path algorithm (i.e. Dijkstra's algorithm), maze generation algorithm etc. Also, we may use a 3-D LED cube to display the algorithm instead of using a 2-D LED panel.

## Work Distribution

### Yefei Si

ys948@cornell.edu

Connected LED panel and built the user interface

### Zhongkai Liu

zl777@cornell.edu

Developed and tested all algorithm programs

## Code Appendix

#### Codes List

• panel.py
• node_point.py
• node_cross.py
• line.py
• tree_point.py
• tree_cross.py
• graph_point.py
• graph_cross.py
• tree_algorithm.py
• graph_algorithm.py
• user_interface.py

#### panel.py

 ``` 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183``` ```import RPi.GPIO as GPIO import time # Class define the LED panel class Panel(object): # time variable delay = 0.000001 frame_duration = 0.1 # Define size of Screen width = 16 length = 32 # Define Pins # RGB Pin red1_pin = 27 green1_pin = 15 blue1_pin = 22 red2_pin = 23 green2_pin = 24 blue2_pin = 25 # Address Pin a_pin = 7 b_pin = 8 c_pin = 9 # Other Pin clock_pin = 3 latch_pin = 4 oe_pin = 2 def __init__(self): # init screen matrix self.screen = [[0 for x in range(self.length)] for x in range(self.width)] # GPIO setups GPIO.setwarnings(False) GPIO.setmode(GPIO.BCM) GPIO.setup(self.red1_pin, GPIO.OUT) GPIO.setup(self.green1_pin, GPIO.OUT) GPIO.setup(self.blue1_pin, GPIO.OUT) GPIO.setup(self.red2_pin, GPIO.OUT) GPIO.setup(self.green2_pin, GPIO.OUT) GPIO.setup(self.blue2_pin, GPIO.OUT) GPIO.setup(self.clock_pin, GPIO.OUT) GPIO.setup(self.a_pin, GPIO.OUT) GPIO.setup(self.b_pin, GPIO.OUT) GPIO.setup(self.c_pin, GPIO.OUT) GPIO.setup(self.latch_pin, GPIO.OUT) GPIO.setup(self.oe_pin, GPIO.OUT) def clean_gpio(self): GPIO.cleanup() def clock(self): GPIO.output(self.clock_pin, 1) GPIO.output(self.clock_pin, 0) def latch(self): GPIO.output(self.latch_pin, 1) GPIO.output(self.latch_pin, 0) def bits_from_int(self, x): a_bit = x & 1 b_bit = x & 2 c_bit = x & 4 return (a_bit, b_bit, c_bit) def set_row(self, row): a_bit, b_bit, c_bit = self.bits_from_int(row) GPIO.output(self.a_pin, a_bit) GPIO.output(self.b_pin, b_bit) GPIO.output(self.c_pin, c_bit) def set_color_top(self, color): red, green, blue = self.bits_from_int(color) GPIO.output(self.red1_pin, red) GPIO.output(self.green1_pin, green) GPIO.output(self.blue1_pin, blue) def set_color_bottom(self, color): red, green, blue = self.bits_from_int(color) GPIO.output(self.red2_pin, red) GPIO.output(self.green2_pin, green) GPIO.output(self.blue2_pin, blue) # refresh whole LED panel def refresh(self): for row in range(8): GPIO.setmode(GPIO.BCM) GPIO.output(self.oe_pin, 1) self.set_color_top(0) self.set_row(row) for col in range(32): self.set_color_top(self.screen[row][col]) self.set_color_bottom(self.screen[row+8][col]) self.clock() self.latch() GPIO.output(self.oe_pin, 0) time.sleep(self.delay) # keep refresh() for frame_duration # call this method every time a new screen should be displayed on the panel def frame(self): start_time = time.time() run = True while run: self.refresh() now_time = time.time() if (now_time - start_time > self.frame_duration): run = False def fill_rectangle(self, x1, y1, x2, y2, color): for x in range(x1, x2 + 1): for y in range(y1, y2 + 1): self.screen[y][x] = color # set one LED at (x, y) to color def set(self, x, y, color): # 0 <= x <= 31 # 0 <= y <= 15 # colors: # Black = 0 # Red = 1 # Green = 2 # Yellow = 3 # Blue = 4 # Magenta = 5 # Cyan = 6 # White = 7 if (x >= 0 and x < self.length and y >= 0 and y < self.width): self.screen[y][x] = color # draw a Point on the screen def draw_point(self, x, y, color): self.set(x, y, color) # draw a Node of tree or graph at (x, y) with color def draw_node(self, x, y, color): # delta of a cross shape delta = [(0, 0), (1, 0), (0, 1), (-1, 0), (0, -1)] for i, j in delta: self.set(x + i, y + j, color) # generate a Line from (x1, y1) to (x2, y2) with color # Only can generate a horizontal or vertical or diagonal line def draw_line(self, x1, y1, x2, y2, color): if not (x1 == x2 or y1 == y2 or abs(x2 - x1) == abs(y2 - y1)): raise ValueError( "Bad x1 = {}, y1 = {}, x2 = {}, y2 = {}! \n Only can generate a horizontal or vertical or diagonal line".format(x1, x2, y1, y2)) delta = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (0, 0)] i = 0 if (x2 > x1): if (y2 == y1): i = 0 elif (y2 > y1): i = 1 else: i = 7 elif (x2 == x1): if (y2 == y1): i = 8 elif (y2 > y1): i = 2 else: i = 6 else: if (y2 == y1): i = 4 elif (y2 > y1): i = 3 else: i = 5 dx, dy = delta[i] if (x2 != x1): for i in range(0, abs(x2 - x1) + 1): self.set(x1 + i * dx, y1 + i * dy, color) else: for i in range(0, abs(y2 - y1) + 1): self.set(x1 + i * dx, y1 + i * dy, color) ```

#### node_point.py

 ``` 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130``` ```from panel import Panel from line import Line class Node(object): # bind Node with a screen object def __init__(self, x, y, color, screen, nid): if (not isinstance(screen, Panel)): raise ValueError("screen must be an object of class Panel!") else: self.id = nid self.x = x self.y = y self.color = color self.screen = screen # draw a point Node on screen, BUT no refresh, need refresh to display later def draw(self): # print("when draw node, node {}, color is {}".format(self.id, self.color)) self.screen.draw_point(self.x, self.y, self.color) def change_color(self, color): self.color = color # return ((x1, y1), (x2, y2)) when connect this node to another node def connection_position(self, node): x1 = self.x y1 = self.y x2 = node.x y2 = node.y if (x1 == x2): if y2 < y1: return ((x1, y1 - 1), (x2, y2 + 1)) else: return ((x1, y1 + 1), (x2, y2 - 1)) elif (y1 == y2): if x2 < x1: return ((x1 - 1, y1), (x2 + 1, y2)) else: return ((x1 + 1, y1), (x2 - 1, y2)) elif (abs(x2 - x1) == abs(y2 - y1)): if x2 > x1: if y2 > y1: return ((x1 + 1, y1 + 1), (x2 - 1, y2 - 1)) elif y2 < y1: return ((x1 + 1, y1 - 1), (x2 - 1, y2 + 1)) elif x2 < x1: if y2 > y1: return ((x1 - 1, y1 + 1), (x2 + 1, y2 - 1)) elif y2 < y1: return ((x1 - 1, y1 - 1), (x2 + 1, y2 + 1)) # return an instance of class Line that connects two cross nodes def line_connect_to(self, node, color): ((x1, y1), (x2, y2)) = self.connection_position(node) return Line(x1, y1, x2, y2, color, self.screen) def get_id(self): return self.id # TreeNode inherited from class Node # TreeNode has parent, children class TreeNode(Node): def __init__(self, x, y, color, screen, nid): super().__init__(x, y, color, screen, nid) self.parent = None self.line = None self.left = None self.right = None def set_children(self, left, right): self.left = left self.right = right def set_left(self, left): self.left = left def set_right(self, right): self.right = right def get_children(self): return (self.left, self.right) def get_left(self): return self.left def get_right(self): return self.right def set_parent(self, parent): self.parent = parent def get_parent(self): return self.parent # For each TreeNode, it has only one line from parent to it def set_line(self, line): self.line = line def get_line(self): return self.line def isLeaf(self): return self.left == None and self.right == None def isRoot(self): return self.parent == None class GraphNode(Node): def __init__(self, x, y, node_color, edge_color, screen, nid): super().__init__(x, y, node_color, screen, nid) # self.neighbors = set() self.edges = {} self.visited = False def mark_visited(self): self.visited = True def new_edge_to(self, node, edge_color): return self.line_connect_to(node, edge_color) def add_neighbor(self, node, edge): # self.neighbors.add(node) self.edges[node] = edge def get_edges(self): return self.edges ```

#### node_cross.py

 ``` 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129``` ```from panel import Panel from line import Line class Node(object): # bind Node with a screen object def __init__(self, x, y, color, screen, nid): if (not isinstance(screen, Panel)): raise ValueError("screen must be an object of class Panel!") else: self.id = nid self.x = x self.y = y self.color = color self.screen = screen # draw a cross Node on screen, BUT no refresh, need refresh to display later def draw(self): # print("when draw node, node {}, color is {}".format(self.id, self.color)) self.screen.draw_node(self.x, self.y, self.color) def change_color(self, color): self.color = color # return ((x1, y1), (x2, y2)) when connect this node to another node def connection_position(self, node): x1 = self.x y1 = self.y x2 = node.x y2 = node.y if (x1 == x2): if y2 < y1: return ((x1, y1 - 2), (x2, y2 + 2)) else: return ((x1, y1 + 2), (x2, y2 - 2)) elif (y1 == y2): if x2 < x1: return ((x1 - 2, y1), (x2 + 2, y2)) else: return ((x1 + 2, y1), (x2 - 2, y2)) elif (abs(x2 - x1) == abs(y2 - y1)): if x2 > x1: if y2 > y1: return ((x1 + 1, y1 + 1), (x2 - 1, y2 - 1)) elif y2 < y1: return ((x1 + 1, y1 - 1), (x2 - 1, y2 + 1)) elif x2 < x1: if y2 > y1: return ((x1 - 1, y1 + 1), (x2 + 1, y2 - 1)) elif y2 < y1: return ((x1 - 1, y1 - 1), (x2 + 1, y2 + 1)) # return an instance of class Line that connects two cross nodes def line_connect_to(self, node, color): ((x1, y1), (x2, y2)) = self.connection_position(node) return Line(x1, y1, x2, y2, color, self.screen) def get_id(self): return self.id # TreeNode inherited from class Node # TreeNode has parent, children class TreeNode(Node): def __init__(self, x, y, color, screen, nid): super().__init__(x, y, color, screen, nid) self.parent = None self.line = None self.left = None self.right = None def set_children(self, left, right): self.left = left self.right = right def set_left(self, left): self.left = left def set_right(self, right): self.right = right def get_children(self): return (self.left, self.right) def get_left(self): return self.left def get_right(self): return self.right def set_parent(self, parent): self.parent = parent def get_parent(self): return self.parent # For each TreeNode, it has only one line from parent to it def set_line(self, line): self.line = line def get_line(self): return self.line def isLeaf(self): return self.left == None and self.right == None def isRoot(self): return self.parent == None class GraphNode(Node): def __init__(self, x, y, node_color, edge_color, screen, nid): super().__init__(x, y, node_color, screen, nid) # self.neighbors = set() self.edges = {} self.visited = False def mark_visited(self): self.visited = True def new_edge_to(self, node, edge_color): return self.line_connect_to(node, edge_color) def add_neighbor(self, node, edge): self.edges[node] = edge def get_edges(self): return self.edges ```

#### line.py

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21``` ```from panel import Panel class Line(object): def __init__(self, x1, y1, x2, y2, color, screen): if (not isinstance(screen, Panel)): raise ValueError("screen must be an instance of class Panel!") else: self.color = color self.screen = screen self.x1 = x1 self.y1 = y1 self.x2 = x2 self.y2 = y2 # draw this Line on screen, BUT no refresh, need refresh to display later def draw(self): self.screen.draw_line(self.x1, self.y1, self.x2, self.y2, self.color) def change_color(self, color): self.color = color ```

#### tree_point.py

 ``` 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253``` ```import random from panel import Panel from node_point import TreeNode from collections import deque class Tree(object): def __init__(self, screen): if (not isinstance(screen, Panel)): raise ValueError("screen must be an object of class Panel!") else: self.screen = screen self.nodes = [] self.lines = [] self.node_num = 0 self.line_num = 0 self.root = None self.duration = 1 # set node_color to WHITE as default self.node_color = 3 # set line_color to GREEN as default self.line_color = 7 # set visited node color to RED as default self.visited_node_color = 1 # set visited line color to GREEN as default self.visited_line_color = 2 # set node and line color of this tree # avoid setting color after having nodes or lines def set_color(self, node_color, line_color, visited_node_color, visited_line_color): self.node_color = node_color self.line_color = line_color self.visited_node_color = visited_node_color self.visited_line_color = visited_line_color # set duration def set_duration(self, duration): self.duration = duration # return a new node at (x, y) def new_node(self, x, y): return TreeNode(x, y, self.node_color, self.screen, self.node_num) # return the line that connects two existing node in this tree with line # node1 should be parent node # node2 should be children node def new_connection(self, node1, node2): line = node1.line_connect_to(node2, self.line_color) if (node2.x < node1.x): node1.set_left(node2) else: node1.set_right(node2) node2.set_parent(node1) node2.set_line(line) return line # add new node instance to nodes def add_node(self, x, y): self.nodes.append(self.new_node(x, y)) self.node_num += 1 # add new line instance to lines def add_line(self, node1, node2): self.lines.append(self.new_connection(node1, node2)) self.line_num += 1 # draw this tree on screen def draw_tree(self): for node in self.nodes: node.draw() for line in self.lines: line.draw() # return a random group of positions of nodes in a large tree def large_tree_nodes(self): nodes_group = [(15, 1), (12, 4), (18, 4), (9, 7), (15, 7), (21, 7), (6, 10), ( 12, 10), (18, 10), (24, 10), (3, 13), (9, 13), (15, 13), (21, 13), (27, 13)] delta = [(0, 0), (1, 0), (2, 0), (3, 0), (-1, 0), (-2, 0), (0, 1), (1, 1), (2, 1), (3, 1), (-1, 1), (-2, 1)] i = random.randint(0, len(delta) - 1) print("use nodes group {}".format(i)) dx, dy = delta[i] for i in range(0, len(nodes_group)): x, y = nodes_group[i] nodes_group[i] = (x + dx, y + dy) return nodes_group # connect a group of nodes in a large tree def connect_large_tree(self): lines = [] lines1 = [(0, 1), (0, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 9), (6, 10), (7, 11), (8, 12), (8, 13), (9, 14)] lines2 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7), (4, 8), (5, 9), (6, 10), (7, 11), (8, 12), (8, 13), (9, 14)] lines3 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7), (4, 8), (5, 9), (6, 10), (7, 11), (7, 12), (9, 13), (9, 14)] lines4 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7), (5, 8), (5, 9), (6, 10), (6, 11), (7, 12), (9, 13), (9, 14)] lines5 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (3, 7), (5, 8), (5, 9), (6, 10), (6, 11), (8, 12), (9, 13), (9, 14)] lines6 = [(0, 1), (0, 2), (1, 3), (2, 4), (2, 5), (3, 6), (4, 7), (5, 8), (5, 9), (6, 10), (6, 11), (7, 12), (8, 13), (9, 14)] lines.append(lines1) lines.append(lines2) lines.append(lines3) lines.append(lines4) lines.append(lines5) lines.append(lines6) i = random.randint(0, 5) print("use line {}".format(i)) for n1, n2 in lines[i]: self.add_line(self.nodes[n1], self.nodes[n2]) # generate a large tree def generate_large_tree(self): # generate 15 TreeNodes nodes_position = self.large_tree_nodes() for x, y in nodes_position: self.add_node(x, y) # set the first node as the root node of this tree self.root = self.nodes[0] # generate 14 lines self.connect_large_tree() # draw a large tree on screen def draw_large_tree(self): # print("call draw_large_tree()") self.generate_large_tree() self.draw_tree() # display tree on panel def display_tree(self, times): for i in range(times): self.screen.frame() # update color of a node in this tree def update_node_color(self, node_id, color): # print("before change, color is {}".format(self.nodes[node_id].color)) self.nodes[node_id].change_color(color) # print("after change, color is {}".format(self.nodes[node_id].color)) # update color of a line of a node in this tree def update_line_color(self, node_id, color): self.nodes[node_id].get_line().change_color(color) # visit the line of this node def visit_line(self, node): node_id = node.get_id() self.update_line_color(node_id, self.visited_line_color) self.draw_tree() self.display_tree(self.duration) # leave the line of this node def leave_line(self, node): node_id = node.get_id() self.update_line_color(node_id, self.line_color) self.draw_tree() self.display_tree(self.duration) # visit the node alone def visit_node(self, node): # print("visit node {}".format(node.get_id())) node_id = node.get_id() # print("visit node {}, want to change to color {}".format( # node_id, self.visited_node_color)) self.update_node_color(node_id, self.visited_node_color) self.draw_tree() self.display_tree(self.duration) # entry for inorder traversal def inorder_traversal(self): self.inorder_recursion(self.root) # recursive function for inorder traversal def inorder_recursion(self, node): # visit left child first left = node.get_left() if (left != None): self.visit_line(left) self.inorder_recursion(left) # visit this node then self.visit_node(node) right = node.get_right() # visit right child last if (right != None): self.visit_line(right) self.inorder_recursion(right) # after visiting this subtree, leave this line if (not node.isRoot()): self.leave_line(node) # entry for preorder traversal def preorder_traversal(self): self.preorder_recursion(self.root) # recursive function for preorder traversal def preorder_recursion(self, node): # visit this node first self.visit_node(node) # visit left child then left = node.get_left() if (left != None): self.visit_line(left) self.preorder_recursion(left) right = node.get_right() # visit right child last if (right != None): self.visit_line(right) self.preorder_recursion(right) # after visiting this subtree, leave this line if (not node.isRoot()): self.leave_line(node) # entry for postorder traversal def postorder_traversal(self): self.postorder_recursion(self.root) # recursive function for preorder traversal def postorder_recursion(self, node): # visit left child fist left = node.get_left() if left: self.visit_line(left) self.postorder_recursion(left) right = node.get_right() # visit right child then if right: self.visit_line(right) self.postorder_recursion(right) # visit this node last self.visit_node(node) # after visiting this subtree, leave this line if (not node.isRoot()): self.leave_line(node) def levelorder_traversal(self): queue = deque([self.root, ]) while queue: n = len(queue) for i in range(n): node = queue.popleft() if (not node.isRoot()): self.visit_line(node) self.visit_node(node) left = node.get_left() right = node.get_right() if left: queue.append(left) if right: queue.append(right) ```

#### tree_cross.py

 ``` 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253``` ```import random from panel import Panel from node_cross import TreeNode from collections import deque class Tree(object): def __init__(self, screen): if (not isinstance(screen, Panel)): raise ValueError("screen must be an object of class Panel!") else: self.screen = screen self.nodes = [] self.lines = [] self.node_num = 0 self.line_num = 0 self.root = None self.duration = 1 # set node_color to WHITE as default self.node_color = 3 # set line_color to GREEN as default self.line_color = 7 # set visited node color to RED as default self.visited_node_color = 1 # set visited line color to GREEN as default self.visited_line_color = 2 # set node and line color of this tree # avoid setting color after having nodes or lines def set_color(self, node_color, line_color, visited_node_color, visited_line_color): self.node_color = node_color self.line_color = line_color self.visited_node_color = visited_node_color self.visited_line_color = visited_line_color # set duration def set_duration(self, duration): self.duration = duration # return a new node at (x, y) def new_node(self, x, y): return TreeNode(x, y, self.node_color, self.screen, self.node_num) # return the line that connects two existing node in this tree with line # node1 should be parent node # node2 should be children node def new_connection(self, node1, node2): line = node1.line_connect_to(node2, self.line_color) if (node2.x < node1.x): node1.set_left(node2) else: node1.set_right(node2) node2.set_parent(node1) node2.set_line(line) return line # add new node instance to nodes def add_node(self, x, y): self.nodes.append(self.new_node(x, y)) self.node_num += 1 # add new line instance to lines def add_line(self, node1, node2): self.lines.append(self.new_connection(node1, node2)) self.line_num += 1 # draw this tree on screen def draw_tree(self): for node in self.nodes: node.draw() for line in self.lines: line.draw() # return a random group of positions of nodes in a large tree def large_tree_nodes(self): nodes_group = [(15, 1), (12, 4), (18, 4), (9, 7), (15, 7), (21, 7), (6, 10), ( 12, 10), (18, 10), (24, 10), (3, 13), (9, 13), (15, 13), (21, 13), (27, 13)] delta = [(0, 0), (1, 0), (2, 0), (3, 0), (-1, 0), (-2, 0), (0, 1), (1, 1), (2, 1), (3, 1), (-1, 1), (-2, 1)] i = random.randint(0, len(delta) - 1) print("use nodes group {}".format(i)) dx, dy = delta[i] for i in range(0, len(nodes_group)): x, y = nodes_group[i] nodes_group[i] = (x + dx, y + dy) return nodes_group # connect a group of nodes in a large tree def connect_large_tree(self): lines = [] lines1 = [(0, 1), (0, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 9), (6, 10), (7, 11), (8, 12), (8, 13), (9, 14)] lines2 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7), (4, 8), (5, 9), (6, 10), (7, 11), (8, 12), (8, 13), (9, 14)] lines3 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7), (4, 8), (5, 9), (6, 10), (7, 11), (7, 12), (9, 13), (9, 14)] lines4 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7), (5, 8), (5, 9), (6, 10), (6, 11), (7, 12), (9, 13), (9, 14)] lines5 = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (3, 6), (3, 7), (5, 8), (5, 9), (6, 10), (6, 11), (8, 12), (9, 13), (9, 14)] lines6 = [(0, 1), (0, 2), (1, 3), (2, 4), (2, 5), (3, 6), (4, 7), (5, 8), (5, 9), (6, 10), (6, 11), (7, 12), (8, 13), (9, 14)] lines.append(lines1) lines.append(lines2) lines.append(lines3) lines.append(lines4) lines.append(lines5) lines.append(lines6) i = random.randint(0, 5) print("use line {}".format(i)) for n1, n2 in lines[i]: self.add_line(self.nodes[n1], self.nodes[n2]) # generate a large tree def generate_large_tree(self): # generate 15 TreeNodes nodes_position = self.large_tree_nodes() for x, y in nodes_position: self.add_node(x, y) # set the first node as the root node of this tree self.root = self.nodes[0] # generate 14 lines self.connect_large_tree() # draw a large tree on screen def draw_large_tree(self): # print("call draw_large_tree()") self.generate_large_tree() self.draw_tree() # display tree on panel def display_tree(self, times): for i in range(times): self.screen.frame() # update color of a node in this tree def update_node_color(self, node_id, color): # print("before change, color is {}".format(self.nodes[node_id].color)) self.nodes[node_id].change_color(color) # print("after change, color is {}".format(self.nodes[node_id].color)) # update color of a line of a node in this tree def update_line_color(self, node_id, color): self.nodes[node_id].get_line().change_color(color) # visit the line of this node def visit_line(self, node): node_id = node.get_id() self.update_line_color(node_id, self.visited_line_color) self.draw_tree() self.display_tree(self.duration) # leave the line of this node def leave_line(self, node): node_id = node.get_id() self.update_line_color(node_id, self.line_color) self.draw_tree() self.display_tree(self.duration) # visit the node alone def visit_node(self, node): # print("visit node {}".format(node.get_id())) node_id = node.get_id() # print("visit node {}, want to change to color {}".format( # node_id, self.visited_node_color)) self.update_node_color(node_id, self.visited_node_color) self.draw_tree() self.display_tree(self.duration) # entry for inorder traversal def inorder_traversal(self): self.inorder_recursion(self.root) # recursive function for inorder traversal def inorder_recursion(self, node): # visit left child first left = node.get_left() if (left != None): self.visit_line(left) self.inorder_recursion(left) # visit this node then self.visit_node(node) right = node.get_right() # visit right child last if (right != None): self.visit_line(right) self.inorder_recursion(right) # after visiting this subtree, leave this line if (not node.isRoot()): self.leave_line(node) # entry for preorder traversal def preorder_traversal(self): self.preorder_recursion(self.root) # recursive function for preorder traversal def preorder_recursion(self, node): # visit this node first self.visit_node(node) # visit left child then left = node.get_left() if (left != None): self.visit_line(left) self.preorder_recursion(left) right = node.get_right() # visit right child last if (right != None): self.visit_line(right) self.preorder_recursion(right) # after visiting this subtree, leave this line if (not node.isRoot()): self.leave_line(node) # entry for postorder traversal def postorder_traversal(self): self.postorder_recursion(self.root) # recursive function for preorder traversal def postorder_recursion(self, node): # visit left child fist left = node.get_left() if left: self.visit_line(left) self.postorder_recursion(left) right = node.get_right() # visit right child then if right: self.visit_line(right) self.postorder_recursion(right) # visit this node last self.visit_node(node) # after visiting this subtree, leave this line if (not node.isRoot()): self.leave_line(node) def levelorder_traversal(self): queue = deque([self.root, ]) while queue: n = len(queue) for i in range(n): node = queue.popleft() if (not node.isRoot()): self.visit_line(node) self.visit_node(node) left = node.get_left() right = node.get_right() if left: queue.append(left) if right: queue.append(right) ```

#### graph_point.py

 ``` 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250``` ```from panel import Panel from node_point import GraphNode from collections import deque from random import randint class Graph(object): def __init__(self, screen): if (not isinstance(screen, Panel)): raise ValueError("screen must be an object of class Panel!") else: self.screen = screen self.adjlist = [] self.nodes = [] self.edges = [] self.node_num = 0 self.edge_num = 0 self.root = None self.duration = 1 # set node_color to WHITE as default self.node_color = 3 # set edge_color to GREEN as default self.edge_color = 7 # set visited node color to RED as default self.visited_node_color = 1 # set visited edge color to GREEN as default self.visited_edge_color = 2 def set_duration(self, duration): self.duration = duration # set node and line color of this graph # avoid setting color after having nodes or lines def set_color(self, node_color, edge_color, visited_node_color, visited_edge_color): self.node_color = node_color self.edge_color = edge_color self.visited_node_color = visited_node_color self.visited_edge_color = visited_edge_color # return a new node at (x, y) def new_node(self, x, y): return GraphNode(x, y, self.node_color, self.edge_color, self.screen, self.node_num) def add_node(self, x, y): self.nodes.append(self.new_node(x, y)) self.node_num += 1 def new_edge(self, node1, node2): edge = node1.new_edge_to(node2, self.edge_color) node1.add_neighbor(node2, edge) node2.add_neighbor(node1, edge) return edge def add_edge(self, node1, node2): self.edges.append(self.new_edge(node1, node2)) self.edge_num += 1 # draw this graph on screen def draw_graph(self): for node in self.nodes: node.draw() for edge in self.edges: edge.draw() # return a random group of postions of nodes in a large graph def large_graph_nodes(self): nodes_group1 = [ (5, 2), (12, 2), (17, 1), (27, 1), (1, 6), (5, 5), (9, 5), (16, 6), (19, 3), (22, 6), (27, 6), (30, 3), (1, 13), (4, 10), (12, 8), (14, 10), (19, 10), (27, 11), (30, 8), (7, 13), (11, 13), (15, 14), (23, 14), (30, 14), (22, 11) ] return nodes_group1 # return a random group of edges in a large graph def large_graph_edges(self): edges1 = [ (0, 1), (0, 4), (1, 7), (1, 14), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (10, 11), (11, 18), (4, 12), (6, 13), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (6, 14), (14, 15), (15, 16), (16, 21), (9, 24), (21, 22), (16, 22), (17, 24), (9, 17), (9, 10), (10, 17), (17, 18), (18, 23), (22, 23), (17, 23) ] edges2 = [ (0, 1), (1, 7), (1, 14), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (10, 11), (11, 18), (4, 12), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (6, 14), (14, 15), (15, 16), (16, 21), (9, 24), (16, 22), (17, 24), (9, 10), (17, 18), (18, 23), (22, 23), (17, 23) ] edges3 = [ (0, 1), (0, 4), (1, 7), (1, 14), (1, 6), (5, 6), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (11, 18), (4, 12), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (6, 14), (15, 16), (16, 21), (9, 24), (21, 22), (16, 22), (17, 24), (9, 17), (9, 10), (10, 17), (17, 18), (18, 23), (22, 23), (17, 23) ] edges4 = [ (0, 1), (0, 4), (1, 7), (1, 14), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (10, 11), (11, 18), (4, 12), (6, 13), (12, 13), (12, 19), (14, 19), (19, 20), (6, 14), (14, 15), (15, 16), (16, 21), (21, 22), (16, 22), (17, 24), (9, 17), (9, 10), (17, 18), (18, 23), (22, 23), (17, 23) ] edges5 = [ (0, 1), (0, 4), (1, 7), (1, 14), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (3, 10), (10, 11), (11, 18), (4, 12), (6, 13), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (6, 14), (14, 15), (15, 16), (16, 21), (21, 22), (16, 22), (17, 24), (9, 17), (10, 17), (17, 18), (18, 23), (22, 23), (17, 23) ] edges6 = [ (0, 1), (0, 4), (1, 7), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (10, 11), (11, 18), (4, 12), (6, 13), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (15, 16), (16, 21), (21, 22), (16, 22), (17, 24), (9, 10), (10, 17), (17, 18), (18, 23), (22, 23), (17, 23), (13, 19) ] edges = [] edges.append(edges1) edges.append(edges2) edges.append(edges3) edges.append(edges4) edges.append(edges5) edges.append(edges6) i = randint(0, 5) return edges[i] # generate a large graph def generate_large_graph(self): # generate all nodes nodes_positions = self.large_graph_nodes() for x, y in nodes_positions: self.add_node(x, y) # generate all edges nodes_connections = self.large_graph_edges() for n1, n2 in nodes_connections: self.add_edge(self.nodes[n1], self.nodes[n2]) # set the start node of graph algorithm def set_root(self, node_id): self.root = self.nodes[node_id] # draw a large graph on the screen def draw_large_graph(self): self.generate_large_graph() self.draw_graph() # display graph on panel def display_graph(self, times): for i in range(times): self.screen.frame() # update color of a node in this graph def update_node_color(self, node, color): node_id = node.get_id() self.nodes[node_id].change_color(color) # update color of a node in this graph def update_edge_color(self, edge, color): edge.change_color(color) # visit the edge def visit_edge(self, edge): self.update_edge_color(edge, self.visited_edge_color) self.draw_graph() self.display_graph(self.duration) # leave the edge def leave_edge(self, edge): self.update_edge_color(edge, self.edge_color) self.draw_graph() self.display_graph(self.duration) # visit the node alone def visit_node(self, node): node.mark_visited() self.update_node_color(node, self.visited_node_color) self.draw_graph() self.display_graph(self.duration) # entry for BFS def bfs_start(self): if (self.root == None): self.root = self.nodes[9] self.bfs(self.root) # BFS Algorithm def bfs(self, root): queue_node = deque([root, ]) queue_edge = deque([]) while queue_node: n = len(queue_node) for i in range(n): node = queue_node.popleft() if (not node.visited): if (queue_edge): edge_from = queue_edge.popleft() self.visit_edge(edge_from) self.visit_node(node) for neighbor, edge in node.get_edges().items(): queue_node.append(neighbor) queue_edge.append(edge) else: if (queue_edge): edge_from = queue_edge.popleft() # entry for DFS def dfs_start(self): if (self.root == None): self.root = self.nodes[9] self.dfs(self.root) # DFS Algorithm def dfs(self, node): self.visit_node(node) for neighbor, edge in node.get_edges().items(): if not neighbor.visited: self.visit_edge(edge) self.dfs(neighbor) self.leave_edge(edge) ```

#### graph_cross.py

 ``` 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251``` ```from panel import Panel from node_cross import GraphNode from collections import deque from random import randint class Graph(object): def __init__(self, screen): if (not isinstance(screen, Panel)): raise ValueError("screen must be an object of class Panel!") else: self.screen = screen self.adjlist = [] self.nodes = [] self.edges = [] self.node_num = 0 self.edge_num = 0 self.root = None self.duration = 1 # set node_color to WHITE as default self.node_color = 3 # set edge_color to GREEN as default self.edge_color = 7 # set visited node color to RED as default self.visited_node_color = 1 # set visited edge color to GREEN as default self.visited_edge_color = 2 def set_duration(self, duration): self.duration = duration # set node and line color of this graph # avoid setting color after having nodes or lines def set_color(self, node_color, edge_color, visited_node_color, visited_edge_color): self.node_color = node_color self.edge_color = edge_color self.visited_node_color = visited_node_color self.visited_edge_color = visited_edge_color # return a new node at (x, y) def new_node(self, x, y): return GraphNode(x, y, self.node_color, self.edge_color, self.screen, self.node_num) def add_node(self, x, y): self.nodes.append(self.new_node(x, y)) self.node_num += 1 def new_edge(self, node1, node2): edge = node1.new_edge_to(node2, self.edge_color) node1.add_neighbor(node2, edge) node2.add_neighbor(node1, edge) return edge def add_edge(self, node1, node2): self.edges.append(self.new_edge(node1, node2)) self.edge_num += 1 # draw this graph on screen def draw_graph(self): for node in self.nodes: node.draw() for edge in self.edges: edge.draw() # return a random group of postions of nodes in a large graph def large_graph_nodes(self): nodes_group1 = [ (5, 2), (12, 2), (17, 1), (27, 1), (1, 6), (5, 5), (9, 5), (16, 6), (19, 3), (22, 6), (27, 6), (30, 3), (1, 13), (4, 10), (12, 8), (14, 10), (19, 10), (27, 11), (30, 8), (7, 13), (11, 13), (15, 14), (23, 14), (30, 14), (22, 11) ] return nodes_group1 # return a random group of edges in a large graph def large_graph_edges(self): edges1 = [ (0, 1), (0, 4), (1, 7), (1, 14), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (10, 11), (11, 18), (4, 12), (6, 13), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (6, 14), (14, 15), (15, 16), (16, 21), (9, 24), (21, 22), (16, 22), (17, 24), (9, 17), (9, 10), (10, 17), (17, 18), (18, 23), (22, 23), (17, 23) ] edges2 = [ (0, 1), (1, 7), (1, 14), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (10, 11), (11, 18), (4, 12), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (6, 14), (14, 15), (15, 16), (16, 21), (9, 24), (16, 22), (17, 24), (9, 10), (17, 18), (18, 23), (22, 23), (17, 23) ] edges3 = [ (0, 1), (0, 4), (1, 7), (1, 14), (1, 6), (5, 6), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (11, 18), (4, 12), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (6, 14), (15, 16), (16, 21), (9, 24), (21, 22), (16, 22), (17, 24), (9, 17), (9, 10), (10, 17), (17, 18), (18, 23), (22, 23), (17, 23) ] edges4 = [ (0, 1), (0, 4), (1, 7), (1, 14), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (10, 11), (11, 18), (4, 12), (6, 13), (12, 13), (12, 19), (14, 19), (19, 20), (6, 14), (14, 15), (15, 16), (16, 21), (21, 22), (16, 22), (17, 24), (9, 17), (9, 10), (17, 18), (18, 23), (22, 23), (17, 23) ] edges5 = [ (0, 1), (0, 4), (1, 7), (1, 14), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (3, 10), (10, 11), (11, 18), (4, 12), (6, 13), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (6, 14), (14, 15), (15, 16), (16, 21), (21, 22), (16, 22), (17, 24), (9, 17), (10, 17), (17, 18), (18, 23), (22, 23), (17, 23) ] edges6 = [ (0, 1), (0, 4), (1, 7), (1, 6), (5, 6), (2, 3), (2, 8), (7, 8), (8, 9), (8, 16), (3, 9), (3, 10), (10, 11), (11, 18), (4, 12), (6, 13), (12, 13), (12, 19), (14, 19), (19, 20), (15, 20), (15, 16), (16, 21), (21, 22), (16, 22), (17, 24), (9, 10), (10, 17), (17, 18), (18, 23), (22, 23), (17, 23), (13, 19) ] edges = [] edges.append(edges1) edges.append(edges2) edges.append(edges3) edges.append(edges4) edges.append(edges5) edges.append(edges6) i = randint(0, 5) return edges[i] # generate a large graph def generate_large_graph(self): # generate all nodes nodes_positions = self.large_graph_nodes() for x, y in nodes_positions: self.add_node(x, y) # generate all edges nodes_connections = self.large_graph_edges() for n1, n2 in nodes_connections: self.add_edge(self.nodes[n1], self.nodes[n2]) # set the start node of graph algorithm def set_root(self, node_id): self.root = self.nodes[node_id] # draw a large graph on the screen def draw_large_graph(self): self.generate_large_graph() self.draw_graph() # display graph on panel def display_graph(self, times): for i in range(times): self.screen.frame() # update color of a node in this graph def update_node_color(self, node, color): node_id = node.get_id() self.nodes[node_id].change_color(color) # update color of a node in this graph def update_edge_color(self, edge, color): edge.change_color(color) # visit the edge def visit_edge(self, edge): self.update_edge_color(edge, self.visited_edge_color) self.draw_graph() self.display_graph(self.duration) # leave the edge def leave_edge(self, edge): self.update_edge_color(edge, self.edge_color) self.draw_graph() self.display_graph(self.duration) # visit the node alone def visit_node(self, node): node.mark_visited() self.update_node_color(node, self.visited_node_color) self.draw_graph() self.display_graph(self.duration) # entry for BFS def bfs_start(self): if (self.root == None): self.root = self.nodes[9] self.bfs(self.root) # BFS Algorithm def bfs(self, root): queue_node = deque([root, ]) queue_edge = deque([]) while queue_node: n = len(queue_node) for i in range(n): node = queue_node.popleft() if (not node.visited): if (queue_edge): edge_from = queue_edge.popleft() self.visit_edge(edge_from) self.visit_node(node) for neighbor, edge in node.get_edges().items(): queue_node.append(neighbor) queue_edge.append(edge) else: if (queue_edge): edge_from = queue_edge.popleft() # entry for DFS def dfs_start(self): if (self.root == None): self.root = self.nodes[9] self.dfs(self.root) # DFS Algorithm def dfs(self, node): self.visit_node(node) for neighbor, edge in node.get_edges().items(): if not neighbor.visited: self.visit_edge(edge) self.dfs(neighbor) self.leave_edge(edge) ```

#### tree_algorithm.py

 ``` 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``` ```from panel import Panel import tree_cross import tree_point class TreeAlgorithm(object): def __init__(self, node_shape, duration): self.screen = Panel() if (node_shape == "cross"): self.tree = tree_cross.Tree(self.screen) else: self.tree = tree_point.Tree(self.screen) self.tree.set_duration(duration) # display the initial tree on the panel def display_init(self): self.tree.draw_large_tree() self.tree.display_tree(2) def inorder(self): self.display_init() self.tree.inorder_traversal() self.tree.display_tree(2) self.screen.clean_gpio() def preorder(self): self.display_init() self.tree.preorder_traversal() self.tree.display_tree(2) self.screen.clean_gpio() def postorder(self): self.display_init() self.tree.postorder_traversal() self.tree.display_tree(2) self.screen.clean_gpio() def levelorder(self): self.display_init() self.tree.levelorder_traversal() self.tree.display_tree(2) self.screen.clean_gpio() ```

#### graph_algorithm.py

 ``` 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``` ```from panel import Panel import graph_cross import graph_point class GraphAlgorithm(object): def __init__(self, node_shape, duration, root_id): self.screen = Panel() if (node_shape == "cross"): self.graph = graph_cross.Graph(self.screen) else: self.graph = graph_point.Graph(self.screen) self.graph.set_duration(duration) self.root_id = root_id # display the initial graph on the panel def display_init(self): self.graph.draw_large_graph() self.graph.set_root(self.root_id) self.graph.display_graph(2) def bfs(self): self.display_init() self.graph.bfs_start() self.graph.display_graph(2) self.screen.clean_gpio() def dfs(self): self.display_init() self.graph.dfs_start() self.graph.display_graph(2) self.screen.clean_gpio() ```

#### user_interface.py

 ``` 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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289``` ```# Zhongkai Liu (zl777) Yefei Si(ys948) # User interface from pygame.locals import * # for event MOUSE variables import pygame import os import time from tree_algorithm import TreeAlgorithm from graph_algorithm import GraphAlgorithm from random import randint # initialize the pygame and set up screen pygame.init() WHITE = 255, 255, 255 BLACK = 0, 0, 0 GREEN = 0, 255, 0 BLUE = 0, 0, 255 RED = 255, 0, 0 size = width, height = 1000, 720 screen = pygame.display.set_mode(size) button_ft = "HotSauce.ttf" background = pygame.image.load('background.jpg') level = [1, 0, 0, 0] class Button: def __init__(self, text, font, posx, posy): self.text = text self.font = font self.posx = posx self.posy = posy def draw(self): button_font = pygame.font.Font(self.font, 50) TextSurf = button_font.render(self.text, True, WHITE) TextRect = TextSurf.get_rect(center=(self.posx, self.posy)) screen.blit(TextSurf, TextRect) def touch(self, x, y): if x <= self.posx+90 and x >= self.posx-90 and y >= self.posy-50 and y <= self.posy+50: return 1 else: return 0 def highligth(self): button_font = pygame.font.Font(self.font, 70) TextSurf = button_font.render(self.text, True, WHITE) TextRect = TextSurf.get_rect(center=(self.posx, self.posy)) screen.blit(TextSurf, TextRect) timelimit = 600 start_time = time.time() # generate tile title_ft = "HotSauce.ttf" my_font = pygame.font.Font(title_ft, 100) title = ["Algorithm Visualizer", "Let's play", "Tree", "Graph", "Tree Control", "Graph Control", "Running"] title_surface = [] title_rect = [] for i in range(len(title)): title_surface.append(my_font.render(title[i], True, WHITE)) title_rect.append(title_surface[i].get_rect(center=(width/2, 200))) # generate level 1 buttons start_button = Button("start", button_ft, 300, 400) quit_button = Button("quit", button_ft, 700, 400) # generate level 2 buttons tree_button = Button("Tree", button_ft, 300, 400) graph_button = Button("Graph", button_ft, 700, 400) back_button = Button("Back", button_ft, 500, 600) # generate level 3 buttons preorder_button = Button("Preorder", button_ft, 500, 300) inorder_button = Button("Inorder", button_ft, 500, 375) postorder_button = Button("Postorder", button_ft, 500, 450) levelorder_button = Button("Levelorder", button_ft, 500, 525) BFS_button = Button("BFS", button_ft, 300, 400) DFS_button = Button("DFS", button_ft, 700, 400) # generate level 4 buttons run_button = Button("Run", button_ft, 300, 600) back4_button = Button("Back", button_ft, 700, 600) slow_button = Button("slow", button_ft, 300, 350) mid = Button("mid", button_ft, 500, 350) fast_button = Button("fast", button_ft, 700, 350) cross_button = Button("Cross node", button_ft, 350, 450) single_button = Button("Point node", button_ft, 650, 450) # Start Running code_run = True tree = False graph = False level4 = "" shape = [0, 0] duration = [0, 0, 0] running = 0 while code_run: time.sleep(0.002) # initialize the text surface and rect for event in pygame.event.get(): if(event.type is MOUSEBUTTONDOWN): # initialize the text surface and rect pos = pygame.mouse.get_pos() x, y = pos # if it's in level 1, if level == [1, 0, 0, 0]: # and if the click position is in the quit button area, then quits the program if quit_button.touch(x, y): level = [1, 0, 0, 0] code_run = False # and if the click position is in the start button area elif start_button.touch(x, y): level = [0, 1, 0, 0] # if it's in level 2 elif level == [0, 1, 0, 0]: # if click "Tree" button if tree_button.touch(x, y): tree = 1 graph = 0 level = [0, 0, 1, 0] # if click "graph" button elif graph_button.touch(x, y): tree = 0 graph = 1 level = [0, 0, 1, 0] # if click "back" button elif back_button.touch(x, y): tree = 0 graph = 0 level = [1, 0, 0, 0] # if it's in level 3 elif level == [0, 0, 1, 0]: if tree == 1: if preorder_button.touch(x, y): level4 = preorder_button.text level = [0, 0, 0, 1] elif inorder_button.touch(x, y): level4 = inorder_button.text level = [0, 0, 0, 1] elif postorder_button.touch(x, y): level4 = postorder_button.text level = [0, 0, 0, 1] elif levelorder_button.touch(x, y): level4 = levelorder_button.text level = [0, 0, 0, 1] elif back_button.touch(x, y): tree = 0 graph = 0 level = [0, 1, 0, 0] elif graph == 1: if BFS_button.touch(x, y): level4 = BFS_button.text level = [0, 0, 0, 1] elif DFS_button.touch(x, y): level4 = DFS_button.text level = [0, 0, 0, 1] elif back_button.touch(x, y): tree = 0 graph = 0 level = [0, 1, 0, 0] # if it's in level 4 elif level == [0, 0, 0, 1]: if slow_button.touch(x, y): duration = [1, 0, 0] elif mid.touch(x, y): duration = [0, 1, 0] elif fast_button.touch(x, y): duration = [0, 0, 1] if cross_button.touch(x, y): shape = [1, 0] elif single_button.touch(x, y): shape = [0, 1] if run_button.touch(x, y) and shape != [0, 0] and duration != [0, 0, 0]: running_surf = my_font.render( level4+" Running...", True, WHITE) running_rect = running_surf.get_rect( center=(width/2, height/2)) screen.blit(background, (0, 0)) screen.blit(running_surf, running_rect) pygame.display.flip() node = "" gap = 0 start_pt = randint(0, 24) if shape == [1, 0]: node = "cross" elif shape == [0, 1]: node = "point" if duration == [1, 0, 0]: gap = 10 elif duration == [0, 1, 0]: gap = 7 elif duration == [0, 0, 1]: gap = 5 if graph == 1: run1 = GraphAlgorithm(node, gap, start_pt) if level4 == "BFS": run1.bfs() elif level4 == "DFS": run1.dfs() elif tree == 1: run1 = TreeAlgorithm(node, gap) if level4 == "Preorder": run1.preorder() if level4 == "Inorder": run1.inorder() if level4 == "Postorder": run1.postorder() if level4 == "Levelorder": run1.levelorder() if back4_button.touch(x, y): shape = [0, 0] duration = [0, 0, 0] level = [0, 0, 1, 0] # clean the screen screen.blit(background, (0, 0)) # if it's in level 1, then display level 1 buttons if level == [1, 0, 0, 0]: screen.blit(title_surface[0], title_rect[0]) start_button.draw() quit_button.draw() # in level 2, then display level 1 buttons elif level == [0, 1, 0, 0]: screen.blit(title_surface[1], title_rect[1]) tree_button.draw() graph_button.draw() back_button.draw() # in level 3, then display level 1 buttons elif level == [0, 0, 1, 0]: if tree == 1: screen.blit(title_surface[2], title_rect[2]) preorder_button.draw() inorder_button.draw() postorder_button.draw() levelorder_button.draw() back_button.draw() elif graph == 1: screen.blit(title_surface[3], title_rect[3]) back_button.draw() BFS_button.draw() DFS_button.draw() # in level4, display the level4 title and show duration button and shape button elif level == [0, 0, 0, 1]: if tree == 1: screen.blit(title_surface[4], title_rect[4]) elif graph == 1: screen.blit(title_surface[5], title_rect[5]) if shape == [1, 0]: cross_button.highligth() single_button.draw() elif shape == [0, 1]: cross_button.draw() single_button.highligth() else: cross_button.draw() single_button.draw() if duration == [1, 0, 0]: slow_button.highligth() mid.draw() fast_button.draw() elif duration == [0, 1, 0]: slow_button.draw() mid.highligth() fast_button.draw() elif duration == [0, 0, 1]: slow_button.draw() mid.draw() fast_button.highligth() else: slow_button.draw() mid.draw() fast_button.draw() run_button.draw() back4_button.draw() pygame.display.flip() now = time.time() if (now - start_time > timelimit): code_run = False ```