Swift Union-Find auf einem Cloud-Mac testen

Bei der Offline-Gruppierung von Kontakten, der Zuordnung von Geräten und dem Clustering von Bildern stellt sich häufig die Frage: „Gehören diese beiden Objekte zur selben Gruppe?“ Wenn Verbindungen nur hinzukommen und nicht gelöscht werden, eignet sich Union-Find besser, als sämtliche Beziehungen immer wieder zu durchlaufen. Müssen dagegen Verbindungspfade nachvollziehbar bleiben oder Verbindungen häufig rückgängig gemacht werden, sollte der ursprüngliche Graph erhalten bleiben; dann sind eine Graphsuche oder spezielle dynamische Datenstrukturen die bessere Wahl. Wird diese reine Swift-Logik auf einem Cloud-Mac vor dem Build geprüft, lassen sich Gruppierungsfehler erkennen, bevor der zeitaufwendige App-Build beginnt.

Zuerst Eingaben und beobachtbare Ergebnisse festlegen

Dieser Artikel verwendet ungerichtete Verbindungen mit festen Knotennummern im Bereich 0..<n. Die Geschäftslogik muss stabile Kennungen zunächst auf Ganzzahlen abbilden. Die aktuelle Anzeigeposition im Array darf dafür nicht verwendet werden, denn sonst würde eine Umsortierung der Liste die Identität der Objekte verändern. Zuordnung und Verbindungsdaten müssen aus demselben Snapshot stammen.

Für die Abnahme zählen nur drei Ergebnisse: ob zwei Knoten verbunden sind, wie viele Zusammenhangskomponenten verbleiben und wie groß die Komponente eines bestimmten Knotens ist. Mehrfach eingefügte Verbindungen und Selbstschleifen dürfen die Komponentenzahl nicht verringern. Nur wenn zwei zuvor getrennte Gruppen tatsächlich vereinigt werden, sinkt die Zahl um eins.

Der Wurzelknoten ist ein Implementierungsdetail, keine fachliche Gruppenkennung. Bei derselben Menge von Verbindungen kann eine andere Eingabereihenfolge zu einem anderen Repräsentanten führen. Die Zusammenhangsrelation muss jedoch unverändert bleiben.

Ungültige Indizes müssen bereits beim Import abgewiesen werden; dabei sollte die Zeilennummer oder die Datensatzkennung protokolliert werden. Die folgende Implementierung drückt interne Bedingungen durch Vorbedingungen aus. Fehlerhafte Eingaben stillschweigend zu ignorieren, gilt hier nicht als Fehlertoleranz.

Eine eigenständig ausführbare Implementierung schreiben

Den folgenden Inhalt als union_find_check.swift speichern. Bei der Vereinigung nach Größe wird der kleinere Baum unter den größeren gehängt. Die Pfadkompression lässt die bei einer Abfrage durchlaufenen Knoten anschließend direkt auf die Wurzel zeigen. Größenangaben sind nur an der Wurzel gültig; beliebige Einträge aus sizes dürfen daher nicht direkt als Komponentengröße gelesen werden.

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

Da Abfragen die Pfade verändern, sind die Methoden als mutating deklariert. Dieselbe Instanz darf nicht direkt von mehreren nebenläufigen Tasks verändert werden. Stattdessen kann eine vollständige Gruppierungsberechnung innerhalb eines einzelnen Tasks erfolgen, der anschließend ein unveränderliches Ergebnis ausgibt. Auch bei einer Kapselung durch einen Actor sollte ein Stapel von Verbindungen innerhalb einer Operation ohne Suspendierungspunkte verarbeitet werden.

Jede Vereinigung mit einer Graphsuche gegenprüfen

Wer nur einige erwartete Wurzelnummern festlegt, riskiert, dass Test und Implementierung denselben Fehler enthalten. Eine zuverlässigere Referenz ist die Suche über eine Adjazenzliste: Sie verwendet weder Elternzeiger noch hängt sie von der Vereinigungsstrategie ab. Den folgenden Code am Ende derselben Datei ergänzen. Er fügt die Verbindungen einzeln hinzu und prüft nach jedem Schritt sämtliche Knotenpaare.

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)

Damit sind Vereinigungen getrennter Gruppen, wiederholte Verbindungen, isolierte Knoten und Selbstschleifen abgedeckt. Die Ausführung in umgekehrter Reihenfolge verlangt keine identischen Zwischenzustände. Vielmehr muss jeder Schritt zum jeweils aktuellen Graphen passen. Auch die endgültige Zerlegung muss unabhängig von der Eingabereihenfolge sein.

Bei kleinen Datenmengen bietet sich eine vollständige Gegenprüfung nach jedem Schritt an. Für große Datenmengen sollten zunächst auf kleinen Graphen sämtliche Kantenteilmengen geprüft werden, gefolgt von Stichproben mit festem Seed. Im Fehlerfall muss die vollständige Kantenfolge gespeichert werden, nicht nur der Zufalls-Seed: Auch der Generator oder die Erzeugungsregeln können sich ändern.

In die Prüfung vor dem Build einbinden und Korrektheit von Leistung trennen

Zunächst sicherstellen, dass auf dem ausführenden Knoten die benötigte Toolchain installiert ist. Anschließend im Verzeichnis des Skripts ausführen:

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

Wird das Skript regulär beendet, ist die Prüfung bestanden. Eine fehlgeschlagene Vorbedingung führt zu einem Exit-Status ungleich null. Skript und Testdaten gehören ins Repository; die Pipeline sollte unmittelbar den Exit-Status auswerten, statt lokalisierte Ausgaben zu parsen. Dieses Prüfprogramm darf nicht mit -Ounchecked kompiliert werden, da diese Option die Prüfungen der Vorbedingungen entfernt.

Pfadkompression gesondert prüfen

Korrekte Konnektivität beweist noch nicht, dass die Pfadkompression wirkt. In einem reinen Test-Build lässt sich eine schreibgeschützte Tiefenprüfung ergänzen: Zuerst wird ein mehrstufiger Baum aufgebaut, dann ein tief liegender Knoten abgefragt und anschließend geprüft, ob er direkt auf die Wurzel zeigt. Das Elternarray sollte nicht allein für Tests über die fachliche Schnittstelle schreibbar gemacht werden.

Leistungsprüfungen erfolgen separat mit größeren Eingaben. Dabei werden die erste Abfrage und wiederholte Abfragen getrennt erfasst. Die vollständige Graphsuche als Referenz darf nicht in die Zeitmessung einfließen. Ebenso wenig sollte der Millisekundenwert eines einzelnen Cloud-Durchlaufs als feste Grenze für alle Rechner dienen. Stabiler ist ein Vergleich der Anzahl von Zugriffen auf Elternzeiger.

Fehler auf klar abgegrenzte Ursachen eingrenzen

Eine falsche Komponentenzahl entsteht meist dadurch, dass auch bei einer wiederholten Vereinigung um eins heruntergezählt wird. Ist die Komponentengröße zu groß, sollten zuerst Selbstschleifen und doppelte Kanten geprüft werden. Bleiben nach einer Vereinigung einzelne Knoten unverbunden, ist zu prüfen, ob versehentlich der Elternzeiger eines Eingabeknotens statt derjenige einer Wurzel geändert wurde. Für jede Fehlerart eine minimale Kantenfolge aufzubewahren, erleichtert Regressionstests stärker als große Mengen fachlicher Daten.

Auf der Eingabeebene sind negative Nummern, eine Knotennummer gleich der Gesamtzahl der Knoten sowie nicht registrierte Kennungen gesondert zu testen. Sie müssen abgewiesen werden, bevor sie die Datenstruktur erreichen. Bei einer leeren Menge sind keine Knotenabfragen erlaubt; die Zahl der Komponenten muss jedoch regulär als null gemeldet werden.

Abschließend muss die Grenze beim Löschen klar sein: Durch Pfadkompression geht die ursprüngliche Verbindungsstruktur verloren. Eine Beziehung lässt sich daher nicht durch das Ändern eines einzelnen Elternzeigers „auflösen“. Bei wenigen Verbindungen ist ein Neuaufbau aus den verbleibenden Kanten am einfachsten. Wird Rollback benötigt, ist ein eigenständiger Entwurf mit Änderungsprotokoll erforderlich; dabei muss auch die Strategie zur Pfadkompression neu bewertet werden. Die Abnahme ist bestanden, wenn gültige Eingaben die richtige Zerlegung liefern, ungültige Eingaben eindeutig fehlschlagen und nicht unterstützte Operationen nicht als erfolgreich ausgegeben werden.

Häufig gestellte Fragen