クラウドMacでSwiftのUnion-Findを検証する

オフラインでの連絡先のグループ分け、デバイスの関連付け、画像のクラスタリングでは、「2つのオブジェクトが同じグループに属するか」を判定する場面がよくあります。接続が追加されるだけで削除されないなら、すべての関係を繰り返し探索するよりもUnion-Findが適しています。一方、接続経路の説明や頻繁な接続の取り消しが必要なら、元のグラフを保持し、グラフ探索や専用の動的データ構造を選ぶべきです。この純粋なSwiftのロジックをクラウドMacのビルド前チェックに組み込めば、時間のかかるアプリのビルドに進む前に、グループ分けの不具合を検出できます。

まず入力と観測可能な結果を定義する

この記事では無向の接続を扱い、ノード番号は 0..<n に固定します。アプリケーション側で、安定した識別子をあらかじめ整数に対応付けておきます。配列内の現在の表示位置を使ってはいけません。リストを並べ替えるだけで、オブジェクトの同一性が変わってしまうためです。識別子の対応表と接続データは、同じスナップショットに基づいている必要があります。

合否判定で確認するのは、2点が連結しているか、連結成分がいくつ残っているか、指定した点の連結成分のサイズはいくつか、の3点だけです。重複した接続や自己ループで成分数が減ってはいけません。それまで連結していなかった2つのグループの併合に成功した場合に限り、成分数を1減らします。

根は実装上の詳細であり、業務上のグループIDではありません。同じ接続の集合でも、入力順を変えると代表元が変わる場合があります。ただし、連結関係は変わってはいけません。

不正なインデックスは取り込み処理で拒否し、行番号またはレコードの識別子を記録します。以下の実装では、内部の制約を事前条件で表現します。不正な入力を黙って無視することは、エラーへの対処とは見なしません。

単独で実行できる実装を書く

次のコードを union_find_check.swift として保存します。サイズに基づく併合では、小さい木を大きい木につなぎます。経路圧縮では、探索で通ったノードが根を直接参照するようにします。サイズが有効なのは根だけなので、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]
    }
}

問い合わせでも経路を書き換えるため、メソッドには mutating を付けています。同じインスタンスを複数の並行タスクにそのまま渡して変更させないでください。1回のグループ分けを単一のタスク内で完結させ、完了後に変更不能な結果を出力する方法が使えます。actorでラップする場合も、一連の接続処理はサスペンションポイントを挟まない操作として完了させます。

グラフ探索で併合のたびに照合する

期待する根の番号をいくつか書くだけでは、テストと実装が同じ誤りを抱えやすくなります。より信頼できる比較対象は、隣接リストを使ったグラフ探索です。親への参照を使わず、併合戦略にも依存しません。次のコードを同じファイルの末尾に追加し、接続を1つずつ加えながら、すべてのノードの組み合わせを照合します。

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)

この例では、異なるグループの併合、重複した接続、孤立ノード、自己ループをまとめて確認しています。逆順での実行は、途中の状態まで同じになることを求めるものではありません。各段階で、その時点のグラフと結果が一致することを求めています。また、最終的なグループ分けは入力順に依存してはいけません。

小規模なデータなら、各段階での全件照合が適しています。大規模なデータを検証する場合は、まず小さなグラフで辺の部分集合を全列挙し、その後、シードを固定したサンプリングを行います。失敗時には乱数シードだけでなく、辺の列全体を保存してください。生成器や生成ルール自体が変わる可能性があるためです。

ビルド前チェックに組み込み、正しさと性能を分けて検証する

まず実行ノードに必要なツールチェーンがインストールされていることを確認し、スクリプトのあるディレクトリで次を実行します。

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

スクリプトが正常終了すれば合格です。事前条件に違反すると、終了ステータスは非ゼロになります。スクリプトとテストデータをリポジトリにコミットし、パイプラインでは終了ステータスをそのまま使います。ローカライズされた出力を解析する必要はありません。この検証プログラムを、事前条件のチェックを取り除く -Ounchecked でコンパイルしてはいけません。

経路圧縮を個別に検証するには

連結関係が正しいだけでは、経路圧縮が機能しているとは証明できません。テスト専用ビルドに、読み取り専用の深さチェックを追加する方法があります。まず複数階層の木を作り、深い位置にあるノードを問い合わせた後、そのノードが根を直接参照していることを確認します。テストのために、アプリケーション向けインターフェースから親配列を書き換えられるようにしてはいけません。

性能の検証には別の大きな入力を使い、初回の問い合わせと繰り返しの問い合わせを分けて記録します。比較用の全件グラフ探索を計測に含めてはいけません。また、クラウドで一度実行して得られたミリ秒単位の値を、すべてのマシンに共通する厳格なしきい値にしないでください。親への参照にアクセスした回数を比較するほうが、安定した検証になります。

不具合の切り分けポイントを明確にする

成分数がおかしい場合は、重複した併合でも数を1減らしていることがよくあります。成分のサイズが大きすぎる場合は、まず自己ループと重複辺を確認します。併合後も一部のノードが連結していない場合は、根の親への参照ではなく、入力ノードの親への参照を誤って変更していないかを確認します。不具合の種類ごとに最小の辺の列を残しておけば、大量の業務データを残すよりも回帰テストを行いやすくなります。

入力処理では、負の番号、ノード総数と等しい番号、未登録の識別子を別途テストし、データ構造に渡る前に拒否されることを確認します。空集合に対してノードを問い合わせることはできませんが、成分数は正常にゼロと報告される必要があります。

最後に、削除に関する限界を明確にします。経路圧縮では元の接続の形が失われるため、親への参照を1つ変更するだけで「関係を解除」することはできません。接続が少なければ、残った辺から再構築するのが最も簡単です。ロールバックが必要なら、変更ログを持つ別設計を採用し、経路圧縮の方針も見直す必要があります。合格の基準は、有効な入力から正しいグループ分けが得られること、不正な入力が明確に失敗すること、そして対応できない操作を成功したかのように扱わないことです。

よくある質問