distance_recorder

Records the distance of each vertex from the source vertex into a property map. When applied to edge e = (u, v), the distance of v is recorded as one more than the distance of u.

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 DistanceMap, typename EventTag>
struct distance_recorder {
  typedef EventTag event_filter;
  distance_recorder(DistanceMap pa);

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

template <typename DistanceMap, typename EventTag>
distance_recorder<DistanceMap, EventTag>
record_distances(DistanceMap pa, EventTag);

Template Parameters

Parameter Description

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

DistanceMap

A WritablePropertyMap whose key type is the graph’s vertex descriptor and whose value type is the distance (a numeric type that supports adding one).

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
`distance_recorder(DistanceMap pa)`	Constructs a recorder writing distances into the property map `pa`.
`void operator()(Edge e, const Graph& g)`	Given edge `e = (u, v)`, records the distance of `v` as one more than the distance of `u`: `put(pa, v, get(pa, u) + 1)`.

distance_recorder(DistanceMap pa)

Constructs a recorder writing distances into the property map pa.

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

Given edge e = (u, v), records the distance of v as one more than the distance of u: put(pa, v, get(pa, u) + 1).

Non-Member Functions

Function Description

Function	Description
`record_distances(DistanceMap pa, EventTag)`	Convenience factory that creates a `distance_recorder`.

record_distances(DistanceMap pa, EventTag)

Convenience factory that creates a distance_recorder.

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>;

    Graph g(5);
    add_edge(0, 1, g);
    add_edge(0, 2, g);
    add_edge(1, 3, g);
    add_edge(3, 4, g);

    std::vector<int> dist(num_vertices(g), 0);
    auto vis = make_bfs_visitor(
        record_distances(dist.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 << "  distance=" << dist[v] << "\n";
    }
}

vertex 0  distance=0
vertex 1  distance=1
vertex 2  distance=1
vertex 3  distance=2
vertex 4  distance=3

Edit this Page