D-Wave Python Pack 1.4.0-alpha1 Trial 2

I decided to take a break from this long weekend’s coding bender to get back to the D-Wave developer tutorials. Taking a break from one coding project by working on another may seem counter-intuitive to non-programmers, but it’s actually a great way of getting a fresh perspective when one function starts blurring into another.

I decided to take a look at some of the new tutorials, namely Travelling Salesman and the Hadamard Matrix search. I’m pleased to report that they function exactly as advertised (despite some criticism from a certain user on the D-Wave forums).

Here is my copy of the complete source code of the Travelling Salesman tutorial (travelling-salesman.py), with corrections (and without comments). You will need the .tsp files from the original tutorial to run this code:

import math
from dwave_sapi import LocalConnection, BlackBoxSolver
from numpy import dot, array, prod

def file_to_coordinates(filename):
f = open(filename, 'r')

coordinates = [i.strip().split() for i in f.readlines()]

coords = []
for line in coordinates:
try:
temp = int(line)
new_index = int(line)-1
coords.append([new_index, float(line), float(line)])
except ValueError:
pass

f.close()

return coords

def make_edge_list(coords):
edges = []
number_of_nodes = len(coords)

for i in range(len(coords)):
j = i+1
while j < len(coords):
x_distance = coords[i] - coords[j]
y_distance = coords[i] - coords[j]
distance = math.sqrt(x_distance**2 + y_distance**2)

edge = [coords[i],coords[j],distance]
edges.append(edge)

j += 1

return edges, number_of_nodes

def BuildIndexMatrix(edge_list, number_of_nodes):
index_matrix = []
for node_index in range(number_of_nodes):
temp_list = []
for line in edge_list:
if line == node_index or line == node_index:
temp_list.append(1)
else:
temp_list.append(0)
index_matrix.append(temp_list)
return index_matrix

def PathLengthFinder(edge_list, w):
present_edges = []
for i in range(len(w)):
if w[i] == 1:
present_edges.append(edge_list[i])

previous_node = 0
current_node = 0
path_length = 0
end = False
element_to_delete = 0

while end == False:
previous_node = current_node
for i in range(len(present_edges)):
if present_edges[i] == current_node:
element_to_delete = i
current_node = present_edges[i]
break
elif present_edges[i] == current_node:
element_to_delete = i
current_node = present_edges[i]
break

if current_node == 0:
path_length += 1
end = True
else:
if previous_node == current_node:
return 0
else:
del present_edges[element_to_delete]
path_length += 1

return path_length

class GeneratingFunction(object):
def __init__(self, edge_list, number_of_nodes):
self.edge_list = edge_list
self.number_of_nodes = number_of_nodes

def __call__(self, states, numStates):

stateLen = len(states)/numStates
states_bin = [(item+1)/2 for item in states]

ret = []
for state_number in range(numStates):
w = array(states_bin[state_number*stateLen:(state_number+1)*stateLen])
index_matrix = BuildIndexMatrix(self.edge_list, self.number_of_nodes)

weights = []
for line in self.edge_list:
weights.append(line)

prefactor = max(weights)*self.number_of_nodes

current_path_length = PathLengthFinder(self.edge_list, w)
if current_path_length == 0:
G = prefactor**10
else:
G = dot(weights, w)
for line in index_matrix:
G += (prefactor*(dot(line, w) - 2))**2
G += (prefactor*(current_path_length - self.number_of_nodes))**2

ret.append(G)

return tuple(ret)

print 'List of nodes:'
coordinates = file_to_coordinates('simple.tsp')
for line in coordinates:
print line

print 'List of edges:'
edges, num_node = make_edge_list(coordinates)
for edge in edges:
print edge
print 'Number of nodes:', num_node
print 'Number of edges:', len(edges)

print 'Index matrix:'
index_matrix = BuildIndexMatrix(edges, num_node)
for line in index_matrix:
print line

conn = LocalConnection()
solver = conn.get_solver('c4-sw_optimize')
blackbox_solver = BlackBoxSolver(solver)

genFunc = GeneratingFunction(edges, num_node)

blackbox_parameter = 10
blackbox_answer = blackbox_solver.solve(genFunc, len(edges), cluster_num = 10, min_iter_inner = blackbox_parameter, max_iter_outer = blackbox_parameter, unchanged_threshold = blackbox_parameter, max_unchanged_objective_outer = blackbox_parameter, max_unchanged_objective_inner = blackbox_parameter, unchanged_best_threshold = blackbox_parameter, verbose = 0)
blackbox_answer_bin = array([(item+1)/2 for item in blackbox_answer])

print 'The best bit string we found was:', blackbox_answer_bin

print 'This corresponds to the edges:'
total_journey = 0.0
for num in range(len(blackbox_answer_bin)):
if blackbox_answer_bin[num] == 1:
total_journey += edges[num]
print edges[num]
print 'For a total journey distance of:', total_journey

I got the exact same results as posted on the tutorial page:

C:\Python27\python.exe "C:/.../travelling-salesman.py"
List of nodes:
[0, 0.0, 3.0]
[1, 0.0, 0.0]
[2, 3.0, 0.0]
[3, 4.0, 3.0]
List of edges:
[0, 1, 3.0]
[0, 2, 4.242640687119285]
[0, 3, 4.0]
[1, 2, 3.0]
[1, 3, 5.0]
[2, 3, 3.1622776601683795]
Number of nodes: 4
Number of edges: 6
Index matrix:
[1, 1, 1, 0, 0, 0]
[1, 0, 0, 1, 1, 0]
[0, 1, 0, 1, 0, 1]
[0, 0, 1, 0, 1, 1]
The best bit string we found was: [1 0 1 1 0 1]
This corresponds to the edges:
[0, 1, 3.0]
[0, 3, 4.0]
[1, 2, 3.0]
[2, 3, 3.1622776601683795]
For a total journey distance of: 13.1622776602

Process finished with exit code 0

The matrix search sourcecode is available in the Git repository or as a single code snippet on the tutorial page.