Depth-First Searching

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

DFSGraph subclassed from Graph

Adds additional methods specific to DFS discovery

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)
            kt_graph.add_vertex(node_id)
            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)
                kt_graph.add_vertex(new_node_id)
                kt_graph.add_edge(node_id, new_node_id)
                
    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]:
node0 0 node10 10 node17 17 node27 27 node17->node27 node33 33 node27->node33 node1 1 node18 18 node1->node18 node8 8 node18->node8 node11 11 node11->node1 node16 16 node26 26 node16->node26 node41 41 node26->node41 node2 2 node8->node2 node12 12 node2->node12 node22 22 node12->node22 node7 7 node22->node7 node19 19 node9 9 node19->node9 node3 3 node9->node3 node20 20 node3->node20 node14 14 node20->node14 node13 13 node13->node19 node4 4 node14->node4 node4->node10 node21 21 node15 15 node21->node15 node5 5 node15->node5 node5->node11 node7->node13 node6 6 node6->node21 node23 23 node23->node6 node25 25 node35 35 node25->node35 node29 29 node35->node29 node24 24 node34 34 node24->node34 node40 40 node34->node40 node41->node24 node33->node16 node28 28 node38 38 node28->node38 node44 44 node38->node44 node29->node23 node30 30 node36 36 node30->node36 node42 42 node36->node42 node31 31 node37 37 node31->node37 node43 43 node37->node43 node32 32 node32->node17 node40->node25 node42->node32 node43->node28 node54 54 node44->node54 node39 39 node45 45 node39->node45 node45->node30 node54->node39 node46 46 node46->node31 node47 47 node62 62 node47->node62 node52 52 node62->node52 node49 49 node59 59 node49->node59 node53 53 node59->node53 node48 48 node58 58 node48->node58 node58->node52 node50 50 node60 60 node50->node60 node60->node43 node51 51 node61 61 node51->node61 node61->node46 node52->node46 node53->node47 node55 55 node55->node61 node57 57 node57->node51 node56 56 node56->node50 node63 63 node63->node53
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