[Boost-commit] svn:boost r38823 - sandbox/SOC/2007/graphs/libs/graph/test/concept

From: asutton_at_[hidden]
Date: 2007-08-21 10:19:49

Author: asutton
Date: 2007-08-21 10:19:48 EDT (Tue, 21 Aug 2007)
New Revision: 38823
URL: http://svn.boost.org/trac/boost/changeset/38823

Log:
Added bron kerbosch concept checks

Added:
   sandbox/SOC/2007/graphs/libs/graph/test/concept/bron_kerbosch_all_cliques.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/test/concept/Jamfile.v2         |     1 +                                       
   sandbox/SOC/2007/graphs/libs/graph/test/concept/archetypes.hpp     |     7 +++----                                 
   sandbox/SOC/2007/graphs/libs/graph/test/concept/new_archetypes.hpp |    23 +++++++++++++++++++++++                 
   3 files changed, 27 insertions(+), 4 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/Jamfile.v2	2007-08-21 10:19:48 EDT (Tue, 21 Aug 2007)
@@ -14,4 +14,5 @@
     [ compile mean_geodesic_check.cpp ]
     [ compile eccentricity_check.cpp ]
     [ compile tiernan_all_cycles.cpp ]
+    [ compile bron_kerbosch_all_cliques.cpp ]
     ;
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/archetypes.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/archetypes.hpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/archetypes.hpp	2007-08-21 10:19:48 EDT (Tue, 21 Aug 2007)
@@ -68,15 +68,14 @@
     struct cycle_visitor_archetype
     {
         template <typename Path, typename Graph>
-        void cycle(const Path&, Graph&)
+        void cycle(const Path&, const Graph&)
         { }
     };
 
-    template <typename Graph>
     struct clique_visitor_archetype
     {
-        template <typename VertexSet>
-        void clique(const VertexSet&, Graph&)
+        template <typename VertexSet, typename Graph>
+        void clique(const VertexSet&, const Graph&)
         { }
     };
 }

Added: sandbox/SOC/2007/graphs/libs/graph/test/concept/bron_kerbosch_all_cliques.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/bron_kerbosch_all_cliques.cpp	2007-08-21 10:19:48 EDT (Tue, 21 Aug 2007)
@@ -0,0 +1,46 @@
+// (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 "archetypes.hpp"
+#include <boost/graph/bron_kerbosch_all_cliques.hpp>
+
+#include <iostream>
+
+using namespace std;
+using namespace boost;
+
+int
+main(int argc, char *argv[])
+{
+    {
+        typedef incidence_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag
+            > IncidenceGraph;
+        typedef vertex_list_graph_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag,
+                IncidenceGraph
+            > VertexListGraph;
+        typedef adjacency_matrix_archetype<
+                undirected_tag,
+                allow_parallel_edge_tag,
+                VertexListGraph
+            > AdjacencyMatrix;
+        typedef vertex_index_graph_archetype<
+                AdjacencyMatrix
+            > VertexIndexGraph;
+        typedef clique_visitor_archetype CliqueVisitor;
+
+        VertexIndexGraph& g = static_object<VertexIndexGraph>::get();
+        CliqueVisitor v;
+
+        bron_kerbosch_all_cliques(g, v);
+        bron_kerbosch_clique_number(g);
+    }
+
+    return 0;
+}

Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/new_archetypes.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/new_archetypes.hpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/new_archetypes.hpp	2007-08-21 10:19:48 EDT (Tue, 21 Aug 2007)
@@ -253,6 +253,29 @@
 
 
     //
+    // AdjacencyMatrix
+    //
+    template <typename Directed,
+              typename Parallel,
+              typename Base = detail::null_graph_archetype >
+    struct adjacency_matrix_archetype
+        : public graph_archetype<Directed, Parallel, Base>
+    {
+        // apparently, this type doesn't contribuet a graph tag to the
+        // traversal category. Fine by me...
+    };
+
+    template <typename D, typename P, typename B>
+    std::pair<typename adjacency_matrix_archetype<D,P,B>::edge_descriptor, bool>
+    edge(typename adjacency_matrix_archetype<D,P,B>::vertex_descriptor u,
+         typename adjacency_matrix_archetype<D,P,B>::vertex_descriptor v,
+         const adjacency_matrix_archetype<D,P,B>& g)
+    {
+        typedef typename adjacency_matrix_archetype<D,P,B>::edge_descriptor Edge;
+        return std::make_pair(Edge(), true);
+    }
+
+    //
     // ProprertyGraph
     //
     // I don't know how this works for bundled properties. I might need to