1//=======================================================================
2// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
3//
4// Distributed under the Boost Software License, Version 1.0. (See
5// accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7//=======================================================================
8#include <boost/graph/adjacency_list.hpp>
9#include <boost/graph/breadth_first_search.hpp>
10#include <boost/pending/indirect_cmp.hpp>
11#include <boost/range/irange.hpp>
12#include <boost/property_map/property_map.hpp>
13
14#include <iostream>
15
16using namespace boost;
17template < typename TimeMap >
18class bfs_time_visitor : public default_bfs_visitor
19{
20 typedef typename property_traits< TimeMap >::value_type T;
21
22public:
23 bfs_time_visitor(TimeMap tmap, T& t) : m_timemap(tmap), m_time(t) {}
24 template < typename Vertex, typename Graph >
25 void discover_vertex(Vertex u, const Graph& g) const
26 {
27 put(m_timemap, u, m_time++);
28 }
29 TimeMap m_timemap;
30 T& m_time;
31};
32
33struct VertexProps
34{
35 boost::default_color_type color;
36 std::size_t discover_time;
37 unsigned int index;
38};
39
40int main()
41{
42 using namespace boost;
43 // Select the graph type we wish to use
44 typedef adjacency_list< listS, listS, undirectedS, VertexProps > graph_t;
45 // Set up the vertex IDs and names
46 enum
47 {
48 r,
49 s,
50 t,
51 u,
52 v,
53 w,
54 x,
55 y,
56 N
57 };
58 const char* name = "rstuvwxy";
59 // Specify the edges in the graph
60 typedef std::pair< int, int > E;
61 E edge_array[] = { E(r, s), E(r, v), E(s, w), E(w, r), E(w, t), E(w, x),
62 E(x, t), E(t, u), E(x, y), E(u, y) };
63 // Create the graph object
64 const int n_edges = sizeof(edge_array) / sizeof(E);
65#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
66 // VC++ has trouble with the edge iterator constructor
67 graph_t g;
68 std::vector< graph_traits< graph_t >::vertex_descriptor > verts;
69 for (std::size_t i = 0; i < N; ++i)
70 verts.push_back(add_vertex(g));
71 for (std::size_t j = 0; j < n_edges; ++j)
72 add_edge(verts[edge_array[j].first], verts[edge_array[j].second], g);
73#else
74 typedef graph_traits< graph_t >::vertices_size_type v_size_t;
75 graph_t g(edge_array, edge_array + n_edges, v_size_t(N));
76#endif
77
78 // Typedefs
79 typedef graph_traits< graph_t >::vertices_size_type Size;
80
81 Size time = 0;
82 typedef property_map< graph_t, std::size_t VertexProps::* >::type
83 dtime_map_t;
84 dtime_map_t dtime_map = get(p: &VertexProps::discover_time, g);
85 bfs_time_visitor< dtime_map_t > vis(dtime_map, time);
86 breadth_first_search(
87 g, s: vertex(n: s, g_: g), params: color_map(p: get(p: &VertexProps::color, g)).visitor(p: vis));
88
89 // a vector to hold the discover time property for each vertex
90 std::vector< Size > dtime(num_vertices(g_: g));
91 typedef iterator_property_map< std::vector< Size >::iterator,
92 property_map< graph_t, unsigned int VertexProps::* >::type >
93 dtime_pm_type;
94 graph_traits< graph_t >::vertex_iterator vi, vi_end;
95 std::size_t c = 0;
96 for (boost::tie(t0&: vi, t1&: vi_end) = vertices(g_: g); vi != vi_end; ++vi, ++c)
97 {
98 dtime[c] = dtime_map[*vi];
99 put(p: &VertexProps::index, g, key: *vi, value: c);
100 }
101 dtime_pm_type dtime_pm(dtime.begin(), get(p: &VertexProps::index, g));
102
103 // Use std::sort to order the vertices by their discover time
104 std::vector< graph_traits< graph_t >::vertices_size_type > discover_order(
105 N);
106 integer_range< int > range(0, N);
107 std::copy(first: range.begin(), last: range.end(), result: discover_order.begin());
108 std::sort(first: discover_order.begin(), last: discover_order.end(),
109 comp: make_indirect_cmp(cmp: std::less< Size >(),
110 pmap: make_iterator_property_map(
111 iter: dtime.begin(), id: typed_identity_property_map< std::size_t >())));
112
113 std::cout << "order of discovery: ";
114 for (int i = 0; i < N; ++i)
115 std::cout << name[discover_order[i]] << " ";
116 std::cout << std::endl;
117
118 return EXIT_SUCCESS;
119}
120

source code of boost/libs/graph/example/bfs-example2.cpp