网络图搜索：dfs_successors vs. dfs_predecessors

Question

考虑以下图形结构（摘自这个问题）：

G = networkx.DiGraph()
G.add_edges_from([('n', 'n1'), ('n', 'n2'), ('n', 'n3')])
G.add_edges_from([('n4', 'n41'), ('n1', 'n11'), ('n1', 'n12'), ('n1', 'n13')])
G.add_edges_from([('n2', 'n21'), ('n2', 'n22')])
G.add_edges_from([('n13', 'n131'), ('n22', 'n221')])

这将产生：

n---->n1--->n11
 |     |--->n12
 |     |--->n13
 |           |--->n131 
 |--->n2              
 |     |---->n21     
 |     |---->n22     
 |            |--->n221 
 |--->n3

我可以从节点n开始执行深度优先搜索来获取其后继节点：

> dfs_successors(G, 'n')
{'n': ['n1', 'n2', 'n3'],
 'n1': ['n12', 'n13', 'n11'],
 'n13': ['n131'],
 'n131': ['n221'],
 'n2': ['n22', 'n21']}

然而，当我对例如节点n221进行深度优先搜索以查找前置节点时，什么也没有发生：

> dfs_predecessors(G, 'n221')
{}

我希望输出结果为：

{'n221': ['n22', 'n2', 'n']}

这里出现了什么问题，我该如何获得预期的行为？

- Michael Schubert

Answer 1

dfs_predecessors()函数仅返回直接前驱节点。因此，如果您执行以下操作（对G进行从节点'n'开始的DFS，并从'n22'向后查找一个链接）

>>> print(networkx.dfs_predecessors(G, 'n')['n221'])
n22

你得到了一部分你想要的。

要从n221回到根节点在深度优先搜索树中的路径：

>>> T = networkx.dfs_tree(G,'n')

>>> print(networkx.shortest_path(G.reverse(),'n221','n'))
['n221', 'n22', 'n2', 'n']

- Aric

---

我希望dfs_predecessors()的行为像dfs_successors()一样，但它并没有。这两个函数都是基于dfs_edges()定义的，而dfs_edges()只能向前运行。唉。 - brocla

从叶子到根的最短路径方法适用于树，也适用于更复杂的图形。想象一下有多个根的DiGraph。 - brocla

我刚刚发现bfs_edges()有一个reverse=选项，可以在反向遍历时使用。如果dfs_edges()也有相同的选项，那么编写一个行为符合预期的dfs_predecessors()版本就会变得简单。听起来像是一次开源工作的机会。愉快！ - brocla