# Depth-First Searching¶

In [1]:
from pythonds9.graphs import Graph
from pythonds9.graphs.utils import viz_graph


## DFSGraph subclassed from Graph¶

In [2]:
class DFSGraph(Graph):
def __init__(self, *args, **kwargs):
super(DFSGraph, self).__init__(*args, **kwargs)
self.time = 0

def dfs(self):
# Init our graph states
self.reset()

for a_vertex in self:
if a_vertex.get_color() == "white":
self.dfs_visit(a_vertex)

def dfs_visit(self, start):
self.time += 1
start.set_color('gray')
start.set_discovery(self.time)

for new_vertex in start.get_connections():
if new_vertex.get_color() == "white":
new_vertex.set_pred(start)
self.dfs_visit(new_vertex)

self.time += 1
start.set_color("black")
start.set_finish(self.time)

def traverse(self, y):
path = []
x = y
pred = x.get_pred()
while x.get_pred():
path.append(x)
x = x.get_pred()
path.append(x)
return path

def reset(self):
for a_vertex in self:
a_vertex.set_color('white')
a_vertex.set_pred(None)


## Using DFSGraph for the Knight's Tour Problem¶

In [3]:
def knight_graph(bd_size):
kt_graph = DFSGraph()

for row in range(bd_size):
for col in range(bd_size):
node_id = pos_to_node_id(row, col, bd_size)
new_positions = gen_legal_moves(row, col, bd_size)

for new_x, new_y in new_positions:
new_node_id = pos_to_node_id(new_x, new_y, bd_size)

return kt_graph

In [4]:
def gen_legal_moves(x, y, bd_size):
new_moves = []
move_offsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1),
( 1, -2), ( 1, 2), ( 2, -1), ( 2, 1)]

for d_x, d_y in move_offsets:
new_x = x + d_x
new_y = y + d_y

if (legal_coord(new_x, bd_size) and
legal_coord(new_y, bd_size)):
new_moves.append((new_x, new_y))

return new_moves

In [5]:
def legal_coord(x, bd_size):
if x >= 0 and x < bd_size:
return True
else:
return False

In [6]:
def pos_to_node_id(row, col, bd_size):
#      2*5 + 2 = 12 (node id)
return row*bd_size + col


## Testing¶

In [7]:
kt = knight_graph(8)

In [8]:
kt.reset()

In [9]:
kt.dfs()

In [10]:
len(kt.vertices)

Out[10]:
64
In [11]:
kt.traverse(kt.vertices[4])

Out[11]:
[Vertex(4), Vertex(10), Vertex(0)]
In [12]:
kt.traverse(kt.vertices[12])

Out[12]:
[Vertex(12),
Vertex(22),
Vertex(7),
Vertex(13),
Vertex(19),
Vertex(9),
Vertex(3),
Vertex(20),
Vertex(14),
Vertex(4),
Vertex(10),
Vertex(0)]
In [13]:
viz_graph(kt, show_pred=True)

Out[13]:
In [14]:
num_edges = 0
for v in kt:
num_edges += len(v.connected_to)
print(num_edges)

336


## Knight's Tour Algorithm¶

In [15]:
def knight_tour(n, path, u, limit):
u.set_color('gray')
path.append(u)
if n < limit:  # recursion base case
nbr_list = list(u.get_connections())
i = 0
done = False
while i < len(nbr_list) and not done:
if nbr_list[i].get_color() == 'white':
done = knight_tour(n+1, path, nbr_list[i], limit)
i += 1

if not done:
path.pop()
u.set_color('white')
else:  # The actual; base case that ends our recursion
done = True

return done

In [27]:
def the_knights_tour(kt, start):
path = []
n = 0
print(n, path, start, 24)
knight_tour(n, path, start, 24)
return path

In [28]:
kt = knight_graph(5)
start = kt.get_vertex(4)
the_path = the_knights_tour(kt, start)

0 [] 4 connected to: [7, 13] 24

In [29]:
the_path

Out[29]:
[Vertex(4),
Vertex(7),
Vertex(0),
Vertex(11),
Vertex(8),
Vertex(1),
Vertex(10),
Vertex(21),
Vertex(18),
Vertex(9),
Vertex(2),
Vertex(5),
Vertex(12),
Vertex(19),
Vertex(22),
Vertex(15),
Vertex(6),
Vertex(3),
Vertex(14),
Vertex(23),
Vertex(16),
Vertex(13),
Vertex(24),
Vertex(17),
Vertex(20)]
In [30]:
len(the_path)

Out[30]:
25