Existe-t-il un moyen élégant de suivre les ensembles d'éléments connectés en Python?

Question

Pour un certain morceau de code, je devais trouver un moyen de reconnaître certains alias. Chose est, on ne sait pas à l'avance quels sont ces alias.

Ce sont mes exigences:

• Si A et B sont des alias et B et C sont des alias, A et C devraient être alias aussi bien.
• Deux ensembles d'alias doivent être fusionnés lorsqu'ils sont connectés de quelque façon que ce soit.
• Dans chaque ensemble d'alias, l'alias primaire doit être utilisé.

J'utilise la solution suivante, en utilisant ce qui se résume à un dictionnaire de jeux:

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 

Cela pourrait-il être amélioré? Par exemple, en faisant usage d'une classe dans la bibliothèque standard (j'ai cherché, mais j'ai peut-être manqué quelque chose d'utile.)

Answer 1

C'est quelque chose que vous pouvez mapper sur un graphique pour que je ferais:

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

Vous ne spécifiez pas l'alias doit être la principale, de sorte que vous pourriez aussi bien choisir le premier de ces listes.

networkx module

Answer 2

Avez-vous envisagé d'utiliser un disjoint set? Il est pratiquement O(1) en vitesse, easy to implement, et semble correspondre exactement à vos besoins.