Как автоматически рассчитать евклидово расстояние между соседями в сети x с использованием координат x, y и найти минимальное остовное дерево - PullRequest
Новая
       92

Как автоматически рассчитать евклидово расстояние между соседями в сети x с использованием координат x, y и найти минимальное остовное дерево

1 голос
/ 19 марта 2020

Пока я вычисляю евклидово расстояние между соседями вручную. Но мне нужна помощь по нашему, чтобы автоматически рассчитать расстояние в коде. Мой код до сих пор: 

    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()

Любая помощь будет оценена

1 Ответ

0 голосов
/ 19 марта 2020

Возможно, вы ищете scipy.spatial.distance.pdist , который рассчитывает все попарные расстояния. Если вам нужно только несколько расстояний, вы также можете рассчитать их с помощью 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()
...