Depth-First Visit

template<typename DistributedGraph, typename DFSVisitor>
void
depth_first_visit(const DistributedGraph& g,
                  typename graph_traits<DistributedGraph>::vertex_descriptor s,
                  DFSVisitor vis);

namespace graph {
  template<typename DistributedGraph, typename DFSVisitor,
         typename VertexIndexMap>
  void
  tsin_depth_first_visit(const DistributedGraph& g,
                         typename graph_traits<DistributedGraph>::vertex_descriptor s,
                         DFSVisitor vis);

  template<typename DistributedGraph, typename DFSVisitor,
           typename VertexIndexMap>
  void
  tsin_depth_first_visit(const DistributedGraph& g,
                         typename graph_traits<DistributedGraph>::vertex_descriptor s,
                         DFSVisitor vis, VertexIndexMap index_map);

  template<typename DistributedGraph, typename ColorMap, typename ParentMap,
           typename ExploreMap, typename NextOutEdgeMap, typename DFSVisitor>
  void
  tsin_depth_first_visit(const DistributedGraph& g,
                         typename graph_traits<DistributedGraph>::vertex_descriptor s,
                         DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore,
                         NextOutEdgeMap next_out_edge);
}

The depth_first_visit() function performs a distributed depth-first traversal of an undirected graph using Tsin's corrections [Tsin02] to Cidon's algorithm [Cidon88]. The distributed DFS is syntactically similar to its sequential counterpart, which provides additional background and discussion. Differences in semantics are highlighted here, and we refer the reader to the documentation of the sequential depth-first search for the remainder of the details. Visitors passed to depth-first search need to account for the distribution of vertices across processes, because events will be triggered on certain processes but not others. See the section Visitor Event Points for details.

Where Defined

<boost/graph/distributed/depth_first_search.hpp>

also available in

<boost/graph/depth_first_search.hpp>

Parameters

IN: const Graph& g

The graph type must be a model of Distributed Graph. The graph must be undirected.

IN: vertex_descriptor s

The start vertex must be the same in every process.

IN: DFSVisitor vis

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: VertexIndexMap map

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: 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 -> black).

Default: A distributed iterator_property_map created from a std::vector of default_color_type.

UTIL/OUT: ParentMap parent

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: ExploreMap explore

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: NextOutEdgeMap next_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

Depth-first search is inherently sequential, so parallel speedup is very poor. Regardless of the number of processors, the algorithm will not be faster than O(V); see [Tsin02] for more details.

Visitor Event Points

The DFS Visitor concept defines 8 event points that will be triggered by the sequential depth-first search. The distributed DFS retains these event points, but the sequence of events triggered and the process in which each event occurs will change depending on the distribution of the graph.

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

The three most important things to remember when updating an existing DFS visitor for distributed DFS or writing a new distributed DFS visitor are:

Be sure that all state is either entirely local or in a distributed data structure (most likely a property map!) using the same process group as the graph.
Be sure that the visitor doesn't require precise event sequences that cannot be guaranteed by distributed DFS, e.g., requiring back_edge and forward_or_cross_edge events to be completely distinct.
Be sure that the visitor can operate on incomplete information. This often includes using an appropriate reduction operation in a distributed property map and verifying that results written are "better" that what was previously written.

Bibliography

[Cidon88]

Isreal Cidon. Yet another distributed depth-first-search algorithm. Information Processing Letters, 26(6):301--305, 1988.

[Tsin02]

(1, 2) Y. H. Tsin. Some remarks on distributed depth-first search. Information Processing Letters, 82(4):173--178, 2002.

Authors: Douglas Gregor and Andrew Lumsdaine