Networkx图搜索：dfs_successors与dfs_predecessors [英] Networkx graph searches: dfs_successors vs. dfs_predecessors

问题描述

考虑以下图形结构（借用这个问题）：

  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 
 | | ---->&n; 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']} 
  code> 

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


解决方案

dfs_predecessors（）函数仅给出了前一个前导。
所以如果你这样说（从节点'n'的G的DFS并且从'n22'回头看一个链接）



 >>> print（networkx.dfs_predecessors（G，'n'）['n221']）
 n22 
  



<

获取DFS树中的路径从n221回到根目录：

 >>> T = networkx.dfs_tree（G，'n'）
 
>>> print（networkx.shortest_path（G.reverse（），'n221'，'n'））
 ['n221'，'n22'，'n2'，'n'] 
  

Consider the following graph structure (borrowed from this 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')])

which yields:

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

I can perform a depth-first search for successors starting at node n and get:

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

However, when I do a depth-first search for predecessors at e.g. node n221, nothing happens:

> dfs_predecessors(G, 'n221')
{}

I would expect the output to be:

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

What is going wrong here, and how can I get my expected behaviour?

解决方案

The dfs_predecessors() function only gives the immediate predecessor. So if you say this (DFS of G from node 'n' and looking back one link from 'n22')

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

you get part of what you want.

To get the path in the DFS tree from n221 back to the root:

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

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

这篇关于Networkx图搜索：dfs_successors与dfs_predecessors的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！