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 {
clique_printerclique_printer22 clique_printer(OutputStream& stream) : os(stream) {}
23
24 template < typename Clique, typename Graph >
cliqueclique_printer25 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
main(int argc,char * argv[])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 //]
72