3
\$\begingroup\$

This is my first C++ class, implementing union find. I’ve tested the implementation very shoddily by checking that unifying two points connects them, and that works. I did a first draft in Python and translated it to C++. I use two buffers to keep track of the traversed items instead of creating a vector each time. Unfortunately I can’t use size_type for the sizes that are used for vectors because that’d require a recursive type. I named the method unify since union is a keyword in C++. I have not tested for performance. I mostly did this by skimming reference materials, tutorials, and examples.

Is this code easy to read, correct, performant, idiomatic, or is there befuddling syntax, bugs, bottlenecks, idiosyncrasies?

#include <vector>
#include <optional>
#include <cstddef>
#include <utility>

class UnionFind {
    std::vector<std::optional<std::size_t>> parents;
    std::vector<std::size_t> crumbs_buf_a;
    std::vector<std::size_t> crumbs_buf_b;
    std::size_t group_count;
    
    std::pair<std::size_t, std::size_t> find_roots(std::size_t a, std::size_t b) {
        std::size_t current;
        std::optional<std::size_t> next;
        crumbs_buf_a[0] = a;
        current = a;
        int i;
        for (i = 1; (next = parents[current]); i++) {
            current = *next;
            crumbs_buf_a[i] = current;
        }
        crumbs_buf_b[0] = b;
        current = b;
        int j;
        for (j = 1; (next = parents[current]); j++) {
            current = *next;
            crumbs_buf_b[j] = current;
        }
        return {i, j};
    }
    
    public:
    UnionFind(std::size_t count) {
        std::optional<std::size_t> nothing = {};
        parents.resize(count, nothing);
        crumbs_buf_a.resize(count, 0);
        crumbs_buf_b.resize(count, 0);
        group_count = count;
    }
    
    bool unify(std::size_t a, std::size_t b) {
        auto [depth_a, depth_b] = find_roots(a, b);
        auto root_a = crumbs_buf_a[depth_a - 1];
        auto root_b = crumbs_buf_b[depth_b - 1];
        if (root_a != root_b) {
            if (depth_a > depth_b)
                for (std::size_t i = 0; i < depth_a; i++)
                    parents[crumbs_buf_a[i]] = root_b;
            else
                for (std::size_t i = 0; i < depth_b; i++)
                    parents[crumbs_buf_b[i]] = root_a;
            group_count--;
            return true;
        }
        return false;
    }
    
    std::size_t find(std::size_t a) {
        auto current = a;
        std::optional<std::size_t> next;
        while ((next = parents[current]))
            current = *next;
        return current;
    }
    
    bool connected(std::size_t a, std::size_t b) {
        return find(a) == find(b);
    }
    
    std::size_t get_group_count() {
        return group_count;
    }
    
    void extend(std::size_t additional = 1) {
        std::optional<std::size_t> nothing = {};
        parents.resize(parents.size() + additional, nothing);
        crumbs_buf_a.resize(crumbs_buf_a.size() + additional, 0);
        crumbs_buf_b.resize(crumbs_buf_b.size() + additional, 0);
        group_count += additional;
    }
};

I used this code to do rudimentary tests:

#include <random>
#include <algorithm>
#include <cassert>
#include <iostream>
#define COUNT 100

int main() {
    UnionFind uf(COUNT);
    std::vector<std::size_t> indices;
    indices.reserve(COUNT);
    for (std::size_t i = 0; i < COUNT; i++)
        indices.push_back(i);
    // mostly copied from https://en.cppreference.com/w/cpp/algorithm/random_shuffle example
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(indices.begin(), indices.end(), g);
    for (std::size_t i = 0; i < COUNT - 1; i++) {
        std::size_t ix_1 = indices[i];
        std::size_t ix_2 = indices[i + 1];
        uf.unify(ix_1, ix_2);
        assert(uf.connected(ix_1, ix_2));
        std::cout << ix_1 << ", " << ix_2 << '\n';
    }
    assert(uf.get_group_count() == 1);
}
\$\endgroup\$
3
  • \$\begingroup\$ Consider adding your test too, for added documentation and facilitating our own testsing. \$\endgroup\$ Commented Oct 11, 2023 at 13:04
  • 1
    \$\begingroup\$ This is unusual, typically the path-compression is in find. There are variants that do it in union however. Which variant is this supposed to be? Or is it just something fairly arbitrary? \$\endgroup\$
    – user555045
    Commented Oct 11, 2023 at 14:10
  • \$\begingroup\$ It arose from a misunderstanding. I have now learned that this is weird. \$\endgroup\$ Commented Oct 11, 2023 at 18:53

1 Answer 1

3
\$\begingroup\$

Honestly, it seems cumbersome.

First, using a std::size_t instead of a std::optional<std::size_t>, and making the roots their own parent, would half the needed memory.

Next, throwing away the additional buffers will reduce it to a third of that.

The interface need not change for that.

Rewriting the algorithm is simple enough:

// Internal use and if the structure is read-only
FindRoot (array, node):
    while array[node] != node:
        node = array[node]
    return node
// Internal use only
CompressPath (array, node, root):
    while array[node] != node:
        (node, array[node]) = (array[node], root)
    array[node] = root

// For finding pass just one node
Unify (array, nodes):
    root = array.size
    foreach node in nodes:
        root = min(root, FindRoot(array, node))
    foreach node in nodes:
        CompressPath(array, node, root)
    return root

CompressAllPaths(array):
    for node = 0; node < array.size; ++node:
        array[node] = array[array[node]]

Still, while it is good for amortized cost, it is terrible for worst case. For that, more intelligence in picking the new root is needed, wikipedia has a good overview.


Regarding your code:

  1. Only pass an element to .resize() if default-constructing is undesirable.
  2. Avoid the preprocessor, a constexpr constant is generally better.
\$\endgroup\$
9
  • \$\begingroup\$ Which variant of union-find is this? It's still something unusual \$\endgroup\$
    – user555045
    Commented Oct 11, 2023 at 14:16
  • 1
    \$\begingroup\$ Not really unusual. FindRoot is the same as yours, roots are marked by self-reference instead of absent parent, and the crumbs are replaced by a second trace of the path. \$\endgroup\$ Commented Oct 11, 2023 at 14:47
  • \$\begingroup\$ Well, not mine but OPs.. and doing a second trace is not unusual, but doing path-compression in unify instead of in find is unusual. There is a variant described by Norbert Blum that works that way (I don't know if it works this specific way, but it does have path-compression in unify), but it's not what you'll typically see. \$\endgroup\$
    – user555045
    Commented Oct 11, 2023 at 14:50
  • \$\begingroup\$ @harold unify is the only one which should be public, just call with a single node... Recursion in find to compress the path would risk stackoverflow. \$\endgroup\$ Commented Oct 11, 2023 at 14:55
  • 3
    \$\begingroup\$ Ok I don't feel like that is a reply to anything I wrote, but I'll take it under advisement. I mean, the usual way to implement union-find, which neither OP nor your code implements, is using path-compression in find, and then unify doesn't need to do it. \$\endgroup\$
    – user555045
    Commented Oct 11, 2023 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.