From: asutton_at_[hidden]
Date: 2007-08-02 12:11:21
Author: asutton
Date: 2007-08-02 12:11:20 EDT (Thu, 02 Aug 2007)
New Revision: 38401
URL: http://svn.boost.org/trac/boost/changeset/38401
Log:
Updating some tests
Added a test for eccentricity (it was missing)
Added:
sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 | 6 +++++
sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp | 7 ++---
sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp | 46 ++++++++++++++-------------------------
sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp | 10 ++++----
sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp | 3 -
5 files changed, 32 insertions(+), 40 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-08-02 12:11:20 EDT (Thu, 02 Aug 2007)
@@ -53,6 +53,12 @@
: <include>../../../
;
+exe eccentricity
+ : eccentricity.cpp
+ : <include>$BOOST_ROOT
+ : <include>../../../
+ ;
+
exe cluster
: cluster.cpp
: <include>$BOOST_ROOT
Modified: sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/clique.cpp 2007-08-02 12:11:20 EDT (Thu, 02 Aug 2007)
@@ -13,7 +13,7 @@
#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/clique.hpp>
+#include <boost/graph/bron_kerbosch_all_cliques.hpp>
#include <boost/graph/generators/prism_graph.hpp>
#include <boost/graph/generators/complete_graph.hpp>
@@ -74,12 +74,11 @@
// build_graph(g);
// make_prism_graph(g, 3, 2);
- make_complete_graph(g, 5);
+ make_complete_graph(g, 4);
- bron_kerbosch_visit_cliques(g, clique_printer<ostream>(cout));
+ bron_kerbosch_all_cliques(g, clique_printer<ostream>(cout));
}
-
int
main(int argc, char *argv[])
{
Modified: sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/cluster.cpp 2007-08-02 12:11:20 EDT (Thu, 02 Aug 2007)
@@ -43,44 +43,32 @@
add_edge(v[4], v[0], g);
};
-
-void test_1()
+template <typename Graph>
+void test()
{
- typedef undirected_graph<> Graph;
-
Graph g;
build_graph(g);
- Graph::vertex_iterator i, end;
+ typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
- cerr << get_vertex_index(*i, g) << "\n";
- cerr << " triples: " << num_centered_triples(g, *i) << "\n";
- cerr << " triangles: " << num_centered_triangles(g, *i) << "\n";
- cerr << " coef: " << clustering_coefficient(g, *i) << "\n\n";
+ unsigned id = get(vertex_index, g, *i);
+ size_t r = vertex_num_routes(g, *i);
+ size_t t = vertex_num_triangles(g, *i);
+ float coef = vertex_clustering_coefficient(g, *i);
+ std::cout << id << " {" << r << " " << t << " " << coef << "}\n";
}
- cerr << "cc: " << clustering_coefficient(g) << "\n";
-}
-
-void test_2()
-{
- typedef directed_graph<> Graph;
-
- Graph g;
- build_graph(g);
-
- Graph::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- cerr << get_vertex_index(*i, g) << "\n";
- cerr << " triples: " << num_centered_triples(g, *i) << "\n";
- cerr << " triangles: " << num_centered_triangles(g, *i) << "\n";
- cerr << " coef: " << clustering_coefficient(g, *i) << "\n\n";
- }
- cerr << "cc: " << clustering_coefficient(g) << "\n";
+ cerr << " cc: " << graph_clustering_coefficient(g) << "\n";
}
int
main(int argc, char *argv[])
{
- test_1();
- test_2();
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> Digraph;
+
+ std::cout << "*** undirected_graph<> ***\n";
+ test<Graph>();
+
+ std::cout << "*** directed_graph<> ***\n";
+ test<Digraph>();
}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/cycle.cpp 2007-08-02 12:11:20 EDT (Thu, 02 Aug 2007)
@@ -13,7 +13,7 @@
#include <boost/graph/undirected_graph.hpp>
#include <boost/graph/directed_graph.hpp>
-#include <boost/graph/cycle.hpp>
+#include <boost/graph/tiernan_all_cycles.hpp>
#include <boost/graph/generators/cycle_graph.hpp>
#include <boost/graph/generators/prism_graph.hpp>
#include <boost/graph/generators/complete_graph.hpp>
@@ -103,14 +103,14 @@
{
Graph g;
// build_graph(g);
- // make_prism_graph(g, 3, 2);
- make_complete_graph(g, 4);
+ make_prism_graph(g, 3, 2);
+ // make_complete_graph(g, 4, with_clockwise_cycle());
size_t count = 0;
- tiernan_visit_cycles(g, count_cycles(count));
+ tiernan_all_cycles(g, count_cycles(count));
std::cout << "number of cycles: " << count << "\n";
- tiernan_visit_cycles(g, print_cycles(cout));
+ tiernan_all_cycles(g, print_cycles(cout));
}
Added: sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp 2007-08-02 12:11:20 EDT (Thu, 02 Aug 2007)
@@ -0,0 +1,159 @@
+// (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 <tr1/unordered_map>
+
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
+
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/floyd_warshall_shortest.hpp>
+#include <boost/graph/eccentricity.hpp>
+#include <boost/graph/radius.hpp>
+#include <boost/graph/diameter.hpp>
+
+using namespace std;
+using namespace boost;
+
+template <typename T>
+struct numeric
+{
+ numeric(T x) : value(x) { }
+ T value;
+};
+
+template <typename Value>
+numeric<Value>
+make_numeric(Value x)
+{ return numeric<Value>(x); }
+
+template <typename Value>
+ostream& operator <<(ostream& os, const numeric<Value>& x)
+{
+ if(x.value == numeric_values<Value>::infinity()) {
+ os << "i";
+ }
+ else {
+ os << x.value;
+ }
+ return os;
+}
+
+struct VertexProp
+{
+ int dummy;
+};
+
+struct EdgeProp
+{
+ int weight;
+};
+
+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);
+ vector<Edge> e;
+
+ // 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)
+ e.push_back(add_edge(v[0], v[1], g).first);
+ e.push_back(add_edge(v[1], v[2], g).first);
+ e.push_back(add_edge(v[2], v[0], g).first);
+ e.push_back(add_edge(v[3], v[4], g).first);
+ e.push_back(add_edge(v[4], v[0], g).first);
+
+ g[e[0]].weight = 1;
+ g[e[1]].weight = 1;
+ g[e[2]].weight = 1;
+ g[e[3]].weight = 1;
+ g[e[4]].weight = 1;
+};
+
+template <typename Graph, typename PropertyMap>
+void print_map(const Graph& g, PropertyMap pm)
+{
+ typename Graph::vertex_iterator i, end;
+ cout << "{ ";
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << make_numeric(pm[*i]) << " ";
+ }
+ cout << "}\n";
+}
+
+template <typename Graph, typename Matrix>
+void print_matrix(const Graph& g, Matrix m)
+{
+ cout << "{ ";
+ typename Graph::vertex_iterator i, j, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ if(i != vertices(g).first) {
+ cout << " ";
+ }
+ print_map(g, m[*i]);
+ }
+}
+
+template <typename Graph>
+void test()
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef exterior_vertex_property<Graph, int> EccentricityProperty;
+ typedef typename EccentricityProperty::container_type EccentricityContainer;
+ typedef typename EccentricityProperty::map_type EccentricityMap;
+
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+
+ typedef typename property_map<Graph, int EdgeProp::*>::type WeightMap;
+
+ Graph g;
+ build_graph(g);
+
+ EccentricityContainer eccs(num_vertices(g));
+ EccentricityMap ecc(eccs);
+ DistanceMatrix dist(num_vertices(g));
+ WeightMap weights(get(&EdgeProp::weight, g));
+
+ floyd_warshall_all_pairs_shortest_paths(g, dist, weight_map(weights));
+ eccentricity(g, dist, ecc);
+
+ print_matrix(g, dist);
+ print_map(g, ecc);
+
+ std::cout << "radius: " << make_numeric(graph_radius(g, ecc)) << "\n";
+ std::cout << "diameter: " << make_numeric(graph_diameter(g, ecc)) << "\n";
+}
+
+int
+main(int argc, char *argv[])
+{
+ typedef undirected_graph<VertexProp, EdgeProp> Graph;
+ typedef directed_graph<VertexProp, EdgeProp> Digraph;
+
+ cout << "\n*** undirected_graph<> *** \n";
+ test<Graph>();
+
+ cout << "\n*** directed_graph<> *** \n";
+ test<Digraph>();
+}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp 2007-08-02 12:11:20 EDT (Thu, 02 Aug 2007)
@@ -137,8 +137,7 @@
print_matrix(g, dist);
print_map(g, geo);
- std::cout << "mgeo: " << make_numeric(graph_mean_geodesic(g, dist)) << "\n";
-
+ std::cout << "mgeo: " << make_numeric(graph_mean_geodesic(g, geo)) << "\n";
}
int