[Boost-commit] svn:boost r7447

From: asutton_at_[hidden]
Date: 2007-07-16 14:31:40

Author: asutton
Date: 2007-07-16 14:31:38 EDT (Mon, 16 Jul 2007)
New Revision: 7447
URL: http://svn.boost.org/trac/boost/changeset/7447

Log:
Preliminary implementation of B&K click-finding algorithm - doesn't perform
optimized candidate selection, but does work on both directed and undirected
graphs.

Added:
   sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 |     6 ++++++                                  
   1 files changed, 6 insertions(+), 0 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2	2007-07-16 14:31:38 EDT (Mon, 16 Jul 2007)
@@ -59,3 +59,9 @@
     : <include>$BOOST_ROOT
     : <include>../../../
     ;
+
+exe clique
+    : clique.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../
+    ;

Added: sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp	2007-07-16 14:31:38 EDT (Mon, 16 Jul 2007)
@@ -0,0 +1,94 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <iterator>
+#include <algorithm>
+#include <vector>
+#include <map>
+#include <tr1/unordered_map>
+
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/clique.hpp>
+#include <boost/graph/generators/prism_graph.hpp>
+#include <boost/graph/generators/complete_graph.hpp>
+
+using namespace std;
+using namespace boost;
+
+template <typename OutStream>
+struct clique_printer : public clique_visitor
+{
+    clique_printer(OutStream& os)
+        : mOs(os)
+    { }
+
+    template <typename VertexSet, typename Graph>
+    inline void
+    clique(const VertexSet& vs, Graph& g)
+    {
+        mOs << "clique: ";
+        typename VertexSet::const_iterator i, end = vs.end();
+        for(i = vs.begin(); i != end; ++i) {
+            mOs << get(vertex_index, g, *i) << " ";
+        }
+        mOs << std::endl;
+    }
+
+    OutStream& mOs;
+};
+
+template <typename Graph>
+void build_graph(Graph& g)
+{
+    typedef typename Graph::vertex_descriptor Vertex;
+    typedef typename Graph::edge_descriptor Edge;
+
+    static const unsigned N = 5;
+    vector<Vertex> v(N);
+
+    // add some vertices
+    for(size_t i = 0; i < N; ++i) {
+        // v[i] = add_vertex(g);
+        v[i] = add_vertex(g);
+    }
+
+    // add some edges (with weights)
+    add_edge(v[0], v[1], g);
+    add_edge(v[1], v[2], g);
+    add_edge(v[2], v[0], g);
+
+    add_edge(v[0], v[3], g);
+    add_edge(v[3], v[4], g);
+    add_edge(v[4], v[0], g);
+};
+
+template <typename Graph>
+void test()
+{
+    Graph g;
+
+    // build_graph(g);
+    // make_prism_graph(g, 3, 2);
+    make_complete_graph(g, 5);
+
+    visit_cliques(g, clique_printer<ostream>(cout));
+}
+
+
+int
+main(int argc, char *argv[])
+{
+    typedef undirected_graph<> Graph;
+    typedef directed_graph<> DiGraph;
+
+    cout << "*** undirected ***\n";
+    test<Graph>();
+
+    cout << "*** directed ***\n";
+    test<DiGraph>();
+}