グループのユニークなIDを作成

Question

私は関連するアイテムをグループ化し、ユニークなIDを割り当てなければならない問題に取り組んでいます。私はPythonでコードを書いていますが、期待される出力が返っていません。私は私の論理を洗練する助けが必要です。以下のコードは次のとおりです。

data = {} 
child_list = [] 


for index, row in df.iterrows(): 
    parent = row['source'] 
    child = row['target'] 
    #print 'Parent: ', parent 
    #print 'Child:', child 
    child_list.append(child) 
    #print child_list 
    if parent not in data.keys(): 
     data[parent] = [] 
    if parent != child: 
     data[parent].append(child) 
    #print data 

op = {} 
gid = 0 


def recursive(op,x,gid): 
    if x in data.keys() and data[x] != []: 
     for x_child in data[x]: 
      if x_child in data.keys(): 
       op[x_child] = gid 
       recursive(op,x_child,gid) 
      else: 
       op[x] = gid 
    else: 
     op[x] = gid 


for key in data.keys(): 
    #print "Key: ", key 
    if key not in child_list: 
     gid = gid + 1 
     op[key] = gid 
     for x in data[key]: 
      op[x] = gid 
      recursive(op,x,gid) 

related = pd.DataFrame({'items':op.keys(), 
        'uniq_group_id': op.values()}) 
mapped.sort_values('items') 

例私のコードが間違っている出力の下に私を与えた

Input: 
source target 
a  b 
b  c 
c  c 
c  d 
d  d 
e  f 
a  d 
h  a 
i  f 

Desired Output: 
item  uniq_group_id 
a   1 
b   1 
c   1 
d   1 
h   1 
e   2 
f   2 
i   2 

下回ります。

item uniq_group_id 
a  3 
b  3 
c  3 
d  3 
e  1 
f  2 
h  3 
i  2 

他の例

Input: 
df = pd.DataFrame({'source': ['a','b','c','c','d','e','a','h','i','a'], 
       'target':['b','c','c','d','d','f','d','a','f','a']}) 
Desired Output: 
item uniq_group_id 
a  1 
b  1 
c  1 
d  1 
e  2 
f  2 

My code Output: 
item uniq_group_id 
e 1 
f 1 

行またはグループIDの順序は重要ではありません。ここで重要なことは、関連するアイテムに同じ一意の識別子を割り当てることです。全体の問題は、関連するアイテムのグループを見つけて、それらに一意のグループIDを割り当てることです。

Answer 1

私はあなたのコードを詳細に分析していませんが、data辞書の作成方法が原因です。子ノードをその親ノードの近隣ノードとして格納するが、親ノードを子ノードの隣人として格納する必要もある。

コードを修正するのではなく、Aseem Goyalが書いたthis pseudocodeを採用することにしました。以下のコードは、単純なPythonリストから入力データを取り出しますが、Pandasデータフレームで使用するためには、入力データを簡単に適応させる必要があります。

''' Find all the connected components of an undirected graph ''' 

from collections import defaultdict 

src = ['a', 'b', 'c', 'c', 'd', 'e', 'a', 'h', 'i', 'a'] 
tgt = ['b', 'c', 'c', 'd', 'd', 'f', 'd', 'a', 'f', 'a'] 

nodes = sorted(set(src + tgt)) 
print('Nodes', nodes) 

neighbors = defaultdict(set) 
for u, v in zip(src, tgt): 
    neighbors[u].add(v) 
    neighbors[v].add(u) 

print('Neighbors') 
for n in nodes: 
    print(n, neighbors[n]) 

visited = {} 
def depth_first_traverse(node, group_id): 
    for n in neighbors[node]: 
     if n not in visited: 
      visited[n] = group_id 
      depth_first_traverse(n, group_id) 

print('Groups') 
group_id = 1 
for n in nodes: 
    if n not in visited: 
     visited[n] = group_id 
     depth_first_traverse(n, group_id) 
     group_id += 1 
    print(n, visited[n]) 

出力

Nodes ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i'] 
Neighbors 
a {'a', 'd', 'b', 'h'} 
b {'a', 'c'} 
c {'d', 'b', 'c'} 
d {'d', 'a', 'c'} 
e {'f'} 
f {'i', 'e'} 
h {'a'} 
i {'f'} 
Groups 
a 1 
b 1 
c 1 
d 1 
e 2 
f 2 
h 1 
i 2 

このコードはPythonの3のために書かれましたが、あなたがあなたの一番上にfrom __future__ import print_functionを追加する必要はPython 2でそれを実行しない場合も、Pythonの2上で実行されますインポートステートメント。それは厳密には必要ではありませんが、出力がより良く見えるようになります。

Answer 2

これにはUnion-Find, or Disjoint-Sets algorithmを使用できます。より完全な説明については、this related answerを参照してください。基本的に、あなたはleadersや先人の木（つまり、ネストされた辞書）を作成するために2つの機能、unionとfindを、必要とする：

leaders = collections.defaultdict(lambda: None) 

def find(x): 
    l = leaders[x] 
    if l is not None: 
     l = find(l) 
     leaders[x] = l 
     return l 
    return x 

def union(x, y): 
    lx, ly = find(x), find(y) 
    if lx != ly: 
     leaders[lx] = ly 

次のようにあなたがあなたの問題にこれを適用することができます。

df = pd.DataFrame({'source': ['a','b','c','c','d','e','a','h','i','a'], 
        'target': ['b','c','c','d','d','f','d','a','f','a']}) 

# build the tree 
for _, row in df.iterrows(): 
    union(row["source"], row["target"]) 

# build groups based on leaders 
groups = collections.defaultdict(set) 
for x in leaders: 
    groups[find(x)].add(x) 
for num, group in enumerate(groups.values(), start=1): 
    print(num, group) 

を結果：

1 {'e', 'f', 'i'} 
2 {'h', 'a', 'c', 'd', 'b'}