1

したがって、NetworkX では、n^2 時間でアルゴリズムを使用してランダムな幾何学的グラフを生成することは明らかです。彼らは、KD ツリーを使用することで、より高速なアルゴリズムが可能になると言っています。私の質問は、このアルゴリズムの KD ツリー バージョンを実装するにはどうすればよいでしょうか? 私はこのデータ構造に精通していませんし、自分自身を 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 G
4

1 に答える 1

5

これは、上記の @tcaswell によって言及された scipy KD ツリー実装を使用する方法です。

import numpy as np
from scipy import spatial
import networkx as nx
import matplotlib.pyplot as plt
nnodes = 100
r = 0.15
positions =  np.random.rand(nnodes,2)
kdtree = spatial.KDTree(positions)
pairs = kdtree.query_pairs(r)
G = nx.Graph()
G.add_nodes_from(range(nnodes))
G.add_edges_from(list(pairs))
pos = dict(zip(range(nnodes),positions))
nx.draw(G,pos)
plt.show()
于 2012-12-13T23:24:03.840 に答える