Python networkx: получить все возможные места назначения для каждого узла

Извините, формулировка моего графа может быть неправильной.
Учитывая ориентированный граф, я хотел бы получить словарь, в котором ключом является узел, а значением является набор всех узлов, до которых мы можем добраться из этого узла, используя любой path.
Например, на этом графике:

1->2->3
4->5

Мы должны получить такой результат:

{
  1: set(2,3),
  2: set(3),
  3: set(),
  4: set(5),
  5: set(),
}

Я мог бы получить это, вызвав что-то вроде этого:

{n: networkx.bfs_tree(graph, n).nodes() for n in networkx.nodes(graph)}

Но это подразумевает O (n ^ 2) итераций, тогда как это можно построить с O (n) итерациями.

Что мне не хватает?

Спасибо!


python graph networkx
person Nitz    schedule 23.02.2017    source источник
comment
Есть ли шанс, что вы можете быть уверены, что это ациклический граф? Если это так, сначала выполните топологическую сортировку, и вы, вероятно, сможете получить ее оттуда.   -  person Joel    schedule 23.02.2017

Ответы (1)


arrow_upward
0
arrow_downward

Оптимизация: мы можем реконструировать BFS из дерева связности базовых узлов. Итак, рекурсивное решение (только ациклические графы):

d = {}
def foo(node):
    if node in d:
        return d[node]
    nodes = g.neighbors(node)
    d[node] = set(nodes)
    for neighbor in nodes:
        d[node].update(foo(neighbor))
    return d[node].union(nodes)

Тест:

> _=[foo(node) for node in g.nodes()]
> d
{1: set([2, 3]), 2: set([3]), 3: set([]), 4: set([5]), 5: set([])}

Предполагая, что кешированные вызовы бесплатны, это должно быть O (e)

person Marat    schedule 23.02.2017
comment
Это будет извлекать только непосредственных соседей, поэтому в приведенном выше примере result[1] будет set(2), а не set(2,3), насколько я вижу. - person Nitz; 23.02.2017
comment
Извините, я недостаточно внимательно прочитал. Я удалю этот ответ и подумаю еще раз - person Marat; 23.02.2017