time_stamper

Stamps a monotonically increasing time value onto a vertex or edge when an event occurs. Commonly used to record the discover and finish times of vertices during a graph search.

Defined in: <boost/graph/visitors.hpp>
Models: EventVisitor
Typical event: any (vertex or edge), e.g. on_discover_vertex, on_finish_vertex

To use it, wrap it in an algorithm adaptor and optionally combine it with other event visitors; see the visitors overview.

Synopsis

template <typename TimeMap, typename TimeT, typename EventTag>
struct time_stamper {
  typedef EventTag event_filter;
  time_stamper(TimeMap pa, TimeT& t);

  template <class X, class Graph>
  void operator()(X x, const Graph& g);
};

template <typename TimeMap, typename TimeT, typename EventTag>
time_stamper<TimeMap, TimeT, EventTag>
stamp_times(TimeMap pa, TimeT& t, EventTag);

Template Parameters

Parameter Description

Parameter	Description
`TimeMap`	A WritablePropertyMap whose key type is the graph’s vertex or edge descriptor (depending on the event tag), and whose value type accepts the time counter.
`TimeT`	The time-counter type. Passed by reference and incremented on each event, so a single counter can be shared across several `time_stamper` objects.
`EventTag`	The event at which to stamp the time. May be any event, vertex or edge.

TimeMap

A WritablePropertyMap whose key type is the graph’s vertex or edge descriptor (depending on the event tag), and whose value type accepts the time counter.

TimeT

The time-counter type. Passed by reference and incremented on each event, so a single counter can be shared across several time_stamper objects.

EventTag

The event at which to stamp the time. May be any event, vertex or 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
`time_stamper(TimeMap pa, TimeT& t)`	Constructs a time stamper writing into the property map `pa` and using the shared counter `t`.
`void operator()(X x, const Graph& g)`	Increments the counter and stamps the new value onto `x` (a vertex or edge): `put(pa, x, ++t)`.

time_stamper(TimeMap pa, TimeT& t)

Constructs a time stamper writing into the property map pa and using the shared counter t.

void operator()(X x, const Graph& g)

Increments the counter and stamps the new value onto x (a vertex or edge): put(pa, x, ++t).

Non-Member Functions

Function Description

Function	Description
`stamp_times(TimeMap pa, TimeT& t, EventTag)`	Convenience factory that creates a `time_stamper`.

stamp_times(TimeMap pa, TimeT& t, EventTag)

Convenience factory that creates a time_stamper.

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <iostream>
#include <vector>

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, directedS>;

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

    std::vector<int> dtime(num_vertices(g));
    std::vector<int> ftime(num_vertices(g));
    int t = 0;

    auto vis = make_dfs_visitor(
        std::make_pair(
            stamp_times(dtime.data(), t, on_discover_vertex()),
            stamp_times(ftime.data(), t, on_finish_vertex())
        )
    );
    depth_first_search(g, visitor(vis));

    for (std::size_t v = 0; v < num_vertices(g); ++v) {
        std::cout << "vertex " << v
                  << "  discover=" << dtime[v]
                  << "  finish=" << ftime[v] << "\n";
    }
}

vertex 0  discover=1  finish=8
vertex 1  discover=2  finish=5
vertex 2  discover=6  finish=7
vertex 3  discover=3  finish=4

Edit this Page