deep_first_visit()функция выполняет распределенное прохождение по глубине ненаправленного графа с использованием поправок Цина[Цин02]Алгоритм Сидона[Сидон88]. Распределенный DFS синтаксически похож на егопоследовательный аналог, который обеспечивает дополнительный фон и обсуждение. Здесь выделены различия в семантике, и мы отсылаем читателя к документации последовательного поиска по глубинедля остальных деталей. Посетители, прошедшие поиск по глубине, должны учитывать распределение вершин между процессами, потому что события будут запускаться на определенных процессах, а не на других. См. разделТочки событий посетителейПодробности.
Where Defined
<boost/graph/distributed/depth_first_search.hpp>
Также доступно в
<boost/graph/depth_first_search.hpp>
Parameters
IN: constGraph&g
The graph type must be a model of Distributed Graph. The graph
must be undirected.
IN: vertex_descriptors
The start vertex must be the same in every process.
IN: DFSVisitorvis
The visitor must be a distributed DFS visitor. The suble differences
between sequential and distributed DFS visitors are discussed in the
section Visitor Event Points.
IN: VertexIndexMapmap
A model of Readable Property Map whose key type is the vertex
descriptor type of the graph g and whose value type is an
integral type. The property map should map from vertices to their
(local) indices in the range [0, num_vertices(g)).
Default: get(vertex_index,g)
UTIL/OUT: ColorMapcolor
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 -> black).
Default: A distributed iterator_property_map created from a
std::vector of default_color_type.
UTIL/OUT: ParentMapparent
The parent map must be a Distributed Property Map with the same
process group as the graph g whose key and values types are the
same as the vertex descriptor type of the graph g. This
property map holds the parent of each vertex in the depth-first
search tree.
Default: A distributed iterator_property_map created from a
std::vector of the vertex descriptor type of the graph.
UTIL: ExploreMapexplore
The explore map must be a Distributed Property Map with the same
process group as the graph g whose key and values types are the
same as the vertex descriptor type of the graph g.
Default: A distributed iterator_property_map created from a
std::vector of the vertex descriptor type of the graph.
UTIL: NextOutEdgeMapnext_out_edge
The next out-edge map must be a Distributed Property Map with the
same process group as the graph g whose key type is the vertex
descriptor of the graph g and whose value type is the
out_edge_iterator type of the graph. It is used internally to
keep track of the next edge that should be traversed from each
vertex.
Default: A distributed iterator_property_map created from a
std::vector of the out_edge_iterator type of the graph.
Complexity
Глубина первого поиска по своей сути последовательна, поэтому параллельное ускорение очень плохо. Независимо от количества процессоров, алгоритм не будет быстрее, чемO(V); см.[Tsin02]для более подробной информации.
Visitor Event Points
КонцепцияDFS Visitorопределяет 8 точек событий, которые будут вызваныпоследовательным поиском по глубине. Распределенный DFS сохраняет эти точки событий, но последовательность событий и процесс, в котором происходит каждое событие, будут меняться в зависимости от распределения графика.
initialize_vertex(s,g)
This will be invoked by every process for each local vertex.
discover_vertex(u,g)
This will be invoked each time a process discovers a new vertex
u.
examine_vertex(u,g)
This will be invoked by the process owning the vertex u.
examine_edge(e,g)
This will be invoked by the process owning the source vertex of
e.
tree_edge(e,g)
Similar to examine_edge, this will be invoked by the process
owning the source vertex and may be invoked only once.
back_edge(e,g)
Some edges that would be forward or cross edges in the sequential
DFS may be detected as back edges by the distributed DFS, so extra
back_edge events may be received.
forward_or_cross_edge(e,g)
Some edges that would be forward or cross edges in the sequential
DFS may be detected as back edges by the distributed DFS, so fewer
forward_or_cross_edge events may be received in the distributed
algorithm than in the sequential case.
finish_vertex(e,g)
See documentation for examine_vertex.
Making Visitors Safe for Distributed DFS
Три наиболее важные вещи, которые следует помнить при обновлении существующего посетителя DFS для распределенного посетителя DFS или написании нового распределенного посетителя DFS:
Убедитесь, что все состояния либо полностью локальны, либо находятся в распределенной структуре данных (скорее всего, карта свойств!), используя ту же группу процессов, что и график.
Убедитесь, что посетитель не требует точных последовательностей событий, которые не могут быть гарантированы распределенными DFS, например, требующимиback_edgeиforward_or_cross_edgeСобытия должны быть совершенно разными.
Убедитесь, что посетитель может оперировать неполной информацией. Это часто включает в себя использование соответствующей операции сокращения враспределенной карте свойстви проверку того, что результаты, написанные, являются "лучше", что было ранее написано.
