networkx construct graph by euclidean distance threshold

Question

I want to construct a geometrical graph via euclidean thresholded edge when given nodes.

For example,

the given nodes are postion on 2D map

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

Then when I set the euclidean distance threshold such as 5, the graph will look like x1-x2-x5. Since x1 and x5 are farther than 5, they are not allowed to be connected.

How can I do this conveniently with networkx or other libraries?

Answer 1

You can use a kd-tree, and specifically you may want to use scipy.spatial.cKDTree (kd-tree for quick nearest-neighbor lookup).

In general, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. They are useful to find poins in the space that are nearest to a given input point.

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)