如何使用图形工具找到替代(冗余)最短路径
How to find alternative (redundant) shortest paths with graph-tool
我正在使用 Dijkstra 的最短路径算法来查找从所有顶点到所有其他顶点的最短路径。然后,我使用边缘过滤器获取第一个边缘并 "hide" 它,然后再次重新计算最短路径以获得备用备用路径。我只想要 单一 备用路径,我 不 希望找到 所有 路径。
def compute_paths(source, dest):
results = graph_tool.topology.shortest_path(g, source, dest, weights=weight)
filteredge[results[1][0]] = 0
g.set_edge_filter(filteredge)
s_results = graph_tool.topology.shortest_path(g, source, dest, weights=weight)
print "PRIMARY PATH: %s" % ([g.vertex_index[x] for x in results[0]])
print "SECONDARY PATH: %s" % ([g.vertex_index[x] for x in s_results[0]])
g.set_edge_filter(None)
如果我以独立的方式调用该函数,并为其提供一对顶点,则效果很好,我得到了我期望的输出:
compute_paths(g.vertex(9), g.vertex(8))
产生:
PRIMARY PATH: [9, 3, 8]
SECONDARY PATH: [9, 4, 8]
但是,尝试在循环中获取备份路径会产生许多本不应该存在的空备份路径。例如:
for v in g.vertices():
for vv in g.vertices():
if v == vv:
continue
else:
compute_paths(v, vv)
顶点 9 和顶点 8 之间的最短主路径和备用路径将产生:
PRIMARY PATH: [9, 3, 8]
SECONDARY PATH: []
我有点卡住了。我已经尝试使用 GraphView class 和其他一些东西创建图表的副本,但是每当我尝试在循环内计算它时,我似乎无法使备份路径发生.
我发现了问题。
与其将边缘过滤器设置为 None
,不如将所需边缘上的布尔 属性 映射重置回 True。
以下是我需要的结果:
def compute_paths(source, dest):
results = graph_tool.topology.shortest_path(g, source, dest, weights=weight)
filteredge[results[1][0]] = 0
g.set_edge_filter(filteredge)
s_results = graph_tool.topology.shortest_path(g, source, dest, weights=weight)
print "PRIMARY PATH: %s" % ([g.vertex_index[x] for x in results[0]])
print "SECONDARY PATH: %s" % ([g.vertex_index[x] for x in s_results[0]])
filteredge[results[1][0]] = 1
我想我仍然可以将边缘过滤器设置为 None
,但这似乎是多余的。
我正在使用 Dijkstra 的最短路径算法来查找从所有顶点到所有其他顶点的最短路径。然后,我使用边缘过滤器获取第一个边缘并 "hide" 它,然后再次重新计算最短路径以获得备用备用路径。我只想要 单一 备用路径,我 不 希望找到 所有 路径。
def compute_paths(source, dest):
results = graph_tool.topology.shortest_path(g, source, dest, weights=weight)
filteredge[results[1][0]] = 0
g.set_edge_filter(filteredge)
s_results = graph_tool.topology.shortest_path(g, source, dest, weights=weight)
print "PRIMARY PATH: %s" % ([g.vertex_index[x] for x in results[0]])
print "SECONDARY PATH: %s" % ([g.vertex_index[x] for x in s_results[0]])
g.set_edge_filter(None)
如果我以独立的方式调用该函数,并为其提供一对顶点,则效果很好,我得到了我期望的输出:
compute_paths(g.vertex(9), g.vertex(8))
产生:
PRIMARY PATH: [9, 3, 8]
SECONDARY PATH: [9, 4, 8]
但是,尝试在循环中获取备份路径会产生许多本不应该存在的空备份路径。例如:
for v in g.vertices():
for vv in g.vertices():
if v == vv:
continue
else:
compute_paths(v, vv)
顶点 9 和顶点 8 之间的最短主路径和备用路径将产生:
PRIMARY PATH: [9, 3, 8]
SECONDARY PATH: []
我有点卡住了。我已经尝试使用 GraphView class 和其他一些东西创建图表的副本,但是每当我尝试在循环内计算它时,我似乎无法使备份路径发生.
我发现了问题。
与其将边缘过滤器设置为 None
,不如将所需边缘上的布尔 属性 映射重置回 True。
以下是我需要的结果:
def compute_paths(source, dest):
results = graph_tool.topology.shortest_path(g, source, dest, weights=weight)
filteredge[results[1][0]] = 0
g.set_edge_filter(filteredge)
s_results = graph_tool.topology.shortest_path(g, source, dest, weights=weight)
print "PRIMARY PATH: %s" % ([g.vertex_index[x] for x in results[0]])
print "SECONDARY PATH: %s" % ([g.vertex_index[x] for x in s_results[0]])
filteredge[results[1][0]] = 1
我想我仍然可以将边缘过滤器设置为 None
,但这似乎是多余的。