graph-tool - 在图形工具中查找源和目标之间的所有路径，返回边而不是顶点

Question

堆栈溢出！

我有一个有向图，需要找到源顶点和目标顶点之间的所有路径。在几个顶点之间，有多个边。使用图形工具，可能会建议使用graph_tool.topology.all_paths(g, source, target)，但是，此顶点迭代器中包含的列表仅用于顶点；请参阅下面的一些输出。由于顶点之间存在多条边，因此会出现多次路径，例如[ 0 4 8 13]and[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).

有没有办法以源顶点和目标顶点之间的边的形式返回所有路径？

标签： graph-tool

Answer 1

最近已将其添加到图形工具中：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 descriptor