Networkx:按波遍历图
Networkx: Traverse graph by waves
假设我在 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
方法通过 "waves" 执行 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:拥有一个不需要遍历整个图的懒惰解决方案对我来说很重要,因为我的图可能非常大,我希望能够在需要时尽早停止遍历。
您可以使用 Dijkstra 算法计算从 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)
应该可以提供您需要的信息。但它 returns 一个由节点键控到与源的距离的字典。因此,您必须对其进行处理以按距离将其分组。这样的事情应该有效:
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])]
假设我在 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
方法通过 "waves" 执行 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:拥有一个不需要遍历整个图的懒惰解决方案对我来说很重要,因为我的图可能非常大,我希望能够在需要时尽早停止遍历。
您可以使用 Dijkstra 算法计算从 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)
应该可以提供您需要的信息。但它 returns 一个由节点键控到与源的距离的字典。因此,您必须对其进行处理以按距离将其分组。这样的事情应该有效:
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])]