Implementatie met gelinkte lijsten voor disjoint sets (C++)

[MartenBE]

Hallo iedereen,

Voor mijn hobbyproject algoritmen in C++ ( https://gitlab.com/MartenBE/varia , staat in kinderschoenen) heb ik een poging gedaan om disjoint sets ( Wikipedia: Disjoint-set data structure ) te implementeren met gelinkte lijsten. In CLRS [1] maken ze gebruik van pointers bij elk element in een node in een gelinkte lijst om snel het representatief element voor de set te kunnen vinden. Alleen zou ik niet goed weten hoe ik dit in mijn code kan implementeren: als je een refentie hebt naar het element, heb kan je toch nog steeds niet aan de pointer in de node? Ik heb nu gezeurd met een unordered_map, aangezien deze ook in O(1) dingen kan ophalen, maar zou graag weten hoe ik deze kan weglaten. Helaas vind ik online niet zo veel concrete implementaties hierover terug.

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd. ed.). The MIT Press.

https://gitlab.com/Marten...int-sets-linked-lists.hpp

C++:

#ifndef DISJOINT_SETS_HPP
#define DISJOINT_SETS_HPP

#include <list>
#include <memory>
#include <unordered_set>
#include <unordered_map>

template <class T>
class disjoint_sets
{
private:
    using disjoint_set = std::list<T>;

public:
    void make_set(const T& member)
    {
        std::unique_ptr<disjoint_set> new_disjoint_set = std::make_unique<disjoint_set>();
        new_disjoint_set->push_back(member);
        m_member_to_disjoint_set[member] = new_disjoint_set.get();

        m_sets.insert(std::move(new_disjoint_set));

        m_amount_sets++;
    }

    void make_union(const T& member1, const T& member2)
    {
        disjoint_set* member1_disjoint_set = m_member_to_disjoint_set[member1];
        disjoint_set* member2_disjoint_set = m_member_to_disjoint_set[member2];

        assert(member1_disjoint_set);
        assert(member2_disjoint_set);

        if (member1_disjoint_set == member2_disjoint_set)
        {
            return;
        }

        if (member2_disjoint_set->size() > member1_disjoint_set->size()) // Weighted-union heuristic
        {
            swap(member1_disjoint_set, member2_disjoint_set);
        }

        for (const T& m : *member1_disjoint_set)
        {
            m_member_to_disjoint_set[m] = member2_disjoint_set;
        }

        member2_disjoint_set->splice(member2_disjoint_set->end(), *member1_disjoint_set);

        m_amount_sets--;
    }

    T& find_set(const T& member) const
    {
        return m_member_to_disjoint_set.at(member)->front();
    }

    ptrdiff_t amount_sets() const
    {
        return m_amount_sets;
    }

private:
    std::unordered_set<std::unique_ptr<disjoint_set>> m_sets;
    std::unordered_map<T, disjoint_set*> m_member_to_disjoint_set;
    ptrdiff_t m_amount_sets{0};
};

#endif

https://gitlab.com/Marten...ts/disjoint-sets-test.cpp

code:

#include "catch2/catch.hpp"

#include "disjoint-sets.hpp"

TEST_CASE("Find connected components using disjoint sets (example CLRS)")
{
    disjoint_sets<char> ds;

    ds.make_set('a');
    ds.make_set('b');
    ds.make_set('c');
    ds.make_set('d');
    ds.make_set('e');
    ds.make_set('f');
    ds.make_set('g');
    ds.make_set('h');
    ds.make_set('i');
    ds.make_set('j');

    ds.make_union('b', 'd');
    ds.make_union('e', 'g');
    ds.make_union('a', 'c');
    ds.make_union('h', 'i');
    ds.make_union('a', 'b');
    ds.make_union('e', 'f');
    ds.make_union('b', 'c');

    SECTION("Union")
    {
        // {{'a', 'b', 'c', 'd'}, {'e', 'f', 'g'}, {'h', 'i'}, {'j'}}

        REQUIRE(ds.find_set('a') == ds.find_set('a'));
        REQUIRE(ds.find_set('b') == ds.find_set('a'));
        REQUIRE(ds.find_set('c') == ds.find_set('a'));
        REQUIRE(ds.find_set('d') == ds.find_set('a'));
        REQUIRE(ds.find_set('e') == ds.find_set('e'));
        REQUIRE(ds.find_set('f') == ds.find_set('e'));
        REQUIRE(ds.find_set('g') == ds.find_set('e'));
        REQUIRE(ds.find_set('h') == ds.find_set('h'));
        REQUIRE(ds.find_set('i') == ds.find_set('h'));
        REQUIRE(ds.find_set('j') == ds.find_set('j'));
    }

    SECTION("Amount sets")
    {
        REQUIRE(ds.amount_sets() == 4);
    }

    SECTION("Weighted-union heuristic")
    {
        ds.make_union('e', 'd');

        // {{'a', 'b', 'c', 'd', 'e', 'f', 'g'}, {'h', 'i'}, {'j'}}

        REQUIRE(ds.find_set('a') == ds.find_set('a'));
        REQUIRE(ds.find_set('b') == ds.find_set('a'));
        REQUIRE(ds.find_set('c') == ds.find_set('a'));
        REQUIRE(ds.find_set('d') == ds.find_set('a'));
        REQUIRE(ds.find_set('e') == ds.find_set('a'));
        REQUIRE(ds.find_set('f') == ds.find_set('a'));
        REQUIRE(ds.find_set('g') == ds.find_set('a'));
        REQUIRE(ds.find_set('h') == ds.find_set('h'));
        REQUIRE(ds.find_set('i') == ds.find_set('h'));
        REQUIRE(ds.find_set('j') == ds.find_set('j'));
    }
}