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[0]) new_index = int(line[0])-1 coords.append([new_index, float(line[1]), float(line[2])]) 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][1] - coords[j][1] y_distance = coords[i][2] - coords[j][2] distance = math.sqrt(x_distance**2 + y_distance**2) edge = [coords[i][0],coords[j][0],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[0] == node_index or line[1] == 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][0] == current_node: element_to_delete = i current_node = present_edges[i][1] break elif present_edges[i][1] == current_node: element_to_delete = i current_node = present_edges[i][0] 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[2]) 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][2] 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.