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
16 using namespace boost;
17 template < typename TimeMap >
18 class bfs_time_visitor : public default_bfs_visitor
19 {
20 typedef typename property_traits< TimeMap >::value_type T;
21
22 public:
bfs_time_visitor(TimeMap tmap,T & t)23 bfs_time_visitor(TimeMap tmap, T& t) : m_timemap(tmap), m_time(t) {}
24 template < typename Vertex, typename Graph >
discover_vertex(Vertex u,const Graph & g) const25 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
33 struct VertexProps
34 {
35 boost::default_color_type color;
36 std::size_t discover_time;
37 unsigned int index;
38 };
39
main()40 int 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(&VertexProps::discover_time, g);
85 bfs_time_visitor< dtime_map_t > vis(dtime_map, time);
86 breadth_first_search(
87 g, vertex(s, g), color_map(get(&VertexProps::color, g)).visitor(vis));
88
89 // a vector to hold the discover time property for each vertex
90 std::vector< Size > dtime(num_vertices(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(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++c)
97 {
98 dtime[c] = dtime_map[*vi];
99 put(&VertexProps::index, g, *vi, c);
100 }
101 dtime_pm_type dtime_pm(dtime.begin(), get(&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(range.begin(), range.end(), discover_order.begin());
108 std::sort(discover_order.begin(), discover_order.end(),
109 make_indirect_cmp(std::less< Size >(),
110 make_iterator_property_map(
111 dtime.begin(), 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