predecessor_recorder<PredecessorMap, EventTag>

This is an EventVisitor that records the predecessor (or parent) of a vertex in a predecessor property map. This is particularly useful in graph search algorithms where recording the predecessors is an efficient way to encode the search tree that was traversed during the search. The predecessor recorder is typically used with the on_tree_edge or on_relax_edge events, and cannot be used with vertex events.

predecessor_recorder can be used with graph algorithms by wrapping it with the algorithm specific adaptor, such as bfs_visitor and dfs_visitor. Also, this event visitor can be combined with other event visitors using std::pair to form an EventVisitorList.

Algorithms such as Dijkstra's and breadth-first search will not assign a predecessor to the source vertex (which is the root of the search tree). Often times it is useful to initialize the source vertex's predecessor to itself, thereby identifying the root vertex as the only vertex which is its own parent. When using an algorithm like depth-first search that creates a forest (multiple search trees), it is useful to intialize the predecessor of every vertex to itself, so that all the root nodes can be distinguished.

Example

See the example for bfs_visitor.

Model of

EventVisitor

Where Defined

boost/graph/visitors.hpp

Template Parameters

Parameter	Description	Default
PredecessorMap	A WritablePropertyMap, where the key type and the value type are the vertex descriptor type of the graph.
EventTag	The tag to specify when the predecessor_recorder should be applied during the graph algorithm. EventTag must be an edge event.

Associated Types

Type	Description
predecessor_recorder::event_filter	This will be the same type as the template parameter EventTag.

Member Functions

Member	Description
predecessor_recorder(PredecessorMap pa);	Construct a predecessor recorder object with predecessor property map pa.
template <class Edge, class Graph> void operator()(Edge e, const Graph& g);	Given edge e = (u,v), this records u as the predecessor (or parent) of v.

Non-Member Functions

Function	Description
template <class PredecessorMap, class Tag> predecessor_recorder<PredecessorMap, Tag> record_predecessors(PredecessorMap pa, Tag);	A convenient way to create a predecessor_recorder.

See Also

Visitor concepts

The following are other event visitors: distance_recorder, time_stamper, and property_writer.

Copyright © 2000-2001

Jeremy Siek, Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) , Indiana University (lums@osl.iu.edu)