在graph-tool中查找源和目标之间的所有路径，返回边而不是顶点
堆栈溢出！
我有一个有向图，需要找到源和目标顶点之间的所有路径。在几个顶点之间，有多条边。使用图形工具，您可能会建议使用graph_tool.topology.all_paths(g, source, target)，但是，此顶点迭代器中包含的列表仅用于顶点；请参阅下面的一些输出。由于顶点之间有多条边，因此存在多次出现的路径，例如[ 0 4 8 13]和[0 4 13]，我无法区分这些路径。
iterator, paths: [ 0 4 8 13]
iterator, paths: [ 0 4 13]
iterator, paths: [ 0 4 8 13]
iterator, paths: [ 0 4 13]
iterator, paths: [ 0 4 8 13]
iterator, paths: [ 0 4 13]我需要边缘形式的路径，以便能够沿着每条路径迭代边缘属性。为了解决这个问题，我只能想到一种方法(除了重写大量代码之外)：创建中间顶点，以避免在任意两个顶点之间出现多条边。对于两个顶点之间的任何平行边，它们都将连接到各自唯一的中间顶点，以便唯一地定义从graph_tool.topology.all_paths(g, source, target)返回的路径。
有没有办法以边的形式返回源顶点和目标顶点之间的所有路径？
回答 2
Stack Overflow用户
发布于 2018-09-24 16:36:06
最近添加到图形工具中的是：https://git.skewed.de/count0/graph-tool/commit/5457d04f5f37c7a49e87b67c666c1a865e206b9a
您只需要传递edges=True参数：
for p in all_paths(g, u, v, edges=True):
for e in p:
print(e) # e is an edge descriptorStack Overflow用户
发布于 2018-09-19 20:51:17
查找所有路径的计算代价已经相当高(O(N+E)，IIRC)。如果你最终对边的数据属性的组合感兴趣，那么我会在简化图(没有多边)上找到路径，然后查找每条边的可能的数据属性(可以在固定的时间内完成)，并计算可能的数据属性组合。一步一步：
找到路径。将节点列表转换为边列表。
path_edges = zip(path_nodes[:-1], path_nodes[1:])创建一个字典(dict)，将每个边(source, target)映射到数据属性列表，例如[0.2, 0.7, 42]。每个数据属性对应于一个多边(在您的情况下，其中许多多边可能是长度为1的列表，因为从您给出的数据样本来看，多边似乎很少)。
计算路径中所有边的数据属性的所有组合。
data = [edge_to_data[edge] for edge in path_edges]
cartesian_product = itertools.product(*data) # returns an iterator!
print(list(cartesian_product))最后，将您的成本函数或其他值应用于值列表。
https://stackoverflow.com/questions/52399377
复制相似问题
腾讯云开发者
