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

   1 // (C) Copyright Andrew Sutton 2007
   2 //
   3 // Use, modification and distribution are subject to the
   4 // Boost Software License, Version 1.0 (See accompanying file
   5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //[code_bron_kerbosch_print_cliques
   8 #include <iostream>
   9
  10 #include <boost/graph/undirected_graph.hpp>
  11 #include <boost/graph/bron_kerbosch_all_cliques.hpp>
  12
  13 #include "helper.hpp"
  14
  15 using namespace std;
  16 using namespace boost;
  17
  18 // The clique_printer is a visitor that will print the vertices that comprise
  19 // a clique. Note that the vertices are not given in any specific order.
  20 template < typename OutputStream > struct clique_printer
  21 {
  22     clique_printer(OutputStream& stream) : os(stream) {}
  23
  24     template < typename Clique, typename Graph >
  25     void clique(const Clique& c, const Graph& g)
  26     {
  27         // Iterate over the clique and print each vertex within it.
  28         typename Clique::const_iterator i, end = c.end();
  29         for (i = c.begin(); i != end; ++i)
  30         {
  31             os << g[*i].name << " ";
  32         }
  33         os << endl;
  34     }
  35     OutputStream& os;
  36 };
  37
  38 // The Actor type stores the name of each vertex in the graph.
  39 struct Actor
  40 {
  41     string name;
  42 };
  43
  44 // Declare the graph type and its vertex and edge types.
  45 typedef undirected_graph< Actor > Graph;
  46 typedef graph_traits< Graph >::vertex_descriptor Vertex;
  47 typedef graph_traits< Graph >::edge_descriptor Edge;
  48
  49 // The name map provides an abstract accessor for the names of
  50 // each vertex. This is used during graph creation.
  51 typedef property_map< Graph, string Actor::* >::type NameMap;
  52
  53 int main(int argc, char* argv[])
  54 {
  55     // Create the graph and and its name map accessor.
  56     Graph g;
  57     NameMap nm(get(&Actor::name, g));
  58
  59     // Read the graph from standard input.
  60     read_graph(g, nm, cin);
  61
  62     // Instantiate the visitor for printing cliques
  63     clique_printer< ostream > vis(cout);
  64
  65     // Use the Bron-Kerbosch algorithm to find all cliques, printing them
  66     // as they are found.
  67     bron_kerbosch_all_cliques(g, vis);
  68
  69     return 0;
  70 }
  71 //]