C++ 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)

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.

Where Defined:

boost/graph/depth_first_search.hpp

Parameters

IN IncidenceGraph& g
A directed or undirected graph. The graph's type must be a model of Incidence Graph.
IN: vertex_descriptor s
The source vertex from which to start the search.
IN: DFSVisitor visitor
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].
UTIL: ColorMap color
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.

Complexity

Time complexity is O(E).

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.


Copyright © 2000-2001 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)