[Boost-commit] svn:boost r38334 - sandbox/SOC/2007/graphs/libs/graph/test

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>();
+}