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

   1 //=======================================================================
   2 // Copyright 2001 University of Notre Dame.
   3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
   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
  10 #include <cstdio>
  11 #include <cstring>
  12 #include <iostream>
  13 #include <boost/graph/stanford_graph.hpp>
  14 #include <boost/graph/strong_components.hpp>
  15
  16 #define specs(v) \
  17  (filename ? index_map[v] : v->cat_no) << " " << v->name
  18
  19 int main(int argc, char* argv[])
  20 {
  21   using namespace boost;
  22   Graph* g;
  23   typedef graph_traits<Graph*>::vertex_descriptor vertex_t;
  24   unsigned long n = 0;
  25   unsigned long d = 0;
  26   unsigned long p = 0;
  27   long s = 0;
  28   char* filename = NULL;
  29   int c, i;
  30
  31   while (--argc) {
  32     if (sscanf(argv[argc], "-n%lu", &n) == 1);
  33     else if (sscanf(argv[argc], "-d%lu", &d) == 1);
  34     else if (sscanf(argv[argc], "-p%lu", &p) == 1);
  35     else if (sscanf(argv[argc], "-s%ld", &s) == 1);
  36     else if (strncmp(argv[argc], "-g", 2) == 0)
  37       filename = argv[argc] + 2;
  38     else {
  39       fprintf(stderr, "Usage: %s [-nN][-dN][-pN][-sN][-gfoo]\n", argv[0]);
  40       return -2;
  41     }
  42   }
  43
  44   g = (filename ? restore_graph(filename) : roget(n, d, p, s));
  45   if (g == NULL) {
  46     fprintf(stderr, "Sorry, can't create the graph! (error code %ld)\n",
  47             panic_code);
  48     return -1;
  49   }
  50   printf("Reachability analysis of %s\n\n", g->id);
  51
  52   // - The root map corresponds to what Knuth calls the "min" field.
  53   // - The discover time map is the "rank" field
  54   // - Knuth uses the rank field for double duty, to record the
  55   //   discover time, and to keep track of which vertices have
  56   //   been visited. The BGL strong_components() function needs
  57   //   a separate field for marking colors, so we use the w field.
  58
  59   std::vector<int> comp(num_vertices(g));
  60   property_map<Graph*, vertex_index_t>::type
  61     index_map = get(vertex_index, g);
  62
  63   property_map<Graph*, v_property<vertex_t> >::type
  64     root = get(v_property<vertex_t>(), g);
  65
  66   int num_comp = strong_components
  67     (g, make_iterator_property_map(comp.begin(), index_map),
  68      root_map(root).
  69      discover_time_map(get(z_property<long>(), g)).
  70      color_map(get(w_property<long>(), g)));
  71
  72   std::vector< std::vector<vertex_t> > strong_comp(num_comp);
  73
  74   // First add representative vertices to each component's list
  75   graph_traits<Graph*>::vertex_iterator vi, vi_end;
  76   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
  77     if (root[*vi] == *vi)
  78       strong_comp[comp[index_map[*vi]]].push_back(*vi);
  79
  80   // Then add the other vertices of the component
  81   for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
  82     if (root[*vi] != *vi)
  83       strong_comp[comp[index_map[*vi]]].push_back(*vi);
  84
  85   // We do not print out the "from" and "to" information as Knuth
  86   // does because we no longer have easy access to that information
  87   // from outside the algorithm.
  88
  89   for (c = 0; c < num_comp; ++c) {
  90     vertex_t v = strong_comp[c].front();
  91     std::cout << "Strong component `" << specs(v) << "'";
  92     if (strong_comp[c].size() > 1) {
  93       std::cout << " also includes:\n";
  94       for (i = 1; i < strong_comp[c].size(); ++i)
  95         std::cout << " " << specs(strong_comp[c][i]) << std::endl;
  96     } else
  97       std::cout << std::endl;
  98   }
  99
 100   // Next we print out the "component graph" or "condensation", that
 101   // is, we consider each component to be a vertex in a new graph
 102   // where there is an edge connecting one component to another if there
 103   // is one or more edges connecting any of the vertices from the
 104   // first component to any of the vertices in the second. We use the
 105   // name of the representative vertex as the name of the component.
 106
 107   printf("\nLinks between components:\n");
 108
 109   // This array provides an efficient way to check if we've already
 110   // created a link from the current component to the component
 111   // of the target vertex.
 112   std::vector<int> mark(num_comp, (std::numeric_limits<int>::max)());
 113
 114   // We go in reverse order just to mimic the output ordering in
 115   // Knuth's version.
 116   for (c = num_comp - 1; c >= 0; --c) {
 117     vertex_t u = strong_comp[c][0];
 118     for (i = 0; i < strong_comp[c].size(); ++i) {
 119       vertex_t v = strong_comp[c][i];
 120       graph_traits<Graph*>::out_edge_iterator ei, ei_end;
 121       for (boost::tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) {
 122         vertex_t x = target(*ei, g);
 123         int comp_x = comp[index_map[x]];
 124         if (comp_x != c && mark[comp_x] != c) {
 125           mark[comp_x] = c;
 126           vertex_t w = strong_comp[comp_x][0];
 127           std::cout << specs(u) << " -> " << specs(w)
 128                     << " (e.g., " << specs(v) << " -> " << specs(x) << ")\n";
 129         } // if
 130       } // for
 131     } // for
 132   } // for
 133 }