16

我在这里寻找的很可能是 中的内置函数networkx，并且有一个数学名称 - 如果是这样，我想知道它是什么！谷歌似乎很难。

给定一个图G和一个起始节点i，我想找到所有“P边内”节点的子图，i即那些i通过小于P边的路径连接的节点。

我对此的实施草案是：

import networkx as nx

N = 30
G = nx.Graph()

# populate the graph...
G.add_cycle(range(N))

# the starting node:
i = 15

# the 'distance' limit:
P = 4

neighborhood = [i]
new_neighbors = [i]
depth = 0

while depth < P:
    new_neighbors = list(set(sum([
        [k for k in G[j].keys() if k not in neighborhood]
    for j in new_neighbors], [])))

    neighborhood.extend(new_neighbors)

    depth += 1

Gneighbors = G.subgraph(neighborhood)

顺便说一句，这段代码有效，所以我不需要帮助来实现。我只是想知道它是否有名称，以及它是否由networkx库提供。

当您的代码崩溃并且您想了解原因时，它非常有用 - 您可以仅在问题节点附近呈现图形的“位置/区域”。

4

2 回答 2

23

晚了两年，但我一直在寻找同样的东西，并找到了一个我认为会得到你想要的子图的内置：ego_graph. 函数签名和文档：

ego_graph(G, n, radius=1, center=True, undirected=False, distance=None)

返回以给定半径内的节点 n 为中心的邻居的诱导子图。

于 2015-07-03T21:54:36.293 回答
12

使用single_source_shortest_path或single_source_shortest_path_length截止p

就像是：

nx.single_source_shortest_path_length(G ,source=i, cutoff=p)
于 2013-06-25T16:04:41.930 回答