Boost Disjoint множеств: как получить множества?

Question

Я пытаюсь использовать непересекающиеся множества из Boost, но, проплыв весь день через StackOverflow и документацию, я не смог решить мою проблему.

Основная проблема заключается в следующем: даны некоторые карты, которые будут действовать как рангРодитель, типа элемента int (хотя в будущем этот тип элемента должен быть указателем на фактический объект), и после выполнения некоторых union_set s, получить вектор векторов: каждый внешний вектор является номером связанного компонента,каждый внутренний вектор - список точек (или указателей), составляющих этот связанный компонент.

Например: v[1] -> [0, 30, 234, ...].

Я смотрел на это , this и this + несколько других вопросов здесь, в SO, и каждый результат на главной странице Google.

Я создал небольшой пример с использованием кода от пользователя @janoma.Тем не менее, его ответ, хотя и очень хороший, он «слишком настроен» для его нужд, и после некоторого перебора я не мог понять, как адаптировать его код для использования std::maps.

/*!
 * Adapted from
 *   http://janoma.cl/post/using-disjoint-sets-with-a-vector/?i=1
 *   https://github.com/janoma/study/blob/master/disjoint_sets/main.cpp
 *
 */

#include <algorithm>
#include <map>
#include <iomanip>
#include <iostream>
#include <stdlib.h>
#include <random>
#include <vector>

#include <boost/pending/disjoint_sets.hpp>
#include <boost/pending/property.hpp>

typedef int element_t;

void
printElements(std::vector<int>& elements, boost::disjoint_sets<boost::associative_property_map<std::map<int,int>>, boost::associative_property_map<std::map<int,int>>> sets)
{
    std::cout << "Elements:            ";
    for (size_t i = 0; i < elements.size(); ++i)
    {
        std::cout << std::setw(4) << elements[i];
    }
    std::cout << std::endl;
    std::cout << "Set representatives: ";
    for (size_t i = 0; i < elements.size(); ++i)
    {
        std::cout << std::setw(4) << sets.find_set(elements[i]);
    }
    std::cout << std::endl;
}

int main()
{
    // initialization
    std::vector<element_t> elements;
    elements.reserve(30);
    for (size_t i = 0; i < elements.capacity(); ++i)
    {
        elements.push_back(element_t(rand() % 90));
    }

    // disjoint sets
    std::map<element_t,int> rank;
    std::map<element_t,element_t> parent;

    boost::disjoint_sets<
        boost::associative_property_map<std::map<element_t,int>>,
        boost::associative_property_map<std::map<element_t,element_t>> > sets(
            boost::make_assoc_property_map(rank),
            boost::make_assoc_property_map(parent));

    // initialize disjoint sets
    for (size_t i = 0; i < elements.size(); ++i)
    {
        sets.make_set(elements.at(i));
    }

    // unions
    for (size_t i = 0; i < elements.size()/2; ++i)
    {
        // Union between this element and one randomly chosen from the rest
        size_t j = rand() % elements.size();
        sets.union_set(elements[i], elements[j]);
    }

    std::cout << "Found " << sets.count_sets(elements.begin(), elements.end()) << " sets:" << std::endl;
    printElements(elements,sets);

    // compression
    sets.compress_sets(elements.begin(), elements.end());

    // QUICK & DIRTY
    std::vector<element_t> representatives;
    representatives.reserve(30);
    for (size_t i = 0; i < elements.capacity(); ++i)
        representatives.push_back(sets.find_set(elements[i]));
    // ---

    std::cout << std::endl << "After path compression:" << std::endl;
    printElements(elements,sets);

    std::sort(elements.begin(),elements.end(), [representatives](auto lhs, auto rhs){ return representatives[lhs] < representatives[rhs]; });

    std::cout << std::endl << "After path compression and sorting:" << std::endl;
    printElements(elements,sets);
}

.ожидаемый результат будет последней частью, которую вы получите, если вы выполните код janoma , то есть:

Alternative, using iterators:
    Sorted set: 1 8 12 16 23 27 32 37 46 46 50 55 60 62 69 73 76 79 87 
    Sorted set: 23 36 
    Sorted set: 62 
    Sorted set: 13 25 25 52 67 69 71 80 

Фактический результат, ну, я не дошел до того, чтобы сломать егов отдельные списки, но:

After path compression and sorting:
Elements:              76  55  37  62  80  62  69  87  71  46  52  36  60  73  79  50  67  32  69  46  23   1   8  12  23  27  13  16  25  25
Set representatives:   76  55  37  62  80  62  50  87  71  55  52  36  60  55  55  50  52  87  50  55  55  87  50  60  55  50  52  50  52  52

Это неупорядочено.

На данный момент у меня нет ресурсов, чтобы продолжать искать / изучать, как правильно использовать расширенные непересекающиеся множества.