Понимание boost:: disjoint_sets

Ответ 1

Что я могу понять из документации:

Disjoint необходимо связать ранг и родительский элемент (в дереве леса) с каждым элементом. Так как вы можете работать с любыми данными, вы можете, например, не всегда хотеть использовать карту для родителя: с целым массивом достаточно. Вы также нуждаетесь в ранге каждого элемента (ранг, необходимый для объединения-поиска).

Вам понадобятся два "свойства":

• чтобы связать целое число с каждым элементом (аргумент первого шаблона), ранг
• чтобы связать элемент с другим (второй аргумент шаблона), отцы

На примере:

std::vector<int>  rank (100);
std::vector<int>  parent (100);
boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]);

Массивы используются &rank[0], &parent[0] для типа в шаблоне int*

Для более сложного примера (с использованием карт) вы можете посмотреть ответ Уго.

Вы просто предоставляете алгоритму две структуры для хранения данных (ранга/родителя), которые ему нужны.

Ответ 2

disjoint_sets<Rank, Parent, FindCompress>

• Ранг PropertyMap используется для хранения размера набора (element → std:: size_t). См. объединение по рангам
• Родительский PropertyMap используется для хранения родительского элемента (element → element). См. Путь сжатия
• FindCompress Дополнительный аргумент, определяющий метод поиска. По умолчанию find_with_full_path_compression Смотрите здесь (по умолчанию должно быть то, что вам нужно).

Пример:

template <typename Rank, typename Parent>
void algo(Rank& r, Parent& p, std::vector<Element>& elements)
{
 boost::disjoint_sets<Rank,Parent> dsets(r, p);
 for (std::vector<Element>::iterator e = elements.begin();
      e != elements.end(); e++)
  dsets.make_set(*e);
  ...
}

int main()
{
  std::vector<Element> elements;
  elements.push_back(Element(...));
  ...

  typedef std::map<Element,std::size_t> rank_t; // => order on Element
  typedef std::map<Element,Element> parent_t;
  rank_t rank_map;
  parent_t parent_map;

  boost::associative_property_map<rank_t>   rank_pmap(rank_map);
  boost::associative_property_map<parent_t> parent_pmap(parent_map);

  algo(rank_pmap, parent_pmap, elements);
}

Обратите внимание: "Библиотека свойств Boost Properties содержит несколько адаптеров, которые преобразуют обычно используемые структуры данных, которые реализуют операцию сопоставления, такую ​​как встроенные массивы (указатели), итераторы и std:: map, чтобы иметь интерфейс карты свойств"

Этот список этих адаптеров (например, boost:: associative_property_map) можно найти здесь.

Ответ 3

Для тех из вас, кто не может позволить себе накладные расходы std::map (или не может использовать его, потому что у вас нет конструктора по умолчанию в вашем классе), но данные которого не так просты, как int, Я написал руководство к решению с помощью std::vector, которое является оптимальным, когда вы знаете общее количество элементов заранее.

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

Решение, упомянутое здесь, предполагает, что вы контролируете код класса, чтобы в частности вы могли добавить некоторые атрибуты. Если это все еще невозможно, вы всегда можете добавить вокруг него обертку:

class Wrapper {
    UntouchableClass const& mInstance;
    size_t dsID;
    size_t dsRank;
    size_t dsParent;
}

Кроме того, если вы знаете, что количество элементов невелик, нет необходимости в size_t, и в этом случае вы можете добавить шаблон для типа UnsignedInt и решить во время выполнения его экземпляр с помощью uint8_t, uint16_t, uint32_t или uint64_t, которые вы можете получить с помощью <cstdint> в С++ 11 или с помощью boost::cstdint в противном случае.

template <typename UnsignedInt>
class Wrapper {
    UntouchableClass const& mInstance;
    UnsignedInt dsID;
    UnsignedInt dsRank;
    UnsignedInt dsParent;
}

Здесь ссылка снова, если вы ее пропустили: http://janoma.cl/post/using-disjoint-sets-with-a-vector/