小编mar*_*rth的帖子

所以我有来自networkx示例的代码,但我想弄清楚如何限制半径'r'内的节点,以便在圆的范围内绘制随机几何图形.我知道如何以逻辑方式做到这一点,但我有点困惑,一切如何运作,并且到目前为止我一直试图自己解决这个问题.谢谢您的帮助!

import networkx as nx
import matplotlib.pyplot as plt

G = nx.random_geometric_graph(1000,0.1)

# position is stored as node attribute data for random_geometric_graph
pos = nx.get_node_attributes(G,'pos')

# find node near center (0.5,0.5)
dmin =1
ncenter =0
for n in pos:
    x,y = pos[n]
    d = (x-0.5)**2+(y-0.5)**2
    if d<dmin:
        ncenter = n
        dmin = d

# color by path length from node near center
p = nx.single_source_shortest_path_length(G,ncenter)

plt.figure(figsize=(8,8))
#node_color=p.values()
nx.draw_networkx_edges(G,pos,nodelist=[ncenter],alpha=0.4)
nx.draw_networkx_nodes(G,pos,nodelist=p.keys(),
                   node_size=80,
                   node_color='#0F1C95',
                   cmap=plt.cm.Reds_r)

plt.xlim(-0.05,1.05)
plt.ylim(-0.05,1.05)
plt.axis('off')
plt.savefig('random_geometric_graph.png')
plt.show()

因此,NetworkX明确表示他们在n ^ 2时间内使用算法生成随机几何图形.他们说使用KD树可以实现更快的算法.我的问题是如何尝试实现此算法的KD Tree版本？我不熟悉这种数据结构,也不称自己为python专家.试图解决这个问题.感谢所有帮助,谢谢!

    def random_geometric_graph(n, radius, dim=2, pos=None):
        G=nx.Graph()
        G.name="Random Geometric Graph"
        G.add_nodes_from(range(n)) 
        if pos is None:
            # random positions
            for n in G:
                G.node[n]['pos']=[random.random() for i in range(0,dim)]
        else:
            nx.set_node_attributes(G,'pos',pos)
        # connect nodes within "radius" of each other
        # n^2 algorithm, could use a k-d tree implementation
        nodes = G.nodes(data=True)
        while nodes:
            u,du = nodes.pop()
            pu = du['pos']
            for v,dv in nodes:
                pv = dv['pos']
                d = sum(((a-b)**2 for a,b in zip(pu,pv)))
                if d <= radius**2:
                    G.add_edge(u,v)
    return …