1import networkx as nx
2
3import numpy as np
4import matplotlib.pyplot as plt
5
6from qiskit_algorithms import SamplingMinimumEigensolverResult
7
8from quantum_launcher.base import Problem
9
10
[docs]
11class TSP(Problem):
12 """
13 Traveling Salesman Problem (TSP) definition.
14 """
15
16 def __init__(self, instance: nx.Graph, instance_name: str = "unnamed"):
17 """
18 Args:
19 instance (nx.Graph): Graph representing the TSP instance.
20 instance_name (str): Name of the instance.
21 quadratic (bool): Whether to use quadratic constraints
22 """
23 super().__init__(instance=instance, instance_name=instance_name)
24
25 @property
26 def setup(self) -> dict:
27 return {"instance_name": self.instance_name}
28
29 def _get_path(self) -> str:
30 return f"{self.name}@{self.instance_name}"
31
32 def _solution_to_node_chain(self, solution: SamplingMinimumEigensolverResult | str) -> np.ndarray:
33 """
34 Converts the solution of the TSP problem to a chain of nodes (order of visiting)
35
36 Args:
37 solution: Solution of the TSP problem. If type is str, qiskit-style ordering is assumed (MSB first)
38
39 Returns:
40 np.ndarray: Solution chain of nodes to visit
41 """
42 if isinstance(solution, str):
43 bitstring = solution[::-1]
44 else:
45 bitstring = solution.best_measurement["bitstring"][::-1]
46
47 node_count = int(len(bitstring)**0.5)
48 chain = []
49
50 for i in range(0, len(bitstring), node_count):
51 step_string = bitstring[i: i + node_count]
52 chosen_node = np.argmax([int(x) for x in step_string])
53 chain.append(chosen_node)
54
55 return np.array(chain)
56
57 def _calculate_solution_cost(self, solution: SamplingMinimumEigensolverResult | str | list[int]) -> float:
58 cost = 0
59 if isinstance(solution, list):
60 chain = solution
61 else:
62 chain = self._solution_to_node_chain(solution)
63
64 for i in range(len(chain) - 1):
65 cost += self.instance[chain[i]][chain[i + 1]]["weight"]
66 cost += self.instance[chain[-1]][chain[0]]["weight"]
67 return cost
68
69 def _visualize_solution(self, solution: SamplingMinimumEigensolverResult | str | list[int]):
70 if isinstance(solution, list):
71 chain = solution
72 else:
73 chain = self._solution_to_node_chain(solution)
74
75 import matplotlib.pyplot as plt
76
77 pos = nx.spring_layout(self.instance, weight=None, seed=42)
78 problem_edges = list(self.instance.edges)
79
80 marked_edges = []
81 for i in range(len(chain) - 1):
82 marked_edges.append(set((chain[i], chain[i + 1])))
83 marked_edges.append(set((chain[-1], chain[0])))
84
85 draw_colors = [] # Limegreen for marked edges, gray for unmarked
86 draw_widths = [] # Draw marked edges thicker
87
88 path_cost = 0
89 for edge in problem_edges:
90 draw_colors.append("limegreen" if set(edge) in marked_edges else "gray")
91 draw_widths.append(2 if set(edge) in marked_edges else 1)
92
93 path_cost += self.instance[edge[0]][edge[1]]["weight"] if set(edge) in marked_edges else 0
94
95 plt.figure(figsize=(8, 6))
96 nx.draw(
97 self.instance,
98 pos,
99 edge_color=draw_colors,
100 width=draw_widths,
101 with_labels=True,
102 node_color="skyblue",
103 node_size=500,
104 font_size=10,
105 font_weight="bold",
106 )
107
108 labels = nx.get_edge_attributes(self.instance, "weight")
109 nx.draw_networkx_edge_labels(
110 self.instance,
111 pos,
112 edge_labels=labels,
113 rotate=False,
114 font_weight="bold",
115 label_pos=0.45,
116 )
117
118 plt.title("TSP Solution Visualization")
119 plt.suptitle(f"Path cost:{path_cost}")
120 plt.show()
121
122 def _visualize_problem(self):
123 """
124 Show plot of the TSP instance.
125 """
126
127 pos = nx.spring_layout(self.instance, weight=None, seed=42)
128 plt.figure(figsize=(8, 6))
129
130 nx.draw(
131 self.instance,
132 pos,
133 with_labels=True,
134 node_color="skyblue",
135 node_size=500,
136 edge_color="gray",
137 font_size=10,
138 font_weight="bold",
139 )
140
141 labels = nx.get_edge_attributes(self.instance, "weight")
142 nx.draw_networkx_edge_labels(
143 self.instance,
144 pos,
145 edge_labels=labels,
146 rotate=False,
147 font_weight="bold",
148 node_size=500,
149 label_pos=0.45,
150 )
151
152 plt.title("TSP Instance Visualization")
153 plt.show()
154
[docs]
155 def visualize(self, solution=None):
156 if solution is None:
157 self._visualize_problem()
158 else:
159 self._visualize_solution(solution)
160
[docs]
161 @staticmethod
162 def from_preset(instance_name: str = 'default', **kwargs) -> "TSP":
163 """
164 Generate TSP instance from a preset name.
165
166 Args:
167 instance_name (str): Name of the preset instance
168 quadratic (bool, optional): Whether to use quadratic constraints. Defaults to False
169
170 Returns:
171 TSP: TSP instance
172 """
173 match instance_name:
174 case 'default':
175 edge_costs = np.array(
176 [
177 [0, 1, 2, 3],
178 [1, 0, 4, 5],
179 [2, 4, 0, 6],
180 [3, 5, 6, 0]
181 ]
182 )
183 case _:
184 raise ValueError("Unknown instance name")
185 G = nx.Graph()
186 n = edge_costs.shape[0]
187 for i in range(n):
188 for j in range(i + 1, n): # No connections to self
189 G.add_edge(i, j, weight=edge_costs[i, j])
190
191 return TSP(instance=G, instance_name=instance_name)
192
[docs]
193 @staticmethod
194 def generate_tsp_instance(num_vertices: int, min_distance: float = 1.0, max_distance: float = 10.0, **kwargs) -> "TSP":
195 """
196 Generate a random TSP instance.
197
198 Args:
199 num_vertices (int): Number of vertices in the graph
200 min_distance (float, optional): Minimum distance between vertices. Defaults to 1.0
201 max_distance (float, optional): Maximum distance between vertices. Defaults to 10.0
202 quadratic (bool, optional): Whether to use quadratic constraints. Defaults to False
203
204 Returns:
205 TSP: TSP instance
206 """
207 if num_vertices < 2:
208 raise ValueError("num_vertices must be at least 2")
209
210 if min_distance <= 0:
211 raise ValueError("min_distance must be greater than 0")
212
213 g = nx.Graph()
214 for i in range(num_vertices):
215 for j in range(i + 1, num_vertices):
216 g.add_edge(i, j, weight=int(
217 np.random.uniform(min_distance, max_distance)))
218
219 return TSP(instance=g, instance_name="generated")
