Что такое алгоритм для получения непересекающегося множества из edgelist с весами

Question

У меня есть список ребер с весами, и я хочу получить от них непересекающийся набор. Тем не менее, я хочу отслеживать веса также в наборе. например Если у меня есть набор данных,

N1 N2 Weight 
a1 a2 1.0 
a2 a3 0.5 
a3 a5 1.0 
a4 a8 1.0 
a8 a9 0.8 

Это приведет в двух сетах

[(a1,1.0), (a2,1.0), (a3,1.0*0.5), (a5,0.5*1.0)] and [(a4,1.0),(a8,1.0), (a9,1.0*0.8)] 

существенно веса в отношениях умножается на вес. Есть ли эффективный алгоритм для отслеживания этого, кроме грубого принуждения? Язык выбора - питон.

Answer 1

Это не очень ясно для меня, что вы просите. Однако, я считаю, что вы ищете Connected components вашего графика. В этом случае вы можете извлечь 2 подграфы, которые соответствуют несвязному множества ребер в исходном графе следующим образом:

G = nx.Graph() 
G.add_weighted_edges_from([('a1', 'a2', 1.0), ('a2', 'a3', 0.5), 
          ('a3', 'a5', 1.0), ('a4', 'a8', 1.0), ('a8', 'a9', 0.8)]) 


graphs = list(nx.connected_component_subgraphs(G)) 
for g in graphs: 
    print(g.edges(data=True)) 

Результаты

[('a1', 'a2', {'weight': 1.0}), ('a3', 'a2', {'weight': 0.5}), 
('a3', 'a5', {'weight': 1.0})] 

и

[('a9', 'a8', {'weight': 0.8}), ('a8', 'a4', {'weight': 1.0})]