NetworkX находит наибольшее полностью связанное подмножество точек ⇐ Python

[Anonymous]

Я новичок в теории графов и пытаюсь найти наибольшее подмножество точек координат x,y, в котором все точки подмножества находятся на заданном расстоянии друг от друга. В настоящее время я использую функцию nx.k_core(G) в следующем коде:

Код: Выделить всё

import networkx as nx

# Create nodes
for idx, point in enumerate(gdf.geometry):
G.add_node(idx, pos=(point.x, point.y))

# Make connections based on 3-mile threshold
threshold = 3 * 5280
for i in range(len(gdf)):
for j in range(i + 1, len(gdf)):
point1 = gdf.geometry.iloc[i]
point2 = gdf.geometry.iloc[j]
distance = point1.distance(point2)
if distance < threshold:
G.add_edge(i, j, weight=distance)

# Find subset of fully connected points
core_g = nx.k_core(G)
gdf_subset = gdf.iloc[np.array(core_g.nodes())]

В качестве примера моего gdf (crs=EPSG:2227) приведено следующее:

Код: Выделить всё

4398    POINT (7014374.920 1153370.503)
5125    POINT (7004008.530 1165484.076)
5126    POINT (7004042.497 1163334.841)
5129    POINT (7019567.772 1165224.270)
5130    POINT (7018905.080 1165504.929)

Похоже, что этот подход работает по большей части, но когда в GDF имеется большое количество точек, результирующее подмножество содержит точки, которые не находятся в пределах 3 миль друг от друга. Мне нужно наибольшее подмножество точек, в котором каждая точка связана со всеми остальными в подмножестве.
Есть ли лучший подход для достижения этой цели? Спасибо!

Подробнее здесь: https://stackoverflow.com/questions/792 ... -of-points