Перечисление всех путей в DAG из исходного узла, посещение только один раз

Question

Моя цель - создать справочную таблицу по узлам, где каждая запись содержит список преемников этого конкретного узла. Например, если у вас есть график

• A-> B -> C
• A-> D-> E-> F
• A-> D -> E-> G
• A-> D-> H

, тогда порядок обхода от A будет A, B, C, D, E, F, G, Н. Это для механизма реактивного программирования, поэтому моя цель состоит в том, что если A «активирован», то я должен посетить все его преемники в первую очередь. Я также хочу короткого замыкания, поэтому, если, например, «E» указывает, что это терминальный узел, порядок выполнения будет A, B, C, D, E, H. В настоящее время я использую пакет networkx в Python, который предлагает BFS, DFS, топологическую сортировку и множество других алгоритмов, но я не нашел способа сделать то, что я пытаюсь достичь с помощью встроенных алгоритмов .

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

def activate(self, evt: Event):
    nodes = networkx.descendants(self.graph, evt)
    ordering = networkx.topological_sort(networkx.subgraph(self.graph, nodes))
    for node in ordering:
        node.on_activate()

, но при этом отсутствует ключевая функция: возможность короткого замыкания и остановки события. распространение, если on_activate () возвращает false. Немного взломав, я нашел следующие работы, но я не уверен, является ли это оптимальным или самым элегантным решением. По сути, я беру топологическую сортировку и сканирую вперед, чтобы найти следующий нетерминальный узел для подавления распространения:

# noinspection PyCallingNonCallable
def activate(self, evt: Event):
    nodes = networkx.descendants(self.graph, evt)
    ordering = networkx.topological_sort(networkx.subgraph(self.graph, nodes))
    self.__clear_activation_flags()

    # process the originating node
    if not evt.on_activate():
        return
    else:
        self.activation_flags[evt] = True

    # process the node's descendents
    for node in ordering:
        if not node.on_activate():
            # skip forward to the next terminal node
            skipping = True
            while skipping:
                node = next(ordering, None)
                if not node or self.graph.out_degree(node) == 0:
                    skipping = False
        else:
            self.activation_flags[node] = True

Answer 1

DFS должен решить эту проблему

graph = {'A': ['B', 'D'],
        'B' : ['C'],
        'C':  ['P'],
        'D': ['E', 'H'],
        'E': ['F', 'G'],
        'F': [],
        'G': [],
        'H': [],
        'P': ['D', 'Q'],
        'Q' : []}
terminal_nodes = ['C']     
path=[]

def _dfs_visit(start_node):
    if start_node in path or start_node in terminal_nodes:
        return
    path.append(start_node)
    for node in graph[start_node]:
        print (path)
        _dfs_visit(node)

_dfs_visit('A', )
print (path)