networkx 通过欧氏距离阈值构造图

Question

我想在给定节点时通过欧几里得阈值边构造几何图。

例如，

给定的节点在二维地图上的位置

x1(1,0) x2(3,4) x5(5,6)

然后当我设置欧氏距离阈值比如5时，该图看起来像 x1-x2-x5。由于x1和x5比5远，所以不允许连接

如何使用 networkx 或其他库方便地执行此操作？

Answer 1

您可以使用 kd-tree，特别是您可能想使用 scipy.spatial.cKDTree（用于快速最近邻查找的 kd-tree）。

一般来说，kd-tree（k维树的简称）是一种space分区数据结构，用于组织k维space中的点。它们对于在 space 中找到最接近给定输入点的点很有用。

from networkx import Graph
from scipy.spatial import cKDTree

# your data and parameters
points = [(1, 0), (3, 4), (5, 6)]
dist = 5

# build KDTree
tree = cKDTree(points)

# build graph
G = Graph()
G.add_nodes_from(points)
G.add_edges_from((point, points[idx2])
                 for idx1, point in enumerate(points)
                 for idx2 in tree.query_ball_point(point, dist)
                 if idx1 != idx2)

networkx 通过欧氏距离阈值构造图

networkx construct graph by euclidean distance threshold

python

graph

networkx