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

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}]

ダウンロード3

 
 
基本的には,前からなぞっていけば解けるイメージなので,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}})

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

広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください