ベクトルから同じクラスのノードを効率的に抽出 – エッジを表す集合から接続コンポーネントを求める

Algorithm to extract nodes of same class efficiently from a vector – StackOverflow

最も単純かつリーズナブルな方法は，無向グラフの接続コンポーネントを求める問題として捉えて，

import networkx as nx


S = (2, 1, 1, 3, 6, 7, 5, 9, 6, 13, 12, 14, 12, 11)

G = nx.Graph()
G.add_edges_from(enumerate(S, 1))

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)

list(nx.connected_components(G))

[{1, 2, 3, 4}, {5, 6, 7, 8, 9}, {10, 11, 12, 13, 14}]

　
　
基本的には，前からなぞっていけば解けるイメージなので，collections.defaultdict(set)を用いても簡単に解けそう．

from collections import defaultdict


def groupby_edges(lst, g=0, sidx=1):
    dd = defaultdict(set)
    for i, x in enumerate(lst, sidx):
        j = lst[x-sidx]
        if i != 1 and x not in dd[g] and j not in dd[g]:
            g += 1
        dd[g].update((i, j))
    return dd


S = (2, 1, 1, 3, 6, 7, 5, 9, 6, 13, 12, 14, 12, 11)
groupby_edges(S)

defaultdict(set,
            {0: {1, 2, 3, 4}, 1: {5, 6, 7, 8, 9}, 2: {10, 11, 12, 13, 14}})

　
　
関連：
データフレームから接続コンポーネントを得る

広告