英文:
Is there a NetworkX function to find the k-nearest nodes of 0-degree nodes
问题
我正在尝试连接建筑物（和其他区域）的质心到表示道路网络的 NetworkX.MultiGraph。这些质心都是0度节点。
我已经阅读了关于在同一图中查找最近邻居的帖子，但未找到关于“离网格”节点的任何信息。Graph.neighbors() 和 ego_graph() 对于质心节点都返回空的可迭代对象。
我想知道是否有适用于这种情况的函数。我是否必须迭代所有道路上的节点来计算它们与质心的距离？还是有更好的想法？
图
红点是要连接的节点。
最小示例数据
some_edges = [((12965572.317313856, 4069201.5797910197),
(12965582.853703659, 4069201.5541923903)),
((12965582.853703659, 4069201.5541923903),
(12965593.39009346, 4069201.528593761)),
((12965593.39009346, 4069201.528593761),
(12965637.645157026, 4069201.426199232)),
((12965593.39009346, 4069201.528593761),
(12965594.291781338, 4069120.115297204)),
((12965593.39009346, 4069201.528593761),
(12965593.790843628, 4069233.4285842725))]
a_centroid = [((12965783.891266523, 4069098.4402361237), {'id': 839812059, 'node_type': 'area_centroid', 'amenity': 'library', 'building': 'yes', 'name': '逸夫图书馆', 'name:zh': '逸夫图书馆', 'name:zh-Hans': '逸夫图书馆', 'name:zh-Hant': '逸夫圖書館', 'operator': '北京工业大学'})]
G = nx.MultiGraph(some_edges)
G.add_nodes_from(a_centroid)
color_map = ['red' if 'name' in attr.keys() else 'blue' for n, attr in G.nodes.data()]
nx.draw(G, {n: (n[0], n[1]) for n in G.nodes()}, node_color=color_map, ax=plt.gca())
应该生成一个类似这样的最小示例图：
其中蓝色节点是图的一部分，而红色节点是要连接的质心（连接到图中最近的节点）。
英文:
I am trying to connect the centroids of buildings (and other areas) to a NetworkX.MultiGraph representing the road network. These centroids are all 0-degree nodes.
I have read posts on finding the nearest neighbors in the same graph but failed to find anything for 'off-grid' nodes. Graph.neighbors() and ego_graph() all returned empty iterables for the centroid nodes.
I wonder if there is a function for this case. Do I have to iterate over all the nodes on the roads to compute their distances to the centroid? Or there is a better idea?
The Graph
The red dots are the nodes to connect.
Minimal example data
some_edges = [((12965572.317313856, 4069201.5797910197),
(12965582.853703659, 4069201.5541923903)),
((12965582.853703659, 4069201.5541923903),
(12965593.39009346, 4069201.528593761)),
((12965593.39009346, 4069201.528593761),
(12965637.645157026, 4069201.426199232)),
((12965593.39009346, 4069201.528593761),
(12965594.291781338, 4069120.115297204)),
((12965593.39009346, 4069201.528593761),
(12965593.790843628, 4069233.4285842725))]
a_centroid = [((12965783.891266523, 4069098.4402361237), {'id': 839812059, 'node_type': 'area_centroid', 'amenity': 'library', 'building': 'yes', 'name': '逸夫图书馆', 'name:zh': '逸夫图书馆', 'name:zh-Hans': '逸夫图书馆', 'name:zh-Hant': '逸夫圖書館', 'operator': '北京工业大学'})]
G = nx.MultiGraph(some_edges)
G.add_nodes_from(a_centroid)
color_map = ['red' if 'name' in attr.keys() else 'blue' for n, attr in G.nodes.data()]
nx.draw(G, {n: (n[0], n[1]) for n in G.nodes()}, node_color=color_map, ax=plt.gca())
should produce a minimal example with a graph like this:
where the blue nodes are parts of the graph while the red node is a centroid to connect (to its nearest node in the graph).
答案1
得分: 1
为了简单起见，您可以使用scipy.spatial包中的KDTree：
from scipy.spatial import KDTree
# 将孤立节点（红色）与道路节点（蓝色）分开
orphans = [node for node, degree in G.degree if degree == 0]
nodes = [node for node, degree in G.degree if degree > 0]
# 找到每个红色节点最近的蓝色节点
distances, indices = KDTree(nodes).query(orphans, k=1)
# 构建新的边连接红色节点
edges = [(orphan, nodes[index]) for orphan, index in zip(orphans, indices)]
G.add_edges_from(edges)
输出：
>>> edges
[((12965783.891266523, 4069098.4402361237), (12965637.645157026, 4069201.426199232))]
英文:
To be simple, you can use KDTree from scipy.spatial package:
from scipy.spatial import KDTree
# Separate orphan nodes (red) from road nodes (blue)
orphans = [node for node, degree in G.degree if degree == 0]
nodes = [node for node, degree in G.degree if degree > 0]
# Find the nearest blue node to each red node
distances, indices = KDTree(nodes).query(orphans, k=1)
# Build new edges to join red nodes
edges = [(orphan, nodes[index]) for orphan, index in zip(orphans, indices)]
G.add_edges_from(edges)
Output:
>>> edges
[((12965783.891266523, 4069098.4402361237), (12965637.645157026, 4069201.426199232))]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论