From: asutton_at_[hidden]
Date: 2007-08-20 13:43:59
Author: asutton
Date: 2007-08-20 13:43:57 EDT (Mon, 20 Aug 2007)
New Revision: 38793
URL: http://svn.boost.org/trac/boost/changeset/38793
Log:
Fixed small issues with archetypes
Added cycle/clique visitor, vertex/edge index graph archetypes
Added tiernan concept checks
Added:
sandbox/SOC/2007/graphs/libs/graph/test/concept/tiernan_all_cycles.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 | 50 ++++++++++++++++++++++++++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/test/concept/closeness_centrality_check.cpp | 8 +++---
sandbox/SOC/2007/graphs/libs/graph/test/concept/degree_centrality_check.cpp | 20 ++++++++--------
sandbox/SOC/2007/graphs/libs/graph/test/concept/eccentricity_check.cpp | 10 ++++----
sandbox/SOC/2007/graphs/libs/graph/test/concept/mean_geodesic_check.cpp | 12 ++++----
sandbox/SOC/2007/graphs/libs/graph/test/concept/new_archetypes.hpp | 1
sandbox/SOC/2007/graphs/libs/graph/test/concept/test_new_archetypes.cpp | 43 ++++++++++++++++++++++++++++++++++
8 files changed, 120 insertions(+), 25 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-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -13,4 +13,5 @@
[ compile closeness_centrality_check.cpp ]
[ compile mean_geodesic_check.cpp ]
[ compile eccentricity_check.cpp ]
+ [ compile tiernan_all_cycles.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-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -12,6 +12,41 @@
namespace boost
{
+ // VertexIndexGraph
+ template <typename GraphArchetype>
+ struct vertex_index_graph_archetype
+ : public property_graph_archetype<GraphArchetype, vertex_index_t, unsigned>
+ {
+ typedef unsigned vertex_index_type;
+ typedef property_graph_archetype<GraphArchetype, vertex_index_t, vertex_index_type> BaseType;
+ typedef typename BaseType::vertex_property_type vertex_property_type;
+ typedef void edge_property_type;
+ typedef typename BaseType::graph_tag graph_tag;
+ };
+
+ template <typename G>
+ void
+ renumber_vertex_indices(vertex_index_graph_archetype<G>&)
+ { }
+
+ // EdgeIndexGraph
+ template <typename GraphArchetype>
+ struct edge_index_graph_archetype
+ : public property_graph_archetype<GraphArchetype, edge_index_t, unsigned>
+ {
+ typedef unsigned edge_index_type;
+ typedef property_graph_archetype<GraphArchetype, edge_index_t, edge_index_type> BaseType;
+ typedef void vertex_property_type;
+ typedef typename BaseType::edge_property_type edge_property_type;
+ typedef typename BaseType::graph_tag graph_tag;
+ };
+
+ template <typename G>
+ void
+ renumber_edge_indices(edge_index_graph_archetype<G>&)
+ { }
+
+ // DegreeMeasure
template <typename Graph>
struct degree_measure_archetype
{
@@ -29,6 +64,21 @@
result_type operator ()(distance_type, const Graph&)
{ return result_type(); }
};
+
+ struct cycle_visitor_archetype
+ {
+ template <typename Path, typename Graph>
+ void cycle(const Path&, Graph&)
+ { }
+ };
+
+ template <typename Graph>
+ struct clique_visitor_archetype
+ {
+ template <typename VertexSet>
+ void clique(const VertexSet&, Graph&)
+ { }
+ };
}
#endif
Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/closeness_centrality_check.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/closeness_centrality_check.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/closeness_centrality_check.cpp 2007-08-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -29,8 +29,8 @@
DistanceMatrix dm;
Measure m;
- closeness_centrality(g, dm, cm);
- closeness_centrality(g, dm, cm, m);
+ all_closeness_centralities(g, dm, cm);
+ all_closeness_centralities(g, dm, cm, m);
}
{
@@ -46,8 +46,8 @@
DistanceMap dm;
Measure m;
- vertex_closeness_centrality(g, dm);
- vertex_closeness_centrality(g, dm, m);
+ closeness_centrality(g, dm);
+ closeness_centrality(g, dm, m);
}
return 0;
Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/degree_centrality_check.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/degree_centrality_check.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/degree_centrality_check.cpp 2007-08-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -31,8 +31,8 @@
CentralityMap cm;
Measure m;
- degree_centrality(g, cm);
- degree_centrality(g, cm, m);
+ all_degree_centralities(g, cm);
+ all_degree_centralities(g, cm, m);
}
{
@@ -53,9 +53,9 @@
CentralityMap cm;
Measure m;
- degree_centrality(g, cm, measure_influence(g));
- degree_centrality(g, cm, measure_prestige(g));
- degree_centrality(g, cm, m);
+ all_influence_values(g, cm);
+ all_prestige_values(g, cm);
+ all_degree_centralities(g, cm, m);
}
{
@@ -70,8 +70,8 @@
Vertex v = static_object<Vertex>::get();
Measure m;
- vertex_degree_centrality(g, v);
- vertex_degree_centrality(g, v, m);
+ degree_centrality(g, v);
+ degree_centrality(g, v, m);
}
{
@@ -86,9 +86,9 @@
Vertex v = static_object<Vertex>::get();
Measure m;
- vertex_degree_centrality(g, v, measure_influence(g));
- vertex_degree_centrality(g, v, measure_prestige(g));
- vertex_degree_centrality(g, v, m);
+ influence(g, v);
+ prestige(g, v);
+ degree_centrality(g, v, m);
}
return 0;
Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/eccentricity_check.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/eccentricity_check.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/eccentricity_check.cpp 2007-08-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -27,7 +27,7 @@
EccentricityMap em;
DistanceMatrix dm;
- eccentricity(g, dm, em);
+ all_eccentricities(g, dm, em);
}
{
@@ -41,7 +41,7 @@
Graph& g = static_object<Graph>::get();
DistanceMap dm;
- vertex_eccentricity(g, dm);
+ eccentricity(g, dm);
}
{
@@ -55,9 +55,9 @@
Graph& g = static_object<Graph>::get();
EccentricityMap em;
- graph_radius(g, em);
- graph_diameter(g, em);
- graph_radius_diameter(g, em);
+ radius(g, em);
+ diameter(g, em);
+ radius_and_diameter(g, em);
}
return 0;
Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/mean_geodesic_check.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/mean_geodesic_check.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/mean_geodesic_check.cpp 2007-08-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -29,8 +29,8 @@
DistanceMatrix dm;
Measure m;
- mean_geodesic(g, dm, cm);
- mean_geodesic(g, dm, cm, m);
+ all_mean_geodesics(g, dm, cm);
+ all_mean_geodesics(g, dm, cm, m);
}
{
@@ -46,8 +46,8 @@
DistanceMap dm;
Measure m;
- vertex_mean_geodesic(g, dm);
- vertex_mean_geodesic(g, dm, m);
+ mean_geodesic(g, dm);
+ mean_geodesic(g, dm, m);
}
{
@@ -63,8 +63,8 @@
CentralityMap cm;
Measure m;
- graph_mean_geodesic(g, cm);
- graph_mean_geodesic(g, cm, m);
+ small_world_distance(g, cm);
+ small_world_distance(g, cm, m);
}
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-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -67,6 +67,7 @@
: public regular_archetype<>
{
descriptor_archetype() { }
+ descriptor_archetype(const descriptor_archetype&) { }
descriptor_archetype(detail::dummy_constructor) { }
};
Modified: sandbox/SOC/2007/graphs/libs/graph/test/concept/test_new_archetypes.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/concept/test_new_archetypes.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/test_new_archetypes.cpp 2007-08-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -5,6 +5,7 @@
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
#include "new_archetypes.hpp"
+#include "archetypes.hpp"
#include <boost/graph/graph_traits.hpp>
using namespace std;
@@ -305,5 +306,47 @@
// put(vertex_index, g, v, size_t());
}
+ // test the enigmatic index graph archetypes
+ {
+ typedef graph_archetype<
+ undirected_tag,
+ allow_parallel_edge_tag
+ > Graph;
+ typedef vertex_index_graph_archetype<
+ Graph
+ > VertexIndexGraph;
+ typedef graph_traits<VertexIndexGraph>::vertex_descriptor Vertex;
+ typedef VertexIndexGraph::vertex_index_type Index;
+ typedef property_map<VertexIndexGraph, vertex_index_t>::type IndexMap;
+
+ VertexIndexGraph& g = static_object<VertexIndexGraph>::get();
+ IndexMap m = get(vertex_index, g);
+ Index x = get(vertex_index, g, Vertex());
+ renumber_vertex_indices(g);
+ ignore_unused_variable_warning(m);
+ ignore_unused_variable_warning(x);
+ }
+
+ // test the enigmatic index graph archetypes
+ {
+ typedef graph_archetype<
+ undirected_tag,
+ allow_parallel_edge_tag
+ > Graph;
+ typedef edge_index_graph_archetype<
+ Graph
+ > EdgeIndexGraph;
+ typedef graph_traits<EdgeIndexGraph>::vertex_descriptor Vertex;
+ typedef EdgeIndexGraph::edge_index_type Index;
+ typedef property_map<EdgeIndexGraph, edge_index_t>::type IndexMap;
+
+ EdgeIndexGraph& g = static_object<EdgeIndexGraph>::get();
+ IndexMap m = get(edge_index, g);
+ Index x = get(edge_index, g, Vertex());
+ renumber_edge_indices(g);
+ ignore_unused_variable_warning(m);
+ ignore_unused_variable_warning(x);
+ }
+
return 0;
}
Added: sandbox/SOC/2007/graphs/libs/graph/test/concept/tiernan_all_cycles.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/concept/tiernan_all_cycles.cpp 2007-08-20 13:43:57 EDT (Mon, 20 Aug 2007)
@@ -0,0 +1,40 @@
+// (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/tiernan_all_cycles.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 vertex_index_graph_archetype<
+ VertexListGraph
+ > VertexIndexGraph;
+ typedef cycle_visitor_archetype CycleVisitor;
+
+ VertexIndexGraph& g = static_object<VertexIndexGraph>::get();
+ CycleVisitor v;
+
+ tiernan_all_cycles(g, v);
+ }
+
+ return 0;
+}