Как сгенерировать все связующее дерево графа - PullRequest
Новая
       14

Как сгенерировать все связующее дерево графа

0 голосов
/ 09 апреля 2020

Дан связанный граф с N узлами и их (x, y) координатами. Мне удалось создать минимальное связующее дерево и его стоимость. Мне нужна помощь о том, как создать все связующие деревья и их стоимость. Ниже приведена реализация минимального связующего дерева. 

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

# Initializing an arbitrary unweighted edges of the graph
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)]

# Initializing an arbitrary (x,y) coordinate of each node in the graph
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))

# Extracting the (x,y) coordinate of each node to enable the calculation of the Euclidean distances of the graph edges
position_array = []
for node in sorted(G):
    position_array.append(G.nodes[node]["pos"])

print("Sorted Nodes of the Graph is:", sorted(G))
print("Position_Array_Nodes is:", 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))

# Building a minimum spanning tree sub-graph, T of the main graph, G
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()              # Extracting the minimum spanning tree graph edges
print("Minimum Spanning Tree Edges is:", red_edges)

# Extracting the neighbours of each node in the minimum spanning tree, T for the purpose of routing using minimum distance between two nodes
neigh_list=[]
for n in T.nodes:
    neigh_list.append(list(T.neighbors(n)))
print("List of Neighbors of Nodes in Minimum Spanning is:", neigh_list)
print("Minimum_Spanning_Tree_Nodes:", T.nodes)

# Calculating the minimum spanning tree cost (distance) of the minimum spanning tree, T
span_ed_distance = []
for u , v in red_edges:
    distance_edge = np.round(distances[u][v], decimals=1)
    span_ed_distance.append(distance_edge)
print("Edge_Distance_In_Minimum_Spanning_Tree:", span_ed_distance)
cost_span_tree = sum(span_ed_distance)
print("minimum spanning tree cost is:", cost_span_tree)

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)
# Show the axis
plt.axis('on')
# Show the plot
plt.show()

Дан связанный граф с N узлами и их (x, y) координатами. Мне удалось создать минимальное связующее дерево и его стоимость. Мне нужна помощь о том, как создать все связующие деревья и их стоимость. Ниже приведена реализация минимального связующего дерева.

...