Boost Graph Library: Depth-First Visit

Boost , ,

depth_first_visit

template <class IncidenceGraph, class DFSVisitor, class ColorMap>
void depth_first_visit(IncidenceGraph& g,
  typename graph_traits<IncidenceGraph>::vertex_descriptor s, 
  DFSVisitor& vis, ColorMap color)
template <class IncidenceGraph, class DFSVisitor, class ColorMap, 
          class TerminatorFunc>
void depth_first_visit(IncidenceGraph& g,
  typename graph_traits<IncidenceGraph>::vertex_descriptor s, 
  DFSVisitor& vis, ColorMap color, TerminatorFunc func = TerminatorFunc())

This function visits all of the vertices in the same connected component as the source vertex s, using the depth-first pattern. The main purpose of the function is for the implementation of depth_first_search() though sometimes it is useful on its own.

The DFSVisitor supplied by the user determines what actions are taken at each event-point within the algorithm.

The ColorMap is used by the algorithm to keep track of which vertices have been visited.

The second variant can be used, for example, to find all marked vertices reachable from a start vertex by a path which does not contain any another marked vertices.

Where Defined:

Parameters

A directed or undirected graph. The graph's type must be a model of Incidence Graph.
Python: The parameter is named graph.

The source vertex from which to start the search.
Python: The parameter is named root_vertex.

A visitor object that is invoked inside the algorithm at the event-points specified by the DFS Visitor concept. The visitor object is passed by value [1].
Python: The parameter should be an object that derives from the DFSVisitor type of the graph.

This is used by the algorithm to keep track of its progress through the graph. The type ColorMap must be a model of Read/Write Property Map and its key type must be the graph's vertex descriptor type and the value type of the color map map must model Color Value.
Python: The color map must be a vertex_color_map for the graph.

A function object callable with two parameters - the descriptor of vertex and the graph instance - and returning bool. The call is made immediately after call to 'discover_vertex' visitor event. If true is returned, the out edges of the vertex are not examined, as if they don't exist.
Python: Unsupported parameter.

Complexity

Notes

[1] Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

Статья Boost Graph Library: Depth-First Visit раздела может быть полезна для разработчиков на c++ и boost.

:: Главная :: ::