predecessor_recorder
Records the predecessor (parent) vertex of each vertex in a property map. This is an efficient way to encode the search tree traversed during a graph search.
Defined in: <boost/graph/visitors.hpp>
Models: EventVisitor
Typical event: on_tree_edge or on_relax_edge (edge events only; cannot be
used with vertex events)
To use it, wrap it in an algorithm adaptor and optionally combine it with other event visitors; see the visitors overview.
Synopsis
template <typename PredecessorMap, typename EventTag>
struct predecessor_recorder {
typedef EventTag event_filter;
predecessor_recorder(PredecessorMap pa);
template <class Edge, class Graph>
void operator()(Edge e, const Graph& g);
};
template <typename PredecessorMap, typename EventTag>
predecessor_recorder<PredecessorMap, EventTag>
record_predecessors(PredecessorMap pa, EventTag);Template Parameters
| Parameter | Description |
|---|---|
|
A WritablePropertyMap whose key and value types are both the graph’s vertex descriptor. |
|
The event at which to record. Must be an edge event (e.g. |
Associated Types
| Type | Description |
|---|---|
|
The event tag the visitor responds to. Same type as |
Member Functions
| Member | Description |
|---|---|
|
Constructs a recorder writing predecessors into the property map |
|
Given edge |
Non-Member Functions
| Function | Description |
|---|---|
|
Convenience factory that creates a |
| Algorithms such as Dijkstra and BFS do not assign a predecessor to the source vertex (the root of the search tree). Initialize the source’s predecessor to itself to mark it as the only vertex that is its own parent. For DFS (which builds a forest), initialize every vertex to itself so all roots can be distinguished. |
Example
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <iostream>
#include <vector>
int main() {
using namespace boost;
using Graph = adjacency_list<vecS, vecS, undirectedS>;
using Vertex = graph_traits<Graph>::vertex_descriptor;
Graph g(6);
add_edge(0, 1, g);
add_edge(0, 2, g);
add_edge(1, 3, g);
add_edge(2, 4, g);
add_edge(3, 5, g);
// Record predecessors during BFS
std::vector<Vertex> pred(num_vertices(g), 0);
pred[0] = 0; // root is its own predecessor
auto vis = make_bfs_visitor(
record_predecessors(pred.data(), on_tree_edge())
);
breadth_first_search(g, vertex(0, g), visitor(vis));
for (std::size_t v = 0; v < num_vertices(g); ++v) {
std::cout << "vertex " << v << " predecessor=" << pred[v] << "\n";
}
}vertex 0 predecessor=0
vertex 1 predecessor=0
vertex 2 predecessor=0
vertex 3 predecessor=1
vertex 4 predecessor=2
vertex 5 predecessor=3