import math import random from PySide6.QtCore import Qt from PySide6.QtGui import QStandardItemModel, QStandardItem, QFont from PySide6.QtWidgets import QApplication, QMainWindow, QGraphicsScene, QMessageBox from tsp_canvas import CustomEllipseItem, CustomLineItem from tsp_data import CustomPath, Edge, Node from tsp_ui import Ui_MainWindow import get_real_data as grd class MainWindow(QMainWindow, Ui_MainWindow): def __init__(self): super(MainWindow, self).__init__() self.selected_conn_id = None # 选中连接 self.edges_info_show = True # 设置是否显示连接信息 self.setupUi(self) self.Nodes = None # 所有节点 self.Edges = None # 所有连接 self.node_ids = None # 节点id集合 self.selected_node_id = None # 选中节点 self.cp = CustomPath() # 初始化路径计算对象 self.Path = [] self.scene = QGraphicsScene() # 实例化场景 self.graphicsView.setScene(self.scene) # 显示场景 self.msg_box = QMessageBox() # 实例化警告弹窗 self.comboBox_node1.setModel(QStandardItemModel(self.Nodes)) # 设置下拉框 self.comboBox_node2.setModel(QStandardItemModel(self.Nodes)) self.comboBox_start_node.setModel(QStandardItemModel(self.Nodes)) self.comboBox_end_node.setModel(QStandardItemModel(self.Nodes)) # 设置视图属性 self.graphicsView.setAlignment(Qt.AlignCenter) # 场景居中 self.creat_node_bt.clicked.connect(self.create_node_show) # 关联创建按钮 创建节点 self.change_node_lb_bt.clicked.connect(self.change_node_lb_show) # 修改节点标签 self.add_node_button.clicked.connect(self.add_one_node) # 添加新节点 self.del_node_button.clicked.connect(self.del_one_node) # 删除选中节点 self.set_must_button.clicked.connect(lambda: self.set_must_node()) # 标记必经点 self.del_must_button.clicked.connect(lambda: self.set_must_node(False)) # 取消标记必经点 self.auto_TSP_btton.clicked.connect(self.create_random_TSP_problem) # 关联自动随机TSP问题 self.pushButton_auto_solve.clicked.connect(self.auto_solve_TSP_problem) # 关联自动求解函数和按钮 self.pushButton_create_node_conn.clicked.connect(self.create_node_conn) # 关联创建节点连接 self.pushButton_del_node_conn.clicked.connect(lambda: self.delete_edge(self.selected_conn_id)) # 关联删除节点连接 self.pushButton_set_node_conn.clicked.connect(self.change_edge_lb) # 关联修改节点连接标签 self.pushButton_conn_to_path.clicked.connect(lambda: self.set_conn_to_path(self.selected_conn_id)) # 关联设置连接为路径 self.pushButton_path_to_conn.clicked.connect(lambda: self.cancel_path_flag(self.selected_conn_id)) # 关联取消路径标记 self.pushButton_del_all_path.clicked.connect(self.cancel_all_path_flag) # 关联取消所有路径标记 self.pushButton_check_connectivity.clicked.connect(self.graph_check_connectivity) # 关联检查两节点之间的可达性 self.pushButton_optimal_path.clicked.connect(self.is_optimal_path) # 关联判断是否最优路径 self.pushButton_greedy_path.clicked.connect(self.is_greedy_path) # 关联判断是否贪心路径 self.pushButton_real_city.clicked.connect(self.create_real_city_TSP_problem) # 关联创建真实城市TSP问题 self.pushButton_ctrl_edges_lb.clicked.connect(self.ctrl_edge_info_show) # 关联控制连接信息显示 # self.set_display_all_conn() def create_random_path(self, node_num): self.create_nodes_and_edges(node_num) conn_order = list(range(node_num)) # 节点连接顺序也就是路径 random.shuffle(conn_order) # 随机打乱顺序 self.Path = self.cp.set_display_path(conn_order, self.Edges)[0] # 设置节点间路径可显示 path_distance = self.cp.path_distance_count # 获取该路径的距离成本 time = self.cp.path_time_count # 获取该路径的时间成本 # self.Path = self.cp.Path if node_num != 0: self.Nodes[3].is_must_node = True # 设置0号节点为必经节点 self.show_node() # 显示节点 self.show_node_conn() # 显示连接 self.show_path() # 显示路径 # print(path_distance,time) def create_random_conn(self, node_num): self.create_nodes_and_edges(node_num) conn_order = list(range(node_num)) # 节点连接顺序 random.shuffle(conn_order) # 随机打乱顺序 self.cp.set_display_conn(conn_order) # 设置节点间路径可显示 if node_num != 0: self.show_node() # 显示节点 self.show_node_conn() # 显示连接 self.show_path() def create_node_show(self): # 创建节点和节点连接 node_num = self.node_num_input.value() # 获取输入值 node_num = int(node_num) if node_num != 0: self.create_nodes_and_edges(node_num) self.show_node() # 显示节点 self.show_node_conn() # 显示连接 self.show_path() else: self.warning_box("节点数不能为0") def create_nodes_and_edges(self, data, real=False): # 创建节点创建边 self.Path = [] self.Nodes = self.cp.creat_node_data(data) # 创建节点 if real: self.Edges = self.cp.creat_real_edge_data(self.Nodes) # 创建所有连接 else: self.Edges = self.cp.creat_edge_data(self.Nodes) self.create_node_combobox() # 创建节点下拉框 # 节点下拉框 def create_node_combobox(self): model = QStandardItemModel() # 创建一个标准项模型 for node in self.Nodes: item = QStandardItem(str(node.label)) # 创建一个标准项 model.setItem(node.id, item) # 在指定的行列位置设置item项 self.comboBox_node1.setModel(model) # 设置下拉框 self.comboBox_node2.setModel(model) # 设置下拉框 self.comboBox_start_node.setModel(model) # 设置下拉框 self.comboBox_end_node.setModel(model) # 设置下拉框 def create_node_conn(self): # 创建节点连接 node1_id = self.comboBox_node1.currentIndex() # 获取下拉框选中的节点 node2_id = self.comboBox_node2.currentIndex() # 获取下拉框选中的节点 if node1_id != node2_id: self.set_edges_displayed(node1_id, node2_id) # 设置连接显示 def delete_edge(self, edge_id): if edge_id is not None: # 判断是否选中连接 for edge in self.Edges: # 遍历所有连接 if edge.id == edge_id: # 找到指定的连接 edge.is_displayed = False # 设置连接不显示 if edge in self.Path: self.Path.remove(edge) # 移除路径 self.cp.Edges = self.Edges # 更新数据对象的数据 break self.show_node_conn() # 刷新连接显示 self.show_path() # 刷新路径显示 else: self.statusbar.showMessage("请先选中一个连接") def change_edge_lb(self): # 修改边的标签 now_edge_lb = self.lineEdit_new_node_lb.text() # 获取用户输入 if now_edge_lb != "" and self.selected_conn_id: # 判断是否为空 for edge in self.Edges: # 遍历所有连接 if edge.id == self.selected_conn_id: # 找到选中的连接 edge.label = now_edge_lb # 修改连接标签 self.cp.Edges = self.Edges self.show_node_conn() # 刷新连接显示 self.show_path() # 刷新路径显示 def set_display_all_conn(self): # 显示所有连接 if self.Edges is not None: for edge in self.Edges: edge.is_displayed = True def show_node(self): self.scene.clear() # 清空场景 self.all_node_lb.setText(str(len(self.Nodes))) # 显示节点数目 if self.Nodes is not None: for node in self.Nodes: x, y = node.vs_coord label = node.label id = node.id if node.is_must_node: circle_item = CustomEllipseItem(x, y, id, label, True) # 必经节点节点显示 else: circle_item = CustomEllipseItem(x, y, id, label) # 非必经节点显示 circle_item.pressMouse.connect(self.select_node_lb_show) # 鼠标点击时更新当前节点显示 circle_item.collideMouse.connect(self.set_edges_displayed) # 当线连接到另外的节点时执行连线函数 self.scene.addItem(circle_item) def show_node_conn(self): # 刷新显示连接 # self.set_display_all_conn() # 显示所有连接 self.auto_solve_init() # 初始化判断显示 self.count_conn_lb.setText(str(0)) # 显示连接数目 self.remove_all_conn() conn_num = 0 for edge in self.Edges: if edge.is_displayed: sx, sy, ex, ey = self.edge_to_coord(edge) line_item = CustomLineItem(sx, sy, ex, ey, edge.id, seq=edge.sequence_number) if self.edges_info_show: line_item.set_text(f"{edge.label} ({edge.distance},{edge.time})") conn_num += 1 self.count_conn_lb.setText(str(conn_num)) # 显示连接数目 line_item.pressMouse.connect(self.selected_conn_lb_show) # 鼠标点击时更新当前连接显示 line_item.pressMouse.connect(self.selected_path_lb_show) # 鼠标点击时更新当前路径显示 self.scene.addItem(line_item) def show_path(self): # 刷新显示路径 将连接替换为路径 self.label_path_num.setText(str(0)) # 显示路径数目 for edge in self.Path: if edge.is_flagged: # 如果是路径 sx, sy, ex, ey = self.edge_to_coord(edge) # 获取路径的起始和结束坐标 for item in self.scene.items(): # 遍历场景中的所有图形项 if isinstance(item, CustomLineItem): # 检查是否是线型对象 if item.id == edge.id: # 检查是否是目标对象 self.scene.removeItem(item) # 删除线 # 重新画线并将其路径参数设置为True line_item = CustomLineItem(sx, sy, ex, ey, edge.id, True, seq=edge.sequence_number) if self.edges_info_show: # 显示连接或路径信息 line_item.set_text(f"{edge.label} ({edge.distance},{edge.time})") if self.Path != []: self.label_path_num.setText(str(len(self.Path))) # 显示路径数目 line_item.pressMouse.connect(self.selected_path_lb_show) # 鼠标点击时更新当前路径显示 line_item.pressMouse.connect(self.selected_conn_lb_show) # 鼠标点击时更新当前连接显示 self.scene.addItem(line_item) def remove_all_conn(self): # 遍历场景中的所有图形项 for item in self.scene.items(): # 检查是否是线型对象 if isinstance(item, CustomLineItem): # 从场景中移除该图形项 self.scene.removeItem(item) def set_edges_displayed(self, self_id, other_id): node_ids = [self_id, other_id] for edge in self.Edges: if edge.node1_id in node_ids and edge.node2_id in node_ids: if edge.sequence_number == 0: edge.is_displayed = True self.show_node_conn() # 刷新连接显示 self.show_path() # 刷新路径显示 # print(edge) # def create_all_conn(self): # 创建全连接图 def select_node_lb_show(self, event, node_id): # 当前节点标签 for node in self.Nodes: if node.id == node_id: self.selected_node_lb.setText(node.label) # 显示节点标签 self.selected_node_id = node_id # 选中节点的属性 # 判断node是否有city属性 X 5 if hasattr(node, 'city'): self.label_city.setText(node.city) self.label_real_coord.setText(str(node.real_coord)) else: self.label_city.setText("") self.label_real_coord.setText("") def selected_conn_lb_show(self, event, conn_id): # 当前连接标签 for edge in self.Edges: if edge.id == conn_id: self.selected_conn_lb.setText(str(conn_id)) # 显示连接标签 self.label_conn_dis.setText(str(edge.distance)) # 显示连接距离 self.label_conn_time.setText(str(edge.time)) # 显示连接时间 self.selected_conn_id = conn_id # 选中连接的id def selected_path_lb_show(self, event, path_id): # 当前路径标签 for path in self.Edges: if path.id == path_id: self.selected_path_lb.setText(str(path_id)) # 显示路径标签 self.label_path_dis.setText(str(path.distance)) # 显示路径距禽 self.label_path_time.setText(str(path.time)) # 显示路径时间 self.selected_conn_id = path_id # 选中连接的id # 取消路径标记 def cancel_path_flag(self, path_id): for path in self.Edges: if path.id == path_id: path.is_flagged = False if path in self.Path: # 如果路径在路径列表中 self.Path.remove(path) # 移除路径 self.cp.Path = self.Path self.label_path_num.setText(str(len(self.Path))) # 显示路径数目 self.show_node_conn() self.show_path() # 取消所有路径标记 def cancel_all_path_flag(self): for path in self.Edges: path.is_flagged = False self.Path = [] self.cp.Path = self.Path self.label_path_num.setText(str(len(self.Path))) # 显示路径数目 self.show_node_conn() self.show_path() # 将选中连接标记为路径 def set_conn_to_path(self, conn_id): for edge in self.Edges: if edge.id == conn_id: edge.is_flagged = True if edge not in self.Path: # 如果路径不在路径列表中 self.Path.append(edge) # 添加路径 self.cp.Path = self.Path self.label_path_num.setText(str(len(self.Path))) # 显示路径数目 self.show_node_conn() self.show_path() # 两节点之间可达性检查 def graph_check_connectivity(self): node1_id = self.comboBox_start_node.currentIndex() node2_id = self.comboBox_end_node.currentIndex() if node1_id != node2_id: for node in self.Nodes: if node.id == node1_id: node1 = node if node.id == node2_id: node2 = node result = self.cp.graph_check_connectivity(node1, node2) font = QFont() font.setPointSize(24) self.label_is_connectivity.setFont(font) if result[0]: self.label_is_connectivity.setStyleSheet("background-color: lightgreen") self.label_is_connectivity.setText(str(result[0])) else: self.label_is_connectivity.setStyleSheet("background-color: lightcoral") self.label_is_connectivity.setText(f"False: \n{result[1]}到{result[2]}无连接") else: self.warning_box("两个节点不能相同") # 判断某路径是否最优路径 def is_optimal_path(self): time_n = self.radioButton_time.isChecked() # 时间优先 must_node = self.check_and_get_must_nodes_id() # 必经点 if time_n: if len(must_node) == 0: result = self.cp.check_user_best(self.Path,False) else: result = self.cp.check_user_best(self.Path, False, 0,must_node) else: if len(must_node) == 0: result = self.cp.check_user_best(self.Path) else: result = self.cp.check_user_best(self.Path, True, 0,must_node) font = QFont() font.setPointSize(24) self.label_is_optimal_path.setFont(font) if result: self.label_is_optimal_path.setStyleSheet("background-color: lightgreen") self.label_is_optimal_path.setText("True") else: self.label_is_optimal_path.setStyleSheet("background-color: lightcoral") self.label_is_optimal_path.setText("False") # 判断是否贪心路径 def is_greedy_path(self): time_n = self.radioButton_time.isChecked() # 时间优先 if time_n: result = self.cp.check_is_greedy(self.Path,False) else: result = self.cp.check_is_greedy(self.Path) font = QFont() font.setPointSize(24) self.label_is_greedy_path.setFont(font) bool_value = result[0] if bool_value: self.label_is_greedy_path.setStyleSheet("background-color: lightgreen") self.label_is_greedy_path.setText("True") else: self.label_is_greedy_path.setStyleSheet("background-color: lightcoral") self.label_is_greedy_path.setText("False") if result[1] is not None: self.warning_box(result[1]) # time_n = self.radioButton_time.isChecked() # 时间优先 # if time_n: # graph = self.cp.creat_graph(self.Nodes, is_distance=False) # 创建图 # else: # graph = self.cp.creat_graph(self.Nodes) # 创建图 # value = self.cp.greedy_search_to_path(graph) # 贪心算法 # font = QFont() # 调整字体大小 # font.setPointSize(24) # self.label_is_greedy_path.setFont(font) # if isinstance(value[0], list): # optimal_path_value = value[1] # 最优路径权重 # current_path_value = self.path_distance_time_count() # 当前路径权重 # if current_path_value == optimal_path_value: # self.label_is_greedy_path.setStyleSheet("background-color: lightgreen") # self.label_is_greedy_path.setText("True") # else: # self.label_is_greedy_path.setStyleSheet("background-color: lightcoral") # self.label_is_greedy_path.setText("False") # else: # self.label_is_greedy_path.setStyleSheet("background-color: lightcoral") # self.label_is_greedy_path.setText("False") # self.warning_box(value[1]) # 计算路径的距离或时间 def path_distance_time_count(self): time_n = self.radioButton_time.isChecked() # 时间优先 min_value = 0 if time_n: for path in self.Path: min_value += path.time return min_value else: for path in self.Path: min_value += path.distance return min_value def edge_to_coord(self, edge): # 边转坐标 sx, sy, ex, ey = 0, 0, 0, 0 for node in self.Nodes: if edge.node1_id == node.id: sx, sy = node.vs_coord if edge.node2_id == node.id: ex, ey = node.vs_coord return sx, sy, ex, ey def change_node_lb_show(self): # 改变节点标签 if self.Nodes is not None: now_node_lb = self.selected_node_lb.text() # 当前节点 new_node_lb = self.edit_node_lb_inp.text() # 用户输入 objs = self.scene.selectedItems() if self.Nodes is not None: for node in self.Nodes: for obj in objs: if node.label == now_node_lb and node.id == obj.id: node.label = new_node_lb self.show_node() self.show_node_conn() self.show_path() else: self.warning_box("请先创建节点") def add_end_node_edges(self, new_node_id): # 添加新节点的潜在连接 edge_ids = set(edge.id for edge in self.Edges) # 边的id集合 for node in self.Nodes: for n in range(3): if node.id != new_node_id: if edge_ids: connection_id = max(edge_ids) + 1 else: connection_id = 0 edge_ids.add(connection_id) node1_id = node.id node2_id = new_node_id is_displayed = False is_flagged = False label = f"C{connection_id}-{n}" distance = random.randint(10, 1000) time = random.randint(1, 6) * distance sequence_number = n edge_info = [connection_id, node1_id, node2_id, is_displayed, is_flagged, label, distance, time, sequence_number] edge = Edge(edge_info) self.Edges.append(edge) self.cp.Edges = self.Edges def update_all_node_positions(self): # 更新所有节点的位置 num_nodes = len(self.Nodes) ang = 360 / num_nodes # 圆形顶点角度 R = 330 # 外接圆半径 for i, node in enumerate(self.Nodes): rad = math.radians(i * ang) x = int(math.cos(rad) * R) y = int(math.sin(rad) * R) node.vs_coord = [x, y] self.cp.Nodes = self.Nodes def add_one_node(self): # 新增一个节点 if isinstance(self.Nodes, list): node_ids = set(node.id for node in self.Nodes) # 找到一个未使用的节点ID new_id = 0 while new_id in node_ids: new_id += 1 # 创建新节点并添加到 self.Nodes 中 new_node = Node([new_id, str(new_id), False, [0, 0], False]) # 初始化新节点 self.Nodes.append(new_node) self.cp.Path = self.Path self.update_all_node_positions() # 更新所有节点的位置 self.add_end_node_edges(new_id) # 添加新节点的潜在连接 self.create_node_combobox() # 创建节点下拉框 self.show_node() # 显示节点 self.show_node_conn() # 显示连接 self.show_path() # 显示路径 else: self.warning_box("请先创建节点") def del_current_node_edges(self, node_id): edges_to_remove = [] # 用于存储需要删除的边的列表 paths_to_remove = [] # 用于储存需要删除的路径的列表 for edge in self.Edges: if edge.is_displayed: id1, id2 = edge.node1_id, edge.node2_id if node_id == id1 or node_id == id2: edges_to_remove.append(edge) for path in self.Path: if path.is_flagged: id1, id2 = path.node1_id, path.node2_id if node_id == id1 or node_id == id2: paths_to_remove.append(path) for edge in edges_to_remove: # 从self.Edges中移除指定的边 self.Edges.remove(edge) for path in paths_to_remove: # 从self.Path中移除指定的路径 self.Path.remove(path) # self.Path.remove(edge) def del_one_node(self): # 删除一个节点 node_id = self.selected_node_id if node_id is not None: for node in self.Nodes: if node.id == node_id: self.Nodes.remove(node) # 删除节点 break self.del_current_node_edges(node_id) # 删除节点关联的边 self.cp.Nodes = self.Nodes # 更新数据对象的数据 self.cp.Edges = self.Edges self.cp.Path = self.Path self.show_node() self.show_node_conn() self.show_path() self.selected_node_id = None def set_must_node(self, status=True): # 标识必经节点和取消标记必经节点 node_id = self.selected_node_id # 当前选中节点 if node_id is not None: for node in self.Nodes: if node.id == node_id: node.is_must_node = status self.show_node() self.show_node_conn() self.show_path() self.selected_node_id = None # 执行完成后归于无 def create_random_TSP_problem(self): nodes = random.randint(3, 7) # 随机节点个数 self.create_nodes_and_edges(nodes) # 创建节点和边 num = random.randint(1, 4) for i in range(num): # 打乱1-4次 conn_order = list(range(nodes)) # 节点连接顺序 random.shuffle(conn_order) # 随机打乱顺序 self.cp.set_display_conn(conn_order) # 设置节点间路径可显示 self.show_node() # 显示节点 self.show_node_conn() # 显示连接 self.show_path() # 显示路径 def create_real_city_TSP_problem(self): data = grd.get_district("湖南省") self.create_nodes_and_edges(data, real=True) num = random.randint(1,4) for i in range(num): conn_order = list(range(len(self.Nodes))) random.shuffle(conn_order) self.cp.set_display_conn(conn_order) self.show_node() # 显示节点 self.show_node_conn() # 显示连接 self.show_path() # 显示路径 def ctrl_edge_info_show(self): if self.edges_info_show: self.edges_info_show = False else: self.edges_info_show = True self.show_node_conn() self.show_path() def check_and_get_must_nodes_id(self): must_nodes = [] for node in self.Nodes: if node.is_must_node: must_nodes.append(node.id) return must_nodes def auto_solve_TSP_problem(self): method = self.auto_solve_comboBox.currentText() # 求解方法 time_n = self.radioButton_time.isChecked() # 时间优先 must_nodes = self.check_and_get_must_nodes_id() # 获取必经节点 if time_n: graph, min_edges = self.cp.creat_graph(self.Nodes, is_distance=False) else: graph, min_edges = self.cp.creat_graph(self.Nodes) if method == '贪心': path = self.cp.greedy_search_to_path(graph) # 贪心算法 else: if len(must_nodes) != 0: path = self.cp.traversal_search_to_path(graph, 0, must_nodes) # 深度优先搜索 else: path = self.cp.traversal_search_to_path(graph) # 深度优先搜索 if isinstance(path[0], list): # 正确返回list时执行路径计算和显示 rvalue = self.cp.set_display_path(path[0][0], min_edges) self.Path = rvalue[0] self.label_distance.setText(str(rvalue[1])) self.label_time.setText(str(rvalue[2])) self.show_node() # 显示节点 self.show_node_conn() # 显示连接 self.show_path() # 显示路径 self.statusbar.showMessage(f"算法执行时间为{path[2]:.2f}") else: rvalue = self.cp.set_display_path(path[2], min_edges) # 路径计算失败时，如果最后一条路径的节点之一和起相同，则删除最后一条路径 if rvalue[0][-1].node1_id == path[2][0] or rvalue[0][-1].node2_id == path[2][0]: rvalue[0].pop() self.Path = rvalue[0] self.show_node() # 显示节点 self.show_node_conn() # 显示连接 self.show_path() # 显示路径 self.statusbar.showMessage(path[1]) self.warning_box(path[1]) self.auto_solve_init() # 初始化判断显示 # 自动判断初始化 def auto_solve_init(self): # 调整字体大小 font = QFont() font.setPointSize(9) self.label_is_connectivity.setFont(font) self.label_is_connectivity.setStyleSheet(u"background-color:rgb(255, 255, 255);\n" "border: 1px solid black;") self.label_is_connectivity.setText("路径未知") self.label_is_optimal_path.setFont(font) self.label_is_optimal_path.setStyleSheet(u"background-color:rgb(255, 255, 255);\n" "border: 1px solid black;") self.label_is_optimal_path.setText("路径未知") self.label_is_greedy_path.setFont(font) self.label_is_greedy_path.setStyleSheet(u"background-color:rgb(255, 255, 255);\n" "border: 1px solid black;") self.label_is_greedy_path.setText("路径未知") # 警告弹窗 def warning_box(self, message): self.msg_box.setIcon(QMessageBox.Warning) self.msg_box.setWindowTitle("警告") self.msg_box.setText(message) self.msg_box.setStandardButtons(QMessageBox.Ok) self.msg_box.exec() if __name__ == '__main__': app = QApplication([]) window = MainWindow() window.show() app.exec()