Tutoriel TypeScript : UnionFind

Dans cette vidéo je vous propose de découvrir une nouvelle structure de données : le "Union-Find" qui permet de travailler sur des groupes disjoint. Pour vous donner un cas concret j'ai créé sur mon site un système permettant de faire le lien entre mes vidéos et j'aimerais obtenir quelques informations sur certains de mes noeuds :

• Combien de formations concernent le backend
• Est-ce que 2 technologies sont dans la même catégorie
• Est-ce que j'ai des groupes orphelin

Pour répondre à cette question l'approche actuelle n'est pas idéal. En effet, j'ai représenté mes noeuds sous forme d'élément contenant un identifiant unique et les liaisons entre ces noeuds sont représentées de la manière suivante :

[
  {
    "source": "a",
    "target": "b"
  },
  {
    "source": "a",
    "target": "c"
  }
  // ...
]

Avec cette structure, pour savoir si 2 noeuds sont connectés ensemble on est obligé de parcourir tout le graph ce qui est peu efficace, surtout si le nombre de noeuds / liens commence à grandir. Et c'est là que le Union Find intervient.

Sommaire

00:00 Introduction
10:23 Optimisation : Compression de chemin
12:04 Optimisation : Groupement par taille
17:00 Cas concret
20:10 Conclusion

Méthodes de bases

Comme son nom l'indique l'objectif du Union Find est de fournir 2 méthodes qui permettront récupérer des informations sur le graph.

class UnionFind {

  // Renvoie le groupe auquel appartient le noeud en question
  find(id: ID): ID

  // Attache 2 noeuds ensemble
  union(id1: ID, id2: ID): boolean

}

Au niveau de l'implémentation, on va sauvegarder dans un dictionnaire (clef / valeur) les éléments et leur parent. Si un élément est son propre parent alors on considèrera qu'il à la racine du groupe auquel il appartient.

class UnionFind {

  private parents: Map<ID, ID>

  constructor(ids: ID[]) {
    // Initialement tous les noeuds sont à la racine
    this.parents = new Map(ids.map(id => [id, id]))
  }

}

Dans la méthode find, on cherchera à remonter à la racine

  find(id: ID) {
    const parentId = this.parents.get('id')
    // L'élément est son propre parent, on est à la racine
    if (parentId === id) {
      return id
    }
    // Sinon on remonte le parent du parent
    return this.find(parentId)
  }

Dans la méthode union, on attachera l'élément à la racine du groupe systématiquement.

  union(id1: ID, id2: ID): boolean {
    const group1 = this.find(id1)
    const group2 = this.find(id2)
    // Les noeuds sont déjà dans le même groupe
    if (group1 === goup2) {
      return false; // Cela indique qu'il y a une boucle dans le graph
    }
    // Un des groupes devient enfant de l'autre
    this.parents.set(group2, group1)
    return true;
  }

Avec cette structure si on souhaite savoir si 2 noeuds sont dans le même groupe, il suffit de vérifier si ils sont dans le même groupe.

  isConnected(id1: ID, id2: ID): boolean {
    return this.find(id1) === this.find(id2)
  }

Optimisations

Maintenant que l'on a le concept de base il y a 2 optimisations qui vont permettre de rendre ce type de structure performant quelque soit la taille du graph.

Compression des chemins

La première optimisation consiste à compresser les chemins lors de la méthode find() afin de limiter le nombre de noeuds à parcourir pour retrouver le groupe auquel appartient un noeud.

  find(id: ID) {
    const parentId = this.parents.get('id')
    if (parentId === id) {
      return id
    }
    // On définit la racine comme nouveau parent, pour une futur exploration plus rapide
    const root = this.find(parentId)
    this.parents.set(id, root)
    return root
  }

Union par taille / rang

La seconde optimisation consister à mieux choisir comment on unifie 2 groupes ensemble. Plutôt que de choisir arbitrairement, on va choisir de faire en sorte que le groupe le plus petit devienne enfant du groupe le plus grand.

class UnionFind {

  private parents: Map<ID, ID>
  private sizes: Map<ID, number>

  constructor(ids: ID[]) {
    this.parents = new Map(ids.map(id => [id, id]))
    // Tous les groupes commencent avec une taille de 1
    this.sizes = new Map(ids.map(id => [id, 1]))
  }

  union (id1: ID, id2: ID) {
    const root1 = this.find(id1);
    const root2 = this.find(id2);

    if (root1 === root2) {
      return false;
    }

    // On adapte le sens de l'union
    const size1 = this.sizes.get(root1) ?? 0;
    const size2 = this.sizes.get(root2) ?? 0;
    if (size1 < root2) {
      this.parents.set(root1, root2);
      this.sizes.set(root2, size2 + size1);
    } else {
      this.parents.set(root2, root1);
      this.sizes.set(root1, root1 + rank2);
    }

    return true;
  }
}

Cette optimisation permet en plus de connaître facilement la taille d'un groupe.

  size(id: ID) {
    return this.sizes.get(this.find(id)))
  }