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