s-t Connectivity
namespace graph { namespace distributed {
template<typename DistributedGraph, typename ColorMap>
inline bool
st_connected(const DistributedGraph& g,
typename graph_traits<DistributedGraph>::vertex_descriptor s,
typename graph_traits<DistributedGraph>::vertex_descriptor t,
ColorMap color)
template<typename DistributedGraph>
inline bool
st_connected(const DistributedGraph& g,
typename graph_traits<DistributedGraph>::vertex_descriptor s,
typename graph_traits<DistributedGraph>::vertex_descriptor t)
template<typename DistributedGraph, typename ColorMap, typename OwnerMap>
bool
st_connected(const DistributedGraph& g,
typename graph_traits<DistributedGraph>::vertex_descriptor s,
typename graph_traits<DistributedGraph>::vertex_descriptor t,
ColorMap color, OwnerMap owner)
} }
Функция st_connected() определяет, существует ли путь от s до t в графе g. Если путь существует, функция возвращает истинное, в противном случае она возвращает ложное.
Этот алгоритм в настоящее время синхронизирован с уровнем , что означает, что все вершины на данном уровне дерева поиска будут обработаны (потенциально параллельно) до того, как будут обработаны любые вершины с последовательного уровня на дереве. Это не обязательно для правильности алгоритма, это скорее деталь реализации. Этот алгоритм может быть переписан полностью асинхронно с использованием триггеров, которые удаляют синхронизированное поведение.
<boost/graph/distributed/st_connected.hpp>
- IN: const DistributedGraph& g
- The graph type must be a model of Distributed Graph. The graph
type must also model the Incidence Graph.
IN: vertex_descriptor
IN: vertex_descriptor t
- UTIL/OUT: color_map(ColorMap color)
- The color map must be a Distributed Property Map with the same
process group as the graph g whose colors must monotonically
darken (white -> gray/green -> black). The default value is a
distributed two_bit_color_map.
- IN: OwnerMap owner
- The owner map must map from vertices to the process that owns them
as described in the GlobalDescriptor concept.
- OUT: bool
- The algorithm returns true if a path from s to t is
found, and false otherwise.
Этот алгоритм выполняет O(V + E) работает в супершагах d/2 + 1 BSP, где d - наименьшее расстояние от s до t. По всем супершагам будут передаваться сообщения постоянного размера O(E).
Алгоритм состоит из двух одновременных переходов по ширине от s и t соответственно. Алгоритм использует одну очередь для обоих обходов, причем обход от s обозначается записью серый на цветной карте, а обход от t обозначается записью зеленый. Метод обхода похож на поиск по ширине, за исключением того, что не называются точки события посетителя. Когда какой-либо процесс обнаруживает столкновение в двух проходах (путем попытки установить вершину gray в green или наоборот), он сигнализирует всем процессам о завершении на следующем супершаге, и все процессы возвращаются true. Если очереди на всех процессах пусты и столкновение не обнаружено, то все процессы заканчиваются и возвращаются ложно.
Copyright (C) 2009 Попечители Университета Индианы.
Авторы: Ник Эдмондс и Эндрю Ламсдейн
