0

重みのあるエッジのリストがあり、それらから互いに素なセットを取得したいと考えています。ただし、セット内でも重みを追跡したいと考えています。たとえば、データセットがある場合、

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

2セットになります

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

基本的に、関係の重みは重みで乗算されます。ブルートフォース以外にこれを追跡するための効率的なアルゴリズムはありますか? 選択した言語は python です。

4

1 に答える 1

0

あなたが何を求めているのか、私にはよくわかりません。ただし、グラフのConnected コンポーネントを探していると思います。その場合、次のように、元のグラフの互いに素なエッジのセットに対応する 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})]
于 2016-01-29T21:11:50.097 に答える