From: asutton_at_[hidden]
Date: 2007-08-01 09:49:15
Author: asutton
Date: 2007-08-01 09:49:13 EDT (Wed, 01 Aug 2007)
New Revision: 38334
URL: http://svn.boost.org/trac/boost/changeset/38334
Log:
Moved distance tests to closeness centrality
Added mean geodesic tests
Added:
sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp
- copied, changed from r7615, /sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp
sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp (contents, props changed)
Removed:
sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2 | 10 +++
sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp | 92 +++++++--------------------------------
sandbox/SOC/2007/graphs/libs/graph/test/degree_centrality.cpp | 2
3 files changed, 25 insertions(+), 79 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-01 09:49:13 EDT (Wed, 01 Aug 2007)
@@ -41,8 +41,14 @@
: <include>../../../
;
-exe distance
- : distance.cpp
+exe closeness_centrality
+ : closeness_centrality.cpp
+ : <include>$BOOST_ROOT
+ : <include>../../../
+ ;
+
+exe mean_geodesic
+ : mean_geodesic.cpp
: <include>$BOOST_ROOT
: <include>../../../
;
Copied: sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp (from r7615, /sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp)
==============================================================================
--- /sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/closeness_centrality.cpp 2007-08-01 09:49:13 EDT (Wed, 01 Aug 2007)
@@ -8,9 +8,7 @@
#include <iterator>
#include <algorithm>
#include <vector>
-#include <map>
#include <tr1/unordered_map>
-#include <cxxabi.h>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/undirected_graph.hpp>
@@ -18,9 +16,7 @@
#include <boost/graph/exterior_property.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
-#include <boost/graph/johnson_all_pairs_shortest.hpp>
#include <boost/graph/floyd_warshall_shortest.hpp>
-#include <boost/graph/distance.hpp>
#include <boost/graph/closeness_centrality.hpp>
using namespace std;
@@ -94,94 +90,40 @@
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::container_type DistanceContainer;
- typedef typename DistanceProperty::map_type DistanceMap;
+ typedef typename DistanceProperty::matrix_type DistanceMatrix;
+
typedef typename property_map<Graph, int EdgeProp::*>::type WeightMap;
Graph g;
build_graph(g);
- // single-vertex computations
- {
- DistanceContainer distances(num_vertices(g));
- DistanceMap dists(distances);
- WeightMap weights = get(&EdgeProp::weight, g);
-
- dijkstra_shortest_paths(g, *vertices(g).first,
- weight_map(weights).
- distance_map(dists));
-
- double total_geo = total_geodesic_distance(g, dists);
- double mean_geo = mean_geodesic_distance(g, dists);
- double inverse_geo = inverse_geodesic_distance(g, dists);
- double close = closeness(g, dists);
-
- cout << "* geodesics: "; print_map(g, dists);
- cout << "* total geo: " << total_geo << "\n";
- cout << "* mean geo: " << mean_geo << "\n";
- cout << "* inv geo: " << inverse_geo << "\n";
- cout << "* closeness: " << close << "\n";
- }
+ CentralityContainer centralities(num_vertices(g));
+ CentralityMap cent(centralities);
+ DistanceMatrix dist(num_vertices(g));
+ WeightMap weights(get(&EdgeProp::weight, g));
+ floyd_warshall_all_pairs_shortest_paths(g, dist, weight_map(weights));
+ closeness_centrality(g, dist, cent);
+
+ print_matrix(g, dist);
+ print_map(g, cent);
- // all-vertices computation
- {
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
-
- WeightMap weights = get(&EdgeProp::weight, g);
- DistanceMatrix dists(num_vertices(g));
-
- // compute all shortest paths so we can run some other stuff
- floyd_warshall_all_pairs_shortest_paths(g, dists,
- weight_map(weights));
-
- print_matrix(g, dists);
-
- typedef exterior_vertex_property<Graph, float> ClosenessProperty;
- typedef typename ClosenessProperty::container_type ClosenessContainer;
- typedef typename ClosenessProperty::map_type ClosenessMap;
-
- {
- ClosenessContainer c(num_vertices(g));
- ClosenessMap m(c);
- all_total_geodesic_distances(g, dists, m);
- std::cout << "all total geodesics: "; print_map(g, m);
- }
-
- {
- ClosenessContainer c(num_vertices(g));
- ClosenessMap m(c);
- all_mean_geodesic_distances(g, dists, m);
- std::cout << "all mean geodesics: "; print_map(g, m);
- }
-
- {
- ClosenessContainer c(num_vertices(g));
- ClosenessMap m(c);
- all_inverse_geodesic_distances(g, dists, m);
- std::cout << "all inverse geodesics: "; print_map(g, m);
- }
-
- {
- ClosenessContainer c(num_vertices(g));
- ClosenessMap m(c);
- all_closenesses(g, dists, m);
- std::cout << "all closenesses: "; print_map(g, m);
- }
- }
}
int
main(int argc, char *argv[])
{
typedef undirected_graph<VertexProp, EdgeProp> Graph;
- typedef adjacency_list<vecS, vecS, undirectedS, VertexProp, EdgeProp> AdjList;
+ typedef directed_graph<VertexProp, EdgeProp> Digraph;
cout << "\n*** undirected_graph<> *** \n";
test<Graph>();
- cout << "\n*** adjacency_list<> *** \n";
- test<AdjList>();
+ cout << "\n*** directed_graph<> *** \n";
+ test<Digraph>();
}
Modified: sandbox/SOC/2007/graphs/libs/graph/test/degree_centrality.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/degree_centrality.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/degree_centrality.cpp 2007-08-01 09:49:13 EDT (Wed, 01 Aug 2007)
@@ -8,7 +8,6 @@
#include <iterator>
#include <algorithm>
#include <vector>
-#include <map>
#include <tr1/unordered_map>
#include <boost/graph/undirected_graph.hpp>
@@ -60,7 +59,6 @@
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
-
typedef exterior_vertex_property<Graph, unsigned> CentralityProperty;
typedef typename CentralityProperty::container_type CentralityContainer;
typedef typename CentralityProperty::map_type CentralityMap;
Deleted: sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/distance.cpp 2007-08-01 09:49:13 EDT (Wed, 01 Aug 2007)
+++ (empty file)
@@ -1,187 +0,0 @@
-// (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 <map>
-#include <tr1/unordered_map>
-#include <cxxabi.h>
-
-#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/johnson_all_pairs_shortest.hpp>
-#include <boost/graph/floyd_warshall_shortest.hpp>
-#include <boost/graph/distance.hpp>
-#include <boost/graph/closeness_centrality.hpp>
-
-using namespace std;
-using namespace boost;
-
-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 << pm[*i] << " ";
- }
- cout << "}\n";
-}
-
-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";
-}
-
-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> DistanceProperty;
- typedef typename DistanceProperty::container_type DistanceContainer;
- typedef typename DistanceProperty::map_type DistanceMap;
- typedef typename property_map<Graph, int EdgeProp::*>::type WeightMap;
-
- Graph g;
- build_graph(g);
-
- // single-vertex computations
- {
- DistanceContainer distances(num_vertices(g));
- DistanceMap dists(distances);
- WeightMap weights = get(&EdgeProp::weight, g);
-
- dijkstra_shortest_paths(g, *vertices(g).first,
- weight_map(weights).
- distance_map(dists));
-
- double total_geo = total_geodesic_distance(g, dists);
- double mean_geo = mean_geodesic_distance(g, dists);
- double inverse_geo = inverse_geodesic_distance(g, dists);
- double close = closeness(g, dists);
-
- cout << "* geodesics: "; print_map(g, dists);
- cout << "* total geo: " << total_geo << "\n";
- cout << "* mean geo: " << mean_geo << "\n";
- cout << "* inv geo: " << inverse_geo << "\n";
- cout << "* closeness: " << close << "\n";
- }
-
-
- // all-vertices computation
- {
- typedef typename DistanceProperty::matrix_type DistanceMatrix;
-
- WeightMap weights = get(&EdgeProp::weight, g);
- DistanceMatrix dists(num_vertices(g));
-
- // compute all shortest paths so we can run some other stuff
- floyd_warshall_all_pairs_shortest_paths(g, dists,
- weight_map(weights));
-
- print_matrix(g, dists);
-
- typedef exterior_vertex_property<Graph, float> ClosenessProperty;
- typedef typename ClosenessProperty::container_type ClosenessContainer;
- typedef typename ClosenessProperty::map_type ClosenessMap;
-
- {
- ClosenessContainer c(num_vertices(g));
- ClosenessMap m(c);
- all_total_geodesic_distances(g, dists, m);
- std::cout << "all total geodesics: "; print_map(g, m);
- }
-
- {
- ClosenessContainer c(num_vertices(g));
- ClosenessMap m(c);
- all_mean_geodesic_distances(g, dists, m);
- std::cout << "all mean geodesics: "; print_map(g, m);
- }
-
- {
- ClosenessContainer c(num_vertices(g));
- ClosenessMap m(c);
- all_inverse_geodesic_distances(g, dists, m);
- std::cout << "all inverse geodesics: "; print_map(g, m);
- }
-
- {
- ClosenessContainer c(num_vertices(g));
- ClosenessMap m(c);
- all_closenesses(g, dists, m);
- std::cout << "all closenesses: "; print_map(g, m);
- }
- }
-}
-
-int
-main(int argc, char *argv[])
-{
- typedef undirected_graph<VertexProp, EdgeProp> Graph;
- typedef adjacency_list<vecS, vecS, undirectedS, VertexProp, EdgeProp> AdjList;
-
- cout << "\n*** undirected_graph<> *** \n";
- test<Graph>();
-
- cout << "\n*** adjacency_list<> *** \n";
- test<AdjList>();
-}
Added: sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp 2007-08-01 09:49:13 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,155 @@
+// (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/geodesic_distance.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 << "[\n";
+ typename Graph::vertex_iterator i, j, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ print_map(g, m[*i]);
+ }
+ cout << "]\n";
+}
+
+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, float> GeodesicProperty;
+ typedef typename GeodesicProperty::container_type GeodesicContainer;
+ typedef typename GeodesicProperty::map_type GeodesicMap;
+
+ 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);
+
+ GeodesicContainer geodesics(num_vertices(g));
+ GeodesicMap geo(geodesics);
+ DistanceMatrix dist(num_vertices(g));
+ WeightMap weights(get(&EdgeProp::weight, g));
+
+ floyd_warshall_all_pairs_shortest_paths(g, dist, weight_map(weights));
+ mean_geodesic(g, dist, geo);
+
+ print_matrix(g, dist);
+ print_map(g, geo);
+
+ std::cout << "mgeo: " << make_numeric(graph_mean_geodesic(g, dist)) << "\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>();
+}