...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
predecessor_recorder<PredecessorMap, EventTag>
predecessor_recorder can be used with graph algorithms by wrapping it with an 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). It is often 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 initialize the predecessor of every vertex to itself. This way all the root nodes can be distinguished.
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. |
Type | Description |
---|---|
predecessor_recorder::event_filter | This will be the same type as the template parameter EventTag. |
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. |
Function | Description |
---|---|
template <class PredecessorMap, class Tag> predecessor_recorder<PredecessorMap, Tag> record_predecessors(PredecessorMap pa, Tag); | A convenient way to create a predecessor_recorder. |
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) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu) |