Connected Components
namespace graph {
// Default constructed ParentMap
template<typename Graph, typename ComponentMap, typename ParentMap>
typename property_traits<ComponentMap>::value_type
connected_components( const Graph& g, ComponentMap c);
// User supplied ParentMap
template<typename Graph, typename ComponentMap, typename ParentMap>
typename property_traits<ComponentMap>::value_type
connected_components( const Graph& g, ComponentMap c, ParentMap p);
}
Connected_components()функция вычисляет связанные компоненты ненаправленного графа. Алгоритм распределенных подключенных компонентов использует последовательную версию алгоритма подключенных компонентов для вычисления подключенных компонентов локального подграфа, а затем выполняет параллельную фазу алгоритма. Параллельная часть алгоритма связанных компонентов слабо основана на работе Годдарда, Кумара и Принса. Интерфейс представляет собой набор интерфейса для алгоритма BGLпоследовательных подключенных компонентов.
Перед выполнением последовательной фазы алгоритма каждый процесс идентифицирует корни его локальных компонентов. Затем в корневой вершине каждого компонента строится список смежности всех вершин, прилегающих к членам компонента.
Параллельная фаза алгоритма распределенных связанных компонентов состоит из серии супершагов. На каждом супершаге каждый корень пытается подключиться к члену его списка смежности, назначая его родительский указатель на эту вершину. Крюк ограничен вершинами, которые логически меньше текущей вершины, чтобы предотвратить зацикливание. Вертикали, которые крючок успешно удаляют из списка корней и помещают в другой список завершенных вершин. Все завершенные вершины теперь выполняют шаг прыжка указателя, пока каждая завершенная вершина не будет иметь в качестве своего родителя корень компонента. Этот шаг прыжка указателя может быть дополнительно оптимизирован добавлением правил сокращения цикла (CR), разработанных Джонсоном и Метаксасом, однако текущие оценки производительности показывают, что это окажет незначительное влияние на общую производительность алгоритма. Эти правила CR уменьшают количество шагов прыжка указателя сO(n)доO(log n). Следуя этому шагу прыжка указателя, корни, которые зацепились за эту фазу, передают свой список смежности своему новому родителю. Остальные корни получают эти края и выполняют обрезку на своих списках смежности, чтобы удалить вершины, которые теперь являются членами их компонента. Параллельная фаза алгоритма завершается, когда корень успешно не зацепляется. После завершения параллельной фазы на всех вершинах выполняется заключительный шаг прыжка указателя, чтобы назначить родительские указатели листьев исходных локальных компонентов подграфа их окончательному родителю, который теперь определен.
Единственным самым большим узким местом производительности в алгоритме распределенных подключенных компонентов является влияние плохого распределения вершин на алгоритм. Для разреженных графиков с одним большим компонентом многие корни могут зацепиться за один и тот же компонент, что приводит к серьезному дисбалансу нагрузки в процессе владения этим компонентом. Было реализовано несколько методов изменения стратегии крючкования, чтобы избежать этого поведения, но ни один из них не был успешным.
<boost/graph/connected_components.hpp>
- IN: Graph& g
- The graph typed must be a model of Distributed Graph.
- OUT: ComponentMap c
- The algorithm computes how many connected components are in the
graph, and assigns each component an integer label. The algorithm
then records to which component each vertex in the graph belongs by
recording the component number in the component property map. The
ComponentMap type must be a Distributed Property Map. The
value type must be the vertices_size_type of the graph. The key
type must be the graph's vertex descriptor type. If you do not wish
to compute component numbers, pass dummy_property_map as the
component map and parent information will be provided in the parent
map.
- UTIL: ParentMap p
- A parent map may be supplied to the algorithm, if not supplied the
parent map will be constructed automatically. The ParentMap type
must be a Distributed Property Map. The value type and key type
must be the graph's vertex descriptor type.
- OUT: property_traits<ComponentMap>::value_type
- The number of components found will be returned as the value type of
the component map.
Локальная фаза алгоритма составляетO(V + E). Параллельная фаза алгоритма требует максимумO(d)супершагов, гдеd— число начальных корней.дв лучшем случаеО(V), но становится значительно меньше по мере увеличенияЕ. Фаза прыжка указателя в пределах каждого супершага требует максимумO(c)шагов на каждом из завершенных корней, гдеcявляется длиной самого длинного цикла. Применение правил CR может уменьшить это доO(log c).
