Поиск графа Networkx: dfs_successors против 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     
 |     |---->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']}

Что здесь происходит не так, и как я могу получить ожидаемое поведение?


python graph traversal networkx
person Michael Schubert    schedule 18.02.2014    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Функция dfs_predecessors() дает только непосредственного предшественника. Итак, если вы скажете это (DFS G из узла «n» и оглядываясь назад на одну ссылку из «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']
person Aric    schedule 19.02.2014
comment
Спасибо за объяснение :-) - person Michael Schubert; 19.02.2014