edge_predecessor_recorder
Records the predecessor edge (not vertex) for each vertex. Useful when a graph has parallel edges and you need to know which specific edge the search used to reach a vertex.
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, directedS>;
using Edge = graph_traits<Graph>::edge_descriptor;
Graph g(4);
add_edge(0, 1, g);
add_edge(0, 2, g);
add_edge(1, 3, g);
// Record the incoming edge for each vertex
std::vector<Edge> pred_edge(num_vertices(g));
auto vis = make_bfs_visitor(
record_edge_predecessors(pred_edge.data(), on_tree_edge())
);
breadth_first_search(g, vertex(0, g), visitor(vis));
for (std::size_t v = 1; v < num_vertices(g); ++v) {
Edge e = pred_edge[v];
std::cout << "vertex " << v << " arrived via edge "
<< source(e, g) << " -> " << target(e, g) << "\n";
}
}vertex 1 arrived via edge 0 -> 1
vertex 2 arrived via edge 0 -> 2
vertex 3 arrived via edge 1 -> 3Synopsis
template <typename PredEdgeMap, typename EventTag>
struct edge_predecessor_recorder;
template <typename PredEdgeMap, typename EventTag>
edge_predecessor_recorder<PredEdgeMap, EventTag>
record_edge_predecessors(PredEdgeMap pa, EventTag);Parameters
| Parameter | Description |
|---|---|
|
WritablePropertyMap. Key type is vertex descriptor, value type is edge descriptor. |
|
Must be an edge event tag (e.g. |
Behavior
Given edge e = (u, v), records e as the predecessor edge of v:
put(pred_edge_map, v, e).
| The source vertex (root of the search tree) will not have a predecessor edge assigned. Initialize it to a sentinel value before running the algorithm. For DFS (which creates a forest), do the same for every vertex so that all roots can be identified. |