From: asutton_at_[hidden]
Date: 2007-08-14 09:19:32
Author: asutton
Date: 2007-08-14 09:19:29 EDT (Tue, 14 Aug 2007)
New Revision: 38655
URL: http://svn.boost.org/trac/boost/changeset/38655
Log:
Rewrote mean_geodesic as a more formal test
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 | 3
sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp | 176 ++++++++++++++++++---------------------
2 files changed, 81 insertions(+), 98 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-14 09:19:29 EDT (Tue, 14 Aug 2007)
@@ -11,6 +11,7 @@
[ run constant_property_map.cpp ]
[ run degree_centrality.cpp ]
[ run closeness_centrality.cpp ]
+ [ run mean_geodesic.cpp ]
;
# exe properties : properties.cpp ;
@@ -25,8 +26,6 @@
#
# exe components : components.cpp ;
#
-# exe mean_geodesic : mean_geodesic.cpp ;
-#
# exe eccentricity : eccentricity.cpp ;
#
# exe cluster : cluster.cpp ;
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-14 09:19:29 EDT (Tue, 14 Aug 2007)
@@ -5,154 +5,138 @@
// 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/constant_property_map.hpp>
-#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
#include <boost/graph/geodesic_distance.hpp>
using namespace std;
using namespace boost;
-template <typename T>
-struct numeric
+// useful types
+// number of vertices in the graph
+static const unsigned N = 5;
+
+template <typename Graph>
+struct vertex_vector
{
- numeric(T x) : value(x) { }
- T value;
+ typedef graph_traits<Graph> traits;
+ typedef vector<typename traits::vertex_descriptor> type;
};
-template <typename Value>
-numeric<Value>
-make_numeric(Value x)
-{ return numeric<Value>(x); }
-
-template <typename Value>
-ostream& operator <<(ostream& os, const numeric<Value>& x)
+template <typename Graph>
+void build_graph(Graph& g,
+ typename vertex_vector<Graph>::type& v)
{
- if(x.value == numeric_values<Value>::infinity()) {
- os << "i";
- }
- else {
- os << x.value;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // add vertices
+ for(size_t i = 0; i < N; ++i) {
+ v[i] = add_vertex(g);
}
- return os;
-}
-struct VertexProp
-{
- int dummy;
+ // add edges
+ add_edge(v[0], v[1], g);
+ add_edge(v[1], v[2], g);
+ add_edge(v[2], v[0], g);
+ add_edge(v[3], v[4], g);
+ add_edge(v[4], v[0], g);
};
-struct EdgeProp
-{
- int weight;
-};
template <typename Graph>
-void build_graph(Graph& g)
+void test_undirected()
{
- typedef typename Graph::vertex_descriptor Vertex;
- typedef typename Graph::edge_descriptor Edge;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef typename graph_traits<Graph>::edge_descriptor Edge;
+
+ typedef exterior_vertex_property<Graph, float> CentralityProperty;
+ typedef typename CentralityProperty::container_type CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
+
+ typedef exterior_vertex_property<Graph, int> DistanceProperty;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+ typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
+
+ typedef constant_property_map<Edge, int> WeightMap;
- static const unsigned N = 5;
+ Graph g;
vector<Vertex> v(N);
- vector<Edge> e;
+ build_graph(g, v);
- // add some vertices
- for(size_t i = 0; i < N; ++i) {
- // v[i] = add_vertex(g);
- v[i] = add_vertex(g);
- }
+ CentralityContainer centralities(num_vertices(g));
+ DistanceMatrix distances(num_vertices(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;
-};
+ CentralityMap cm(centralities, g);
+ DistanceMatrixMap dm(distances, g);
-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";
-}
+ WeightMap wm(1);
-template <typename Graph, typename Matrix>
-void print_matrix(const Graph& g, Matrix m)
-{
- cout << "[\n";
- typename Graph::vertex_iterator i, j, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- print_map(g, m[*i]);
- }
- cout << "]\n";
+ floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+ mean_geodesic(g, dm, cm);
+
+ float geo = graph_mean_geodesic(g, cm);
+
+ BOOST_ASSERT(cm[v[0]] == float(5)/5);
+ BOOST_ASSERT(cm[v[1]] == float(7)/5);
+ BOOST_ASSERT(cm[v[2]] == float(7)/5);
+ BOOST_ASSERT(cm[v[3]] == float(9)/5);
+ BOOST_ASSERT(cm[v[4]] == float(6)/5);
+ BOOST_ASSERT(geo == float(34)/15);
}
template <typename Graph>
-void test()
+void test_directed()
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
- typedef exterior_vertex_property<Graph, float> GeodesicProperty;
- typedef typename GeodesicProperty::container_type GeodesicContainer;
- typedef typename GeodesicProperty::map_type GeodesicMap;
+ typedef exterior_vertex_property<Graph, float> CentralityProperty;
+ typedef typename CentralityProperty::container_type CentralityContainer;
+ typedef typename CentralityProperty::map_type CentralityMap;
typedef exterior_vertex_property<Graph, int> DistanceProperty;
typedef typename DistanceProperty::matrix_type DistanceMatrix;
typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
- typedef typename property_map<Graph, int EdgeProp::*>::type WeightMap;
+ typedef constant_property_map<Edge, int> WeightMap;
Graph g;
- build_graph(g);
+ vector<Vertex> v(N);
+ build_graph(g, v);
- GeodesicContainer geodesics(num_vertices(g));
- GeodesicMap gm(geodesics, g);
+ CentralityContainer centralities(num_vertices(g));
+ DistanceMatrix distances(num_vertices(g));
- DistanceMatrix dist(num_vertices(g));
- DistanceMatrixMap dm(dist, g);
+ CentralityMap cm(centralities, g);
+ DistanceMatrixMap dm(distances, g);
- WeightMap wm(get(&EdgeProp::weight, g));
+ WeightMap wm(1);
floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
- mean_geodesic(g, dm, gm);
-
- print_matrix(g, dm);
- print_map(g, gm);
+ mean_geodesic(g, dm, cm);
+ float geo = graph_mean_geodesic(g, cm);
- std::cout << "mgeo: " << make_numeric(graph_mean_geodesic(g, gm)) << "\n";
+ float inf = numeric_values<float>::infinity();
+ BOOST_ASSERT(cm[v[0]] == inf);
+ BOOST_ASSERT(cm[v[1]] == inf);
+ BOOST_ASSERT(cm[v[2]] == inf);
+ BOOST_ASSERT(cm[v[3]] == float(10)/5);
+ BOOST_ASSERT(cm[v[4]] == inf);
+ BOOST_ASSERT(geo == inf);
}
+
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>();
+ typedef undirected_graph<> Graph;
+ typedef directed_graph<> Digraph;
- cout << "\n*** directed_graph<> *** \n";
- test<Digraph>();
+ test_undirected<Graph>();
+ test_directed<Digraph>();
}