如何使用x，y坐标自动计算networkx中邻居之间的欧氏距离并找到最小生成树

Question

到目前为止，我手动计算了邻居之间的欧式距离。但是我需要帮助我们在代码中自动计算距离。到目前为止我的代码是：

    import networkx as nx
    import matplotlib.pyplot as plt
    import seaborn as sns
    sns.set()

    G = nx.Graph()

    list_edges = [(0,1,3.8), (0,2,3.6), (1,3,2.5), (2,4,3.5), (3,5,4.6), (3,6,4.0), (3,7,2.8), (4,8,2.9), 
 (4,9,2.7), (4,10,4.1), (7,8,2.2), (5,6,3.1), (6,7,3.2), (8,9,3.6), (9,10,3.4)]
    G.add_weighted_edges_from(list_edges)

    G.add_node(0, pos = (8.5,10.5))
    G.add_node(1, pos = (5,9))
    G.add_node(2, pos = (11.5,8.5))
    G.add_node(3, pos = (5,6.5))
    G.add_node(4, pos = (11.5,5))
    G.add_node(5, pos = (1.5,3.5))
    G.add_node(6, pos = (4.5,2.5))
    G.add_node(7, pos = (7,4.5))
    G.add_node(8, pos = (9,3.5))
    G.add_node(9, pos = (12.5,2.5))
    G.add_node(10, pos = (15.5,4))

    T = nx.minimum_spanning_tree(G, algorithm='kruskal')
    #print(G.adj.items())
    #print(T.edges())
    #node_list = G.nodes()
    #print(node_list)
    #print(nx.get_node_attributes(G,'pos'))

    node_pos=nx.get_node_attributes(G,'pos')
    edge_weight=nx.get_edge_attributes(G,'weight')
    red_edges = T.edges()
    node_col = ['white']
    # If the edge is in the shortest path set it to red, else set it to white color
    edge_col = ['black' if not edge in red_edges else 'red' for edge in G.edges()]
    # Draw the nodes
    nx.draw_networkx(G, node_pos,node_color= node_col, node_size=450)
    # Draw the node labels
    nx.draw_networkx_labels(G, node_pos,node_color= node_col)
    # Draw the edges
    nx.draw_networkx_edges(G, node_pos,edge_color= edge_col)
    # Draw the edge labels
    nx.draw_networkx_edge_labels(G, node_pos,edge_color= edge_col, edge_labels=edge_weight)
    # Remove the axis
    plt.axis('off')
    # Show the plot
    plt.show()

任何帮助将不胜感激

Answer 1

您可能正在寻找 scipy.spatial.distance.pdist, which calculates all pairwise distances. If you need only few distances, you could also calculate them with scipy.spatial.distane.euclidean。

以下代码无需指定距离即可重现您的结果：

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial.distance import pdist, squareform

import seaborn as sns
sns.set()

G = nx.Graph()

# list_edges = [(0, 1, 3.8), (0, 2, 3.6), (1, 3, 2.5), (2, 4, 3.5), (3, 5, 4.6), (3, 6, 4.0), (3, 7, 2.8), (4, 8, 2.9),
#               (4, 9, 2.7), (4, 10, 4.1), (7, 8, 2.2), (5, 6, 3.1), (6, 7, 3.2), (8, 9, 3.6), (9, 10, 3.4)]
# G.add_weighted_edges_from(list_edges)

list_unweighted_edges = [(0, 1), (0, 2), (1, 3), (2, 4), (3, 5), (3, 6), (3, 7), (4, 8),
                         (4, 9), (4, 10), (7, 8), (5, 6), (6, 7), (8, 9), (9, 10)]

G.add_node(0, pos=(8.5, 10.5))
G.add_node(1, pos=(5, 9))
G.add_node(2, pos=(11.5, 8.5))
G.add_node(3, pos=(5, 6.5))
G.add_node(4, pos=(11.5, 5))
G.add_node(5, pos=(1.5, 3.5))
G.add_node(6, pos=(4.5, 2.5))
G.add_node(7, pos=(7, 4.5))
G.add_node(8, pos=(9, 3.5))
G.add_node(9, pos=(12.5, 2.5))
G.add_node(10, pos=(15.5, 4))

position_array = []
for node in sorted(G):
    position_array.append(G.nodes[node]["pos"])

print(position_array)
distances = squareform(pdist(np.array(position_array)))

for u, v in list_unweighted_edges:
    G.add_edge(u, v, weight=np.round(distances[u][v],decimals=1))

T = nx.minimum_spanning_tree(G, algorithm='kruskal')

node_pos = nx.get_node_attributes(G, 'pos')
edge_weight = nx.get_edge_attributes(G, 'weight')
red_edges = T.edges()
node_col = ['white']
# If the edge is in the shortest path set it to red, else set it to white color
edge_col = ['black' if not edge in red_edges else 'red' for edge in G.edges()]
# Draw the nodes
nx.draw_networkx(G, node_pos, node_color=node_col, node_size=450)
# Draw the node labels
nx.draw_networkx_labels(G, node_pos, node_color=node_col)
# Draw the edges
nx.draw_networkx_edges(G, node_pos, edge_color=edge_col)
# Draw the edge labels
nx.draw_networkx_edge_labels(G, node_pos, edge_color=edge_col, edge_labels=edge_weight)
# Remove the axis
plt.axis('off')
# Show the plot
plt.show()

如何使用x，y坐标自动计算networkx中邻居之间的欧氏距离并找到最小生成树

How to calculate the euclidean distance between neighbors in networkx using x,y coordinates automatically and find the minimum spanning tree

edges

minimum-spanning-tree

euclidean-distance

networkx

python-3.x