I have a networkx graph, in which each node has a x and y attributes that form a geogrpahic coordinate. I want to use this information to merge nodes that are within a specific distance of each other, say 10 meters. I have tried this as a iterative with a while function that merges nodes until none are within 10 meters. I currently am working on creating a list of all the nodes that need to be merged together. I am facing two difficulties because the runtime for computing the distances is very long for my almost 2000 nodes and I am not sure if I should make this a iterative approach where I compute distances then merge and then compute again until no nodes are within the 10 meters anymore or if I can somehow immediately combine the nodes into a group of nodes and merge them all at once.
This is the current functions I am using
def compute_distances(graph):
distances = {}
for node1, node2 in combinations(graph.nodes(data=True), 2):
try:
if node1[1]['type'] == node2[1]['type']:
distance = geodesic((node1[1]['y'], node1[1]['x']), (node2[1]['y'], node2[1]['x'])).meters
distances[(node1[0], node2[0])] = distance
print(f"Distance between {node1[0]} and {node2[0]}: {distance} meters")
except KeyError as e:
print(f"KeyError: {e} for nodes {node1[0]} and {node2[0]}")
return distances
def find_nodes_to_merge(distances, threshold_distance):
nodes_to_merge = []
for (node1, node2), distance in distances.items():
if distance < threshold_distance:
nodes_to_merge.append((node1, node2))
return nodes_to_merge
I would like that instead of pairs of nodes for nodes_to_merge I get all the nodes that need to be merged grouped into clusters already in a list of lists potentially.