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