Проверка union-find на Swift в облачном Mac

При офлайн-группировке контактов, связывании устройств и кластеризации изображений часто нужно определить, принадлежат ли два объекта одной группе. Если связи только добавляются и не удаляются, система непересекающихся множеств (union-find) подходит лучше, чем повторный обход всех связей. Если же требуется восстанавливать пути между объектами или часто отменять связи, следует сохранить исходный граф и использовать обход графа либо специализированную динамическую структуру. Этот код на чистом Swift можно включить в предварительные проверки на облачном Mac, чтобы обнаруживать ошибки группировки до запуска длительной сборки приложения.

Сначала определим входные данные и наблюдаемые результаты

В статье рассматриваются неориентированные связи с фиксированными номерами узлов 0..<n. На уровне бизнес-логики стабильные идентификаторы нужно заранее сопоставить с целыми числами. Использовать текущие позиции элементов в отображаемом массиве нельзя: после перестановки списка изменится идентичность объектов. Таблица соответствий и данные о связях должны относиться к одному снимку данных.

При проверке учитываются только три результата: связаны ли два узла, сколько компонент осталось и каков размер компоненты заданного узла. Повторные связи и петли не должны уменьшать число компонент. Счётчик уменьшается на один только при успешном объединении двух ранее несвязанных групп.

Корень — это деталь реализации, а не бизнес-идентификатор группы. При другом порядке ввода тех же связей представитель множества может измениться, но связность должна остаться прежней.

Недопустимые индексы следует отклонять на этапе импорта, записывая номер строки или идентификатор записи. В приведённой ниже реализации внутренние ограничения выражены через предусловия: молчаливое игнорирование некорректного ввода не считается обработкой ошибок.

Напишем реализацию, которую можно запускать отдельно

Сохраните следующий код в файл 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. Не передавайте один и тот же экземпляр нескольким параллельным задачам для изменения. Расчёт одной группировки можно выполнить внутри одной задачи, а по завершении выдать неизменяемый результат. Если используется обёртка на основе actor, пакет связей также следует обрабатывать за одну операцию без точек приостановки.

Проверим каждое объединение независимым обходом графа

Если проверять лишь несколько ожидаемых номеров корней, тесты легко могут повторить ошибку самой реализации. Более надёжный эталон — обход графа по спискам смежности: он не использует родительские указатели и не зависит от стратегии объединения. Добавьте следующий код в конец того же файла: он последовательно добавляет связи и после каждого шага проверяет все пары узлов.

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: этот режим удаляет проверки предусловий.

Как отдельно проверить сжатие путей

Правильная связность ещё не доказывает, что сжатие путей работает. В сборку, предназначенную только для тестов, можно добавить проверку глубины с доступом только на чтение: сначала построить многоуровневое дерево, выполнить запрос для глубоко расположенного узла, а затем убедиться, что он указывает непосредственно на корень. Не открывайте изменяемый массив родителей через бизнес-интерфейс ради тестирования.

Для проверки производительности используйте отдельный, более крупный набор данных и отдельно измеряйте первый и повторные запросы. Не включайте полный эталонный обход графа в замеры и не превращайте время в миллисекундах, полученное при одном запуске в облаке, в жёсткий порог для всех машин. Более стабильный критерий — сравнение числа обращений к родительским указателям.

Локализуем сбои по чётким границам

Неверное число компонент обычно означает, что счётчик уменьшается и при повторном объединении. Если размер компоненты завышен, сначала проверьте петли и повторные рёбра. Если после объединения часть узлов остаётся несвязанной, убедитесь, что изменяется родительский указатель корня, а не входного узла. Для каждого типа сбоя сохраняйте минимальную последовательность рёбер: с ней проще проводить регрессионные проверки, чем с большим массивом бизнес-данных.

На уровне ввода отдельно проверьте отрицательные номера, номер, равный общему числу узлов, и незарегистрированные идентификаторы. Все они должны отклоняться до попадания в структуру. Для пустого множества запросы к узлам недопустимы, но число компонент должно корректно возвращаться как ноль.

Наконец, явно обозначьте ограничения удаления связей. Сжатие путей теряет исходную структуру связей, поэтому «разорвать связь» изменением одного родительского указателя нельзя. При небольшом числе связей проще всего перестроить структуру по оставшимся рёбрам. Если нужен откат, потребуется отдельная реализация с журналом изменений и пересмотром стратегии сжатия путей. Проверка считается успешной, когда корректный ввод даёт правильное разбиение, некорректный ввод явно отклоняется, а неподдерживаемые операции не выдаются за успешно выполненные.

Часто задаваемые вопросы