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>
21 struct clique_printer
22 {
clique_printerclique_printer23 clique_printer(OutputStream& stream)
24 : os(stream)
25 { }
26
27 template <typename Clique, typename Graph>
cliqueclique_printer28 void clique(const Clique& c, const Graph& g)
29 {
30 // Iterate over the clique and print each vertex within it.
31 typename Clique::const_iterator i, end = c.end();
32 for(i = c.begin(); i != end; ++i) {
33 os << g[*i].name << " ";
34 }
35 os << endl;
36 }
37 OutputStream& os;
38 };
39
40 // The Actor type stores the name of each vertex in the graph.
41 struct Actor
42 {
43 string name;
44 };
45
46 // Declare the graph type and its vertex and edge types.
47 typedef undirected_graph<Actor> Graph;
48 typedef graph_traits<Graph>::vertex_descriptor Vertex;
49 typedef graph_traits<Graph>::edge_descriptor Edge;
50
51 // The name map provides an abstract accessor for the names of
52 // each vertex. This is used during graph creation.
53 typedef property_map<Graph, string Actor::*>::type NameMap;
54
55 int
main(int argc,char * argv[])56 main(int argc, char *argv[])
57 {
58 // Create the graph and and its name map accessor.
59 Graph g;
60 NameMap nm(get(&Actor::name, g));
61
62 // Read the graph from standard input.
63 read_graph(g, nm, cin);
64
65 // Instantiate the visitor for printing cliques
66 clique_printer<ostream> vis(cout);
67
68 // Use the Bron-Kerbosch algorithm to find all cliques, printing them
69 // as they are found.
70 bron_kerbosch_all_cliques(g, vis);
71
72 return 0;
73 }
74 //]
75