有沒有一種優雅的方式來跟蹤Python中連接項目的集合？

Question

對於某段代碼，我需要找到一種方法來識別某些別名。事情是，事先並不知道這些別名是什麼。

這些是我的要求：

• 如果一個和乙是別名，並乙和ç是別名，一個和ç應該是別名也。
• 兩組別名以任何方式連接時應合併。
• 在每組別名中，一個應該是主別名。

我採用如下方案，利用什麼歸結爲套字典：

class Alias(object): 
    def __init__(self, initial): 
     self._set = {initial} 
     self.initial = initial 
    def add(self, alias): 
     self._set.add(alias) 
    def merge(self, other): 
     self._set.update(other._set) 
    def __iter__(self): 
     return iter(self._set) 

class AliasDict(object): 
    def __init__(self): 
     self._dict = {} 
    def add(self, one, other): 
     if one in self._dict: 
      if other in self._dict: #merge! 
       self._dict[one].merge(self._dict[other]) 
       for k in self._dict[other]: 
        self._dict[k] = self._dict[one] 
      else: 
       self._dict[one].add(other) 
     elif other in self._dict: 
      self._dict[other].add(one) 
     else: 
      self._dict[one] = self._dict[other] = Alias(one) 
      self._dict[one].add(other) 
    def get(self, n): 
     return self._dict.get(n) 
    def __contains__(self, s): 
     return s in self._dict 

難道這加以改進？例如，通過使用標準庫中的類（我已經搜索過，但我可能錯過了一些有用的東西）。

Answer 1

這是你可以映射在圖形上，所以我會怎麼做：

from networkx import Graph 
from networkx.algorithms.components.connected import connected_components 

# see aliases as the edges between nodes in a graph 
aliases = [('A', 'B'), ('B', 'C'), ('D','E')] 

g = Graph(aliases) 

# connected components are alias groups 
print connected_components(g) # [['A', 'C', 'B'], ['E', 'D']] 

你不指定別名應該是首要的，所以你不妨挑從這些第一個名單。

networkx module

Answer 2

您是否考慮過使用disjoint set？它的速度幾乎爲O(1)，easy to implement，似乎完全符合您的要求。