edge_predecessor_recorder

Records the predecessor edge of each vertex in a property map, an efficient way to encode the search tree traversed during a graph search. Use this instead of predecessor_recorder (which records the predecessor vertex) 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; 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 PredEdgeMap, typename EventTag>
struct edge_predecessor_recorder {
  typedef EventTag event_filter;
  edge_predecessor_recorder(PredEdgeMap pa);

  template <class Edge, class Graph>
  void operator()(Edge e, const Graph& g);
};

template <typename PredEdgeMap, typename EventTag>
edge_predecessor_recorder<PredEdgeMap, EventTag>
record_edge_predecessors(PredEdgeMap pa, EventTag);

Template Parameters

Parameter Description

Parameter	Description
`PredEdgeMap`	A WritablePropertyMap whose key type is the graph’s vertex descriptor and whose value type is the graph’s edge descriptor.
`EventTag`	The event at which to record. Must be an edge event (e.g. `on_tree_edge`, `on_relax_edge`).

PredEdgeMap

A WritablePropertyMap whose key type is the graph’s vertex descriptor and whose value type is the graph’s edge descriptor.

EventTag

The event at which to record. Must be an edge event (e.g. on_tree_edge, on_relax_edge).

Associated Types

Type Description

Type	Description
`event_filter`	The event tag the visitor responds to. Same type as `EventTag`.

event_filter

The event tag the visitor responds to. Same type as EventTag.

Member Functions

Member Description

Member	Description
`edge_predecessor_recorder(PredEdgeMap pa)`	Constructs a recorder writing predecessor edges into the property map `pa`.
`void operator()(Edge e, const Graph& g)`	Given edge `e = (u, v)`, records `e` as the predecessor edge of `v`: `put(pa, v, e)`.

edge_predecessor_recorder(PredEdgeMap pa)

Constructs a recorder writing predecessor edges into the property map pa.

void operator()(Edge e, const Graph& g)

Given edge e = (u, v), records e as the predecessor edge of v: put(pa, v, e).

Non-Member Functions

Function Description

Function	Description
`record_edge_predecessors(PredEdgeMap pa, EventTag)`	Convenience factory that creates an `edge_predecessor_recorder`.

record_edge_predecessors(PredEdgeMap pa, EventTag)

Convenience factory that creates an edge_predecessor_recorder.

The source vertex (the root of the search tree) is not assigned a predecessor edge. Initialize it to a sentinel value before running the algorithm to identify the root. For DFS (which builds a forest), do the same for every vertex 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, 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 -> 3

Edit this Page