Networkx: обход графа по волнам
Предположим, у меня есть следующий график в networkx
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 кольцами и т. д.
Я могу сделать это с помощью Queue, но я заинтересован в использовании инструментов networkx, если это возможно. Также можно использовать несколько итераторов с разными значениями depth_limit, но я надеюсь, что можно найти более красивый способ.
UPD: Для меня важно иметь ленивое решение, которое не потребует обхода всего графа, потому что мой граф может быть довольно большим, и я хочу иметь возможность остановить обход раньше, если это необходимо.
Ответы 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
Правильный. Если вы не укажете максимальную глубину.
К сожалению, мне нужна какая-то ленивая оценка, потому что мой график может быть довольно большим, и я должен иметь возможность остановиться раньше (обычно после первых нескольких «колец»). Извините за это, я обновлю свой вопрос
Функция 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])]
Спасибо за ответ! Правильно ли я понимаю, что этот подход будет проходить весь граф, прежде чем я получу результат?