Structure Union-Find

I/ Partition

1) Partition d'un ensemble

Une partition d'un ensemble E est une collection de sous-ensembles de E telle que

• Chaque élément de E appartient à un des sous-ensembles de la partition
• Deux sous-ensembles de la partition sont
  • ou bien égaux
  • ou bien sans élément commun

Par exemple voici une partition d'un ensemble de 30 éléments en 5 sous-ensembles :

{1/2,0.5,5/10,3/6,4/8,6/12,8/16,2/4}
{5/25,0.2,3/15,1/5,4/20,2/10}
{0.75,3/4,6/8,9/12,12/16}
{6/4,3/2,1.5,18/12,9/6,15/10,12/8}
{6/9,2/3,4/6,8/12}

On vérifie que par exemple la fraction 3/2 est dans le quatrième sous-ensemble et dans aucun autre.

2) Relation d'équivalence

La relation « est dans le même sous-ensemble que » est une relation d'équivalence :

• Chaque élément est dans le même sous-ensemble que lui-même.
• Si a est dans le même sous-ensemble que b alors b est dans le même sous-ensemble que a.
• Si deux éléments sont dans le même sous-ensemble qu'un troisième élément, alors ils sont dans le même sous-ensemble.

Les sous-ensembles de la partition sont appelés classes d'équivalence de la partition. En abrégé on dira seulement classes. Mais ce n'est pas exactement la même notion que les classes Css ou celles de la programmation objet.

3) Structure Union-Find

Au début des années 1960, Bernard Galler et Michael Fischer ont proposé la structure Union-Find. Pour distinguer les sous-ensembles, on affecte à chacun une étiquette (ci-dessus, leur numéro). En machine cela se fait par un pointeur ou un tableau associatif. Dans la suite on choisit pour étiquette un des éléments du sous-ensemble, appelé représentant. Il ne représente pas le sous-ensemble, mais chacun de ses éléments. Une structure Union-Find est une partition dotée de deux méthodes :

• Find est une fonction qui, à chaque élément de E, associe sa classe (ou son représentant),
• Union réunit une classe à une autre. Dans la suite ce sera une opération en place, ce qui signifie qu'on choisit des classes mutables.

Par exemple en appliquant Union entre la cinquième et la quatrième classe ci-dessus, on obtient cette nouvelle partition :

{1/2,0.5,5/10,3/6,4/8,6/12,8/16,2/4}
{5/25,0.2,3/15,1/5,4/20,2/10}
{0.75,3/4,6/8,9/12,12/16}
{6/4,3/2,1.5,18/12,9/6,15/10,12/8,6/9,2/3,4/6,8/12}

4) Applications

• L'équivalence logique entre propositions est une relation d'équivalence.
• Les fractions sont des classes d'équivalence, le représentant étant en général choisi irréductible.
• L'isomorphisme entre graphes est une relation d'équivalence. Dans le cas d'un graphe planaire, on choisit souvent un représentant planaire.
• Les composantes connexes d'un graphe constituent une partition de ses sommets. La structure Union-Find permet de calculer les composantes connexes : on parcourt le graphe et chaque fois qu'on trouve un chemin entre deux sommets, on réunit leurs classes.
• En 1956, Joseph Kruskal a publié son algorithme pour construire un arbre couvrant de poids minimal dans un graphe pondéré. Cet algorithme utilise une structure Union-Find.
• Le jeu de la crapette consiste à construire (par unions successives) une partition par couleur de cartes. Le représentant de chaque couleur est l'as de cette couleur. Certains jeux à un joueur ressemblent aussi à l'établissement de classes par unions successives.

II/ Implémentations

1) Liste de listes

On représente E par une liste, dont les éléments sont eux-mêmes des listes (les classes) :

class UnionFind():
    def __init__(self):
        self.liste = []
    def makeSet(self,elt):
        if elt not in [e for k in self.liste for e in k ]:
            self.liste.append([elt])
    def is_representative(self,elt):
        return elt in [k[0] for k in self.liste]
    def find(self,elt):
        for k in range(len(self.liste)):
            if elt in self.liste[k]:
                return k,self.liste[k]
        return None
    def union(self,e1,e2):
        i,r1 = self.find(e1)
        j,r2 = self.find(e2)
        self.liste.remove(r1)
        self.liste[j] += r1

On ajoute une méthode makeSet permettant de créer une nouvelle classe singleton (en général pour la réunir ultérieurement à une autre classe, plus grosse). On rajoute également une méthode permettant de savoir si un élément est un représentant :

• On choisit que le premier élément de chaque sous-ensemble est son représentant.
• Pour find, on parcourt toute la liste à la recherche d'un élément et on renvoie
  • Le numéro de la classe
  • La classe
  • Ou le représentant.
  Dans tous les cas, cette méthode est de complexité linéaire.
• Pour union il suffit de concaténer la première classe à la seconde.

Dans le graphe ci-dessous, les arcs vont vers le représentant qui est donc la queue de liste.

2) Tableau associatif

On peut implémenter sous forme de tableau associatif (en Python dictionnaire) la fonction qui, à chaque élément de E, associe son représentant :

class UnionFind():
    def __init__(self):
        self.dico = {}
    def makeSet(self,elt):
        if elt not in self.dico:
            self.dico[elt] = elt
    def is_representative(self,elt):
        return elt in self.dico and self.dico[elt]==elt
    def find(self,elt):
        if elt in self.dico:
            return self.dico[elt]
        else:
            return None
    def union(self,e1,e2):
        r1,r2 = self.find(e1),self.find(e2)
        for k in self.dico:
            if self.dico[k]==r1:
                self.dico[k] = r2

La modélisation est plus compacte :

• On choisit qu'un représentant pointe sur lui-même (il est son propre représentant).
• La méthode find est une simple lecture dans le dictionnaire.
• Par contre la méthode union nécessite un parcours de E et est de complexité linéaire.

3) Forêt (graphe sans cycle)

Il est possible de rendre les deux méthodes find et union rapides toutes les deux, en remplaçant la fonction représentant par une fonction père telle que le représentant est le père du père du père ... jusqu'à ce qu'il n'y ait plus de père. Le graphe obtenu est une forêt, dont les composantes connexes sont des arbres. Le représentant est alors la racine de l'arbre. L'arbre est défini récursivement par la fonction père :

• Tout nœud autre que la racine possède un unique père.
• Seule la racine n'a pas de père du tout.
• Les nœuds qui ne sont père de personne sont les feuilles de l'arbre.

class UnionFind():
    def __init__(self):
        self.dico = {}
    def makeSet(self,elt):
        if elt not in self.dico:
            self.dico[elt] = None
    def is_representative(self,elt):
        return elt in self.dico and self.dico[elt] is None
    def find(self,elt):
        if elt in self.dico:
            pere = elt
            while self.dico[pere] is not None:
                pere = self.dico[pere]
            return pere
        else:
            return None
    def union(self,e1,e2):
        r1 = self.find(e1)
        self.dico[r1] = e2

• Un représentant se reconnaît maintenant au fait qu'il n'a pas de père.
• La méthode find nécessite de remonter dans l'arbre jusqu'à sa racine, et sa complexité dépend de la hauteur de l'arbre.
• La méthode union ne nécessite qu'une greffe d'un arbre sur un autre (le second élément, celui sur lequel on greffe, devient le nouveau père du premier élément, celui qui se fait greffer ; ainsi le premier élément a pour représentant celui du second élément).

III/ Compression des chemins

1) Hauteur des arbres

On a vu que l'efficacité de l'implémentation par une forêt dépend de la hauteur des arbres. Or celle-ci dépend de l'ordre dans lequel ont été réalisées les opérations union.

a) Union de chacun au précédent

Si, chaque fois qu'un élément est ajouté à E, on l'unit au plus récent élément de la même classe, on retrouve une structure similaire à celle vue au I/1 : liste de liste. Les arbres sont unaires.

b) Union de chacun au représentant

Si par contre dès qu'on a ajouté un élément on l'unit tout de suite à son représentant, on retrouve la représentation du I/2 : tous les arbres sont de hauteur 1.

c) Exemple

Si on unit 8/16 à 4/8 avant d'unir 4/8 à 2/4 l'arbre de représentant 1/2 est de hauteur 3 :

Alors que si on unit 4/8 à 2/4 avant d'unir 8/16 à 4/8, l'arbre de représentant (racine) 1/2 a une hauteur 2 :

2) Compression des chemins dans les arbres

Voici la même partition, mais avec un ordre différent des opérations d'union :

Une première amélioration consiste à greffer, non pas sur le nœud sélectionné, mais sur son représentant :

    def union(self,e1,e2):
        r1 = self.find(e1)
        r2 = self.find(e2)
        self.dico[r1] = r2

on obtient alors cette nouvelle forêt, avec les mêmes unions successives :

Mais on peut aussi modifier la méthode find pour qu'en parcourant les nœuds à la recherche du représentant, elle en profite pour les faire adopter par le représentant :

    def find(self,elt):
        if elt in self.dico:
            pere = elt
            vus = [elt]
            while self.dico[pere] is not None:
                pere = self.dico[pere]
                vus.append(pere)
            for s in vus:
                if self.dico[s] is not None:
                    self.dico[s] = pere
            return pere
        else:
            return None

C'est un peu comme une mémoïsation (on stocke les nœuds parcourus) mais avec effet de bord (la racine devient père adoptif de tous les nœuds parcourus).

En fait la fonction find est récursive : si le nœud n'a pas de père il est son propre représentant, sinon on applique la fonction find à son père car ils ont le même représentant.

On obtient la forêt suivante, avec les conditions précédentes :

Pour faire des manipulations sur une forêt voir cette application en ligne.

3) Coût amorti

a) Principe

Le coût en temps n'est pas meilleur avec la représentation par forêt dans le pire cas : dans ce cas la hauteur de chaque arbre est égale à 1 de moins que sa taille et le coût dans le pire cas est linéaire. Or le pire cas est rare, et on dispose d'heuristiques permettant d'éviter le pire cas.

La modification de find ralentit cette méthode (puisqu'on y ajoute des instructions) mais au bénéfice de maintenir relativement bas le coût de union. C'est comme si on effectuait des dépenses prématurées et en apparence inutiles pour engranger des bénéfices par la suite. D'où le nom de coût amorti donné par Bob Tarjan en 1985.

Union Find est le troisième exemple donné par Bob Tarjan dans l'article fondateur sur le coût amorti.

b) Union par taille

Comme l'union n'est pas commutative, on a le choix entre

• unir A à B (le nouveau sous-ensemble est B)
• unir B à A comme ci-dessus.

On peut choisir d'unir l'arbre de hauteur la plus faible à celui de hauteur la plus grande. Le coût est modélisé par 1 de plus que la plus grande hauteur.