|
|
# -*- coding: utf-8 -*-
|
|
|
# Time : 2023/11/7 17:03
|
|
|
# Author : lirunsheng
|
|
|
# User : l'r's
|
|
|
# Software: PyCharm
|
|
|
# File : X4_1.py
|
|
|
|
|
|
# -*- coding: utf-8 -*-
|
|
|
# Time : 2023/10/30 15:49
|
|
|
# Author : lirunsheng
|
|
|
# User : l'r's
|
|
|
# Software: PyCharm
|
|
|
# File : X4.py
|
|
|
from tkinter import Tk
|
|
|
import random
|
|
|
import math
|
|
|
import time
|
|
|
import tkinter as tk
|
|
|
from tkinter import *
|
|
|
from tkinter import messagebox
|
|
|
import numpy as np
|
|
|
|
|
|
MODE = 0
|
|
|
BLUE = "#0080FF"
|
|
|
BLACK = "#000000"
|
|
|
RED = "#FFAAAA"
|
|
|
YELLOW = "#FFFACD"
|
|
|
LINE = '#c8d2c8'
|
|
|
GREY = '#070b19'
|
|
|
GREEN = '#5ba585'
|
|
|
NODE = '#33a8cd'
|
|
|
ZERO = 'gold'
|
|
|
MARK_NODE = 0
|
|
|
Specify_Nodes = ''
|
|
|
Edges_list = []
|
|
|
NAME = []
|
|
|
|
|
|
class Data:
|
|
|
def __init__(self, source: int, num: int):
|
|
|
global NAME
|
|
|
if num <= 0 or num > 10:
|
|
|
raise ValueError("num must be a positive integer")
|
|
|
self.edgeinfo = 1 # 是否显示详情
|
|
|
self.nodes_num = num # 节点个数
|
|
|
self.ang = 360 / self.nodes_num # 圆心顶点角度
|
|
|
self.R = 300 # 外接圆半径
|
|
|
self.bc = 2 * self.R * math.sin(math.pi / self.nodes_num) # 节点之间的正多边形距离
|
|
|
self.canvas_len = int(2 * self.R + 80) # 画布边长
|
|
|
self.center = (self.canvas_len // 2, self.canvas_len // 2) # 画布中心点坐标
|
|
|
self.drop = []
|
|
|
self.index = 0
|
|
|
if source == 3 or source == 2: # 指定删除
|
|
|
# name = [str(i) for i in range(1, num + 2)]
|
|
|
# print(name)
|
|
|
if source == 2:
|
|
|
NAME.pop()
|
|
|
else:
|
|
|
# print(Specify_Nodes)
|
|
|
NAME.remove(Specify_Nodes)
|
|
|
self.name = NAME
|
|
|
self.coordinate = self.coord_creat() # 纯节点坐标
|
|
|
self.Nodes = self.nodes_creat() # 创建节点列表
|
|
|
print(self.Nodes)
|
|
|
self.Edges = self.edges_delete(source) # 创建第一条连接
|
|
|
else:
|
|
|
if source == 1:
|
|
|
name = str(int(NAME[-1])+1)
|
|
|
# print(name)
|
|
|
NAME.append(name)
|
|
|
else:
|
|
|
NAME = [str(i) for i in range(1, num + 1)]
|
|
|
# print(NAME)
|
|
|
self.name = NAME
|
|
|
self.coordinate = self.coord_creat() # 纯节点坐标
|
|
|
self.Nodes = self.nodes_creat() # 创建节点列表
|
|
|
print(self.Nodes)
|
|
|
self.Edges = self.edges_creat(source) # 创建第一条连接
|
|
|
self.edge_add(2, source) # 创建第2条连接
|
|
|
self.edge_add(3, source) # 创建第3条连接
|
|
|
|
|
|
def nodes_creat(self, n_sum=None):
|
|
|
if n_sum == None:
|
|
|
n_sum = self.nodes_num
|
|
|
nodes = [] # 初始化node表
|
|
|
# 设置画布中心点坐标x0,y0
|
|
|
x0 = self.center[0]
|
|
|
y0 = self.center[1]
|
|
|
for i in range(n_sum): # 通过几何运算得到多边形各个顶点坐标
|
|
|
rad = math.radians(i * self.ang) # 计算第i个点的弧度
|
|
|
x = int(math.cos(rad) * self.R) # 计算第i个顶点x坐标
|
|
|
y = int(math.sin(rad) * self.R) # 计算第i个顶点y坐标
|
|
|
# name = '' + str(i + 1) # 给第i个顶点命名
|
|
|
name = '' + self.name[i]
|
|
|
mark = 0 # 节点为未标记
|
|
|
dominator = 1 # 设置为必经节点
|
|
|
nodes.append([i, name, mark, (x0 + x, y0 + y), dominator]) # 将当前节点加入node中
|
|
|
return nodes
|
|
|
|
|
|
def edges_delete(self, source):
|
|
|
edges = [] # 初始化所有链接集合
|
|
|
ser = 0
|
|
|
# print(str(int(Specify_Nodes) + 1))
|
|
|
for list_edge in Edges_list:
|
|
|
# print(list_edge)
|
|
|
edges.append([ser, list_edge[1], list_edge[2],list_edge[3], list_edge[4],list_edge[5], list_edge[6],
|
|
|
list_edge[7], list_edge[8]]) # 将连接加入到边的集合中
|
|
|
nox = [int(num) for num in edges[ser][5].split('-')]
|
|
|
# print(nox)
|
|
|
if len(nox) == 2:
|
|
|
ss = edges[ser][5]
|
|
|
else:
|
|
|
ss = edges[ser][5][:-2]
|
|
|
# print(ss)
|
|
|
if source == 2:
|
|
|
if str(len(self.Nodes)+1) in ss:
|
|
|
# print(edges[ser])
|
|
|
edges.pop()
|
|
|
ser -= 1
|
|
|
else:
|
|
|
if Specify_Nodes in ss:
|
|
|
# print(edges[ser])
|
|
|
edges.pop()
|
|
|
ser -= 1
|
|
|
ser += 1
|
|
|
return edges
|
|
|
|
|
|
def edges_creat(self, source):
|
|
|
edges = [] # 初始化所有链接集合
|
|
|
ser = 0 # 初始化链接对象编号
|
|
|
nodes = self.Nodes.copy() # 复制节点对象
|
|
|
nodes1 = self.Nodes.copy() # 复制节点对象
|
|
|
# print(nodes1)
|
|
|
self.drop = []
|
|
|
for node in nodes: # 遍历节点对象
|
|
|
if node in nodes1: # 删除nodes1中当期遍历的节点信息
|
|
|
nodes1.remove(node)
|
|
|
# print(nodes1)
|
|
|
for node1 in nodes1: # 遍历删除后的节点信息
|
|
|
n1 = node[0] # 节点对象编号1
|
|
|
n2 = node1[0] # 节点对象编号2
|
|
|
if self.drop.count(n2) > 3 or self.drop.count(n1) > 3:
|
|
|
dist_c = random.randint(101, 120) # 随机生成距离成本
|
|
|
time_c = random.randint(101, 120) # 随机生成链接的时间
|
|
|
else:
|
|
|
dist_c = random.randint(10, 120) # 随机生成距离成本
|
|
|
time_c = random.randint(10, 120) # 随机生成链接的时间
|
|
|
seq = 1 # 链接序号
|
|
|
mark = False # 连接是否标记
|
|
|
tag = f"{NAME[n1]}-{NAME[n2]}" # 链接标签
|
|
|
enable = 1 # 连接是否可用
|
|
|
if dist_c >= 100 or time_c >= 100: # 设置某些节点为不显示
|
|
|
enable = 0
|
|
|
else:
|
|
|
self.drop.append(n1)
|
|
|
self.drop.append(n2)
|
|
|
if source == 1:
|
|
|
# print(n2, len(self.Nodes))
|
|
|
if n2 == len(self.Nodes)-1:
|
|
|
# print('进来了')
|
|
|
edges.append([ser, int(NAME[n1])-1, int(NAME[n2])-1, enable, mark, tag, dist_c, time_c, seq]) # 将连接加入到边的集合中
|
|
|
else:
|
|
|
# print(self.index)
|
|
|
edges.append([ser, Edges_list[self.index][1], Edges_list[self.index][2],
|
|
|
Edges_list[self.index][3], Edges_list[self.index][4],
|
|
|
Edges_list[self.index][5],Edges_list[self.index][6],
|
|
|
Edges_list[self.index][7], Edges_list[self.index][8]]) # 将连接加入到边的集合中
|
|
|
self.index += 1
|
|
|
else:
|
|
|
edges.append([ser, int(NAME[n1])-1, int(NAME[n2])-1, enable, mark, tag, dist_c, time_c, seq]) # 将连接加入到边的集合中
|
|
|
ser += 1 # 计数加一
|
|
|
return edges
|
|
|
|
|
|
def edge_add(self, no, source):
|
|
|
nodes = self.Nodes.copy() # 复制节点对象
|
|
|
nodes1 = self.Nodes.copy() # 复制节点对象
|
|
|
for node in nodes: # 遍历节点对象
|
|
|
if node in nodes1: # 删除nodes1中当期遍历的节点信息
|
|
|
nodes1.remove(node)
|
|
|
for node1 in nodes1: # 遍历删除后的节点信息
|
|
|
ser = len(self.Edges) # 链接序号
|
|
|
n1 = node[0] # 节点对象编号1
|
|
|
n2 = node1[0] # 节点对象编号2
|
|
|
show = 0 # 设置为不显示
|
|
|
mark = False # 连接是否标记
|
|
|
tag = f"{NAME[n1]}-{NAME[n2]}-{no}" # 链接标签
|
|
|
dist_c = random.randint(30, 100) # 距离成本
|
|
|
time_c = random.randint(1, 30) # 链接的时间
|
|
|
enable = no # 连接是否可用
|
|
|
if source == 1:
|
|
|
if n2 == len(self.Nodes)-1:
|
|
|
# print('进来了')
|
|
|
self.Edges.append([ser, int(NAME[n1])-1, int(NAME[n2])-1, show, mark, tag, dist_c, time_c, enable]) # 将连接加入到边的集合中
|
|
|
else:
|
|
|
# print(no ,self.index)
|
|
|
self.Edges.append([ser, Edges_list[self.index][1], Edges_list[self.index][2],
|
|
|
Edges_list[self.index][3], Edges_list[self.index][4],
|
|
|
Edges_list[self.index][5], Edges_list[self.index][6],
|
|
|
Edges_list[self.index][7], Edges_list[self.index][8]]) # 将连接加入到边的集合中
|
|
|
|
|
|
self.index += 1
|
|
|
else:
|
|
|
self.Edges.append([ser, int(NAME[n1])-1, int(NAME[n2])-1, show, mark, tag, dist_c, time_c, enable])
|
|
|
|
|
|
def coord_creat(self):
|
|
|
'''返回每个节点的坐标'''
|
|
|
coordinate = []
|
|
|
x0 = self.center[0]
|
|
|
y0 = self.center[1]
|
|
|
for i in range(self.nodes_num):
|
|
|
rad = math.radians(i * self.ang)
|
|
|
x = int(math.cos(rad) * self.R)
|
|
|
y = int(math.sin(rad) * self.R)
|
|
|
coordinate.append((x0 + x, y0 + y))
|
|
|
return coordinate
|
|
|
|
|
|
def node_co(self, key): # 通过节点编号返回编号的坐标
|
|
|
"""通过节点编号返回编号的坐标"""
|
|
|
nodes = self.Nodes
|
|
|
for n in nodes:
|
|
|
if n[1] == str(key + 1):
|
|
|
return n[3]
|
|
|
|
|
|
def node_no(self, key): # 通过节点编号返回编号的坐标
|
|
|
"""通过节点编号返回编号的坐标"""
|
|
|
nodes = self.Nodes
|
|
|
for n in nodes:
|
|
|
if n[1] == str(key + 1):
|
|
|
return n[0]
|
|
|
# G = Graph()
|
|
|
# print(1)
|
|
|
nodes = 6 # 设置初始节点数量
|
|
|
d = Data(0, nodes)
|
|
|
# print(1)
|
|
|
root = Tk() # 设置主界面
|
|
|
root.title("旅行商问题") # 设置标题
|
|
|
root.geometry(f"{d.canvas_len + 700}x{d.canvas_len + 100}") # 设置大小
|
|
|
root.resizable(0, 0) # 设置不能调整显示边框
|
|
|
|
|
|
frame = tk.Frame(root, padx=20, pady=20, width=d.canvas_len + 340, height=d.canvas_len + 50)
|
|
|
frame.grid() # 绘制显示框
|
|
|
|
|
|
frame_top = tk.Frame(frame, width=d.canvas_len, height=50)
|
|
|
frame_top.grid(row=0, column=0) # 绘制信息输出栏
|
|
|
|
|
|
cv = canvas = tk.Canvas(frame, bg='white', bd=2, relief="sunken", width=d.canvas_len + 330, height=d.canvas_len)
|
|
|
canvas.grid(row=1, column=0) # 放置绘图Canvas画布
|
|
|
|
|
|
frame_right = tk.Frame(root, bg=RED, width=300, height=d.canvas_len + 50) # 右边栏
|
|
|
frame_right.grid(row=0, column=1) # 右边栏
|
|
|
|
|
|
class Graph:
|
|
|
# Graph定义
|
|
|
def edge_info(self, cv: tk.Canvas, info: str, n1: tuple, n2: tuple): # 显示路径信息
|
|
|
if d.edgeinfo == 0: # 若设置为不显示则直接返回
|
|
|
return
|
|
|
# print(n1)
|
|
|
# print(n2)
|
|
|
x = (n1[0] - n2[0]) // 2 + n2[0] # 计算中点x坐标
|
|
|
y = (n1[1] - n2[1]) // 2 + n2[1] # 计算中点y坐标
|
|
|
if (n2[1] - n1[1]) != 0: # 斜率为非0度时的显示
|
|
|
reat = math.atan((n2[0] - n1[0]) / (n2[1] - n1[1])) # 根据斜率计算弧度
|
|
|
ang = round(math.degrees(reat)) + 90 # 根据弧度转角度
|
|
|
if ang > 89: # 斜度大于90度调整坐标
|
|
|
text_x, text_y = x + 15, y
|
|
|
else: # 斜度大于90度调整坐标
|
|
|
text_x, text_y = x, y + 15
|
|
|
else: # 斜率为0度时的显示
|
|
|
ang = round(math.degrees(0)) # 根据弧度转角度
|
|
|
text_x, text_y = x - 30, y + 10
|
|
|
# print(info.split(' ')[-1])
|
|
|
cv.create_text(text_x, text_y, text=f'{info.split()[-2]}', fill="black", font=('微软雅黑', 12), angle=ang) # 根据信息显示文字
|
|
|
|
|
|
def draw(self):
|
|
|
cv.delete('all') # 清空画布
|
|
|
dis, tim = self.edges_show(cv, d.Edges) # 绘制边
|
|
|
self.lab_show(frame_top, len(d.Nodes), tim, dis) # 显示边信息
|
|
|
self.nodes_show(cv) # 绘制点
|
|
|
cv.update() # 更新画布
|
|
|
|
|
|
|
|
|
def lab_show(self, frame: tk.Frame, nodes: int, time: int, distance: int):
|
|
|
labs = ["节点数目", "时间", "距离(成本)"]
|
|
|
x0 = d.canvas_len // 3
|
|
|
for i in range(len(labs)):
|
|
|
lab1 = tk.Label(frame, text=labs[i], fg=BLACK, font=('微软雅黑', 12))
|
|
|
if i == 0:
|
|
|
lab2 = tk.Label(frame, text=f"{nodes}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12))
|
|
|
elif i == 1:
|
|
|
lab2 = tk.Label(frame, text=f"{time}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12))
|
|
|
else:
|
|
|
lab2 = tk.Label(frame, text=f"{distance}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(x=10 + x0 * i, y=10, width=80, height=30)
|
|
|
lab2.place(x=10 + x0 * i + 80, y=10, width=80, height=30)
|
|
|
lab1 = tk.Label(frame, text='分钟', fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(x=170 + x0, y=10, width=50, height=30)
|
|
|
lab1 = tk.Label(frame, text='千米', fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(x=170 + x0 * 2, y=10, width=50, height=30)
|
|
|
|
|
|
def nodes_show(self, cv: tk.Canvas):
|
|
|
COL = NODE # 初始化节点颜色
|
|
|
for i in d.Nodes: # 遍历每一个节点
|
|
|
x, y = i[3] # 记录该节点坐标
|
|
|
if i[2] == 1 or i[2] == 2: # 如果节点被标记，则将节点标为红色
|
|
|
COL = RED
|
|
|
elif i[0] == 0: # 如果节点为起始节点，则将节点标记为特殊颜色
|
|
|
COL = ZERO
|
|
|
elif i[2] == 5: # 如果节点已经被访问，则将节点标记（用户路径功能）
|
|
|
COL = 'gold'
|
|
|
else: # 否则则使用初始颜色
|
|
|
COL = NODE
|
|
|
if i[4] == 1: # 如果是必经节点，则加黑色边框
|
|
|
w = 1
|
|
|
else: # 如果是非必经节点，则没有边框
|
|
|
w = 0
|
|
|
# 根据坐标，圆的颜色与是否有边框绘制圆圈来表示节点
|
|
|
cv.create_oval(x - 20, y - 20, x + 20, y + 20, fill=COL, width=w, ) # outline='#ee28a3')
|
|
|
cv.create_text(x, y, text=f'{i[1]}', fill=GREY, font=('华文楷体', 18))
|
|
|
cv.update()
|
|
|
|
|
|
def edges_show(self, cv: tk.Canvas, edges: d.Edges):
|
|
|
"""
|
|
|
显示链接
|
|
|
:param cv: tkcanvas对象
|
|
|
:return:
|
|
|
"""
|
|
|
distance = 0 # 初始化被标记的线的总路径
|
|
|
time1 = 0 # 初始化被标记的线的总时间
|
|
|
for edge in edges:
|
|
|
node_1 = d.node_co(edge[1]) # 链接线编号对应的坐标1
|
|
|
node_2 = d.node_co(edge[2]) # 链接线编号对应的坐标2
|
|
|
# print(node_1,node_2)
|
|
|
if edge[8] == 2 and edge[3] == 1: # 若该链接为两点间第二条连线
|
|
|
self.more_edge_show(2, edge)
|
|
|
elif edge[8] == 3 and edge[3] == 1: # 若为两点间第3条连线
|
|
|
self.more_edge_show(3, edge)
|
|
|
if edge[8] == 1 and edge[3] == 1: # 若为两点间第1条连线且该连接存在
|
|
|
self.edge_info(cv, f'{edge[5]} {edge[6]} {edge[7]}', node_1, node_2)
|
|
|
point = [node_1, node_2]
|
|
|
if edge[4] == 1 and edge[8] == 1 and edge[3] == 1: # 如果路径被标记，则用绿色绘制
|
|
|
if MODE == 1:
|
|
|
cv.create_line(point, fill=RED, width=4)
|
|
|
elif MODE == 2:
|
|
|
cv.create_line(point, fill=BLUE, width=4)
|
|
|
else:
|
|
|
cv.create_line(point, fill=GREEN, width=4)
|
|
|
distance += edge[6] # 更新总路径
|
|
|
time1 += edge[7] # 更新总时间
|
|
|
elif edge[8] == 1 and edge[3] == 1: # 如果是节点之间的第一条线，则用正常颜色标记
|
|
|
cv.create_line(point, fill=LINE, width=2)
|
|
|
if d.Nodes[d.node_no(edge[2])][2] + d.Nodes[d.node_no(edge[2])][2] == 3: # 若该线被用户选中，则用蓝色虚线标记
|
|
|
cv.create_line(point, fill=BLUE, width=5, dash=(4, 14))
|
|
|
return (distance, time1) # 返回标记路径的总时间与路程
|
|
|
|
|
|
# def node_edge(self, a, b): # 根据点的编号找边的编号
|
|
|
# if a > b:
|
|
|
# x = a
|
|
|
# a = b
|
|
|
# b = x
|
|
|
# return int(a * (2 * len(d.Nodes) - a - 3) / 2 + b - 1)
|
|
|
|
|
|
def node_edge(self, a, b): # 根据点的编号找边的编号
|
|
|
for edge in d.Edges:
|
|
|
if a == edge[1] and b == edge[2]:
|
|
|
return edge[0]
|
|
|
if b == edge[1] and a == edge[2]:
|
|
|
return edge[0]
|
|
|
|
|
|
def way_node_edge(self, a, b): # 根据点的编号找边的编号
|
|
|
way = []
|
|
|
for node in d.Nodes:
|
|
|
way.append(int(node[1]))
|
|
|
# print(way)
|
|
|
# print(a, b)
|
|
|
x, y = way[a]-1, way[b]-1
|
|
|
for edge in d.Edges:
|
|
|
if x == edge[1] and y == edge[2]:
|
|
|
return edge[0]
|
|
|
if y == edge[1] and x == edge[2]:
|
|
|
return edge[0]
|
|
|
|
|
|
def delete_all(self):
|
|
|
cv.delete('all') # 清空画布
|
|
|
self.lab_show(frame_top, 0, 0, 0) # 显示边信息
|
|
|
W.user_way = [0]
|
|
|
W.way_route_markings()
|
|
|
|
|
|
class Edge:
|
|
|
def __init__(self):
|
|
|
self.mark = []
|
|
|
# 记录已标记的节点数目（连接操作）
|
|
|
self.user_cur = 0
|
|
|
# 记录用户所在点
|
|
|
|
|
|
def node_edge(self, no, n1, n2): # 根据节点返回编号
|
|
|
if n1 > n2:
|
|
|
n = n1
|
|
|
n1 = n2
|
|
|
n2 = n
|
|
|
for e in d.Edges:
|
|
|
if e[1] == n1 and e[2] == n2 and e[8] == no:
|
|
|
return e[0]
|
|
|
return -1
|
|
|
def edge_del_all(self, mode):
|
|
|
# mode = 1:优先最短路径
|
|
|
# mode = 2:优先最短时间
|
|
|
# cur1 = node_edge()
|
|
|
if mode == 1:
|
|
|
for e in d.Edges:
|
|
|
if (e[8] == 2 and e[3] == 1) or (e[8] == 3 and e[3] == 1):
|
|
|
self.edge_merge_cost(e[1], e[2])
|
|
|
else:
|
|
|
for e in d.Edges:
|
|
|
if (e[8] == 2 and e[3] == 1) or (e[8] == 3 and e[3] == 1):
|
|
|
self.edge_merge_time(e[1], e[2])
|
|
|
G.draw()
|
|
|
|
|
|
def edge_merge_cost(self, n1, n2):
|
|
|
cur1 = node_edge(n1, n2) # 初始化三条可能的边的编号
|
|
|
cur2 = node_edge(n1, n2, 2) # 初始化三条可能的边的编号
|
|
|
cur3 = node_edge(n1, n2, 3) # 初始化三条可能的边的编号
|
|
|
edges = [(cur1, d.Edges[cur1][6]), (cur2, d.Edges[cur2][6]), (cur3, d.Edges[cur3][6])] # 提出编号与路径花费
|
|
|
valid_edges = [(edge, cost) for edge, cost in edges if d.Edges[edge][3] == 1] # 过滤出存在的边
|
|
|
valid_edges.sort(key=lambda x: x[1]) # 按照 cost 排序，保留 cost 最小的边
|
|
|
for idx, (edge, _) in enumerate(valid_edges):
|
|
|
d.Edges[edge][8] = idx + 1 # 设置边的优先级
|
|
|
d.Edges[edge][0] = edge # 确保边的索引正确
|
|
|
for edge, _ in valid_edges[1:]: # 对于非最优边，设置其为不显示
|
|
|
d.Edges[edge][3] = 0
|
|
|
def edge_merge_time(self, n1, n2):
|
|
|
cur1 = node_edge(n1, n2) # 初始化三条可能的边的编号
|
|
|
cur2 = node_edge(n1, n2, 2) # 初始化三条可能的边的编号
|
|
|
cur3 = node_edge(n1, n2, 3) # 初始化三条可能的边的编号
|
|
|
edges = [(cur1, d.Edges[cur1][7]), (cur2, d.Edges[cur2][7]), (cur3, d.Edges[cur3][7])] # 提出编号与路径花费
|
|
|
valid_edges = [(edge, cost) for edge, cost in edges if d.Edges[edge][3] == 1] # 过滤出存在的边
|
|
|
valid_edges.sort(key=lambda x: x[1]) # 按照 cost 排序，保留 cost 最小的边
|
|
|
for idx, (edge, _) in enumerate(valid_edges):
|
|
|
d.Edges[edge][8] = idx + 1 # 设置边的优先级
|
|
|
d.Edges[edge][0] = edge # 确保边的索引正确
|
|
|
for edge, _ in valid_edges[1:]: # 对于非最优边，设置其为不显示
|
|
|
d.Edges[edge][3] = 0
|
|
|
|
|
|
class Solve:
|
|
|
def __init__(self):
|
|
|
self.ans = [] # 记录答案
|
|
|
self.mutians = [] # 若有多个最短路，则保存在mutians中
|
|
|
self.way_sum = 0 # 记录遍历的路径数目
|
|
|
self.minn = float("inf") # 初始化最小值为正无穷
|
|
|
self.start = 0 # 起始点
|
|
|
self.end = 0 # 终点
|
|
|
self.mark = [] # 记录该点是否已经经过
|
|
|
self.user_cur = 0 # 记录用户所在点
|
|
|
self.cura = -1 # 记录用户选择的第一个点
|
|
|
self.curb = -1 # 记录用户选择的第二个点
|
|
|
self.con = 0 # 记录必经的节点数目
|
|
|
|
|
|
def node_greedy(self): # 贪心
|
|
|
global MODE, MARK_NODE
|
|
|
MARK_NODE = 0
|
|
|
MODE = 2
|
|
|
self.start = time.time() # 记录开始时间
|
|
|
self.ans.clear() # 初始化答案列表
|
|
|
E.edge_del_all(1) # 两点间仅保留距离最短路径
|
|
|
for edge in d.Edges: # 清空标记
|
|
|
edge[4] = False
|
|
|
i = 0 # 起始点
|
|
|
flag = [0] * len(d.Nodes) # 初始化已经过点
|
|
|
cur = i # 初始化起始点
|
|
|
flag[cur] = 1 # 将起始点标记为已经过
|
|
|
l = len(d.Nodes)
|
|
|
# print(l)
|
|
|
distances = [[math.inf for _ in range(l)] for _ in range(l)]
|
|
|
ladder_sum = 0
|
|
|
for j in range(1, l + 1):
|
|
|
ladder_sum += j - 1
|
|
|
for j in d.Edges: # 每一步选择当前最短的链接加到路径中去
|
|
|
i += 1
|
|
|
# print(j)
|
|
|
if i > ladder_sum:
|
|
|
break
|
|
|
# print(1)
|
|
|
else:
|
|
|
if j[6] < 99 and j[7] < 99:
|
|
|
distances[d.node_no(j[1])][d.node_no(j[2])] = j[6]
|
|
|
distances[d.node_no(j[2])][d.node_no(j[1])] = j[6]
|
|
|
ways = self.greedy(distances)
|
|
|
self.ans = ways.copy()
|
|
|
# 如果找到的路径不合法，则表示贪心法无法求解得到合法路径
|
|
|
# print(ways)
|
|
|
# for i in distances:
|
|
|
# print(i)
|
|
|
if len(ways) != l+1 :
|
|
|
tk.messagebox.askokcancel(title='结果', message='该图不存在贪心算法路径')
|
|
|
print(ways)
|
|
|
for way in range(len(ways) - 1): # 标记一条路径
|
|
|
d.Edges[G.way_node_edge(ways[way], ways[way + 1])][4] = True
|
|
|
G.draw()
|
|
|
self.ans.clear()
|
|
|
return -1
|
|
|
for way in range(len(ways) - 1): # 标记一条路径
|
|
|
d.Edges[G.way_node_edge(ways[way], ways[way + 1])][4] = True
|
|
|
# print(ways[len(ways) - 1], i)
|
|
|
# d.Edges[G.way_node_edge(ways[len(ways) - 1], i)][4] = True # 标记起点终点形成环线
|
|
|
# print(ways)
|
|
|
tk.messagebox.askokcancel(title='结果', message='贪心算法路径')
|
|
|
self.end = time.time() # 记录结束时间
|
|
|
G.draw()
|
|
|
def greedy(self,distances):
|
|
|
num_cities = len(distances)
|
|
|
visited = [False] * num_cities
|
|
|
path = [0] # 起始城市为0
|
|
|
visited[0] = True
|
|
|
|
|
|
for _ in range(num_cities - 1):
|
|
|
curr_city = path[-1]
|
|
|
min_distance = float('inf')
|
|
|
next_city = None
|
|
|
|
|
|
for city in range(num_cities):
|
|
|
if not visited[city] and distances[curr_city][city] < min_distance and distances[curr_city][city] != 0:
|
|
|
min_distance = distances[curr_city][city]
|
|
|
next_city = city
|
|
|
|
|
|
if next_city is not None:
|
|
|
path.append(next_city)
|
|
|
visited[next_city] = True
|
|
|
if distances[path[-1]][0] != np.inf:
|
|
|
path.append(0) # 回到起始城市形成闭合路径
|
|
|
# print(path)
|
|
|
return path
|
|
|
|
|
|
def tsp_backtracking(self,distances):
|
|
|
num_cities = len(distances)
|
|
|
path = [0] # 起始城市为0
|
|
|
visited = [False] * num_cities
|
|
|
visited[0] = True
|
|
|
min_distance = float('inf')
|
|
|
shortest_path = None
|
|
|
|
|
|
def backtrack(curr_city, curr_distance, visited, path):
|
|
|
nonlocal min_distance, shortest_path
|
|
|
if len(path) == num_cities:
|
|
|
# 到达所有城市，更新最短路径
|
|
|
if curr_distance + distances[curr_city][0] < min_distance:
|
|
|
min_distance = curr_distance + distances[curr_city][0]
|
|
|
shortest_path = path + [0]
|
|
|
else:
|
|
|
for next_city in range(num_cities):
|
|
|
if not visited[next_city]:
|
|
|
# 选择下一个未访问的城市
|
|
|
visited[next_city] = True
|
|
|
path.append(next_city)
|
|
|
new_distance = curr_distance + distances[curr_city][next_city]
|
|
|
# 剪枝条件：当前路径已经大于最短路径，不继续搜索
|
|
|
if new_distance < min_distance:
|
|
|
backtrack(next_city, new_distance, visited, path)
|
|
|
# 回溯
|
|
|
visited[next_city] = False
|
|
|
path.pop()
|
|
|
|
|
|
backtrack(0, 0, visited, path)
|
|
|
return shortest_path
|
|
|
def node_dfs(self): # 遍历 深度优先算法
|
|
|
global MODE, MARK_NODE
|
|
|
MARK_NODE = 0
|
|
|
MODE = 2
|
|
|
self.start = time.time() # 记录开始时间
|
|
|
self.ans.clear() # 初始化答案列表
|
|
|
E.edge_del_all(1) # 两点间仅保留距离最短路径
|
|
|
for edge in d.Edges: # 清空标记
|
|
|
edge[4] = False
|
|
|
i = 0 # 起始点
|
|
|
flag = [0] * len(d.Nodes) # 初始化已经过点
|
|
|
cur = i # 初始化起始点
|
|
|
flag[cur] = 1 # 将起始点标记为已经过
|
|
|
l = len(d.Nodes)
|
|
|
# print(l)
|
|
|
distances = [[math.inf for _ in range(l)] for _ in range(l)]
|
|
|
ladder_sum = 0
|
|
|
for j in range(1, l + 1):
|
|
|
ladder_sum += j - 1
|
|
|
for j in d.Edges: # 每一步选择当前最短的链接加到路径中去
|
|
|
i += 1
|
|
|
# print(j)
|
|
|
if i > ladder_sum:
|
|
|
break
|
|
|
# print(1)
|
|
|
else:
|
|
|
if j[6] < 99 and j[7] < 99:
|
|
|
distances[d.node_no(j[1])][d.node_no(j[2])] = j[6]
|
|
|
distances[d.node_no(j[2])][d.node_no(j[1])] = j[6]
|
|
|
cost, ways = self.dfs(distances)
|
|
|
self.ans = ways.copy()
|
|
|
if len(ways) != l + 1:
|
|
|
tk.messagebox.askokcancel(title='结果', message='该图不存在dfs路径')
|
|
|
print(ways)
|
|
|
for way in range(len(ways) - 1): # 标记一条路径
|
|
|
d.Edges[G.way_node_edge(ways[way], ways[way + 1])][4] = True
|
|
|
G.draw()
|
|
|
self.ans.clear()
|
|
|
return -1
|
|
|
for way in range(len(ways) - 1): # 标记一条路径
|
|
|
d.Edges[G.way_node_edge(ways[way], ways[way + 1])][4] = True
|
|
|
tk.messagebox.askokcancel(title='结果', message='dfs算法路径')
|
|
|
self.end = time.time() # 记录结束时间
|
|
|
G.draw()
|
|
|
|
|
|
def dfs_tsp(self,graph, start, current, path, visited, cost, min_cost, min_path):
|
|
|
if len(path) == len(graph) and graph[current][start] != np.inf:
|
|
|
path.append(start)
|
|
|
cost += graph[current][start]
|
|
|
if cost < min_cost[0]:
|
|
|
min_cost[0] = cost
|
|
|
min_path[0] = path.copy()
|
|
|
path.pop()
|
|
|
cost -= graph[current][start]
|
|
|
return
|
|
|
|
|
|
for next_node in range(len(graph)):
|
|
|
if graph[current][next_node] != np.inf and not visited[next_node]:
|
|
|
visited[next_node] = True
|
|
|
path.append(next_node)
|
|
|
cost += graph[current][next_node]
|
|
|
self.dfs_tsp(graph, start, next_node, path, visited, cost, min_cost, min_path)
|
|
|
visited[next_node] = False
|
|
|
path.pop()
|
|
|
cost -= graph[current][next_node]
|
|
|
|
|
|
def dfs(self,graph):
|
|
|
n = len(graph)
|
|
|
min_cost = [float('inf')]
|
|
|
min_path = [[]]
|
|
|
|
|
|
for start_node in range(n):
|
|
|
visited = [False] * n
|
|
|
path = [start_node]
|
|
|
cost = 0
|
|
|
visited[start_node] = True
|
|
|
self.dfs_tsp(graph, start_node, start_node, path, visited, cost, min_cost, min_path)
|
|
|
return min_cost[0], min_path[0]
|
|
|
|
|
|
def graph_check(self, a, b): # 检查A点B点是否互通
|
|
|
find = [] # 使用并查集来检测a，b点是否互通
|
|
|
for i in range(len(d.Nodes)): # 初始化并查集
|
|
|
find.append(i) # 使得find[i]=i
|
|
|
for edge in d.Edges: # 根据已有的边来更新并查集
|
|
|
if (edge[8] == 1 and edge[3] == 0):
|
|
|
continue
|
|
|
x = edge[1]
|
|
|
y = edge[2]
|
|
|
while not x == find[x]:
|
|
|
x = find[x]
|
|
|
while not y == find[y]:
|
|
|
y = find[y]
|
|
|
if x < y:
|
|
|
find[y] = x
|
|
|
else:
|
|
|
find[x] = y
|
|
|
x = a
|
|
|
y = b
|
|
|
while not x == find[x]: # 查询a点所在集合
|
|
|
x = find[x]
|
|
|
while not y == find[y]: # 查询b点所在集合
|
|
|
y = find[y]
|
|
|
if find[x] == find[y]: # 输出检查结果
|
|
|
messagebox.askokcancel(title='结果', message='节点 ' + str(a + 1) + '与节点 ' + str(b + 1) + '互通')
|
|
|
else:
|
|
|
messagebox.askokcancel(title='结果', message='节点 ' + str(a + 1) + '与节点 ' + str(b + 1) + '不互通')
|
|
|
|
|
|
def check(self): # 检查是否存在最短路
|
|
|
global MARK_NODE
|
|
|
MARK_NODE = 0
|
|
|
find = []
|
|
|
for i in range(len(d.Nodes)):
|
|
|
find.append(i)
|
|
|
for edge in d.Edges:
|
|
|
if edge[8] == 1 and edge[3] == 0:
|
|
|
continue
|
|
|
x = edge[1]
|
|
|
y = edge[2]
|
|
|
while not x == find[x]:
|
|
|
x = find[x]
|
|
|
while not y == find[y]:
|
|
|
y = find[y]
|
|
|
if x < y:
|
|
|
find[y] = x
|
|
|
else:
|
|
|
find[x] = y
|
|
|
flag = 1
|
|
|
for i in range(len(d.Nodes)):
|
|
|
if not find[i] == find[0]:
|
|
|
flag = 0
|
|
|
if flag:
|
|
|
tk.messagebox.askokcancel(title='结果', message='该图存在最短路')
|
|
|
else:
|
|
|
tk.messagebox.askokcancel(title='结果', message='该图不能完全互通')
|
|
|
|
|
|
def node_edge(n1, n2, no=1): # 根据点的编号找边的编号
|
|
|
if n1 > n2: # 为了防止充分编号，让n1小于n2
|
|
|
n1, n2 = n2, n1
|
|
|
for e in d.Edges: # 遍历所有路径，找到符合要求的返回
|
|
|
if e[1] == n1 and e[2] == n2 and e[8] == no:
|
|
|
return e[0]
|
|
|
return -1 # 若找不到，则返回-1
|
|
|
|
|
|
class Ways ():
|
|
|
def __init__(self):
|
|
|
self.user_way = [0] # 记录用户路径
|
|
|
self.user_cur = 0 # 记录用户所在点
|
|
|
self.user_flag = set() # 记录用户已经过的点
|
|
|
def auto_ways(self): # 标记用户路径
|
|
|
for w in d.Edges: # 清空路径标记
|
|
|
w[4] = 0
|
|
|
for N in d.Nodes: # 清空节点标记
|
|
|
N[2] = 0
|
|
|
for w in self.user_way: # 标记用户已选的点
|
|
|
d.Nodes[w][2] = 5
|
|
|
# 标记用户经过的路径
|
|
|
for w in range(len(self.user_way) - 1):
|
|
|
d.Edges[G.node_edge(self.user_way[w],self.user_way[w + 1])][4] = 1
|
|
|
# 如果已经访问所有节点，自动回到初始节点
|
|
|
if len(set(self.user_way)) == len(d.Nodes):
|
|
|
d.Edges[G.node_edge(self.user_way[len(self.user_way) - 1], 0)][4] = 1
|
|
|
G.draw() # 按照标记重新绘制图形
|
|
|
|
|
|
def check_user_best(self): # 检查用户路径是不是最佳路径
|
|
|
# global user_way
|
|
|
# global ans
|
|
|
s.node_dfs()
|
|
|
# 长度不一样肯定不匹配
|
|
|
if not len(self.user_way) == len(s.ans):
|
|
|
return -1,0
|
|
|
dis_user = 0
|
|
|
dis_ans = 0
|
|
|
# print(user_way)
|
|
|
# print(ans)
|
|
|
num = len(self.user_way)
|
|
|
for i in range(num - 1):
|
|
|
dis_user += d.Edges[G.node_edge(self.user_way[i]+1, self.user_way[i+1] + 1)][6]
|
|
|
dis_ans += d.Edges[G.way_node_edge(s.ans[i], s.ans[i + 1])][6]
|
|
|
return dis_ans, dis_user
|
|
|
# if dis_ans == dis_user: # 匹配成功，用户路径是最短路
|
|
|
# return 1
|
|
|
# # 匹配失败，不是最短路
|
|
|
# return 0
|
|
|
|
|
|
def show_best_ans(self, top, best, user):
|
|
|
lab1 = tk.Label(top, text="最短路径:", fg=BLACK, font=('微软雅黑', 20))
|
|
|
b_way = ""
|
|
|
for a in s.ans:
|
|
|
b_way += d.Nodes[a][1]
|
|
|
b_way += "->"
|
|
|
|
|
|
b_way += d.Nodes[0][1]
|
|
|
y0 = 0.05
|
|
|
lab2 = tk.Label(top, text=f"{b_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left')
|
|
|
lab1.place(relx=0.1, rely=0.50 + y0, width=150, height=30)
|
|
|
lab2.place(relx=0.4, rely=0.45 + y0, width=200, height=100)
|
|
|
|
|
|
lab2 = tk.Label(top, text=f"最佳路径总成本：{best}\n用户路径总成本：{user}", bg=BLUE, fg=BLACK,
|
|
|
font=('微软雅黑', 12), wraplength=200, justify='left')
|
|
|
lab2.place(relx=0.4, rely=0.7 + y0, width=200, height=100)
|
|
|
|
|
|
def show_BEST(self):
|
|
|
best, user = self.check_user_best() # 计算最优路径与用户路径的总花费
|
|
|
if best == user: # 如果最优路径与用户路径的总花费相等，则说明用户路径是最短路径
|
|
|
lab1 = tk.Label(frame_right, text="最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(relx=0.1, rely=0.8, width=80, height=30)
|
|
|
else: # 否则说明用户路径不是最短路径
|
|
|
self.servey_path_display()
|
|
|
def servey_path_display(self):
|
|
|
lab1 = tk.Label(frame_right, text="最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(relx=0.1, rely=0.75, width=80, height=30)
|
|
|
# self.auto_ways()
|
|
|
b_way = ""
|
|
|
for a in s.ans:
|
|
|
b_way += d.Nodes[a][1]
|
|
|
b_way += "->"
|
|
|
b_way += d.Nodes[0][1]
|
|
|
lab2 = tk.Label(frame_right, text=f"{b_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200,
|
|
|
justify='left')
|
|
|
lab2.place(relx=0.1, rely=0.8, width=200, height=100)
|
|
|
|
|
|
def check_user_greey(self): # 检查用户路径是不是贪心路径,不是的话返回错误点
|
|
|
s.node_greedy()# 计算贪心路径
|
|
|
if not len(self.user_way) == len(s.ans):# 路径长度不一样肯定不匹配，直接返回
|
|
|
self.auto_ways()
|
|
|
return
|
|
|
num = len(self.user_way)
|
|
|
for i in range(num):#逐个节点进行匹配
|
|
|
if not self.user_way[i] == s.ans[i]:# 若第i位匹配失败则返回i
|
|
|
return i
|
|
|
return -1 #-1表示是贪心路径
|
|
|
|
|
|
|
|
|
def show_greddy_ans(self, top):
|
|
|
lab1 = tk.Label(top, text="贪心路径:", fg=BLACK, font=('微软雅黑', 20))
|
|
|
b_way = ""
|
|
|
for a in s.ans:
|
|
|
b_way += d.Nodes[a][1]
|
|
|
b_way += "->"
|
|
|
b_way += d.Nodes[0][1]
|
|
|
y0 = 0.05
|
|
|
lab2 = tk.Label(top, text=f"{b_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left')
|
|
|
lab1.place(relx=0.1, rely=0.50 + y0, width=150, height=30)
|
|
|
lab2.place(relx=0.4, rely=0.45 + y0, width=200, height=100)
|
|
|
|
|
|
def show_GREDDY(self):
|
|
|
top = Toplevel(root, width = 500, height = 500)
|
|
|
top.title('判断路径是否为贪心路径')# 新建一个窗口来显示判断路径是否为贪心路径的结果
|
|
|
lab1 = tk.Label(top, text="用户路径:", fg=BLACK, font=('微软雅黑', 20))
|
|
|
u_way = ""# 显示用户路径
|
|
|
for a in self.user_way:
|
|
|
u_way += d.Nodes[a][1]
|
|
|
u_way += "->"
|
|
|
u_way += d.Nodes[0][1]
|
|
|
# print(u_way)
|
|
|
y0 = 0.05
|
|
|
lab2 = tk.Label(top, text=f"{u_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left')
|
|
|
lab1.place(relx=0.1, rely=0.10 + y0, width=150, height=30)
|
|
|
lab2.place(relx=0.4, rely=0.05 + y0, width=200, height=100)
|
|
|
# 逐个节点比较用户路径是否为贪心路径
|
|
|
g = self.check_user_greey()
|
|
|
print(g)
|
|
|
print(self.user_way)
|
|
|
if g == -1:#如果用户路径是贪心路径则显示
|
|
|
result = '用户路径是贪心路径'
|
|
|
elif g:
|
|
|
result = '用户路径不是贪心路径'
|
|
|
result2 = '用户路径: ' + u_way
|
|
|
if len(s.ans) == 7:
|
|
|
g_way = ''
|
|
|
for a in s.ans:
|
|
|
g_way += d.Nodes[a][1]
|
|
|
g_way += "->"
|
|
|
g_way += d.Nodes[0][1]
|
|
|
result2 += '\n贪心路径：' + g_way
|
|
|
else:
|
|
|
result2 += '\n贪心路径不存在'
|
|
|
lab = tk.Label(top, text=result2, bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left')
|
|
|
lab.place(relx=0.1, rely=0.5 + y0, width=250, height=100)
|
|
|
else:# 若用户路径不是贪心路径，则显示在第几步时选择出错，并将该次选择的正确选择与用户实际选择显示出来
|
|
|
result = '用户路径不是贪心路径'
|
|
|
result2 = '用户路径：'+u_way
|
|
|
if len(s.ans) == 7:
|
|
|
g_way = ''
|
|
|
for a in s.ans:
|
|
|
g_way += d.Nodes[a][1]
|
|
|
g_way += "->"
|
|
|
g_way += d.Nodes[0][1]
|
|
|
result2 += '\n贪心路径：' + g_way
|
|
|
else:
|
|
|
result2 += '\n贪心路径不存在'
|
|
|
lab = tk.Label(top, text=result2, bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left')
|
|
|
lab.place(relx=0.1, rely=0.5 + y0, width=250, height=100)
|
|
|
lab = tk.Label(top, text=result, bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=250, justify='left')
|
|
|
lab.place(relx=0.1, rely=0.3 + y0, width=200, height=50)
|
|
|
self.auto_ways()#将结果输出到输出框
|
|
|
|
|
|
# 对用户路径进行标记与记录
|
|
|
def way_route_markings(self):
|
|
|
global MARK_NODE
|
|
|
MARK_NODE = 0
|
|
|
# E.newedge_del_all(1)
|
|
|
for w in frame_right.winfo_children():
|
|
|
w.destroy()
|
|
|
# 清除右侧组件
|
|
|
self.user_way = [0]
|
|
|
lab = tk.Label(frame_right, text="路径操作", bg=RED, fg=BLACK, font=('微软雅黑', 20))
|
|
|
lab.place(relx=0.18, rely=0.02, width=200, height=30)
|
|
|
y0 = 0.1
|
|
|
global entry1,entry2,default_value
|
|
|
# 定义默认值变量
|
|
|
default_value = tk.StringVar()
|
|
|
default_value.set(self.user_way[-1]+1)
|
|
|
laba1 = tk.Label(frame_right, text="当前节点:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
laba1.place(relx=0.00, rely=0.02 + y0, width=80, height=30)
|
|
|
# 创建第一个输入框
|
|
|
entry1 = tk.Entry(frame_right, textvariable=default_value)
|
|
|
entry1.place(relx=0.3, rely=0.02 + y0, width=50, height=30)
|
|
|
labb1 = tk.Label(frame_right, text="当前下一节点:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
labb1.place(relx=0.48, rely=0.02 + y0, width=100, height=30)
|
|
|
# 创建第二个输入框
|
|
|
entry2 = tk.Entry(frame_right)
|
|
|
entry2.place(relx=0.82, rely=0.02 + y0, width=50, height=30)
|
|
|
|
|
|
labb3 = tk.Label(frame_right, text="是否进行连接:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
labb3.place(relx=0.2, rely=0.08 + y0, width=120, height=30)
|
|
|
|
|
|
button = tk.Button(frame_right, text="确认", command=lambda: self.extract_values())
|
|
|
button.place(relx=0.7, rely=0.08 + y0, width=80, height=30)
|
|
|
button2 = tk.Button(frame_right, text="撤销", command=lambda: self.revoke())
|
|
|
button2.place(relx=0.01, rely=0.18 + y0, width=140, height=30)
|
|
|
button3 = tk.Button(frame_right, text="清除路径", command=lambda: self.clear_all_paths())
|
|
|
button3.place(relx=0.52, rely=0.18 + y0, width=140, height=30)
|
|
|
button4 = tk.Button(frame_right, text="判断路径是否为贪心路径", command=lambda: self.greedy_path())
|
|
|
button4.place(relx=0.01, rely=0.26 + y0, width=290, height=30)
|
|
|
button5 = tk.Button(frame_right, text="判断路径是否为最短路径", command=lambda: self.shortest_path())
|
|
|
button5.place(relx=0.01, rely=0.33 + y0, width=290, height=30)
|
|
|
|
|
|
self.user_path_display()
|
|
|
def extract_values(self):
|
|
|
global entry1, entry2, default_value
|
|
|
value1 = entry1.get() # 获取第一个输入框的值
|
|
|
value2 = entry2.get() # 获取第二个输入框的值
|
|
|
try:
|
|
|
value1 = int(value1) # 将值转换为整数
|
|
|
value2 = int(value2) # 将值转换为整数
|
|
|
print("值1:", value1)
|
|
|
print("值2:", value2)
|
|
|
# 判断两点是否连接
|
|
|
if abs(value2) > 10 and abs(value1) > 10:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请重新输入正确的编号！')
|
|
|
return
|
|
|
else:
|
|
|
E = 0
|
|
|
if value1 < value2:
|
|
|
str_route = f'{value1}-{value2}'
|
|
|
else:
|
|
|
str_route = f'{value2}-{value1}'
|
|
|
for item in d.Edges:
|
|
|
if str_route == item[5]:
|
|
|
if item[6] < 100 and item[7] < 100:
|
|
|
if d.Edges[G.node_edge(value1-1, value2-1)][4]:
|
|
|
E = 2
|
|
|
tk.messagebox.askokcancel(title='错误', message='城市已连接！')
|
|
|
else:
|
|
|
if self.user_way[-1] == (value1-1):
|
|
|
E = 1
|
|
|
global MODE
|
|
|
MODE = 1
|
|
|
self.user_way.append(value2 - 1)
|
|
|
default_value.set(value2)
|
|
|
d.Edges[G.node_edge(value1-1, value2-1)][4] = True
|
|
|
entry1.config(textvariable=default_value) # 更新entry1的默认值
|
|
|
entry2.delete(0, tk.END)
|
|
|
else:
|
|
|
E = 3
|
|
|
tk.messagebox.askokcancel(title='错误', message='未连贯！')
|
|
|
break
|
|
|
print(E)
|
|
|
if E == 1:
|
|
|
G.draw()
|
|
|
self.user_path_display()
|
|
|
elif E == 0:
|
|
|
tk.messagebox.askokcancel(title='错误', message='城市未连接！')
|
|
|
except ValueError:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！')
|
|
|
|
|
|
def extract_ligature(self, n1, n2):
|
|
|
no = G.way_node_edge(n1, n2)
|
|
|
if d.Edges[no][4]:
|
|
|
tk.messagebox.askokcancel(title='错误', message='城市已连接！')
|
|
|
else:
|
|
|
if self.user_way[-1] == int(d.Nodes[n1][1])-1:
|
|
|
global MODE
|
|
|
MODE = 1
|
|
|
self.user_way.append(int(d.Nodes[n2][1]) - 1)
|
|
|
d.Edges[no][4] = True
|
|
|
else:
|
|
|
tk.messagebox.askokcancel(title='错误', message='未连贯！')
|
|
|
G.draw()
|
|
|
self.user_path_display()
|
|
|
def revoke(self):
|
|
|
try:
|
|
|
if len(self.user_way) > 1:
|
|
|
value1 = int(self.user_way[-1]) # 将值转换为整数
|
|
|
value2 = int(self.user_way[-2]) # 将值转换为整数
|
|
|
if value1 < value2:
|
|
|
str_route = f'{value1+1}-{value2+1}'
|
|
|
else:
|
|
|
str_route = f'{value2+1}-{value1+1}'
|
|
|
# print(str_route)
|
|
|
for item in d.Edges:
|
|
|
# print(item)
|
|
|
if str_route == item[5]:
|
|
|
# print(item)
|
|
|
global MODE
|
|
|
global entry1, default_value
|
|
|
MODE = 1
|
|
|
self.user_way.pop()
|
|
|
print(self.user_way)
|
|
|
d.Edges[G.node_edge(value1, value2)][4] = False
|
|
|
default_value.set(value2+1)
|
|
|
entry1.config(textvariable=default_value) # 更新entry1的默认值
|
|
|
break
|
|
|
G.draw()
|
|
|
self.user_path_display()
|
|
|
else:
|
|
|
tk.messagebox.askokcancel(title='提示', message='未进行路径建设！')
|
|
|
except ValueError:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！')
|
|
|
|
|
|
def clear_all_paths(self):
|
|
|
try:
|
|
|
if len(self.user_way) > 1:
|
|
|
for i in range(len(self.user_way)-1):
|
|
|
value1 = int(self.user_way[-1]) # 将值转换为整数
|
|
|
value2 = int(self.user_way[-2]) # 将值转换为整数
|
|
|
if value1 < value2:
|
|
|
str_route = f'{value1 + 1}-{value2 + 1}'
|
|
|
else:
|
|
|
str_route = f'{value2 + 1}-{value1 + 1}'
|
|
|
# print(str_route)
|
|
|
for item in d.Edges:
|
|
|
# print(item)
|
|
|
if str_route == item[5]:
|
|
|
# print(item)
|
|
|
global MODE
|
|
|
global entry1, default_value
|
|
|
MODE = 3
|
|
|
self.user_way.pop()
|
|
|
print(self.user_way)
|
|
|
d.Edges[G.node_edge(value1, value2)][4] = False
|
|
|
default_value.set(value2 + 1)
|
|
|
entry1.config(textvariable=default_value) # 更新entry1的默认值
|
|
|
break
|
|
|
else:
|
|
|
tk.messagebox.askokcancel(title='提示', message='未进行路径建设！')
|
|
|
for i in range(len(d.Edges)):
|
|
|
d.Edges[i][4] = False
|
|
|
G.draw()
|
|
|
self.user_path_display()
|
|
|
except ValueError:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！')
|
|
|
|
|
|
def greedy_path(self):
|
|
|
g = self.check_user_greey()
|
|
|
# print(g)
|
|
|
# print(self.user_way)
|
|
|
if g == -1: # 如果用户路径是贪心路径则显示
|
|
|
lab1 = tk.Label(frame_right, text="用户路径是贪心路径", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(relx=0.1, rely=0.8, width=180, height=30)
|
|
|
elif g:
|
|
|
self.servey_greedy_path()
|
|
|
def servey_greedy_path(self):
|
|
|
lab1 = tk.Label(frame_right, text="最短路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(relx=0.1, rely=0.75, width=80, height=30)
|
|
|
# self.auto_ways()
|
|
|
g_way = ''
|
|
|
for a in s.ans:
|
|
|
g_way += d.Nodes[a][1]
|
|
|
g_way += "->"
|
|
|
g_way += d.Nodes[0][1]
|
|
|
lab2 = tk.Label(frame_right, text=f"{g_way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200,
|
|
|
justify='left')
|
|
|
lab2.place(relx=0.1, rely=0.8, width=200, height=100)
|
|
|
|
|
|
def shortest_path(self):
|
|
|
best, user = self.check_user_best() # 计算最优路径与用户路径的总花费
|
|
|
if best == user: # 如果最优路径与用户路径的总花费相等，则说明用户路径是最短路径
|
|
|
lab1 = tk.Label(frame_right, text="用户路径是最短路径", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(relx=0.1, rely=0.8, width=180, height=30)
|
|
|
else: # 否则说明用户路径不是最短路径
|
|
|
self.servey_path_display()
|
|
|
|
|
|
# 用户路径展示
|
|
|
def user_path_display(self):
|
|
|
lab1 = tk.Label(frame_right, text="用户路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(relx=0.1, rely=0.55, width=80, height=30)
|
|
|
# self.auto_ways()
|
|
|
way = ""
|
|
|
# d_way = []
|
|
|
# for i in d.Nodes:
|
|
|
# d_way.append(i[1])
|
|
|
for i in range(len(self.user_way)):
|
|
|
if len(self.user_way)-i > 1:
|
|
|
way += str(self.user_way[i]+1)
|
|
|
way += "->"
|
|
|
else:
|
|
|
way += str(self.user_way[i]+1)
|
|
|
lab2 = tk.Label(frame_right, text=f"{way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200,
|
|
|
justify='left')
|
|
|
lab2.place(relx=0.1, rely=0.6, width=200, height=100)
|
|
|
|
|
|
def way_operate(self):
|
|
|
global MARK_NODE
|
|
|
MARK_NODE = 0
|
|
|
# E.newedge_del_all(1)
|
|
|
for w in frame_right.winfo_children():
|
|
|
w.destroy()
|
|
|
# 清除右侧组件
|
|
|
self.user_way = [0]
|
|
|
lab = tk.Label(frame_right, text="路径增加与删除", bg=RED, fg=BLACK, font=('微软雅黑', 20))
|
|
|
lab.place(relx=0.18, rely=0.02, width=200, height=30)
|
|
|
y0 = 0.1
|
|
|
label1 = tk.Label(frame_right, text="节点1:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
label1.place(relx=0.00, rely=0.02 + y0, width=80, height=30)
|
|
|
global entry3, entry4
|
|
|
# 创建第一个输入框
|
|
|
entry3 = tk.Entry(frame_right)
|
|
|
entry3.place(relx=0.3, rely=0.02 + y0, width=50, height=30)
|
|
|
|
|
|
label2 = tk.Label(frame_right, text="节点2:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
label2.place(relx=0.48, rely=0.02 + y0, width=100, height=30)
|
|
|
# 创建第二个输入框
|
|
|
entry4 = tk.Entry(frame_right)
|
|
|
entry4.place(relx=0.82, rely=0.02 + y0, width=50, height=30)
|
|
|
|
|
|
label3 = tk.Label(frame_right, text="是否进行两节点之间操作:", bg=RED, fg=BLACK, font=('微软雅黑', 14))
|
|
|
label3.place(relx=0.1, rely=0.1 + y0, width=240, height=30)
|
|
|
|
|
|
button = tk.Button(frame_right, text="线路增加", command=lambda: self.way_add())
|
|
|
button.place(relx=0.25, rely=0.18 + y0, width=160, height=30)
|
|
|
button2 = tk.Button(frame_right, text="线路修改", command=lambda: self.way_change())
|
|
|
button2.place(relx=0.25, rely=0.28 + y0, width=160, height=30)
|
|
|
button3 = tk.Button(frame_right, text="线路删除", command=lambda: self.way_delete())
|
|
|
button3.place(relx=0.25, rely=0.38 + y0, width=160, height=30)
|
|
|
|
|
|
def way_add(self):
|
|
|
global entry3, entry4
|
|
|
value1 = entry3.get() # 获取第一个输入框的值
|
|
|
value2 = entry4.get() # 获取第二个输入框的值
|
|
|
try:
|
|
|
value1 = int(value1) # 将值转换为整数
|
|
|
value2 = int(value2) # 将值转换为整数
|
|
|
print("值1:", value1)
|
|
|
print("值2:", value2)
|
|
|
ways_list = [int(node[1]) for node in d.Nodes]
|
|
|
# 判断两点是否连接
|
|
|
if abs(value2) > 10 and abs(value1) > 10:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请重新输入正确的编号！')
|
|
|
return
|
|
|
else:
|
|
|
if value1 < value2:
|
|
|
str_route = f'{value1}-{value2}'
|
|
|
else:
|
|
|
str_route = f'{value2}-{value1}'
|
|
|
if d.drop.count(ways_list.index(value1)) > 4 or d.drop.count(ways_list.index(value2)) > 4:
|
|
|
print(d.drop)
|
|
|
tk.messagebox.askokcancel(title='提醒', message='当前节点已经到达最大连接数！')
|
|
|
return
|
|
|
no = 0
|
|
|
for item in d.Edges:
|
|
|
if str_route == item[5]:
|
|
|
no = G.node_edge(value1 - 1, value2 - 1)
|
|
|
if d.Edges[no][3] == 1:
|
|
|
tk.messagebox.askokcancel(title='提醒', message='当前路线已存在！')
|
|
|
return
|
|
|
top = creat_window(str_route+'路径参数配置') # 创建弹出窗口
|
|
|
distance_entry = create_input_box(top, "路程/公里：（1-99）", 101) # 创建一个输入框，获取卷积核大小
|
|
|
time_entry = create_input_box(top, "时间/h：（1-99）", 101) # 创建一个输入框，获取卷积步长
|
|
|
|
|
|
def get_input(): # 创建
|
|
|
# 获取输入框的内容
|
|
|
try:
|
|
|
result1 = int(distance_entry.get())
|
|
|
result2 = int(time_entry.get())
|
|
|
print(result1,result2)
|
|
|
if 100 > result1 > 0 and 0 < result2 < 100:
|
|
|
d.Edges[no][3] = 1
|
|
|
d.Edges[no][6] = result1
|
|
|
d.Edges[no][7] = result2
|
|
|
top.destroy() # 关闭窗口
|
|
|
G.draw()
|
|
|
# for i in d.Edges:
|
|
|
# print(i)
|
|
|
else:
|
|
|
tk.messagebox.askokcancel(title='错误', message='路程与时间范围错误！')
|
|
|
except ValueError:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请输入正确的路程与时间！')
|
|
|
button = tk.Button(top, text="获取信息", command=get_input)
|
|
|
button.pack()
|
|
|
except ValueError:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！')
|
|
|
|
|
|
def way_change(self):
|
|
|
global entry3, entry4
|
|
|
value1 = entry3.get() # 获取第一个输入框的值
|
|
|
value2 = entry4.get() # 获取第二个输入框的值
|
|
|
try:
|
|
|
value1 = int(value1) # 将值转换为整数
|
|
|
value2 = int(value2) # 将值转换为整数
|
|
|
print("值1:", value1)
|
|
|
print("值2:", value2)
|
|
|
ways_list = [int(node[1]) for node in d.Nodes]
|
|
|
# 判断两点是否连接
|
|
|
if abs(value2) > 10 and abs(value1) > 10:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请重新输入正确的编号！')
|
|
|
return
|
|
|
else:
|
|
|
if value1 < value2:
|
|
|
str_route = f'{value1}-{value2}'
|
|
|
else:
|
|
|
str_route = f'{value2}-{value1}'
|
|
|
no = 0
|
|
|
for item in d.Edges:
|
|
|
if str_route == item[5]:
|
|
|
no = G.node_edge(value1 - 1, value2 - 1)
|
|
|
if d.Edges[no][3] == 0:
|
|
|
tk.messagebox.askokcancel(title='提醒', message='当前路线不存在！')
|
|
|
return
|
|
|
top = creat_window(str_route + '路径参数修改') # 创建弹出窗口
|
|
|
distance_entry = create_input_box(top, "路程/公里：（1-99）", d.Edges[no][6]) # 创建一个输入框，获取卷积核大小
|
|
|
time_entry = create_input_box(top, "时间/h：（1-99）", d.Edges[no][7]) # 创建一个输入框，获取卷积步长
|
|
|
|
|
|
def get_input(): # 创建
|
|
|
# 获取输入框的内容
|
|
|
try:
|
|
|
result1 = int(distance_entry.get())
|
|
|
result2 = int(time_entry.get())
|
|
|
print(result1, result2)
|
|
|
if 100 > result1 > 0 and 0 < result2 < 100:
|
|
|
d.Edges[no][6] = result1
|
|
|
d.Edges[no][7] = result2
|
|
|
top.destroy() # 关闭窗口
|
|
|
G.draw()
|
|
|
# for i in d.Edges:
|
|
|
# print(i)
|
|
|
else:
|
|
|
tk.messagebox.askokcancel(title='错误', message='路程与时间范围错误！')
|
|
|
except ValueError:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请输入正确的路程与时间！')
|
|
|
button = tk.Button(top, text="获取信息", command=get_input)
|
|
|
button.pack()
|
|
|
except ValueError:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！')
|
|
|
|
|
|
def way_delete(self):
|
|
|
global entry3, entry4
|
|
|
value1 = entry3.get() # 获取第一个输入框的值
|
|
|
value2 = entry4.get() # 获取第二个输入框的值
|
|
|
try:
|
|
|
value1 = int(value1) # 将值转换为整数
|
|
|
value2 = int(value2) # 将值转换为整数
|
|
|
print("值1:", value1)
|
|
|
print("值2:", value2)
|
|
|
ways_list = [int(node[1]) for node in d.Nodes]
|
|
|
# 判断两点是否连接
|
|
|
if abs(value2) > 10 and abs(value1) > 10:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请重新输入正确的编号！')
|
|
|
return
|
|
|
else:
|
|
|
if value1 < value2:
|
|
|
str_route = f'{value1}-{value2}'
|
|
|
else:
|
|
|
str_route = f'{value2}-{value1}'
|
|
|
no = 0
|
|
|
for item in d.Edges:
|
|
|
if str_route == item[5]:
|
|
|
no = G.node_edge(value1 - 1, value2 - 1)
|
|
|
if d.Edges[no][3] == 0:
|
|
|
tk.messagebox.askokcancel(title='提醒', message='当前路线不存在！')
|
|
|
return
|
|
|
d.Edges[no][3] = 0
|
|
|
d.Edges[no][6] = 111
|
|
|
d.Edges[no][7] = 111
|
|
|
G.draw()
|
|
|
except ValueError:
|
|
|
tk.messagebox.askokcancel(title='错误', message='请输入正确的城市编号！')
|
|
|
|
|
|
|
|
|
class Node:
|
|
|
# 标记节点按钮
|
|
|
def node_mark_display(self):
|
|
|
global MARK_NODE,Specify_Nodes
|
|
|
W.user_way = [0]
|
|
|
MARK_NODE = 1
|
|
|
for w in frame_right.winfo_children():
|
|
|
w.destroy()
|
|
|
# 清除右侧组件
|
|
|
curx = -1
|
|
|
y0 = 0.1
|
|
|
for i in d.Nodes:
|
|
|
if i[2] == 1:
|
|
|
curx = i[0]
|
|
|
lab = tk.Label(frame_right, text="节点操作", bg=RED, fg=BLACK, font=('微软雅黑', 20))
|
|
|
lab.place(relx=0.18, rely=0.02, width=200, height=30)
|
|
|
lab1 = tk.Label(frame_right, text=f"当前共有{len(d.Nodes)}个节点", bg=RED, fg=BLACK, font=('微软雅黑', 15))
|
|
|
lab1.place(relx=0.1, rely=0.0 + y0, width=200, height=30)
|
|
|
lab1 = tk.Label(frame_right, text="当前节点:", bg=RED, fg=BLACK, font=('微软雅黑', 12))
|
|
|
if curx == -1:
|
|
|
text = "未选择"
|
|
|
else:
|
|
|
text = f"{d.Nodes[curx][1]}"
|
|
|
Specify_Nodes = str(d.Nodes[curx][1])
|
|
|
lab2 = tk.Label(frame_right, text=text, bg=BLUE, fg=BLACK, font=('微软雅黑', 12))
|
|
|
lab1.place(relx=0.1, rely=0.05 + y0, width=80, height=30)
|
|
|
lab2.place(relx=0.4, rely=0.05 + y0, width=80, height=30)
|
|
|
B = tk.Button(frame_right, text="删除当前节点", command=lambda: self.node_del_exact())
|
|
|
B.place(relx=0.1, rely=0.1 + y0, width=150, height=30)
|
|
|
B = tk.Button(frame_right, text="增加一个节点", command=lambda: self.node_add())
|
|
|
B.place(relx=0.1, rely=0.25 + y0, width=150, height=30)
|
|
|
B = tk.Button(frame_right, text="减少一个节点", command=lambda: self.node_del())
|
|
|
B.place(relx=0.1, rely=0.3 + y0, width=150, height=30)
|
|
|
|
|
|
def node_add(self):
|
|
|
global d,Edges_list
|
|
|
for i in range(len(d.Edges)):
|
|
|
d.Edges[i][4] = False
|
|
|
Edges_list = []
|
|
|
Edges_list = d.Edges
|
|
|
# print(len(Edges_list))
|
|
|
# 增加一个节点
|
|
|
nodes = len(d.Nodes) + 1
|
|
|
# 如果节点数目大于五，则将连接详细信息改为不显示
|
|
|
if nodes > 5:
|
|
|
d.edgeinfo = 0
|
|
|
if nodes > 10:
|
|
|
tk.messagebox.askokcancel(title='错误', message='已达到最大节点')
|
|
|
return
|
|
|
d = Data(1, nodes)
|
|
|
# for i in d.Edges:
|
|
|
# print(i)
|
|
|
G.draw()
|
|
|
self.node_mark_display()
|
|
|
|
|
|
|
|
|
def node_del(self):
|
|
|
global d,Edges_list
|
|
|
for i in range(len(d.Edges)):
|
|
|
d.Edges[i][4] = False
|
|
|
Edges_list = []
|
|
|
Edges_list = d.Edges
|
|
|
# print(len(Edges_list))
|
|
|
if d.nodes_num <= 2:
|
|
|
tk.messagebox.askokcancel(title='错误', message='节点过少')
|
|
|
return
|
|
|
nodes = len(d.Nodes) - 1
|
|
|
if nodes < 6:
|
|
|
d.edgeinfo = 1
|
|
|
d = Data(2, nodes)
|
|
|
# for i in d.Edges:
|
|
|
# print(i)
|
|
|
G.draw()
|
|
|
self.node_mark_display()
|
|
|
|
|
|
def node_del_exact(self):
|
|
|
global d,Edges_list
|
|
|
for i in range(len(d.Edges)):
|
|
|
d.Edges[i][4] = False
|
|
|
Edges_list = d.Edges
|
|
|
if len(Specify_Nodes) == 3:
|
|
|
tk.messagebox.askokcancel(title='错误', message='未选择节点')
|
|
|
return
|
|
|
if d.nodes_num <= 2:# 若删除节点以后节点过少，则直接返回并警告
|
|
|
tk.messagebox.askokcancel(title='错误', message='节点过少')
|
|
|
return
|
|
|
nodes = len(d.Nodes) - 1
|
|
|
if nodes < 6:
|
|
|
d.edgeinfo = 1
|
|
|
d = Data(3, nodes)
|
|
|
# for i in d.Edges:
|
|
|
# print(i)
|
|
|
G.draw()
|
|
|
self.node_mark_display()
|
|
|
|
|
|
|
|
|
def refresh():
|
|
|
node = random.randint(4, 10)
|
|
|
global d, MODE,MARK_NODE
|
|
|
MARK_NODE = 0
|
|
|
MODE = 0
|
|
|
d = Data(0, node)
|
|
|
print(node)
|
|
|
W.user_way=[0]
|
|
|
G.draw()
|
|
|
W.way_route_markings()
|
|
|
def graph_init():
|
|
|
global MODE,MARK_NODE
|
|
|
MARK_NODE = 0
|
|
|
MODE = 0
|
|
|
G.draw()
|
|
|
W.way_route_markings()
|
|
|
|
|
|
def empty():
|
|
|
global MARK_NODE
|
|
|
MARK_NODE = 0
|
|
|
G.delete_all()
|
|
|
|
|
|
def auto_opera_mu(menu: tk.Menu):
|
|
|
"""TSP问题自动生成与自动求解相关"""
|
|
|
menu_node = Menu(menu, tearoff=False)
|
|
|
menu_node.add_command(label="自动随机产生一个TSP问题", command=lambda: graph_init())
|
|
|
menu_node.add_command(label="重新生成", command=lambda: refresh())
|
|
|
menu_node.add_command(label="清空", command=lambda: empty())
|
|
|
menu_node.add_command(label="自动求解最优路径-dfs遍历", command=lambda: s.node_dfs())
|
|
|
menu_node.add_command(label="自动求解优化路径-贪心", command=lambda: s.node_greedy())
|
|
|
menu_node.add_command(label="检查是否存在路径", command=lambda: s.check())
|
|
|
# 在主目录菜单上新增"文件"选项，并通过menu参数与下拉菜单绑定
|
|
|
menu.add_cascade(label="TSP问题自动生成与自动求解相关", menu=menu_node)
|
|
|
|
|
|
# 创建弹出窗口
|
|
|
def creat_window(title):
|
|
|
top = tk.Toplevel(root)
|
|
|
top.geometry("300x350")
|
|
|
top.title(title)
|
|
|
return top
|
|
|
|
|
|
# 输入框
|
|
|
def create_input_box(top, text, value):
|
|
|
box_label = tk.Label(top, text=text)
|
|
|
box_label.pack(padx=10, pady=10)
|
|
|
box_size = tk.IntVar(top, value=value) # 创建一个IntVar对象，并设置默认值为3
|
|
|
box_size_entry = tk.Entry(top, textvariable=box_size) # 关联IntVar对象
|
|
|
box_size_entry.pack(padx=20, pady=20)
|
|
|
return box_size_entry
|
|
|
|
|
|
def dir2(x, y): # 计算两点间距离
|
|
|
return (x[0] - y[0]) * (x[0] - y[0]) + (x[1] - y[1]) * (x[1] - y[1])
|
|
|
|
|
|
def left1(event):
|
|
|
# 查找鼠标左键按下时位置是否在某个节点内
|
|
|
n = -1
|
|
|
for node in d.Nodes:
|
|
|
if dir2([event.x, event.y], [node[3][0], node[3][1]]) < 20 * 20:
|
|
|
n = node[0]
|
|
|
|
|
|
# n为点击的节点，若没有则为-1
|
|
|
m = mode.get() # 查看现在操作类型
|
|
|
if m == 1 and not n == -1:
|
|
|
# 节点操作
|
|
|
# N.node_mark(n)
|
|
|
if n >= len(d.Nodes):
|
|
|
# 弹出对话框
|
|
|
tk.messagebox.askokcancel(title='错误', message='该节点不存在')
|
|
|
return
|
|
|
for node in d.Nodes:
|
|
|
if node[0] == n:
|
|
|
node[2] = 1
|
|
|
else:
|
|
|
node[2] = 0
|
|
|
G.draw()
|
|
|
if MARK_NODE == 1:
|
|
|
N.node_mark_display()
|
|
|
elif MARK_NODE == 2:
|
|
|
pass
|
|
|
print(n)
|
|
|
def node_opera_mu(menu: tk.Menu):
|
|
|
"""节点操作"""
|
|
|
menu_node = Menu(menu, tearoff=False)
|
|
|
menu_node.add_command(label="添加一个节点", command=lambda: N.node_add())
|
|
|
menu_node.add_command(label="删除一个节点", command=lambda: N.node_del())
|
|
|
menu_node.add_command(label="选择一个节点", command=lambda: N.node_mark_display())
|
|
|
# 在主目录菜单上新增"文件"选项，并通过menu参数与下拉菜单绑定
|
|
|
menu.add_cascade(label="节点操作", menu=menu_node)
|
|
|
|
|
|
def path_opera_mu(menu: tk.Menu):
|
|
|
"""路径操作"""
|
|
|
menu_node = Menu(menu, tearoff=False)
|
|
|
menu_node.add_command(label="路径选择", command=lambda: W.way_route_markings())
|
|
|
menu_node.add_command(label="路径修改", command=lambda: W.way_operate())
|
|
|
# 在主目录菜单上新增"文件"选项，并通过menu参数与下拉菜单绑定
|
|
|
menu.add_cascade(label="路径操作", menu=menu_node, )
|
|
|
|
|
|
if __name__ == '__main__':
|
|
|
G = Graph()
|
|
|
mode = tk.IntVar(value=1)
|
|
|
main_menu = tk.Menu(root)
|
|
|
root.config(menu=main_menu)
|
|
|
cv.bind('<Button-1>', left1)
|
|
|
E = Edge()
|
|
|
W = Ways()
|
|
|
s = Solve()
|
|
|
N = Node()
|
|
|
auto_opera_mu(main_menu)
|
|
|
node_opera_mu(main_menu)
|
|
|
path_opera_mu(main_menu)
|
|
|
W.way_route_markings()
|
|
|
root.mainloop()
|
