Testing Swift Union-Find on a Cloud Mac

Offline contact grouping, device association, and image clustering often need to answer the same question: “Do these two objects belong to the same group?” When connections are only added, never removed, union-find is a better fit than repeatedly traversing every relationship. If you also need to explain the path between objects or frequently undo connections, keep the original graph and use graph traversal or a specialized dynamic data structure. Running this pure Swift logic as a pre-build check on a cloud Mac lets you catch grouping errors before starting a time-consuming app build.

Define the Inputs and Observable Results First

This article uses undirected connections, with node IDs fixed to 0..<n. The application layer must first map stable identifiers to integers. Do not use an item's current display position in an array: reordering the list would then change the object's identity. The mapping and connection data should come from the same snapshot.

Acceptance checks cover just three things: whether two nodes are connected, how many components remain, and the size of the component containing a given node. Duplicate connections and self-loops must not reduce the component count. The count decreases by one only when two previously disconnected groups are successfully merged.

A root node is an implementation detail, not a business-level group ID. Changing the input order of the same set of connections may change the representative node, but connectivity must remain the same.

Reject invalid indices at the import layer and log the line number or record identifier. The implementation below uses preconditions to express internal constraints; silently ignoring invalid input is not treated as fault tolerance.

Write a Standalone Implementation

Save the following as union_find_check.swift. Union by size attaches the smaller tree to the larger one, while path compression makes nodes visited during a query point directly to the root. Sizes are valid only at roots, so do not read arbitrary entries in 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]
    }
}

Queries rewrite paths, so the methods are marked mutating. Do not pass the same instance directly to multiple concurrent tasks for modification. Instead, run a grouping calculation within a single task and return immutable results when it finishes. If you wrap the structure in an actor, process each batch of connections in an operation that does not cross a suspension point.

Cross-Check Every Merge with Graph Traversal

Tests that assert only a few expected root IDs can easily share the same mistake as the implementation. Traversing an adjacency list provides a more reliable reference: it uses neither parent pointers nor the union strategy. Append the following code to the same file to add connections one at a time and check every pair of nodes.

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)

This covers merges between groups, duplicate connections, isolated nodes, and self-loops. Running the edges in reverse does not mean the intermediate states must match those of the forward run. Each step must match the graph as it exists at that point. The final partition should also be independent of input order.

For small datasets, a full comparison after every step is practical. For larger datasets, first exhaustively enumerate edge subsets on small graphs, then use sampling with a fixed seed. When a test fails, save the complete edge sequence, not just the random seed: the generator or its generation rules may change.

Add a Pre-Build Check and Separate Correctness from Performance

First confirm that the node has the required toolchain installed, then run the following from the directory containing the script:

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

A normal script exit means the check passed; a failed precondition produces a nonzero exit status. Commit the script and test data to the repository so the pipeline can use the exit status directly, without parsing localized output. Do not compile this acceptance check with -Ounchecked, which removes precondition checks.

Test Path Compression Separately

Correct connectivity does not prove that path compression is working. In a test-only build, add a read-only depth check: construct a tree with multiple levels, query a deeply nested node, and then verify that it points directly to the root. Do not expose a writable parent array through the application-facing API just to support testing.

Use a separate, larger input for performance checks, recording the first query and repeated queries separately. Keep the exhaustive graph-traversal reference out of the timed section. Nor should a millisecond measurement from a single cloud run become a hard threshold for every machine; comparing parent-pointer access counts is a more stable check.

Isolate Failures at Clear Boundaries

An incorrect component count usually means a duplicate union still decrements the count. If component sizes are too large, check self-loops and duplicate edges first. If some nodes remain disconnected after a merge, check whether the code changed an input node's parent pointer instead of a root's. Keeping a minimal edge sequence for each failure mode makes regression testing easier than retaining large amounts of application data.

Test the input layer separately with negative IDs, an ID equal to the total node count, and unregistered identifiers. Confirm that all are rejected before entering the data structure. An empty set must not allow node queries, but it should correctly report zero components.

Finally, make the deletion boundary explicit: path compression discards the original connection structure, so changing a single parent pointer cannot “remove a relationship.” When the number of connections is small, rebuilding from the remaining edges is the simplest approach. If rollback is required, use a separate design with a change log and reassess the path-compression strategy. Acceptance means valid input produces the correct partition, invalid input fails explicitly, and unsupported operations are never presented as successful.

Frequently asked questions