Connected Components Parallel Search

namespace graph { namespace distributed {
  template<typename Graph, typename ComponentMap>
  typename property_traits<ComponentMap>::value_type
  connected_components_ps(const Graph& g, ComponentMap c)
} }

Connected_components_ps()функция вычисляет связанные компоненты графа, выполняя поиск по ширине из нескольких источников параллельно, записывая и в конечном итоге разрешая столкновения.

Contents

Where Defined

<boost/graph/distributed/connected_components_parallel_search.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 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.

Complexity

O(PN^2 + VNP)работа, вO(N + V)время, где N — число отображений и V — число локальных вершин.

Algorithm Description

КаждыйNузлов начинает параллельный поиск с первой вершины в их локальном списке вершин во время первого супершага (другие узлы остаются бездействующими во время первого супершага, чтобы уменьшить количество конфликтов в нумерации компонентов). На каждом супершаге обрабатываются все новые отображения компонентов из удаленных узлов. Если работы от удаленных обновлений нет, из локального списка удаляется новая вершина и добавляется в очередь работы.

Компоненты выделяются из объектаcomponent_value_allocator, что обеспечивает уникальность данного номера компонента в системе, в настоящее время с помощью ранга и числа процессов для шага распределения.

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

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

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

Parallel BGL Connected Components Parallel Search

Boost , ,

Boost C++ Libraries

Connected Components Parallel Search

Where Defined

Parameters

Complexity

Algorithm Description