Function build_equivalent_groups

cpp_core/src/symmetry.cpp:152–190

Union-find for equivalent groups

// Union-find for equivalent groups
std::vector<std::vector<int>> build_equivalent_groups(
    const std::vector<std::vector<int>>& all_perms,
    int n_atoms
) {
    std::vector<int> parent(n_atoms);
    std::iota(parent.begin(), parent.end(), 0);

    std::function<int(int)> find = [&](int x) -> int {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };

    auto unite = [&](int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) parent[rb] = ra;
    };

    for (const auto& perm : all_perms) {
        for (int i = 0; i < static_cast<int>(perm.size()); ++i) {
            unite(i, perm[i]);
        }
    }

    std::map<int, std::vector<int>> groups;
    for (int i = 0; i < n_atoms; ++i) {
        groups[find(i)].push_back(i);
    }

    std::vector<std::vector<int>> result;
    result.reserve(groups.size());
    for (auto& [_, g] : groups) {
        std::sort(g.begin(), g.end());
        result.push_back(std::move(g));
    }
    return result;
}

// Positive modulo: ((x % n) + n) % n — always returns [0, n)
int posmod(int x, int n) {