从源节点枚举 DAG 中的所有路径，仅访问一次

Question

我的目标是按节点创建查找 table，每个条目都包含该特定节点的后继列表。例如。如果你有图表

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

那么从A开始的遍历顺序就是A,B,C,D,E,F,G,H。这是一个反应式编程机制，所以我的目标是如果 A 是 "activated" 那么我应该深度优先访问它的所有后继者。我也想短路，所以如果例如 "E" 表示它是一个终端节点，则执行顺序将是 A,B,C,D,E,H。我目前在 Python 中使用 networkx 包，它提供 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() returns 为假，则能够短路并停止事件传播。通过一些黑客攻击，我发现了以下作品，但我不确定它是否是最佳或最优雅的解决方案。本质上我采用拓扑排序并向前扫描以找到下一个非终端节点以抑制传播：

# 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)

从源节点枚举 DAG 中的所有路径，仅访问一次

Enumerating all paths with in a DAG from a source node, visiting only once

python

networkx

graph-algorithm