Connected Components

template<typename Graph, typename ComponentMap>
inline typename property_traits<ComponentMap>::value_type
strong_components( const Graph& g, ComponentMap c);
namespace graph {
  template<typename Graph, typename VertexComponentMap>
  void
  fleischer_hendrickson_pinar_strong_components(const Graph& g, VertexComponentMap r);
  template<typename Graph, typename ReverseGraph,
           typename ComponentMap, typename IsoMapFR, typename IsoMapRF>
  inline typename property_traits<ComponentMap>::value_type
  fleischer_hendrickson_pinar_strong_components(const Graph& g,
                                                ComponentMap c,
                                                const ReverseGraph& gr,
                                                IsoMapFR fr, IsoMapRF rf);
}

сильные_компоненты()функция вычисляет сильно связанные компоненты направленного графа. Алгоритм распределенных сильных компонентов использует алгоритмпоследовательных сильных компонентовдля идентификации компонентов, локальных для процессора. Распределенная часть алгоритма построена на алгоритмераспределённой широты первого поискаи основана на работе Флейшера, Хендриксона и Пинара[FHP00].. Интерфейс представляет собой супернабор интерфейса для алгоритма BGLпоследовательных сильных компонентов. Количество сильно связанных компонентов в графе возвращается ко всем процессам.

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

Contents

Where Defined

<boost/graph/distributed/strong_components.hpp>

Также доступны из

<boost/graph/strong_components.hpp>

Parameters

IN: const Graph& g

The graph type must be a model of Distributed Graph. The graph type must also model the Incidence Graph and be directed.

OUT: ComponentMap c

The algorithm computes how many strongly 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.

UTIL: VertexComponentMap r

The algorithm computes a mapping from each vertex to the representative of the strong component, stored in this property map. The VertexComponentMap type must be a Distributed Property Map. The value and key types must be the vertex descriptor of the graph.

IN: const ReverseGraph& gr

The reverse (or transpose) graph of g, such that for each directed edge (u, v) in g there exists a directed edge (fr(v), fr(u)) in gr and for each edge (v', u') in gr there exists an edge (rf(u'), rf(v')) in g. The functions fr and rf map from vertices in the graph to the reverse graph and vice-verse, and are represented as property map arguments. The concept requirements on this graph type are equivalent to those on the Graph type, but the types need not be the same.

Default: Either a reverse_graph adaptor over the original graph (if the graph type is bidirectional, i.e., models the Bidirectional Graph concept) or a distributed adjacency list constructed from the input graph.

IN: IsoMapFR fr

A property map that maps from vertices in the input graph g to vertices in the reversed graph gr. The type IsoMapFR must model the Readable Property Map concept and have the graph's vertex descriptor as its key type and the reverse graph's vertex descriptor as its value type.

Default: An identity property map (if the graph type is bidirectional) or a distributed iterator_property_map (if the graph type is directed).

IN: IsoMapRF rf

A property map that maps from vertices in the reversed graph gr to vertices in the input graph g. The type IsoMapRF must model the Readable Property Map concept and have the reverse graph's vertex descriptor as its key type and the graph's vertex descriptor as its value type.

Default: An identity property map (if the graph type is bidirectional) or a distributed iterator_property_map (if the graph type is directed).

Complexity

Локальная фаза алгоритмаO(V + E). Параллельная фаза алгоритма требует максимумO(V)супершагов, каждый из которых содержит два первых поиска широты, которые являютсяO(V + E)каждый.

Algorithm Description

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

Параллельная фаза алгоритма распределенных сильных компонентов состоит из ряда супершагов. Каждый супершаг начинается с одного или нескольких наборов вершин, которые гарантированно содержат все оставшиеся сильные компоненты.Распределенная ширина первого поискавыполняется начиная с первой вершины в каждом наборе вершин. Все эти первые поиски по ширине выполняются параллельно, имея каждый вызов процессораbreadth_first_search()с различной начальной вершиной и при необходимости вставляя дополнительные вершины враспределеннуюочередь, используемую для первого поиска по ширине перед вызовом алгоритма. Второйраспределенный по ширине первый поисквыполняется на обратном графике таким же образом. Для каждого начального набора вершин вычисляется набор преемника (вершины, достигнутые в передней ширине первого поиска), и набор предшественника (вершины, достигнутые в задней ширине первого поиска). Пересечение наборов предшественника и преемника образует сильно связанный компонент, который обозначен как таковой. Остальные вершины в исходном наборе вершин разделены на три подмножества, каждое из которых гарантированно полностью содержит любые оставшиеся сильные компоненты. Эти три набора представляют собой вершины в наборе предшественника, не содержащиеся в идентифицированном сильно связанном компоненте, вершины в наборе преемника, не содержащиеся в сильно связанном компоненте, и оставшиеся вершины в исходном наборе вершины, не содержащиеся в наборах предшественника или преемника. Как только новые наборы вершин определены, алгоритм начинает новый супершаг. Алгоритм останавливается, когда не остается вершин.

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

Bibliography

[FHP00]

Лиза Флейшер, Брюс Хендриксон и Али Пинар. Идентификация сильно связанных компонентов параллельно. In Parallel and Distributed Processing (IPDPS), volume 1800 of Lecture Notes in Computer Science, pages 505--511, 2000. Спрингер.

Авторы: Ник Эдмондс, Дуглас Грегор и Эндрю Ламсдейн

Статья Parallel BGL Connected Components раздела может быть полезна для разработчиков на c++ и boost.

Parallel BGL Connected Components