Networkx: траверсировать граф волнами

Question

Предположим, у меня есть следующий график в сети x

import networkx as nx

g = nx.Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(3, 1)
g.add_edge(4, 2)

Так что это в основном 3-1-0-2-4 строка.

Есть ли networkx способ выполнить поиск BFS "волнами"? Примерно так:

for x in nx.awesome_bfs_by_waves_from_networkx(g, 0):
    print(x)
# should print
# [1, 2]
# [3, 4]

Другими словами, я хочу найти все окрестности с 1 кольцом, затем с 2 кольцами и т. Д.

Я могу сделать это с помощью очереди, но я заинтересован в использовании инструментов networkx, если это возможно. Также можно использовать несколько итераторов с разными значениями depth_limit, но я надеюсь, что можно найти более красивый способ.

UPD: Для меня важно иметь ленивое решение, которое не будет требовать обхода всего графа, потому что мой график может быть довольно большим, и я хочу иметь возможность прекратить обход рано, если это необходимо.

Answer 1

Функция nx.single_source_shortest_path_length(G, source=0, cutoff=7) должна предоставлять необходимую информацию.Но он возвращает диктовку, заданную узлом, на расстоянии от источника.Таким образом, вы должны обработать его, чтобы разделить на группы по расстоянию.Примерно так должно работать:

from itertools import groupby
spl = nx.single_source_shortest_path_length(G, source=0, cutoff=7)
rings = [set(nodes) for dist, nodes in groupby(spl, lambda x: spl[x])]

Answer 2

Вы можете рассчитать кратчайшие пути из 0 (или любого другого узла n), используя алгоритм Дейкстры, а затем сгруппировать узлы по расстоянию:

from itertools import groupby
n = 0
distances = nx.shortest_paths.single_source_dijkstra(g, n)[0]
{node: [node1 for (node1, d) in y] for node,y 
                                   in groupby(distances.items(), 
                                              key=lambda x: x[1])}
#{0: [0], 1: [1, 2], 2: [3, 4]}

Если вы хотите продолжить по кольцам (также известным как корки ), используйте понятие окрестности:

core = set()
crust = {n} # The most inner ring
while crust:
    core |= crust
    # The next ring
    crust = set.union(*(set(g.neighbors(i)) for i in crust)) - core