Генерация полных путей DFS с использованием networkx

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 : Для упрощения создаются данные. В моем случае список ребер происходит из набора данных. Предполагается, что дан график и узел (скажем, 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]]