Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
executable file 209 lines (168 sloc) 4.25 KB
#!/usr/bin/env ruby
require 'tk'
COLOR_BACKGROUND = '#ffffff'
COLOR_NODE = '#000000'
COLOR_VISITED = '#ff0000'
COLOR_UNVISITED = '#efefef'
LINE_LENGTH = 20
HEIGHT = 20
WIDTH = 20
class Node
attr_accessor :visited
attr_accessor :up, :down
attr_accessor :left, :right
attr_accessor :x, :y
def initialize
@visited = false
@up, @down, @left, @right = nil, nil, nil, nil
@x, @y = 0, 0
end
def visited?
@visited
end
def visited=(val)
@visited = val
end
end
class Traversal
def draw_initial_graph
(WIDTH+1).times do |x|
(HEIGHT+1).times do |y|
draw_line_down x, y, COLOR_UNVISITED
draw_line_right x, y, COLOR_UNVISITED
end
end
end
def draw_line_down(x, y, color)
x1 = x * (LINE_LENGTH + 1)
y1 = y * (LINE_LENGTH + 1) + 1
x2 = x1
y2 = y1 + LINE_LENGTH
TkcRectangle.new @canvas, x1, y1, x2, y2, :outline => color
draw_node x, y
draw_node x, y+1
end
def draw_line_up(x, y, color)
draw_line_down(x, y-1, color)
end
def draw_line_right(x, y, color)
x1 = x * (LINE_LENGTH + 1) + 1
y1 = y * (LINE_LENGTH + 1)
x2 = x1 + LINE_LENGTH
y2 = y1
TkcRectangle.new @canvas, x1, y1, x2, y2, :outline => color
draw_node x, y
draw_node x+1, y
end
def draw_line_left(x, y, color)
draw_line_right(x-1, y, color)
end
def draw_node(x, y)
# Node
point_x = x * (LINE_LENGTH + 1)
point_y = y * (LINE_LENGTH + 1)
TkcRectangle.new @canvas, point_x, point_y, point_x, point_y, :fill => COLOR_NODE
end
def go
Thread.new() {
# Prep traversal
start_node = @node_array[0][0]
end_node = @node_array[WIDTH][HEIGHT]
@hits = 0
@button.state = 'disabled'
@button.text = "Hits: 0"
# Go!
visit_node start_node, end_node
@button.text = "Complete: #{@hits}"
@button.state = 'normal'
}
end
def visit_node(current_node, destination_node)
# Win?
if current_node == destination_node
@hits += 1
@button.text = "Hits: #{@hits}"
return
end
# Mark visited
current_node.visited = true
# Right
if !current_node.right.nil? && !current_node.right.visited?
draw_line_right current_node.x, current_node.y, COLOR_VISITED
visit_node(current_node.right, destination_node)
draw_line_right current_node.x, current_node.y, COLOR_UNVISITED
end
# Down
if !current_node.down.nil? && !current_node.down.visited?
draw_line_down current_node.x, current_node.y, COLOR_VISITED
visit_node(current_node.down, destination_node)
draw_line_down current_node.x, current_node.y, COLOR_UNVISITED
end
# Unmark visited
current_node.visited = false
end
def initialize
# Build a node array
@node_array = []
(WIDTH+1).times do |x|
@node_array[x] = []
(HEIGHT+1).times do |y|
node = Node.new
node.x = x
node.y = y
@node_array[x][y] = node
end
end
# Link the node array
(WIDTH+1).times do |x|
(HEIGHT+1).times do |y|
node = @node_array[x][y]
# Up
if y != 0
other_node = @node_array[x][y-1]
node.up = other_node
other_node.down = node
end
# Down
if y != HEIGHT
other_node = @node_array[x][y+1]
node.down = other_node
other_node.up = node
end
# Left
if x != 0
other_node = @node_array[x-1][y]
node.left = other_node
other_node.right = node
end
# Right
if x != WIDTH
other_node = @node_array[x+1][y]
node.right = other_node
other_node.left = node
end
end
end
# Build the canvas
root = TkRoot.new { title 'Graph Traversal' }
frame = TkFrame.new root
p = proc { go }
canvas_width = (WIDTH + 1) + (WIDTH * LINE_LENGTH)
canvas_height = (HEIGHT + 1) + (HEIGHT * LINE_LENGTH)
@canvas = TkCanvas.new frame do
background COLOR_BACKGROUND
height canvas_width
width canvas_height
end
@canvas.pack
@button = TkButton.new frame do
text 'Go!'
command p
end
@button.pack
frame.pack
draw_initial_graph
end
end
Traversal.new
Tk.mainloop
You can’t perform that action at this time.