Tester union-find en Swift sur un Mac distant

Le regroupement de contacts hors ligne, l’association d’appareils et le regroupement d’images posent souvent la même question : « Ces deux objets appartiennent-ils au même groupe ? » Si les liens ne font que s’ajouter, sans jamais être supprimés, une structure union-find est plus adaptée que des parcours répétés de l’ensemble des relations. En revanche, s’il faut aussi expliquer le chemin qui relie deux objets ou annuler fréquemment des liens, mieux vaut conserver le graphe d’origine et utiliser des parcours de graphe ou une structure dynamique spécialisée. Intégrer cette logique en Swift pur aux vérifications préalables à la compilation sur un Mac distant permet de détecter les erreurs de regroupement avant de lancer une compilation d’application coûteuse en temps.

Définir les entrées et les résultats observables

Cet article utilise des liens non orientés et des nœuds dont les identifiants sont fixés à 0..<n. La couche métier doit d’abord associer les identifiants stables à des entiers. Il ne faut pas utiliser la position d’affichage actuelle dans un tableau : un réordonnancement de la liste changerait alors l’identité des objets. La table de correspondance et les données de liaison doivent provenir du même instantané.

La validation ne porte que sur trois éléments : la connexité de deux nœuds, le nombre de composantes connexes restantes et la taille de la composante contenant un nœud donné. Ni les liens répétés ni les boucles sur un même nœud ne doivent réduire le nombre de composantes. Ce nombre ne diminue de un que lorsque deux groupes auparavant disjoints sont effectivement fusionnés.

La racine est un détail d’implémentation, pas un identifiant de groupe métier. Pour un même ensemble de liens, un ordre d’insertion différent peut changer le représentant choisi, mais les relations de connexité doivent rester identiques.

Les indices invalides doivent être rejetés par la couche d’importation, avec consignation du numéro de ligne ou de l’identifiant de l’enregistrement. L’implémentation ci-dessous exprime ses contraintes internes au moyen de préconditions ; ignorer silencieusement des entrées erronées ne constitue pas une stratégie de tolérance aux erreurs.

Écrire une implémentation exécutable de façon autonome

Enregistrez le contenu suivant dans union_find_check.swift. L’union par taille rattache le plus petit arbre au plus grand, tandis que la compression de chemin fait pointer directement vers la racine les nœuds traversés lors d’une recherche. La taille n’est valide qu’à la racine : il ne faut pas lire directement une entrée quelconque de sizes.

struct UnionFind {
    private var parent: [Int]
    private var sizes: [Int]
    private(set) var components: Int

    init(_ count: Int) {
        precondition(count >= 0)
        parent = Array(0..<count)
        sizes = Array(repeating: 1, count: count)
        components = count
    }

    mutating func root(_ node: Int) -> Int {
        precondition(parent.indices.contains(node))
        var r = node
        while parent[r] != r {
            r = parent[r]
        }
        var current = node
        while parent[current] != current {
            let next = parent[current]
            parent[current] = r
            current = next
        }
        return r
    }

    @discardableResult
    mutating func union(_ a: Int, _ b: Int) -> Bool {
        var ra = root(a)
        var rb = root(b)
        guard ra != rb else { return false }
        if sizes[ra] < sizes[rb] {
            swap(&ra, &rb)
        }
        parent[rb] = ra
        sizes[ra] += sizes[rb]
        components -= 1
        return true
    }

    mutating func connected(_ a: Int, _ b: Int) -> Bool {
        let ra = root(a)
        let rb = root(b)
        return ra == rb
    }

    mutating func size(of node: Int) -> Int {
        let r = root(node)
        return sizes[r]
    }
}

Les recherches modifient les chemins, d’où le marquage des méthodes avec mutating. Ne confiez pas directement la même instance à plusieurs tâches concurrentes susceptibles de la modifier. Vous pouvez effectuer tout un calcul de regroupement dans une seule tâche, puis produire un résultat immuable. Si vous encapsulez la structure dans un actor, traitez également chaque lot de liens dans une opération qui ne traverse aucun point de suspension.

Vérifier chaque fusion par un parcours de graphe indépendant

Se contenter de quelques identifiants de racine attendus risque de reproduire la même erreur dans le test et dans l’implémentation. Un parcours de listes d’adjacence fournit une référence plus fiable : il n’utilise pas de pointeurs parents et ne dépend pas de la stratégie de fusion. Ajoutez le code suivant à la fin du même fichier pour insérer les liens un à un et vérifier toutes les paires de nœuds.

func reachable(_ start: Int, in graph: [[Int]]) -> Set<Int> {
    var seen: Set<Int> = [start]
    var stack = [start]
    while let node = stack.popLast() {
        for next in graph[node] {
            if seen.insert(next).inserted {
                stack.append(next)
            }
        }
    }
    return seen
}

func verify(_ edges: [(Int, Int)], count: Int) {
    var uf = UnionFind(count)
    var graph = Array(repeating: [Int](), count: count)

    for (a, b) in edges {
        let expectedMerge = !reachable(a, in: graph).contains(b)
        precondition(uf.union(a, b) == expectedMerge)
        graph[a].append(b)
        graph[b].append(a)

        var unseen = Set(0..<count)
        var expectedComponents = 0
        for node in 0..<count {
            let group = reachable(node, in: graph)
            if unseen.contains(node) {
                expectedComponents += 1
                unseen.subtract(group)
            }
            precondition(uf.size(of: node) == group.count)
            for other in 0..<count {
                precondition(
                    uf.connected(node, other) == group.contains(other)
                )
            }
        }
        precondition(uf.components == expectedComponents)
    }
}

let edges = [(0, 1), (2, 3), (1, 2), (0, 3), (4, 4)]
verify(edges, count: 6)
verify(Array(edges.reversed()), count: 6)
precondition(UnionFind(0).components == 0)

Ces tests couvrent à la fois la fusion de groupes distincts, les liens répétés, les nœuds isolés et les boucles. L’exécution dans l’ordre inverse n’impose pas des états intermédiaires identiques : elle exige que chaque étape corresponde au graphe tel qu’il existe à cet instant. La partition finale doit, elle aussi, être indépendante de l’ordre des entrées.

Pour de petits jeux de données, une vérification exhaustive à chaque étape convient bien. Pour les volumes plus importants, commencez par énumérer tous les sous-ensembles d’arêtes sur de petits graphes, puis procédez par échantillonnage avec une graine fixe. En cas d’échec, conservez la séquence complète des arêtes, et pas seulement la graine aléatoire : le générateur ou les règles de génération peuvent eux aussi évoluer.

Intégrer le contrôle avant compilation et séparer correction et performances

Vérifiez d’abord que la chaîne d’outils requise est installée sur le nœud, puis exécutez les commandes suivantes depuis le répertoire du script :

set -eu
xcrun swift --version
xcrun swift union_find_check.swift

Une fin d’exécution normale indique que le contrôle a réussi ; l’échec d’une précondition produit un code de sortie non nul. Versionnez le script et les données de test dans le dépôt afin que le pipeline exploite directement le code de sortie, sans devoir analyser des messages localisés. Ne compilez pas ce programme de validation avec -Ounchecked, qui supprime les vérifications de préconditions.

Valider séparément la compression de chemin

Une connexité correcte ne prouve pas que la compression de chemin fonctionne. Dans une compilation réservée aux tests, vous pouvez ajouter une inspection de profondeur en lecture seule : construisez d’abord un arbre à plusieurs niveaux, recherchez un nœud profond, puis vérifiez qu’il pointe directement vers la racine. N’exposez pas un tableau de parents modifiable dans l’interface métier uniquement pour faciliter les tests.

Les tests de performances doivent utiliser séparément des entrées plus volumineuses et mesurer la première recherche puis les recherches répétées. N’incluez pas le parcours exhaustif du graphe de référence dans les mesures. N’imposez pas non plus à toutes les machines un seuil strict fondé sur le nombre de millisecondes observé lors d’une seule exécution distante ; comparer le nombre d’accès aux pointeurs parents fournit un contrôle plus stable.

Localiser les échecs à des frontières précises

Un nombre de composantes incorrect vient souvent d’un décrément effectué même lors d’une fusion répétée. Si la taille d’une composante est trop élevée, vérifiez d’abord les boucles et les arêtes en double. Si certains nœuds restent déconnectés après une fusion, vérifiez que le code n’a pas modifié le pointeur parent du nœud fourni en entrée au lieu de celui de sa racine. Conserver une séquence minimale d’arêtes pour chaque type de défaut facilite davantage les tests de non-régression que garder de grandes quantités de données métier.

Testez séparément, au niveau de la couche d’entrée, les nombres négatifs, les identifiants égaux au nombre total de nœuds et les identifiants non enregistrés. Assurez-vous qu’ils sont rejetés avant d’atteindre la structure. Un ensemble vide ne permet aucune recherche de nœud, mais doit signaler normalement zéro composante.

Enfin, définissez clairement les limites concernant la suppression : la compression de chemin fait perdre la forme des liens d’origine. Modifier un seul pointeur parent ne permet donc pas de « supprimer une relation ». Lorsque le nombre de liens reste faible, le plus simple est de reconstruire la structure à partir des arêtes restantes. Si un retour arrière est nécessaire, il faut une conception distincte avec un journal des modifications et réévaluer la stratégie de compression de chemin. La validation est réussie lorsque les entrées valides produisent la bonne partition, que les entrées invalides provoquent un échec explicite et que les opérations non prises en charge ne sont pas présentées comme réussies.

Questions fréquentes