import tkinter as tk
from tkinter import ttk, messagebox
import networkx as nx
import matplotlib
matplotlib.use("TkAgg")
import matplotlib.pyplot as plt
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg
import time
import threading
# Small sleep used to allow GUI to update between steps (very short)
STEP_DELAY = 0.15
# -------------------------
# Data structure backends
# -------------------------
class Stack:
def __init__(self):
self.items = []
def push(self, v):
self.items.append(v)
def pop(self):
if self.items:
return self.items.pop()
return None
def to_list(self):
# top at right
return list(self.items)
class Queue:
def __init__(self):
self.items = []
def enqueue(self, v):
self.items.append(v)
def dequeue(self):
if self.items:
return self.items.pop(0)
return None
def to_list(self):
# front at left
return list(self.items)
class LinkedListNode:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def to_list(self):
out = []
cur = self.head
while cur:
out.append(cur.val)
cur = cur.next
return out
def insert_at(self, index, value):
node = LinkedListNode(value)
if index <= 0 or not self.head:
# insert at head
node.next = self.head
self.head = node
return
cur = self.head
i = 0
while cur.next and i < index-1:
cur = cur.next
i += 1
node.next = cur.next
cur.next = node
def delete_at(self, index):
if not self.head:
return None
if index <= 0:
removed = self.head
self.head = self.head.next
return removed.val
cur = self.head
i = 0
while cur.next and i < index-1:
cur = cur.next
i += 1
if cur.next:
removed = cur.next
cur.next = removed.next
return removed.val
return None
class BSTNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if self.root is None:
self.root = BSTNode(val)
return
cur = self.root
while True:
if val == cur.val:
# ignore duplicates
return
if val < cur.val:
if cur.left:
cur = cur.left
else:
cur.left = BSTNode(val)
return
else:
if cur.right:
cur = cur.right
else:
cur.right = BSTNode(val)
return
def search(self, val):
cur = self.root
while cur:
if val == cur.val:
return True
elif val < cur.val:
cur = cur.left
else:
cur = cur.right
return False
def delete(self, val):
# standard BST delete (recursively)
def _delete(node, key):
if node is None:
return node, None
if key < node.val:
node.left, removed = _delete(node.left, key)
return node, removed
elif key > node.val:
node.right, removed = _delete(node.right, key)
return node, removed
else:
# found node
removed_val = node.val
if node.left is None:
return node.right, removed_val
elif node.right is None:
return node.left, removed_val
else:
# find inorder successor (smallest in right subtree)
succ_parent = node
succ = node.right
while succ.left:
succ_parent = succ
succ = succ.left
node.val = succ.val
node.right, _ = _delete(node.right, succ.val)
return node, removed_val
self.root, removed = _delete(self.root, val)
return removed
def to_graph(self):
# output nodes and edges for visualization
g = nx.DiGraph()
def add_nodes(n):
if not n:
return
g.add_node(str(n.val), label=str(n.val))
if n.left:
g.add_node(str(n.left.val), label=str(n.left.val))
g.add_edge(str(n.val), str(n.left.val))
add_nodes(n.left)
if n.right:
g.add_node(str(n.right.val), label=str(n.right.val))
g.add_edge(str(n.val), str(n.right.val))
add_nodes(n.right)
add_nodes(self.root)
return g
# -------------------------
# Visualization helpers
# -------------------------
def draw_stack(ax, stack: Stack):
ax.clear()
items = stack.to_list()
g = nx.DiGraph()
# nodes left->right, top is rightmost
for i, it in enumerate(items):
g.add_node(f"{i}:{it}", label=str(it))
if i > 0:
g.add_edge(f"{i-1}:{items[i-1]}", f"{i}:{it}")
pos = {}
# horizontal positions
for i in range(len(items)):
pos[f"{i}:{items[i]}"] = (i, 0)
nx.draw_networkx_nodes(g, pos, ax=ax, node_color='skyblue', node_size=1800)
labels = {n: g.nodes[n]['label'] for n in g.nodes()}
nx.draw_networkx_labels(g, pos, labels, ax=ax, font_size=12)
nx.draw_networkx_edges(g, pos, ax=ax, arrows=False)
ax.set_title("Stack (top on the right)")
ax.set_axis_off()
def draw_queue(ax, queue: Queue):
ax.clear()
items = queue.to_list()
g = nx.DiGraph()
for i, it in enumerate(items):
g.add_node(f"{i}:{it}", label=str(it))
if i > 0:
g.add_edge(f"{i-1}:{items[i-1]}", f"{i}:{it}")
pos = {f"{i}:{items[i]}": (i, 0) for i in range(len(items))}
nx.draw_networkx_nodes(g, pos, ax=ax, node_color='lightgreen', node_size=1800)
labels = {n: g.nodes[n]['label'] for n in g.nodes()}
nx.draw_networkx_labels(g, pos, labels, ax=ax, font_size=12)
nx.draw_networkx_edges(g, pos, ax=ax, arrows=False)
ax.set_title("Queue (front on the left)")
ax.set_axis_off()
def draw_linked_list(ax, ll: LinkedList):
ax.clear()
items = ll.to_list()
g = nx.DiGraph()
for i, it in enumerate(items):
g.add_node(f"{i}:{it}", label=str(it))
if i > 0:
g.add_edge(f"{i-1}:{items[i-1]}", f"{i}:{it}")
pos = {f"{i}:{items[i]}": (i, 0) for i in range(len(items))}
nx.draw_networkx_nodes(g, pos, ax=ax, node_color='lightyellow', node_size=1600)
labels = {n: g.nodes[n]['label'] for n in g.nodes()}
nx.draw_networkx_labels(g, pos, labels, ax=ax, font_size=12)
nx.draw_networkx_edges(g, pos, ax=ax, arrows=True, arrowstyle='-|>', arrowsize=20)
ax.set_title("Singly Linked List (head on left)")
ax.set_axis_off()
def hierarchical_pos(G, root=None, width=1.0, vert_gap=0.2, vert_loc=0, xcenter=0.5, pos=None, parent=None):
"""
Create a hierarchical position layout for a tree (recursive).
G: networkx graph
root: root node
returns dict node->(x,y)
"""
if pos is None:
pos = {root: (xcenter, vert_loc)}
children = list(G.successors(root))
if len(children) != 0:
dx = width / len(children)
nextx = xcenter - width/2 - dx/2
for child in children:
nextx += dx
pos[child] = (nextx, vert_loc - vert_gap)
hierarchical_pos(G, root=child, width=dx, vert_gap=vert_gap, vert_loc=vert_loc-vert_gap, xcenter=nextx, pos=pos, parent=root)
return pos
def draw_bst(ax, bst: BST):
ax.clear()
g = bst.to_graph()
if g.number_of_nodes() == 0:
ax.text(0.5, 0.5, "Empty BST", horizontalalignment='center')
ax.set_axis_off()
return
# pick root
root = list(g.nodes())[0]
pos = hierarchical_pos(g, root=root, width=1.0, vert_gap=0.2, vert_loc=0.9, xcenter=0.5)
nx.draw_networkx_nodes(g, pos, ax=ax, node_size=1400, node_color='lightcoral')
labels = {n: g.nodes[n]['label'] for n in g.nodes()}
nx.draw_networkx_labels(g, pos, labels, ax=ax, font_size=12)
nx.draw_networkx_edges(g, pos, ax=ax, arrows=True)
ax.set_title("Binary Search Tree (root at top)")
ax.set_axis_off()
# -------------------------
# GUI Application
# -------------------------
class DSVisualizerApp:
def __init__(self, root):
self.root = root
self.root.title("Interactive Data Structure Visualizer")
self.root.geometry("1000x700")
self.notebook = ttk.Notebook(root)
self.notebook.pack(fill='both', expand=True)
# Data structures
self.stack = Stack()
self.queue = Queue()
self.ll = LinkedList()
self.bst = BST()
# Create tabs
self.create_stack_tab()
self.create_queue_tab()
self.create_linkedlist_tab()
self.create_bst_tab()
def make_canvas_frame(self, parent):
frame = ttk.Frame(parent)
# matplotlib figure
fig, ax = plt.subplots(figsize=(6,4))
canvas = FigureCanvasTkAgg(fig, master=frame)
canvas_widget = canvas.get_tk_widget()
canvas_widget.pack(side=tk.LEFT, fill=tk.BOTH, expand=True)
return frame, fig, ax, canvas
def add_log(self, text_widget, message):
text_widget.config(state='normal')
text_widget.insert('end', message + "\n")
text_widget.see('end')
text_widget.config(state='disabled')
# ---- Stack Tab ----
def create_stack_tab(self):
tab = ttk.Frame(self.notebook)
self.notebook.add(tab, text="Stack")
left = ttk.Frame(tab)
left.pack(side=tk.LEFT, fill=tk.BOTH, expand=True)
right = ttk.Frame(tab, width=300)
right.pack(side=tk.RIGHT, fill=tk.Y)
canvas_frame, fig, ax, canvas = self.make_canvas_frame(left)
canvas_frame.pack(fill=tk.BOTH, expand=True)
self.stack_fig = fig; self.stack_ax = ax; self.stack_canvas = canvas
# Controls
ttk.Label(right, text="Push value:").pack(pady=6)
val_entry = ttk.Entry(right); val_entry.pack(pady=6)
def on_push():
v = val_entry.get().strip()
if not v:
messagebox.showwarning("Input", "Enter a value to push")
return
self.stack.push(v)
self.add_log(stack_log, f"PUSH {v}")
val_entry.delete(0, 'end')
self.redraw_stack()
ttk.Button(right, text="Push", command=on_push).pack(pady=6)
def on_pop():
val = self.stack.pop()
if val is None:
messagebox.showinfo("Stack", "Stack is empty")
else:
self.add_log(stack_log, f"POP {val}")
self.redraw_stack()
ttk.Button(right, text="Pop", command=on_pop).pack(pady=6)
ttk.Button(right, text="Clear", command=lambda: (self.stack.items.clear(), self.redraw_stack())).pack(pady=6)
# Log
ttk.Label(right, text="Operations:").pack(pady=6)
stack_log = tk.Text(right, height=20, width=30, state='disabled')
stack_log.pack(pady=6)
self.redraw_stack()
def redraw_stack(self):
draw_stack(self.stack_ax, self.stack)
self.stack_canvas.draw_idle()
# ---- Queue Tab ----
def create_queue_tab(self):
tab = ttk.Frame(self.notebook)
self.notebook.add(tab, text="Queue")
left = ttk.Frame(tab)
left.pack(side=tk.LEFT, fill=tk.BOTH, expand=True)
right = ttk.Frame(tab, width=300)
right.pack(side=tk.RIGHT, fill=tk.Y)
canvas_frame, fig, ax, canvas = self.make_canvas_frame(left)
canvas_frame.pack(fill=tk.BOTH, expand=True)
self.queue_fig = fig; self.queue_ax = ax; self.queue_canvas = canvas
ttk.Label(right, text="Enqueue value:").pack(pady=6)
val_entry = ttk.Entry(right); val_entry.pack(pady=6)
def on_enqueue():
v = val_entry.get().strip()
if not v:
messagebox.showwarning("Input", "Enter a value to enqueue")
return
self.queue.enqueue(v)
self.add_log(queue_log, f"ENQUEUE {v}")
val_entry.delete(0, 'end')
self.redraw_queue()
ttk.Button(right, text="Enqueue", command=on_enqueue).pack(pady=6)
def on_dequeue():
v = self.queue.dequeue()
if v is None:
messagebox.showinfo("Queue", "Queue is empty")
else:
self.add_log(queue_log, f"DEQUEUE {v}")
self.redraw_queue()
ttk.Button(right, text="Dequeue", command=on_dequeue).pack(pady=6)
ttk.Button(right, text="Clear", command=lambda: (self.queue.items.clear(), self.redraw_queue())).pack(pady=6)
ttk.Label(right, text="Operations:").pack(pady=6)
queue_log = tk.Text(right, height=20, width=30, state='disabled')
queue_log.pack(pady=6)
self.redraw_queue()
def redraw_queue(self):
draw_queue(self.queue_ax, self.queue)
self.queue_canvas.draw_idle()
# ---- Linked List Tab ----
def create_linkedlist_tab(self):
tab = ttk.Frame(self.notebook)
self.notebook.add(tab, text="Linked List")
left = ttk.Frame(tab)
left.pack(side=tk.LEFT, fill=tk.BOTH, expand=True)
right = ttk.Frame(tab, width=320)
right.pack(side=tk.RIGHT, fill=tk.Y)
canvas_frame, fig, ax, canvas = self.make_canvas_frame(left)
canvas_frame.pack(fill=tk.BOTH, expand=True)
self.ll_fig = fig; self.ll_ax = ax; self.ll_canvas = canvas
ttk.Label(right, text="Value:").pack(pady=6)
val_entry = ttk.Entry(right); val_entry.pack(pady=6)
ttk.Label(right, text="Index (0-based):").pack(pady=6)
idx_entry = ttk.Entry(right); idx_entry.pack(pady=6)
def on_insert():
v = val_entry.get().strip()
idx = idx_entry.get().strip()
if not v:
messagebox.showwarning("Input", "Enter a value")
return
try:
idxi = int(idx) if idx != "" else 0
except:
messagebox.showwarning("Input", "Index must be integer")
return
self.ll.insert_at(idxi, v)
self.add_log(ll_log, f"INSERT {v} at {idxi}")
val_entry.delete(0, 'end'); idx_entry.delete(0,'end')
self.redraw_ll()
ttk.Button(right, text="Insert", command=on_insert).pack(pady=6)
def on_delete():
idx = idx_entry.get().strip()
try:
idxi = int(idx) if idx != "" else 0
except:
messagebox.showwarning("Input", "Index must be integer")
return
removed = self.ll.delete_at(idxi)
if removed is None:
messagebox.showinfo("LinkedList", "No node at that index")
else:
self.add_log(ll_log, f"DELETE {removed} from {idxi}")
val_entry.delete(0, 'end'); idx_entry.delete(0,'end')
self.redraw_ll()
ttk.Button(right, text="Delete", command=on_delete).pack(pady=6)
ttk.Button(right, text="Clear", command=lambda: (self.ll.__init__(), self.redraw_ll())).pack(pady=6)
ttk.Label(right, text="Operations:").pack(pady=6)
ll_log = tk.Text(right, height=20, width=36, state='disabled')
ll_log.pack(pady=6)
self.redraw_ll()
def redraw_ll(self):
draw_linked_list(self.ll_ax, self.ll)
self.ll_canvas.draw_idle()
# ---- BST Tab ----
def create_bst_tab(self):
tab = ttk.Frame(self.notebook)
self.notebook.add(tab, text="Binary Search Tree")
left = ttk.Frame(tab)
left.pack(side=tk.LEFT, fill=tk.BOTH, expand=True)
right = ttk.Frame(tab, width=350)
right.pack(side=tk.RIGHT, fill=tk.Y)
canvas_frame, fig, ax, canvas = self.make_canvas_frame(left)
canvas_frame.pack(fill=tk.BOTH, expand=True)
self.bst_fig = fig; self.bst_ax = ax; self.bst_canvas = canvas
ttk.Label(right, text="Value (integer):").pack(pady=6)
val_entry = ttk.Entry(right); val_entry.pack(pady=6)
def on_insert():
v = val_entry.get().strip()
if not v:
messagebox.showwarning("Input", "Enter a value")
return
try:
vi = int(v)
except:
messagebox.showwarning("Input", "BST requires integer values")
return
self.bst.insert(vi)
self.add_log(bst_log, f"INSERT {vi}")
val_entry.delete(0,'end')
self.redraw_bst()
ttk.Button(right, text="Insert", command=on_insert).pack(pady=6)
def on_delete():
v = val_entry.get().strip()
if not v:
messagebox.showwarning("Input", "Enter a value")
return
try:
vi = int(v)
except:
messagebox.showwarning("Input", "BST requires integer values")
return
removed = self.bst.delete(vi)
if removed is None:
messagebox.showinfo("BST", f"Value {vi} not found")
else:
self.add_log(bst_log, f"DELETE {vi}")
val_entry.delete(0,'end')
self.redraw_bst()
ttk.Button(right, text="Delete", command=on_delete).pack(pady=6)
def on_search():
v = val_entry.get().strip()
if not v:
messagebox.showwarning("Input", "Enter a value")
return
try:
vi = int(v)
except:
messagebox.showwarning("Input", "BST requires integer values")
return
found = self.bst.search(vi)
self.add_log(bst_log, f"SEARCH {vi} -> {'Found' if found else 'Not found'}")
messagebox.showinfo("Search", f"{vi} {'found' if found else 'not found'} in BST")
val_entry.delete(0,'end')
# small highlight trick: we can redraw quickly (no highlight implemented)
self.redraw_bst()
ttk.Button(right, text="Search", command=on_search).pack(pady=6)
ttk.Button(right, text="Clear", command=lambda: (self.bst.__init__(), self.redraw_bst())).pack(pady=6)
ttk.Label(right, text="Operations:").pack(pady=6)
bst_log = tk.Text(right, height=18, width=36, state='disabled')
bst_log.pack(pady=6)
self.redraw_bst()
def redraw_bst(self):
draw_bst(self.bst_ax, self.bst)
self.bst_canvas.draw_idle()
# -------------------------
# Run the app
# -------------------------
def main():
root = tk.Tk()
app = DSVisualizerApp(root)
root.mainloop()
if __name__ == "__main__":
main()
No comments:
Post a Comment