Trees/Graphs¶
In [169]:
# here is a list of edges:
T = [('Bob','Eve'),('Alice','Carol'),('Eve','Frank'),('Alice','Doug'),('Frank','Ginger'), \
('Eve','Howard'),('Carol','Irene'),('Frank','Jeff'),('Doug','Kathy'),('Bob','Luis'), \
('Alice','Bob'),('Bob','Mabel'),('Ginger','Norm'),('Howard','Oprah'),('Carol','Peter'), \
('Kathy','Queen'),('Mabel','Ursala'),('Luis','Ronald'),('Ginger','Sarah'),('Irene','Tom'), \
('Jeff','Vince'),('Peter','Wanda'),('Oprah','Xanthia'),('Norm','Yaakov'),('Luis','Zandra')]
print ('T has',len(T),'edges')
vertices = set()
for edge in T:
s,t = edge
vertices.add(s)
vertices.add(t)
print ('T has',len(vertices),'vertices')
T has 25 edges T has 26 vertices
So this could be a tree. Now lets compute the number of parents for each vertex. The result confirms that we indeed have a tree and that the root is Alice (right?). Yes.
In [170]:
np = {}
for v in vertices:
np[v] = 0
for parent,child in T:
np[child] += 1
print (np)
{'Yaakov': 1, 'Wanda': 1, 'Zandra': 1, 'Tom': 1, 'Carol': 1, 'Ginger': 1, 'Howard': 1, 'Bob': 1, 'Jeff': 1, 'Ursala': 1, 'Kathy': 1, 'Ronald': 1, 'Xanthia': 1, 'Vince': 1, 'Oprah': 1, 'Queen': 1, 'Luis': 1, 'Eve': 1, 'Sarah': 1, 'Norm': 1, 'Mabel': 1, 'Peter': 1, 'Alice': 0, 'Frank': 1, 'Irene': 1, 'Doug': 1}
We now construct a dictionary of pairs (p,c) where p is the parent of the list of children c
In [171]:
adjacency_map = {}
for v in vertices:
adjacency_map[v] = []
for p,c in T:
adjacency_map[p].append(c)
print ("node and children:")
for p in adjacency_map:
print (p, ":", adjacency_map[p])
print ()
print (adjacency_map)
node and children:
Yaakov : []
Wanda : []
Zandra : []
Tom : []
Carol : ['Irene', 'Peter']
Ginger : ['Norm', 'Sarah']
Howard : ['Oprah']
Bob : ['Eve', 'Luis', 'Mabel']
Jeff : ['Vince']
Ursala : []
Kathy : ['Queen']
Ronald : []
Xanthia : []
Vince : []
Oprah : ['Xanthia']
Queen : []
Luis : ['Ronald', 'Zandra']
Eve : ['Frank', 'Howard']
Sarah : []
Norm : ['Yaakov']
Mabel : ['Ursala']
Peter : ['Wanda']
Alice : ['Carol', 'Doug', 'Bob']
Frank : ['Ginger', 'Jeff']
Irene : ['Tom']
Doug : ['Kathy']
{'Yaakov': [], 'Wanda': [], 'Zandra': [], 'Tom': [], 'Carol': ['Irene', 'Peter'], 'Ginger': ['Norm', 'Sarah'], 'Howard': ['Oprah'], 'Bob': ['Eve', 'Luis', 'Mabel'], 'Jeff': ['Vince'], 'Ursala': [], 'Kathy': ['Queen'], 'Ronald': [], 'Xanthia': [], 'Vince': [], 'Oprah': ['Xanthia'], 'Queen': [], 'Luis': ['Ronald', 'Zandra'], 'Eve': ['Frank', 'Howard'], 'Sarah': [], 'Norm': ['Yaakov'], 'Mabel': ['Ursala'], 'Peter': ['Wanda'], 'Alice': ['Carol', 'Doug', 'Bob'], 'Frank': ['Ginger', 'Jeff'], 'Irene': ['Tom'], 'Doug': ['Kathy']}
In [172]:
print (5*"Hello!")
Hello!Hello!Hello!Hello!Hello!
In [160]:
# A recursive Depth-First traversal of a tree defined by an adjacency_map
def print_tree_depth_first(parent, adjacency_map, level=0):
print (level*' ', parent)
children = adjacency_map[parent]
for child in children:
print_tree_depth_first(child, adjacency_map, level+1)
root = 'Alice'
print_tree_depth_first(root, adjacency_map)
Alice
Carol
Irene
Tom
Peter
Wanda
Doug
Kathy
Queen
Bob
Eve
Frank
Ginger
Norm
Yaakov
Sarah
Jeff
Vince
Howard
Oprah
Xanthia
Luis
Ronald
Zandra
Mabel
Ursala
Question 1¶
extend the breadth-first traversal to include the generation, so that the output is like below. Do this by storing a tuple with generation and node in the queue.
In [173]:
from collections import deque
# breadth-first traversal using a queue
def print_tree_breath_first(root, adjacency_map):
Q = deque()
Q.append((1,root))
print(str(1) + ":", end = "")
while len(Q)>0:
index,p = Q.popleft()
children = adjacency_map[p]
print(" " + p, end = "")
if (len(Q) == 0 and (len(children) > 0)) or (len(Q) > 0 and index != Q[0][0]):
print("\n" + str(index+1) + ":", end = "")
for child in children:
Q.append((index+1, child))
print_tree_breath_first("Alice", adjacency_map)
1: Alice 2: Carol Doug Bob 3: Irene Peter Kathy Eve Luis Mabel 4: Tom Wanda Queen Frank Howard Ronald Zandra Ursala 5: Ginger Jeff Oprah 6: Norm Sarah Vince Xanthia 7: Yaakov
Question 2¶
Write a function that checks if for the given directed graph (given by a list of edges E) root is connected to every other vertex.
In [174]:
def all_connected_to(edge_list, root):
""" return true if you can reach all nodes in the graph given
by a list of edges (edge_list) can be reached by root """
# start by constructing set of vertices and a dictionary for looking up children
vertices = set()
for edge in edge_list:
s,t = edge
vertices.add(s)
vertices.add(t)
adjacency_map = {}
for v in vertices:
adjacency_map[v] = []
for p,c in edge_list:
adjacency_map[p].append(c)
Q = deque()
Q.append(root)
visitedVertices = set()
while len(Q)>0:
p = Q.popleft()
children = adjacency_map[p]
if p not in visitedVertices:
visitedVertices.add(p)
else:
newChildren = []
for child in children:
if child not in visitedVertices:
newChildren.append(child)
adjacency_map[p] = newChildren
for child in children:
Q.append(child)
if len(visitedVertices) < len(vertices):
return False
return True
In [75]:
G = [("A","B"), ("B","C")]
print (all_connected_to(G, "A"))
G2 = [("1","2"), ("A","B"), ("B","C"), ("C","A")]
print (all_connected_to(G2, "A"))
print (all_connected_to(G2, "1"))
G3 = [("A","B"), ("B","C"), ("C","A")]
print (all_connected_to(G3, "C"))
# and our graph from above?
print (all_connected_to(T, "Alice"))
True False False True True
Question 3¶
We now treat the the graph T from above as undirected (edges going in both directions) and construct a tree rooted in Bob. The tree will contain edges from a vertex to the parent and direct children. The result will tell us how far removed the vertices from our root Bob are.
In [175]:
root = 'Bob'
# construct adjacency for graph T:
adjacency_map = {}
for vertex in vertices:
adjacency_map[vertex] = []
for edge in T:
s,t = edge
adjacency_map[s].append(t)
adjacency_map[t].append(s)
print ("parents/children of Ginger:",adjacency_map['Ginger'])
print (adjacency_map)
# now create tree as a dictionary "n maps to children(n)"
tree = {}
Q = deque()
Q.append(root)
# ??? use the queue!
visitedVertices = set()
while len(Q)>0:
p = Q.popleft()
children = adjacency_map[p]
treeChildren = []
if p not in visitedVertices:
visitedVertices.add(p)
for child in children:
if child not in visitedVertices:
treeChildren.append(child)
tree[p] = treeChildren
else:
newChildren = []
for child in children:
if child not in visitedVertices:
newChildren.append(child)
adjacency_map[p] = newChildren
for child in children:
Q.append(child)
print (tree)
parents/children of Ginger: ['Frank', 'Norm', 'Sarah']
{'Yaakov': ['Norm'], 'Wanda': ['Peter'], 'Zandra': ['Luis'], 'Tom': ['Irene'], 'Carol': ['Alice', 'Irene', 'Peter'], 'Ginger': ['Frank', 'Norm', 'Sarah'], 'Howard': ['Eve', 'Oprah'], 'Bob': ['Eve', 'Luis', 'Alice', 'Mabel'], 'Jeff': ['Frank', 'Vince'], 'Ursala': ['Mabel'], 'Kathy': ['Doug', 'Queen'], 'Ronald': ['Luis'], 'Xanthia': ['Oprah'], 'Vince': ['Jeff'], 'Oprah': ['Howard', 'Xanthia'], 'Queen': ['Kathy'], 'Luis': ['Bob', 'Ronald', 'Zandra'], 'Eve': ['Bob', 'Frank', 'Howard'], 'Sarah': ['Ginger'], 'Norm': ['Ginger', 'Yaakov'], 'Mabel': ['Bob', 'Ursala'], 'Peter': ['Carol', 'Wanda'], 'Alice': ['Carol', 'Doug', 'Bob'], 'Frank': ['Eve', 'Ginger', 'Jeff'], 'Irene': ['Carol', 'Tom'], 'Doug': ['Alice', 'Kathy']}
{'Bob': ['Eve', 'Luis', 'Alice', 'Mabel'], 'Eve': ['Frank', 'Howard'], 'Luis': ['Ronald', 'Zandra'], 'Alice': ['Carol', 'Doug'], 'Mabel': ['Ursala'], 'Frank': ['Ginger', 'Jeff'], 'Howard': ['Oprah'], 'Ronald': [], 'Zandra': [], 'Carol': ['Irene', 'Peter'], 'Doug': ['Kathy'], 'Ursala': [], 'Ginger': ['Norm', 'Sarah'], 'Jeff': ['Vince'], 'Oprah': ['Xanthia'], 'Irene': ['Tom'], 'Peter': ['Wanda'], 'Kathy': ['Queen'], 'Norm': ['Yaakov'], 'Sarah': [], 'Vince': [], 'Xanthia': [], 'Tom': [], 'Wanda': [], 'Queen': [], 'Yaakov': []}
Execute the following two blocks to check your result:
In [176]:
print_tree_depth_first(root, tree)
Bob
Eve
Frank
Ginger
Norm
Yaakov
Sarah
Jeff
Vince
Howard
Oprah
Xanthia
Luis
Ronald
Zandra
Alice
Carol
Irene
Tom
Peter
Wanda
Doug
Kathy
Queen
Mabel
Ursala
In [177]:
print_tree_breath_first(root, tree)
1: Bob 2: Eve Luis Alice Mabel 3: Frank Howard Ronald Zandra Carol Doug Ursala 4: Ginger Jeff Oprah Irene Peter Kathy 5: Norm Sarah Vince Xanthia Tom Wanda Queen 6: Yaakov
Question 4: n queens problem¶
Backtracking is the technique of recursively exploring the tree that contains all the possible solutions to a problem. Choose a systematic way to explore all the possible cases. This approach should reflect a rooted tree, and the backtracking approach is a depth-first search of the rooted tree. Whenever the search has found a solution or determined that there are no further solutions on the branches below the current vertex, backtrack to the preceeding vertex.
A classic example of a problem that can be easily solved with this approach is the n queens problem. This problem is to determine all the possible ways to place n nonattacking queens on an n-by-n chess board. The following code provides two helpful routines for this problem and illustrates one of the solutions for the 4 queens problem.
In [1]:
import numpy as np
def build_chessboard(N):
chessboard = np.zeros((N,N))
return chessboard
def print_chessboard(chessboard):
N = len(chessboard)
for r in range(N):
for c in range(N):
if chessboard[r,c] == 1:
print ('Q', end="")
else:
print ('.', end="")
print ()
print ()
# generate an empty 4x4 chessboard:
chessboard = build_chessboard(4)
print (chessboard)
# Place 4 non-attacking queens on this board
chessboard[1,0] = 1
chessboard[3,1] = 1
chessboard[0,2] = 1
chessboard[2,3] = 1
# Pretty print the resulting board
print_chessboard(chessboard)
[[0. 0. 0. 0.] [0. 0. 0. 0.] [0. 0. 0. 0.] [0. 0. 0. 0.]] ..Q. Q... ...Q .Q..
Complete the following code to solve the n queens problem by returning the total number of solutions while printing only the first five solutions.
In [2]:
import copy
def n_queens(chessboard, col=0, count=0):
""" given a partially filled <chessboard>, try to place a queen in column <col> and recursively fill the board.
Finally return the number of solutions (added to <count>)"""
N = len(chessboard)
if col == N:
if count < 5:
print_chessboard(chessboard)
return count+1
# Examine all available squares in column <col> (value is 0), place the queen, and
# mark all squares under attack by that queen (use anything except 0 or 1).
# Note: you can make a copy of a chessboard using chessboard.copy()
#
# ????
for i in range(0,N):
newchessboard = chessboard.copy()
if (newchessboard[i,col] == 0):
x = np.ones(N)*2
newchessboard[i,:] = x
#no need to set column
for j in range(1,min(i+1,N-col)):
newchessboard[i-j, col+j] = 2
for j in range(1,min(N-i,N-col)):
newchessboard[i+j, col+j] = 2
newchessboard[i,col] = 1
count = n_queens(newchessboard, col+1, count)
return count
chessboard = build_chessboard(8)
count = n_queens(chessboard)
print ("solutions: ", count)
Q....... ......Q. ....Q... .......Q .Q...... ...Q.... .....Q.. ..Q..... Q....... ......Q. ...Q.... .....Q.. .......Q .Q...... ....Q... ..Q..... Q....... .....Q.. .......Q ..Q..... ......Q. ...Q.... .Q...... ....Q... Q....... ....Q... .......Q .....Q.. ..Q..... ......Q. .Q...... ...Q.... .....Q.. Q....... ....Q... .Q...... .......Q ..Q..... ......Q. ...Q.... solutions: 92
In [3]:
def test(cb):
cb[0,0]=1
print_chessboard(cb)
chessboard = build_chessboard(4)
print_chessboard(chessboard)
test(chessboard.copy())# try chessboard.copy() instead
print_chessboard(chessboard) # oooops!
.... .... .... .... Q... .... .... .... .... .... .... ....
In [4]:
def test(b):
b=b+1
print (b)
n = 1
print (n)
test(n)
print (n)
1 2 1
In [5]:
import copy
def test(b):
b.append(1)
print (b)
n = [1,2,3]
print (n)
test(copy.copy(n))
print (n)
test(n)
print (n)
[1, 2, 3] [1, 2, 3, 1] [1, 2, 3] [1, 2, 3, 1] [1, 2, 3, 1]
In [6]:
import copy
a=[]
copy.deepcopy(a)
Out[6]:
[]
In [184]:
import copy
# copy makes a copy of the outer-most object, but keeps the same references to the inner
# object.
a=[2,4,[6]]
print ("before: a=", a)
b=copy.copy(a)
b[0]+=1
b[2][0]+=1
print ("after: a=",a," b=", b, " (using copy)")
# deepcopy also makes a copy of each contained element (recursively)
a=[2,4,[6]]
b=copy.deepcopy(a)
b[0]+=1
b[2][0]+=1
print ("after: a=",a," b=", b, " (using deepcopy)")
before: a= [2, 4, [6]] after: a= [2, 4, [7]] b= [3, 4, [7]] (using copy) after: a= [2, 4, [6]] b= [3, 4, [7]] (using deepcopy)
In [ ]: