|
|
|
Boost Disjoint SetsBoost , ,
|
||||||||||||||||||||||||||||||||||||||||||
| Ранг | Должна быть модельReadWritePropertyMapс целочисленным типом значения и ключевым типом, равным типу элемента набора. |
| Родитель | Должна быть модельReadWritePropertyMapи тип ключа и значения такой же, как тип элемента набора. |
| FindCompress | должен быть одним из объектов функции нахождения репрезентативного и пути сжатия. |
Типичный шаблон использования дляdisjoint_setsможно увидеть вkruskal_minimum_spanning_tree()алгоритм. В этом примере мы называемссылку().вместоunion_set(), посколькуuиvбыли получены изfind_set()и, следовательно, уже являются представителями для их наборов.
...
disjoint_sets<Rank, Parent, FindCompress> dsets(rank, p);
for (ui = vertices(G).first; ui != vertices(G).second; ++ui)
dsets.make_set(*ui);
...
while ( !Q.empty() ) {
e = Q.front();
Q.pop();
u = dsets.find_set(source(e));
v = dsets.find_set(target(e));
if ( u != v ) {
*out++ = e;
dsets.link(u, v);
}
}
| Member | Description |
|---|---|
| disjoint_sets(Rank r, Parent p) | Конструктор. |
| disjoint_sets(const disjoint_sets&x) | Копировать конструктор. |
| шаблон void make_set(Element x) |
Создает однотонный набор, содержащий Элементх. |
| шаблон void link(Element x, Element y) |
Соединение двух множествпредставленоэлементомxиу. |
| шаблон void union_set(Element x, Element y) |
Соедините два множества, которыесодержатэлементыхиу. Это эквивалентноссылке (find_set(x),find_set(y)). |
| шаблон<класс Элемент> Элемент find_set(Элемент x) |
Возврат представителя для набора, содержащего элементx. |
| шаблон<класс ElementIterator> std::size_t count_sets(ElementIterator first, ElementIterator last) |
Возвращает количество разрозненных наборов. |
| шаблон<класс ElementIterator> void compress_sets(ElementIterator first, ElementIterator last) |
Расплющи дерево родителей так, чтобы родитель каждого элемента был его представителем. |
Сложность времениO(m alpha(m,n)), гдеalphaявляется функцией обратного Акермана,m— число операций разъединения (make_set(),find_set()иlink()иn— число элементов. Функцияальфарастет очень медленно, намного медленнее, чем функциялог.
disjoint_sets_with_storage<ID,InverseID,FindCompress>
Этот класс управляет хранением ранга и родительских свойств внутри. Хранилище находится в массивах, которые индексируются идентификатором элемента, следовательно, требование дляидентификатораифункторов InverseID. Ранговые и родительские свойства инициализируются во время строительства таким образом, что каждый элемент находится в наборе сам по себе (так что нет необходимости инициализировать объекты этого класса с функциейinitialize_incremental_components()). Этот класс особенно полезен при вычислении (динамических) связанных компонентов графаedge_list, который не обеспечивает место для хранения вершинных свойств.
| Parameter | Description | Default |
|---|---|---|
| ID | Должна быть модельReadablePropertyMap, которая отображает элементы в целые числа между 0 и N, общее количество элементов в наборах. | boost::identity_property_map |
| Инверсид | Должна быть модельReadablePropertyMap, которая отображает целые числа на элементы. | boost::identity_property_map |
| FindCompress | должен быть одним из объектов функции нахождения репрезентативного и пути сжатия. | representative_with_full_path_compression |
У этого класса есть все члены вdisjoint_sets, а также следующие члены.
disjoint_sets_with_storage(size_type n = 0,
ID id = ID(),
InverseID inv = InverseID())
Constructor.
template <class ElementIterator> void disjoint_sets_with_storage:: normalize_sets(ElementIterator first, ElementIterator last)This rearranges the representatives such that the representative of each set is the element with the smallest ID.
representative_with_path_halving<Parent>
Это функтор, который находит репрезентативную вершину для того же компонента, что и элементx. Во время прохождения по репрезентативному дереву, функтор также применяет технику сокращения пути вдвое, чтобы сократить высоту дерева.
Element operator()(Parent p, Element x)
representative_with_full_path_compression<Parent>
Это функтор, который находит репрезентативный элемент для множества, к которому принадлежит элементх.
Element operator()(Parent p, Element x)
Пересмотрено01 Декабря 200601 December, 2006[ORIG_END] -->
| Copyright © 2000 | Джереми Сик, Univ.of Notre Damejsiek@lsc.nd.edu] Ли-Куан Ли, Univ.of Notre Damellee1@lsc.nd.edu] Эндрю Лумсдейн, Univ.of Notre Damelums@lsc.nd.edu |
Распространяется по лицензии Boost Software License, версия 1.0. (См. сопроводительный файлLICENSE_1_0.txtили копию на) http://www.boost.org/LICENSE_1_0.txt)
Статья Boost Disjoint Sets раздела может быть полезна для разработчиков на c++ и boost.
:: Главная :: ::
реклама |