Найти все пути в DAG от начального узла

Question

Я пытаюсь найти все пути в DAG из выбранного узла.

Таким образом, я случайно генерирую список кортежей, который выглядит следующим образом:

glavnaLista = [(6, 7), (6, 15), (15, 16), (16, 21), (15, 9), (9, 13), (13, 4), (4, 1), (1, 5)]

Из этого списка мы можем видеть, чтоузел "6" является отправной точкой графа

Теперь я создаю граф:

G = nx.DiGraph() 
    G.add_edges_from(glavnaLista)

Так выглядит это изображение

Теперь яя пытаюсь найти все пути (завершено) от начального узла с кодом:

def find_all_paths(graph, start, path=[]):

    path = path + [start]
    if start not in graph:
        return [path]
    paths = [path]
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, path)
            for newpath in newpaths:
                print (newpath)
                paths.append(newpath)        
    return paths

Результатом является список всех путей:

[[6], [6, 7], [6, 15], [6, 15, 16], [6, 15, 16, 21], [6, 15, 9], [6, 15, 9, 13], [6, 15, 9, 13, 4], [6, 15, 9, 13, 4, 1], [6, 15, 9, 13, 4, 1, 5]]

Но моя проблема в том, что мне не нужнопути, которые не являются полными (не идут до конечного узла), мой список должен содержать только полные пути:

[6, 7]
[6, 15, 9, 13, 4, 1, 5]
[6, 15, 16, 21]

Моя идея состоит в том, чтобы проверить, есть ли у узла оба соседа, и если нет, чемдобавить путь в список, но я не уверен, как это реализовать, так как я довольно плохо знаком с python.

Answer 1

То, что вы пытаетесь создать, на самом деле - дерево, созданное из BFS или DFS обхода через DAG.Вы можете сделать это, немного изменив код.

Прежде всего, обратите внимание, что у вас есть некоторые ненужные части кода:

def find_all_paths(graph, start, path=[]):
    path = path + [start]
    paths = [path]
    for node in graph[start]:
        newpaths = find_all_paths(graph, node, path)
        for newpath in newpaths:
            print (newpath)
            paths.append(newpath)        
    return paths

Поскольку мы предполагаем, что это DAG, мы можем получитьизбавление от некоторых условий ...

Теперь мы хотим сгенерировать пути прохождения DFS.Печать здесь будет печатать путь после каждой итерации, но мы хотели бы напечатать путь после того, как достигли конца.
Поэтому мы добавим простой оператор if, чтобы проверить, является ли это концом пути, и если онэто мы напечатаем путь:

def find_all_paths(graph, start, path=[]):
    path = path + [start]
    paths = [path]
    if len(graph[start]) == 0:  # No neighbors
        print(path)
    for node in graph[start]:
        newpaths = find_all_paths(graph, node, path)
        for newpath in newpaths:
            paths.append(newpath)
    return paths

Результат:

[6, 7]
[6, 15, 16, 21]
[6, 15, 9, 13, 4, 1, 5]