|
|
# 数据模型
|
|
|
import math, random
|
|
|
from pprint import pprint
|
|
|
|
|
|
import get_real_data as grd
|
|
|
|
|
|
|
|
|
class Node(object):
|
|
|
'''节点类'''
|
|
|
|
|
|
def __init__(self, node_info: list) -> None:
|
|
|
self.node_info = node_info
|
|
|
self.id = node_info[0]
|
|
|
self.label = node_info[1]
|
|
|
self.is_flag = node_info[2]
|
|
|
self.vs_coord = node_info[3]
|
|
|
self.is_must_node = node_info[4] # 是否必经节点
|
|
|
if len(node_info) >= 6: # 如果有实际坐标
|
|
|
self.label = node_info[5][0]
|
|
|
self.city = node_info[5] # 所在城市
|
|
|
self.real_coord = node_info[6] # 实际坐标
|
|
|
|
|
|
def __str__(self):
|
|
|
# 判断
|
|
|
if hasattr(self, "city"):
|
|
|
return (f"<Node Obj - NO: {self.id}, Label: {self.label}"
|
|
|
f"x,y={self.vs_coord} - {self.city}>")
|
|
|
return (f"<Node Obj - NO: {self.id}, Label: {self.label}"
|
|
|
f"x,y={self.vs_coord}> ")
|
|
|
|
|
|
|
|
|
class Edge(object):
|
|
|
'''链接类'''
|
|
|
|
|
|
def __init__(self, edge_info):
|
|
|
self.edge_info = edge_info
|
|
|
self.id = edge_info[0]
|
|
|
self.node1_id = edge_info[1]
|
|
|
self.node2_id = edge_info[2]
|
|
|
self.is_displayed = edge_info[3] # 是否显示，连接
|
|
|
self.is_flagged = edge_info[4] # 是否标记，路径
|
|
|
self.label = edge_info[5] # 标签
|
|
|
self.distance = edge_info[6] # 距离成本
|
|
|
self.time = edge_info[7] # 时间成本
|
|
|
self.sequence_number = edge_info[8] # 连接序号（两点多连接时用）
|
|
|
|
|
|
def __str__(self):
|
|
|
return f"<Edge {self.id} node-conn {self.node1_id}-{self.node2_id} distance: {self.distance}>"
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
class CustomPath:
|
|
|
'''从连接构造路径'''
|
|
|
def __init__(self):
|
|
|
self.Path = [] # 路径对象列表
|
|
|
self.path_distance_count = 0 # 路径距离成本
|
|
|
self.path_time_count = 0 # 路径时间成本
|
|
|
self.graph = {} # 邻接图
|
|
|
self.Edges = None
|
|
|
self.Nodes = None
|
|
|
self.elapsed_time = 0 # 运行时间
|
|
|
|
|
|
# def create_one_edge(self,id1, id2, ):
|
|
|
# connection_id = len(self.Edges) + 1
|
|
|
# node1_id = nodes[i].id
|
|
|
# node2_id = nodes[j].id
|
|
|
# is_displayed = False
|
|
|
# is_flagged = False
|
|
|
# label = f"Con{connection_id}"
|
|
|
# distance = random.randint(10, 1000) # 你需要设置实际的距离值
|
|
|
# time = random.randint(60, 720) # 你需要设置实际的时间值
|
|
|
# sequence_number = 0
|
|
|
|
|
|
def creat_edge_data(self, nodes): # 全连接图
|
|
|
self.Edges = []
|
|
|
# 构造全部连接
|
|
|
for i in range(len(nodes)):
|
|
|
for j in range(i + 1, len(nodes)):
|
|
|
for n in range(3): # 两点多连接
|
|
|
connection_id = len(self.Edges) + 1
|
|
|
node1_id = nodes[i].id
|
|
|
node2_id = nodes[j].id
|
|
|
is_displayed = False
|
|
|
is_flagged = False
|
|
|
label = f"C{connection_id}-{n}"
|
|
|
distance = random.randint(10, 1000) # 你需要设置实际的距离值
|
|
|
time = random.randint(60, 720) # 你需要设置实际的时间值
|
|
|
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)
|
|
|
return self.Edges
|
|
|
|
|
|
def creat_real_edge_data(self, nodes): # 全连接图
|
|
|
self.Edges = []
|
|
|
for i in range(len(nodes)):
|
|
|
for j in range(i + 1, len(nodes)):
|
|
|
paths = grd.get_route_planning(nodes[i].real_coord, nodes[j].real_coord, nodes[i].city, nodes[j].city)
|
|
|
for n in range(len(paths)):
|
|
|
connection_id = len(self.Edges) + 1
|
|
|
node1_id = nodes[i].id
|
|
|
node2_id = nodes[j].id
|
|
|
is_displayed = False
|
|
|
is_flagged = False
|
|
|
label = f"C{connection_id}-{paths[n]['seq']}"
|
|
|
distance = paths[n]['distance']
|
|
|
time = paths[n]['time']
|
|
|
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)
|
|
|
return self.Edges
|
|
|
|
|
|
|
|
|
def creat_node_data(self, data):
|
|
|
if isinstance(data, int):
|
|
|
num = data
|
|
|
else:
|
|
|
num = len(data)
|
|
|
ang = 360 / num
|
|
|
R = 330
|
|
|
self.Nodes = []
|
|
|
for i in range(num):
|
|
|
rad = math.radians(i * ang)
|
|
|
x = int(math.cos(rad) * R)
|
|
|
y = int(math.sin(rad) * R)
|
|
|
node = [i, str(i), False, [x, y], False]
|
|
|
if isinstance(data, list):
|
|
|
node = node+data[i]
|
|
|
self.Nodes.append(Node(node))
|
|
|
return self.Nodes
|
|
|
|
|
|
|
|
|
|
|
|
def edge_select(self, node1, node2):
|
|
|
node_id = [node1.id, node2.id]
|
|
|
for edge in self.Edges:
|
|
|
if edge.node1_id in node_id and edge.node2_id in node_id:
|
|
|
return edge
|
|
|
|
|
|
# def set_display_path_(self, node_ids: list): # 根据节点顺序，创建路径,自动闭环
|
|
|
# self.Path = []
|
|
|
# for i in range(len(node_ids)):
|
|
|
# if i < len(node_ids) - 1:
|
|
|
# id1 = node_ids[i];id2 = node_ids[i + 1]
|
|
|
# else:
|
|
|
# id1 = node_ids[i];id2 = node_ids[0]
|
|
|
# node_id = [id1, id2]
|
|
|
# for edge in self.Edges:
|
|
|
# if edge.node1_id in node_id and edge.node2_id in node_id:
|
|
|
# edge.is_flagged = True # 标记为路径
|
|
|
# self.Path.append(edge)
|
|
|
# return self.Path
|
|
|
|
|
|
|
|
|
def set_display_path(self, node_ids:list, Edges:list): # 根据节点顺序，创建路径,自动闭环,并计算成本
|
|
|
self.Path = []
|
|
|
self.path_distance_count = 0
|
|
|
self.path_time_count = 0
|
|
|
for i in range(len(node_ids)):
|
|
|
if i < len(node_ids) - 1:
|
|
|
id1 = node_ids[i]
|
|
|
id2 = node_ids[i + 1]
|
|
|
else:
|
|
|
id1 = node_ids[i]
|
|
|
id2 = node_ids[0]
|
|
|
node_id = [id1, id2]
|
|
|
for edge in Edges:
|
|
|
if edge.node1_id in node_id and edge.node2_id in node_id:
|
|
|
edge.is_flagged = True
|
|
|
self.Path.append(edge) # 添加到路径
|
|
|
self.path_distance_count += edge.distance # 计算距离成本
|
|
|
self.path_time_count += edge.time # 计算时间成本
|
|
|
return self.Path, self.path_distance_count, self.path_time_count
|
|
|
|
|
|
def set_display_conn(self, node_ids: list, more=False): # 选择显示哪些连接，自动闭环
|
|
|
for i in range(len(node_ids)):
|
|
|
if i < len(node_ids) - 1:
|
|
|
id1 = node_ids[i]
|
|
|
id2 = node_ids[i + 1]
|
|
|
else:
|
|
|
id1 = node_ids[i]
|
|
|
id2 = node_ids[0]
|
|
|
node_id = [id1, id2]
|
|
|
seq = random.randint(0,2)
|
|
|
for edge in self.Edges:
|
|
|
if edge.node1_id in node_id and edge.node2_id in node_id:
|
|
|
if not more:
|
|
|
if edge.sequence_number == seq:
|
|
|
edge.is_displayed = True
|
|
|
break
|
|
|
else:
|
|
|
edge.is_displayed = True # 标记为连接可视
|
|
|
|
|
|
|
|
|
def creat_graph(self, Nodes, is_distance=True): # 创建邻接图
|
|
|
'''默认统计距离成本，否则统计时间成本'''
|
|
|
# 路径归一，让节点之间的路径只留一条权重最小的路径
|
|
|
self.graph = dict()
|
|
|
min_edges = [] # 任一两点间的最短路径
|
|
|
# 限定遍历的两点间路径
|
|
|
for i in range(len(Nodes)):
|
|
|
for j in range(i + 1, len(Nodes)):
|
|
|
ids = [Nodes[i].id, Nodes[j].id] # 确定点间路径
|
|
|
min_value = float('inf')
|
|
|
min_edge = None
|
|
|
for edge in self.Edges:
|
|
|
if edge.node1_id in ids and edge.node2_id in ids:
|
|
|
if edge.is_displayed: # 显示标志为True,表示已连接
|
|
|
if is_distance:
|
|
|
if min_value > edge.distance:
|
|
|
min_value = edge.distance
|
|
|
min_edge = edge
|
|
|
else:
|
|
|
if min_value > edge.time:
|
|
|
min_value = edge.time
|
|
|
min_edge = edge
|
|
|
if min_edge is not None:
|
|
|
min_edges.append(min_edge)
|
|
|
|
|
|
for node in Nodes:
|
|
|
self.graph[node.id] = []
|
|
|
for edge in min_edges:
|
|
|
if edge.is_displayed: # 显示标志为True,表示已连接
|
|
|
node_ids = [edge.node1_id, edge.node2_id]
|
|
|
if node.id in node_ids:
|
|
|
node_ids.remove(node.id) # 去掉自己
|
|
|
if is_distance:
|
|
|
self.graph[node.id].append((node_ids[0], edge.distance))
|
|
|
else:
|
|
|
self.graph[node.id].append((node_ids[0], edge.time))
|
|
|
# pprint(self.graph)
|
|
|
return self.graph, min_edges # 返回邻接图和点间最短路径列表
|
|
|
|
|
|
def creat_graph_(self, Path, is_distance=True): # 根据路径创建邻接图
|
|
|
self.graph = dict()
|
|
|
order_nodes = self.Path_to_nodes(Path)
|
|
|
for node in order_nodes:
|
|
|
self.graph[node] = []
|
|
|
for edge in Path:
|
|
|
if edge.is_displayed:
|
|
|
node_ids = [edge.node1_id, edge.node2_id]
|
|
|
if node in node_ids:
|
|
|
node_ids.remove(node)
|
|
|
if is_distance:
|
|
|
self.graph[node].append((node_ids[0], edge.distance))
|
|
|
else:
|
|
|
self.graph[node].append((node_ids[0], edge.time))
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
def set_display_all_conn(self): # 显示所有连接
|
|
|
for edge in self.Edges:
|
|
|
edge.is_displayed = True
|
|
|
|
|
|
################################### 11.8 ##########################
|
|
|
def find_complete_cycles(self, graph, start_node=0):
|
|
|
"""
|
|
|
寻找图中所有能够回到起点的完整连接路径。
|
|
|
|
|
|
Parameters:
|
|
|
- graph: 图的邻接表示，以字典形式表示每个节点的邻居和权重。
|
|
|
- start_node: 起始节点，默认为0。
|
|
|
|
|
|
Returns:
|
|
|
一个列表，包含所有能够回到起点的完整连接路径。
|
|
|
每个路径都表示为一个列表，包含按顺序访问的节点。
|
|
|
"""
|
|
|
|
|
|
def dfs(node, visited, path):
|
|
|
visited[node] = True
|
|
|
path.append(node)
|
|
|
|
|
|
# 如果路径长度等于节点总数 并且最后一个节点是起点的邻接点，表示找到完整的连接路径
|
|
|
if len(path) == len(graph) and path[-1] in start_neighbors:
|
|
|
# 找到了一个完整的连接路径
|
|
|
cycles.append(path.copy())
|
|
|
|
|
|
# 遍历当前节点的邻居
|
|
|
for neighbor, _ in graph[node]:
|
|
|
if not visited[neighbor]:
|
|
|
dfs(neighbor, visited.copy(), path.copy())
|
|
|
|
|
|
cycles = []
|
|
|
visited = [False] * len(graph)
|
|
|
start_neighbors = [node for node, _ in graph[start_node]] # 获取起始节点的邻接点
|
|
|
dfs(start_node, visited, [])
|
|
|
return cycles
|
|
|
|
|
|
def find_min_cycles(self,graph,start_node, must_nodes):
|
|
|
def must_nodes_check(must_nodes, path):
|
|
|
for node in must_nodes:
|
|
|
if node not in path:
|
|
|
return False
|
|
|
return True
|
|
|
def dfs(node, visited,path):
|
|
|
visited[node] = True
|
|
|
path.append(node)
|
|
|
# 如果路径长度大于2节点 并且最后一个节点是起点的邻接点，表示找到完整的连接路径
|
|
|
if len(path) > 2 and path[-1] in start_neighbors:
|
|
|
if must_nodes_check(must_nodes, path): min_cycles.append(path.copy())
|
|
|
# 遍历当前节点的邻居
|
|
|
for neighbor, _ in graph[node]:
|
|
|
if not visited[neighbor]:
|
|
|
dfs(neighbor, visited.copy(), path.copy())
|
|
|
min_cycles = []
|
|
|
visited = [False] * len(graph)
|
|
|
start_neighbors = [node for node, _ in graph[start_node]] # 获取起始节点的邻接点
|
|
|
dfs(start_node, visited, [])
|
|
|
return min_cycles
|
|
|
|
|
|
def traversal_search_to_path(self, graph, start_node=0, must_node=None): # 遍历搜索
|
|
|
import time
|
|
|
start_time = time.time() # 记录开始时间
|
|
|
if must_node is not None:
|
|
|
all_paths = self.find_min_cycles(graph, start_node, must_node) # 获取所有完整路径
|
|
|
else:
|
|
|
all_paths = self.find_complete_cycles(graph, start_node)
|
|
|
if len(all_paths) == 0:
|
|
|
return False, f"当前图无法获取完整路径,请检查节点连接是否完整"
|
|
|
min_path = [] # 计算每个排列组合的路径长度
|
|
|
min_value = float('inf')
|
|
|
for permutation in all_paths: # 遍历所有路径
|
|
|
|
|
|
current_path = list(permutation) + [start_node]
|
|
|
current_value = self.calculate_path_dort(graph,
|
|
|
current_path)
|
|
|
if current_value < min_value: # 选取距离最小的路径
|
|
|
min_path = [] # 清空路径
|
|
|
min_value = current_value
|
|
|
min_path.append(current_path)
|
|
|
elif current_value == min_value:
|
|
|
min_path.append(current_path)
|
|
|
end_time = time.time() # 记录结束时间
|
|
|
self.elapsed_time = end_time - start_time # 计算运行时间
|
|
|
return min_path, min_value, self.elapsed_time
|
|
|
|
|
|
def indeterminate_search_to_path(self, start_node=0, must_nodes=None):
|
|
|
# 确定必经点和起始点是否有一条完整路径
|
|
|
for i in range(len(must_nodes)):
|
|
|
self.graph_check_connectivity(start_node, must_nodes[i])
|
|
|
|
|
|
pass
|
|
|
|
|
|
def calculate_path_dort(self, graph, path): # 根据节点顺序计算节点权重（时间或者距离）
|
|
|
min_value = 0
|
|
|
for i in range(len(path) - 1):
|
|
|
current_node = path[i]
|
|
|
next_node = path[i + 1]
|
|
|
if graph[current_node] is not []:
|
|
|
for edge in graph[current_node]:
|
|
|
if edge[0] == next_node:
|
|
|
min_value += edge[1]
|
|
|
break
|
|
|
else:
|
|
|
break
|
|
|
return min_value
|
|
|
|
|
|
#############################################
|
|
|
############################# 11.9 ########################################
|
|
|
def greedy_search_to_path(self, graph, start_node=0, must_node=None):
|
|
|
|
|
|
import time
|
|
|
start_time = time.time() # 记录开始时间
|
|
|
start_neighbors = [node for node, _ in graph[start_node]] # 获取起始节点的邻接点
|
|
|
# num_nodes = len(graph) # 获取节点数
|
|
|
remaining_nodes = set(graph.keys()) - {start_node} # 剩余节点
|
|
|
current_node = start_node # 当前节点
|
|
|
path = [start_node] # 记录路径
|
|
|
while remaining_nodes:
|
|
|
# 检查当前节点是否有相邻的边
|
|
|
if not any(graph[current_node]):
|
|
|
break
|
|
|
next_node = None # 搜寻下一节点
|
|
|
value = float('inf')
|
|
|
for nv in graph[current_node]:
|
|
|
if nv[1] < value and nv[0] not in path: # 选择剩下节点中值最小的且非已选节点的节点，
|
|
|
value = nv[1]
|
|
|
next_node = nv[0]
|
|
|
# 如果未找到符合条件的节点，退出循环
|
|
|
if next_node is None:
|
|
|
label, label2 = None, None
|
|
|
for node in self.Nodes:
|
|
|
if node.id == current_node:
|
|
|
label = node.label
|
|
|
if node.id == list(remaining_nodes)[0]:
|
|
|
label2 = node.label
|
|
|
if label and label2:
|
|
|
return False, (f"当前贪心路径{path}\n'{label}'的节点无直接路径到"
|
|
|
f"'{label2}'的节点贪心算法求解失败"), path
|
|
|
path.append(next_node)
|
|
|
remaining_nodes.remove(next_node)
|
|
|
current_node = next_node
|
|
|
if path[-1] in start_neighbors:
|
|
|
path.append(start_node) # 添加到路径
|
|
|
else:
|
|
|
label, label2 = None, None
|
|
|
for node in self.Nodes:
|
|
|
if node.id == path[-1]:
|
|
|
label = node.label
|
|
|
if node.id == start_node:
|
|
|
label2 = node.label
|
|
|
if label and label2:
|
|
|
return False, (f"当前贪心路径{path}\n'{label}'节点无直接路径到"
|
|
|
f"'{label2}'节点贪心算法求解失败"), path
|
|
|
end_time = time.time() # 记录结束时间
|
|
|
self.elapsed_time = end_time - start_time # 计算运行时间
|
|
|
return [path], self.calculate_path_dort(graph, path), self.elapsed_time
|
|
|
|
|
|
#####################################################################################
|
|
|
|
|
|
############################# 11.10 ########################################
|
|
|
def graph_check_connectivity(self, node1, node2):
|
|
|
"""
|
|
|
检查两点之间是否有完整连接
|
|
|
|
|
|
Parameters:
|
|
|
- node1: 第一个节点
|
|
|
- node2: 第二个节点
|
|
|
|
|
|
Returns:
|
|
|
- True: 如果两点有完整连接
|
|
|
- False: 如果两点没有完整连接
|
|
|
- None: 如果图的节点或边为 None
|
|
|
"""
|
|
|
# 检查图的节点和边是否存在
|
|
|
if self.Nodes is not None and self.Edges is not None:
|
|
|
find = [] # 使用并查集来检测两点是否互通
|
|
|
# 初始化并查集，每个节点自成一个集合
|
|
|
for node in self.Nodes:
|
|
|
find.append(node.id)
|
|
|
|
|
|
# 根据已有的边来更新并查集
|
|
|
for edge in self.Edges:
|
|
|
if edge.is_displayed:
|
|
|
x = edge.node1_id
|
|
|
y = edge.node2_id
|
|
|
# 路径压缩，找到每个节点所在集合的根节点
|
|
|
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 = node1.id
|
|
|
y = node2.id
|
|
|
while not x == find[x]:
|
|
|
x = find[x]
|
|
|
while not y == find[y]:
|
|
|
y = find[y]
|
|
|
|
|
|
# 判断两个节点是否在同一个集合
|
|
|
if find[x] == find[y]:
|
|
|
return True, x, y
|
|
|
else:
|
|
|
return False, x, y
|
|
|
else:
|
|
|
# 如果图的节点或边为 None，返回 None
|
|
|
return None
|
|
|
|
|
|
############################# 11.10 ########################################
|
|
|
|
|
|
############################# 11.11 ########################################
|
|
|
def check_user_best(self, Path: list, is_distance=True, start_node=0, must_nodes=None):
|
|
|
'''检查用户输入的路径是否最优'''
|
|
|
self.graph, min_edges = self.creat_graph(self.Nodes, is_distance) # 创建邻接图，默认距离最优，取否则时间最优
|
|
|
if must_nodes and len(must_nodes) != 0:
|
|
|
revalue = self.traversal_search_to_path(self.graph, start_node, must_nodes) # 遍历最优路径
|
|
|
else:
|
|
|
revalue = self.traversal_search_to_path(self.graph, start_node) # 遍历最优路径
|
|
|
min_path = revalue[0][0] # 获取最小路径
|
|
|
if not len(Path) + 1 == len(min_path): # 节点个数不一样就不匹配
|
|
|
return False
|
|
|
min_value = revalue[1] # 获取最小值
|
|
|
user_min_value = self.path_distance_time_count(Path, is_distance) # 计算用户输入路径的值
|
|
|
if user_min_value == min_value:
|
|
|
return True
|
|
|
else:
|
|
|
return False
|
|
|
|
|
|
def path_distance_time_count(self, Path: list, is_distance=True):
|
|
|
min_value = 0
|
|
|
if not is_distance:
|
|
|
for path in Path:
|
|
|
min_value += path.time
|
|
|
return min_value
|
|
|
else:
|
|
|
for path in Path:
|
|
|
min_value += path.distance
|
|
|
return min_value
|
|
|
|
|
|
############################################################################
|
|
|
|
|
|
############################# 11.12 ########################################
|
|
|
def check_is_greedy(self, Path: list, is_distance=True, start_node: int = 0):
|
|
|
'''检查用户输入的路径是否是贪心路径'''
|
|
|
self.graph, min_edges = self.creat_graph(self.Nodes, is_distance) # 临接图
|
|
|
revalue = self.greedy_search_to_path(self.graph, start_node) # 先算出贪心路径
|
|
|
if not revalue[0]: # 如果没有找到贪心路径
|
|
|
return False, "当前图贪心算法求解失败"
|
|
|
min_path = revalue[0][0]
|
|
|
if not len(Path)+1 == len(min_path):
|
|
|
return False, None
|
|
|
user_paths = self.Path_to_nodes(Path)
|
|
|
num = len(user_paths)
|
|
|
for i in range(num): # 逐个节点进行匹配
|
|
|
if not user_paths[i] == min_path[i]:
|
|
|
return False, f"正确的贪心节点顺序为{min_path}\n当前路径不符合贪心规则。" # 返回不匹配的节点
|
|
|
return True , None # 返回True表示是贪心路径
|
|
|
|
|
|
def Path_to_nodes(self, Path, start_node=0):
|
|
|
paths = [start_node]
|
|
|
next_node = paths[0]
|
|
|
for path in Path:
|
|
|
two_nodes = [path.node1_id, path.node2_id]
|
|
|
if next_node in two_nodes:
|
|
|
two_nodes.remove(next_node)
|
|
|
next_node = two_nodes.pop()
|
|
|
paths.append(next_node)
|
|
|
return paths
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
############################################################################
|
|
|
|
|
|
############################# 11.12 ########################################
|
|
|
|
|
|
|
|
|
############################################################################
|
|
|
if __name__ == '__main__':
|
|
|
def passs():
|
|
|
pass
|
|
|
|
|
|
pa = CustomPath()
|
|
|
# data = grd.get_district("")
|
|
|
# Nodes = pa.creat_node_data(6)
|
|
|
# Edges = pa.creat_edge_data(Nodes)
|
|
|
# pa.set_display_all_conn()
|
|
|
# pa.Path_to_nodes(Edges)
|
|
|
|
|
|
# for node in Nodes:
|
|
|
# print(node)
|
|
|
|
|
|
# pa.set_display_all_conn() # 全连接
|
|
|
# conn = pa.check_is_greedy([0, 1,2, 0])
|
|
|
# print(conn) # 打印判断结果
|
|
|
|
|
|
# while True:
|
|
|
# a = int(input('a:'))
|
|
|
# b = int(input('b:'))
|
|
|
#
|
|
|
# conn = pa.graph_check_connectivity(Nodes[a], Nodes[b])
|
|
|
#
|
|
|
# print(conn)
|
|
|
|
|
|
# # pa.set_display_all_conn()
|
|
|
# pa.creat_graph(is_distance=True)
|
|
|
# pprint(pa.graph)
|
|
|
#
|
|
|
#
|
|
|
# # 从节点0开始进行深度优先搜索
|
|
|
# Path, min_dis,time = pa.traversal_search_to_path(pa.graph)
|
|
|
# print(Path, min_dis, time)
|
|
|
# #
|
|
|
# Path, min_dis, time = pa.greedy_search_to_path(pa.graph)
|
|
|
# print(Path, min_dis, time)
|
|
|
|
|
|
graph = {0: [(3, 77), (4, 63), (5, 719), (6, 163), (7, 256)],
|
|
|
1: [(2, 138), (4, 925), (5, 851), (6, 257), (7, 985)],
|
|
|
2: [(1, 138), (3, 448), (4, 115), (5, 512), (6, 302)],
|
|
|
3: [(0, 77), (2, 448), (4, 678), (5, 533), (6, 842)],
|
|
|
4: [(0, 63), (1, 925), (2, 115), (3, 678), (6, 855), (7, 620)],
|
|
|
5: [(0, 719), (1, 851), (2, 512), (3, 533), (6, 141), (7, 303)],
|
|
|
6: [(0, 163), (1, 257), (2, 302), (3, 842), (4, 855), (5, 141)],
|
|
|
7: [(0, 256), (1, 985), (4, 620), (5, 303)]}
|
|
|
#
|
|
|
# a = pa.find_complete_cycles(graph)
|
|
|
b = pa.find_min_cycles(graph,0,[3])
|
|
|
|
|
|
#
|
|
|
# print(pa.graph_check_connectivity(pa.Nodes[0], pa.Nodes[2]))
|
|
|
#
|
|
|
# pprint(a)
|
|
|
pprint(b)
|
