# -*- encoding: utf-8 -*- from head import * from NODE import * from SOLVE import * solve = Solve() N = Node() class Ways: def __init__(self): self.user_way = []#记录用户路径 self.user_cur = 0#记录用户所在点 self.user_flag = set()#记录用户已经过的点 def clear(self): self.user_flag.clear() self.user_way.clear() self.user_cur = 0 self.auto_ways() def check_user_best2(self): # 检查用户路径是不是最佳路径 solve.node_dfs()#遍历计算最优路径 if not len(self.user_way) == len(solve.ans):# 节点个数不一样肯定不匹配 return 0 dis_user = 0 dis_ans = 0 num = len(self.user_way) for i in range(num - 1):#计算两条路径的长度 dis_user += d.Edges[G.node_edge(self.user_way[i], self.user_way[i + 1])][6] dis_ans += d.Edges[G.node_edge(solve.ans[i], solve.ans[i + 1])][6] if dis_ans == dis_user: # 用户路径长度与最短路径长度相同，用户路径是最短路 return 1 return 0# 匹配失败，不是最短路 def check_user_best(self): # 检查用户路径是不是最佳路径 # global user_way # global ans solve.node_dfs() # 长度不一样肯定不匹配 if not len(self.user_way) == len(solve.ans): return 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], self.user_way[i + 1])][6] dis_ans += d.Edges[G.node_edge(solve.ans[i], solve.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 solve.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): 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]#回到起始点 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) best, user = self.check_user_best()# 计算最优路径与用户路径的总花费 if best == user:# 如果最优路径与用户路径的总花费相等，则说明用户路径是最短路径 result = "用户路径是最短路径" else:#否则说明用户路径不是最短路径 result = "用户路径不是最短路径" # 如果用户路径不是最短路径，则增加一个"显示最佳路径"的按钮 B = tk.Button(top, text="显示最佳路径", command=lambda: self.show_best_ans(top, best, user)) B.place(relx=0.6, rely=0.30 + y0, width=100, height=50) lab = tk.Label(top, text=f"{result}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab.place(relx=0.1, rely=0.3 + y0, width=200, height=50) def check_user_greey(self): # 检查用户路径是不是贪心路径,不是的话返回错误点 solve.node_greedy()# 计算贪心路径 if not len(self.user_way) == len(solve.ans):# 路径长度不一样肯定不匹配，直接返回 self.auto_ways() return num = len(self.user_way) for i in range(num):#逐个节点进行匹配 if not self.user_way[i] == solve.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 solve.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] 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() if g == -1:#如果用户路径是贪心路径则显示 result = '用户路径是贪心路径' else:# 若用户路径不是贪心路径，则显示在第几步时选择出错，并将该次选择的正确选择与用户实际选择显示出来 result = '用户路径不是贪心路径' result2 = '用户路径'+d.Nodes[self.user_way[g-1]][1]+'->'+d.Nodes[self.user_way[g]][1]+' 成本为%d\n'%d.Edges[G.node_edge(self.user_way[g-1],self.user_way[g])][6] result2 += '贪心路径' + d.Nodes[solve.ans[g - 1]][1] + '->' + d.Nodes[solve.ans[g]][1] + ' 成本为%d\n' % d.Edges[G.node_edge(solve.ans[g-1],solve.ans[g])][6] 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_mark_display(self): # 用户路径显示 E.newedge_del_all(1) for w in frame_right.winfo_children(): w.destroy() # 清除右侧组件 lab = tk.Label(frame_right, text="路径操作", bg=RED, fg=BLACK, font=('微软雅黑', 20)) lab.place(relx=0.05, rely=0.02, width=300, height=30) y0 = 0.1 lab1 = tk.Label(frame_right, text="用户路径:", bg=RED, fg=BLACK, font=('微软雅黑', 12)) self.auto_ways() way = "" for a in self.user_way: way += d.Nodes[a][1] way += "->" way += d.Nodes[0][1] lab2 = tk.Label(frame_right, text=f"{way}", bg=BLUE, fg=BLACK, font=('微软雅黑', 12), wraplength=200, justify='left') lab1.place(relx=0.1, rely=0.05 + y0, width=80, height=30) lab2.place(relx=0.1, rely=0.15 + y0, width=200, height=100) B = tk.Button(frame_right, text="清除路径", command=lambda: self.user_way_clear()) B.place(relx=0.8, rely=0.15 + y0, width=50, height=30) B = tk.Button(frame_right, text="撤销", command=lambda: self.user_way_del()) B.place(relx=0.8, rely=0.20 + y0, width=50, height=30) B = tk.Button(frame_right, text="检查路径", command=lambda: self.user_way_check()) B.place(relx=0.8, rely=0.25 + y0, width=50, height=30) B = tk.Button(frame_right, text="判断路径是否为最短路径", command=lambda: self.user_way_best()) B.place(relx=0.1, rely=0.30 + y0, width=200, height=30) B = tk.Button(frame_right, text="判断路径是否为贪心路径", command=lambda: self.user_way_greedy()) B.place(relx=0.1, rely=0.35 + y0, width=200, height=30) 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 user_way_clear(self): self.user_flag.clear() self.user_flag.add(0) self.user_way.clear() self.user_cur = 0 self.user_way.append(0) self.auto_ways() self.way_mark_display() def user_way_del(self): # 删除路径最后一步 if len(self.user_way) <= 1: return cur = self.user_way.pop() self.user_cur = self.user_way[len(self.user_way) - 1] self.user_flag.discard(cur) self.auto_ways() self.way_mark_display() def way_check(self): # 检查路径是否合法 if not len(self.user_way) == len(d.Nodes):# 若用户路径没有遍历所有节点，则不合法 return "Error: not all nodes are traversed in the user path" for w in range(len(self.user_way) - 1):# 若用户路径不连通，则不合法 if not d.Edges[G.node_edge(self.user_way[w], self.user_way[w + 1])][3] == 1: return "Error: user path is not connected between node {} and node {}".format(self.user_way[w], self.user_way[w + 1]) if d.Edges[G.node_edge(0, self.user_way[len(self.user_way) - 1])][3] == 1: return "Valid path" else:# 若用户路径无法回到出发点，则不合法 return "Error: user path does not return to the starting point" def user_way_check(self): # 检查路径是否合法并弹窗 check = self.way_check() if not check == "Valid path": result = tk.messagebox.askokcancel(title='结果', message = check) else: result = tk.messagebox.askokcancel(title='结果', message ='该路径合法') def user_way_add(self, nxt): # 用户路径操作 # print(nxt) if nxt in self.user_flag: return # 看用户选择的路径是否存在 if d.Edges[G.node_edge(self.user_cur, nxt)][3] == 1: # 将该点加入用户路径 self.user_way.append(nxt) self.user_flag.add(nxt) self.user_cur = nxt self.way_mark_display() # print(user_way) def user_way_greedy(self): # 检查路径是否为最短路径并显示 check = self.way_check() if not check == "Valid path": result = tk.messagebox.askokcancel(title='错误', message = check) return 0 # 若路径不合法，直接弹窗并返回 if solve.node_greedy() == -1: return 0 self.show_GREDDY() def user_way_best(self): # 检查路径是否为最短路径并显示 check = self.way_check() if not check == "Valid path":# 如果用户路径不合法，则直接返回 tk.messagebox.askokcancel(title='错误', message = check) return 0 # 若路径不合法，直接弹窗并返回 self.show_BEST() if __name__ == '__main__': G.draw() # userG = USER_GREEDY() # userB = USER_BSET() W = Ways() W.way_mark_display() mainloop()