ceph/src/boost/libs/graph/example/boost_web_graph.cpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9 #include <boost/config.hpp>
  10 #include <iostream>
  11 #include <fstream>
  12 #include <string>
  13 #include <algorithm>
  14 #include <map>
  15 #include <boost/pending/stringtok.hpp>
  16 #include <boost/utility.hpp>
  17 #include <boost/graph/adjacency_list.hpp>
  18 #include <boost/graph/visitors.hpp>
  19 #include <boost/graph/breadth_first_search.hpp>
  20 #include <boost/graph/depth_first_search.hpp>
  21
  22
  23 template <class Distance>
  24 class calc_distance_visitor : public boost::bfs_visitor<>
  25 {
  26 public:
  27   calc_distance_visitor(Distance d) : distance(d) { }
  28
  29   template <class Graph>
  30   void tree_edge(typename boost::graph_traits<Graph>::edge_descriptor e,
  31                  Graph& g)
  32   {
  33     typename boost::graph_traits<Graph>::vertex_descriptor u, v;
  34     u = boost::source(e, g);
  35     v = boost::target(e, g);
  36     distance[v] = distance[u] + 1;
  37   }
  38 private:
  39   Distance distance;
  40 };
  41
  42
  43 template <class VertexNameMap, class DistanceMap>
  44 class print_tree_visitor : public boost::dfs_visitor<>
  45 {
  46 public:
  47   print_tree_visitor(VertexNameMap n, DistanceMap d) : name(n), distance(d) { }
  48   template <class Graph>
  49   void
  50   discover_vertex(typename boost::graph_traits<Graph>::vertex_descriptor v,
  51             Graph&)
  52   {
  53     typedef typename boost::property_traits<DistanceMap>::value_type Dist;
  54     // indentation based on depth
  55     for (Dist i = 0; i < distance[v]; ++i)
  56       std::cout << "  ";
  57     std::cout << name[v] << std::endl;
  58   }
  59
  60   template <class Graph>
  61   void tree_edge(typename boost::graph_traits<Graph>::edge_descriptor e,
  62                  Graph& g)
  63   {
  64     distance[boost::target(e, g)] = distance[boost::source(e, g)] + 1;
  65   }
  66
  67 private:
  68   VertexNameMap name;
  69   DistanceMap distance;
  70 };
  71
  72 int
  73 main(int argc, const char** argv)
  74 {
  75   using namespace boost;
  76
  77   std::ifstream datafile(argc >= 2 ? argv[1] : "./boost_web.dat");
  78   if (!datafile) {
  79     std::cerr << "No ./boost_web.dat file" << std::endl;
  80     return -1;
  81   }
  82
  83   //===========================================================================
  84   // Declare the graph type and object, and some property maps.
  85
  86   typedef adjacency_list<vecS, vecS, directedS,
  87     property<vertex_name_t, std::string,
  88       property<vertex_color_t, default_color_type> >,
  89     property<edge_name_t, std::string, property<edge_weight_t, int> >
  90   > Graph;
  91
  92   typedef graph_traits<Graph> Traits;
  93   typedef Traits::vertex_descriptor Vertex;
  94   typedef Traits::edge_descriptor Edge;
  95
  96   typedef std::map<std::string, Vertex> NameVertexMap;
  97   NameVertexMap name2vertex;
  98   Graph g;
  99
 100   typedef property_map<Graph, vertex_name_t>::type NameMap;
 101   NameMap node_name  = get(vertex_name, g);
 102   property_map<Graph, edge_name_t>::type link_name = get(edge_name, g);
 103
 104   //===========================================================================
 105   // Read the data file and construct the graph.
 106
 107   std::string line;
 108   while (std::getline(datafile,line)) {
 109
 110     std::list<std::string> line_toks;
 111     boost::stringtok(line_toks, line, "|");
 112
 113     NameVertexMap::iterator pos;
 114     bool inserted;
 115     Vertex u, v;
 116
 117     std::list<std::string>::iterator i = line_toks.begin();
 118
 119     boost::tie(pos, inserted) = name2vertex.insert(std::make_pair(*i, Vertex()));
 120     if (inserted) {
 121       u = add_vertex(g);
 122       put(node_name, u, *i);
 123       pos->second = u;
 124     } else
 125       u = pos->second;
 126     ++i;
 127
 128     std::string hyperlink_name = *i++;
 129
 130     boost::tie(pos, inserted) = name2vertex.insert(std::make_pair(*i, Vertex()));
 131     if (inserted) {
 132       v = add_vertex(g);
 133       put(node_name, v, *i);
 134       pos->second = v;
 135     } else
 136       v = pos->second;
 137
 138     Edge e;
 139     boost::tie(e, inserted) = add_edge(u, v, g);
 140     if (inserted) {
 141       put(link_name, e, hyperlink_name);
 142     }
 143   }
 144
 145   //===========================================================================
 146   // Calculate the diameter of the graph.
 147
 148   typedef Traits::vertices_size_type size_type;
 149   typedef std::vector<size_type> IntVector;
 150   // Create N x N matrix for storing the shortest distances
 151   // between each vertex. Initialize all distances to zero.
 152   std::vector<IntVector> d_matrix(num_vertices(g),
 153                                   IntVector(num_vertices(g), 0));
 154
 155   size_type i;
 156   for (i = 0; i < num_vertices(g); ++i) {
 157     calc_distance_visitor<size_type*> vis(&d_matrix[i][0]);
 158     Traits::vertex_descriptor src = vertices(g).first[i];
 159     breadth_first_search(g, src, boost::visitor(vis));
 160   }
 161
 162   size_type diameter = 0;
 163   BOOST_USING_STD_MAX();
 164   for (i = 0; i < num_vertices(g); ++i)
 165     diameter = max BOOST_PREVENT_MACRO_SUBSTITUTION(diameter, *std::max_element(d_matrix[i].begin(),
 166                                                     d_matrix[i].end()));
 167
 168   std::cout << "The diameter of the boost web-site graph is " << diameter
 169             << std::endl << std::endl;
 170
 171   std::cout << "Number of clicks from the home page: " << std::endl;
 172   Traits::vertex_iterator vi, vi_end;
 173   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 174     std::cout << d_matrix[0][*vi] << "\t" << node_name[*vi] << std::endl;
 175   std::cout << std::endl;
 176
 177   //===========================================================================
 178   // Print out the breadth-first search tree starting at the home page
 179
 180   // Create storage for a mapping from vertices to their parents
 181   std::vector<Traits::vertex_descriptor> parent(num_vertices(g));
 182   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 183     parent[*vi] = *vi;
 184
 185   // Do a BFS starting at the home page, recording the parent of each
 186   // vertex (where parent is with respect to the search tree).
 187   Traits::vertex_descriptor src = vertices(g).first[0];
 188   breadth_first_search
 189     (g, src,
 190      boost::visitor(make_bfs_visitor(record_predecessors(&parent[0],
 191                                                          on_tree_edge()))));
 192
 193   // Add all the search tree edges into a new graph
 194   Graph search_tree(num_vertices(g));
 195   boost::tie(vi, vi_end) = vertices(g);
 196   ++vi;
 197   for (; vi != vi_end; ++vi)
 198     add_edge(parent[*vi], *vi, search_tree);
 199
 200   std::cout << "The breadth-first search tree:" << std::endl;
 201
 202   // Print out the search tree. We use DFS because it visits
 203   // the tree nodes in the order that we want to print out:
 204   // a directory-structure like format.
 205   std::vector<size_type> dfs_distances(num_vertices(g), 0);
 206   print_tree_visitor<NameMap, size_type*>
 207     tree_printer(node_name, &dfs_distances[0]);
 208   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 209     get(vertex_color, g)[*vi] = white_color;
 210   depth_first_visit(search_tree, src, tree_printer, get(vertex_color, g));
 211
 212   return EXIT_SUCCESS;
 213 }