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

Question

Мне нужно использовать boost :: disjoint_sets, но документация мне неясна. Может кто-нибудь объяснить, что означает каждый параметр шаблона, и, возможно, привести небольшой пример кода для создания disjoint_sets?

В соответствии с запросом я использую disjoint_sets для реализации автономного алгоритма наименее общих предков Тарьяна , т.е. тип значения должен быть vertex_descriptor.

Answer 1

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

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

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

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

В примере:

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*

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

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

Answer 2

disjoint_sets<Rank, Parent, FindCompress>

• Ранг PropertyMap используется для хранения размера набора (element -> std :: size_t).См. объединение по рангу
• Parent 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содержит несколько адаптеров, которые преобразуют обычно используемые структуры данных, которые реализуют операцию отображения, такие как встроенные массивы (указатели), итераторы и std :: map, чтобы иметь интерфейс карты свойств "

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

Answer 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> в C ++ 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/