ceph/src/boost/libs/graph/example/bfs-name-printer.cpp

   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(
  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:
  55     bfs_name_printer(VertexNameMap n_map) : m_name_map(n_map) {}
  56     template < typename Vertex, typename Graph >
  57     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
  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 }