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/config.hpp>
9 #include <iostream>
10 #include <fstream>
11 #include <boost/graph/adjacency_list.hpp>
12 #include <boost/graph/breadth_first_search.hpp>
13 using namespace boost;
14
15 template < typename Graph, typename VertexNameMap, typename TransDelayMap >
build_router_network(Graph & g,VertexNameMap name_map,TransDelayMap delay_map)16 void build_router_network(
17 Graph& g, VertexNameMap name_map, TransDelayMap delay_map)
18 {
19 typename graph_traits< Graph >::vertex_descriptor a, b, c, d, e;
20 a = add_vertex(g);
21 name_map[a] = 'a';
22 b = add_vertex(g);
23 name_map[b] = 'b';
24 c = add_vertex(g);
25 name_map[c] = 'c';
26 d = add_vertex(g);
27 name_map[d] = 'd';
28 e = add_vertex(g);
29 name_map[e] = 'e';
30
31 typename graph_traits< Graph >::edge_descriptor ed;
32 bool inserted;
33
34 boost::tie(ed, inserted) = add_edge(a, b, g);
35 delay_map[ed] = 1.2;
36 boost::tie(ed, inserted) = add_edge(a, d, g);
37 delay_map[ed] = 4.5;
38 boost::tie(ed, inserted) = add_edge(b, d, g);
39 delay_map[ed] = 1.8;
40 boost::tie(ed, inserted) = add_edge(c, a, g);
41 delay_map[ed] = 2.6;
42 boost::tie(ed, inserted) = add_edge(c, e, g);
43 delay_map[ed] = 5.2;
44 boost::tie(ed, inserted) = add_edge(d, c, g);
45 delay_map[ed] = 0.4;
46 boost::tie(ed, inserted) = add_edge(d, e, g);
47 delay_map[ed] = 3.3;
48 }
49
50 template < typename VertexNameMap >
51 class bfs_name_printer : public default_bfs_visitor
52 {
53 // inherit default (empty) event point actions
54 public:
bfs_name_printer(VertexNameMap n_map)55 bfs_name_printer(VertexNameMap n_map) : m_name_map(n_map) {}
56 template < typename Vertex, typename Graph >
discover_vertex(Vertex u,const Graph &) const57 void discover_vertex(Vertex u, const Graph&) const
58 {
59 std::cout << get(m_name_map, u) << ' ';
60 }
61
62 private:
63 VertexNameMap m_name_map;
64 };
65
66 struct VP
67 {
68 char name;
69 };
70
71 struct EP
72 {
73 double weight;
74 };
75
main()76 int main()
77 {
78 typedef adjacency_list< listS, vecS, directedS, VP, EP > graph_t;
79 graph_t g;
80
81 property_map< graph_t, char VP::* >::type name_map = get(&VP::name, g);
82 property_map< graph_t, double EP::* >::type delay_map = get(&EP::weight, g);
83
84 build_router_network(g, name_map, delay_map);
85
86 typedef property_map< graph_t, char VP::* >::type VertexNameMap;
87 graph_traits< graph_t >::vertex_descriptor a = *vertices(g).first;
88 bfs_name_printer< VertexNameMap > vis(name_map);
89 std::cout << "BFS vertex discover order: ";
90 breadth_first_search(g, a, visitor(vis));
91 std::cout << std::endl;
92 }
93