predecessor_recorder
Records the predecessor (parent) vertex for each vertex in a property map.
Defined in: <boost/graph/visitors.hpp>
Models: EventVisitor
Typical event: on_tree_edge or on_relax_edge (edge events only)
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| Initialize the source vertex’s predecessor to itself before running the algorithm. This marks the root of the search tree as the only vertex that is its own parent. For DFS (which creates a forest), initialize every vertex to itself. |
Synopsis
template <typename PredecessorMap, typename EventTag>
struct predecessor_recorder;
template <typename PredecessorMap, typename EventTag>
predecessor_recorder<PredecessorMap, EventTag>
record_predecessors(PredecessorMap pa, EventTag);