使用networkx生成完整的DFS路径

Question

我正在尝试生成完整的路径列表，而不是优化的。使用下面的示例可以更好地解释。

import networkx as nx
G = nx.Graph()
G.add_edges_from([(0, 1), (1, 2), (2, 3)])
G.add_edges_from([(0, 1), (1, 2), (2, 4)])
G.add_edges_from([(0, 5), (5, 6)])

上面代码创建了一个带有边的图0=>1=>2=>3和0=>1=>2=>4和0=>5=>6

我想要的只是从0中提取所有路径。

我试过：

>> list(nx.dfs_edges(G, 0))
[(0, 1), (1, 2), (2, 3), (2, 4), (0, 5), (5, 6)]

我想要的只是：

[(0, 1, 2, 3), (0, 1, 2, 4), (0, 5, 6)]

是否有任何来自networkx的预先存在的方法可以使用？如果没有，有什么方法可以编写一个最优的方法来完成这项工作？

注意：我的问题仅限于给出的例子。再也不可能有拐角案件了。

注2：为简化起见，生成数据。在我的例子中，edges列表来自数据集。假设给定一个图和一个节点（比如0)，我们能生成所有的路径吗？

Answer 1

试一试：

import networkx as nx

G = nx.Graph()
G.add_edges_from([(0, 1), (1, 2), (2, 3)])
G.add_edges_from([(0, 1), (1, 2), (2, 4)])
G.add_edges_from([(0, 5), (5, 6)])

pathes = []

path = [0]
for edge in nx.dfs_edges(G, 0):
    if edge[0] == path[-1]:
        # node of path
        path.append(edge[1])
    else:
        # new path
        pathes.append(path)
        search_index = 2
        while search_index <= len(path):
            if edge[0] == path[-search_index]:
                path = path[:-search_index + 1] + [edge[1]]
                break
            search_index += 1
        else:
            raise Exception("Wrong path structure?", path, edge)
# append last path
pathes.append(path)
print(pathes)
# [[0, 1, 2, 3], [0, 1, 2, 4], [0, 5, 6]]