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

From: asutton_at_[hidden]
Date: 2007-08-15 08:38:06

Author: asutton
Date: 2007-08-15 08:38:03 EDT (Wed, 15 Aug 2007)
New Revision: 38673
URL: http://svn.boost.org/trac/boost/changeset/38673

Log:
Making a more formal unit test for eccentricity

Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/test/Jamfile.v2        |     2                                         
   sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp  |   174 +++++++++++++++++---------------------- 
   sandbox/SOC/2007/graphs/libs/graph/test/mean_geodesic.cpp |    14 +-                                      
   3 files changed, 86 insertions(+), 104 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-15 08:38:03 EDT (Wed, 15 Aug 2007)
@@ -12,6 +12,7 @@
     [ run degree_centrality.cpp ]
     [ run closeness_centrality.cpp ]
     [ run mean_geodesic.cpp ]
+    [ run eccentricity.cpp ]
     ;
 
 # exe properties : properties.cpp ;
@@ -26,7 +27,6 @@
 #
 # exe components : components.cpp ;
 #
-# exe eccentricity : eccentricity.cpp ;
 #
 # exe cluster : cluster.cpp ;
 #

Modified: sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/eccentricity.cpp	2007-08-15 08:38:03 EDT (Wed, 15 Aug 2007)
@@ -5,115 +5,93 @@
 // 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/eccentricity.hpp>
-#include <boost/graph/radius.hpp>
-#include <boost/graph/diameter.hpp>
+#include "io.hpp"
 
 using namespace std;
 using namespace boost;
 
-template <typename T>
-struct numeric
+// 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, 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 DistanceProperty::matrix_map_type DistanceMatrixMap;
 
-    static const unsigned N = 5;
+    typedef constant_property_map<Edge, int> WeightMap;
+
+    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);
-    }
+    EccentricityContainer eccs(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;
-};
+    EccentricityMap em(eccs, 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 << "{ ";
-    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]);
-    }
+    floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
+    eccentricity(g, dm, em);
+    int radius = graph_radius(g, em);
+    int diameter = graph_diameter(g, em);
+
+    BOOST_ASSERT(em[v[0]] == 2);
+    BOOST_ASSERT(em[v[1]] == 3);
+    BOOST_ASSERT(em[v[2]] == 3);
+    BOOST_ASSERT(em[v[3]] == 3);
+    BOOST_ASSERT(em[v[4]] == 2);
+    BOOST_ASSERT(radius == 2);
+    BOOST_ASSERT(diameter == 3);
 }
 
 template <typename Graph>
-void test()
+void test_directed()
 {
     typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
     typedef typename graph_traits<Graph>::edge_descriptor Edge;
@@ -126,38 +104,42 @@
     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);
 
     EccentricityContainer eccs(num_vertices(g));
-    EccentricityMap em(eccs, g);
+    DistanceMatrix distances(num_vertices(g));
 
-    DistanceMatrix dist(num_vertices(g));
-    DistanceMatrixMap dm(dist, g);
+    EccentricityMap em(eccs, 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));
     eccentricity(g, dm, em);
+    int radius = graph_radius(g, em);
+    int diameter = graph_diameter(g, em);
 
-    print_matrix(g, dm);
-    print_map(g, em);
-
-    std::cout << "radius: " << make_numeric(graph_radius(g, em)) << "\n";
-    std::cout << "diameter: " << make_numeric(graph_diameter(g, em)) << "\n";
+    int inf = numeric_values<int>::infinity();
+    BOOST_ASSERT(em[v[0]] == inf);
+    BOOST_ASSERT(em[v[1]] == inf);
+    BOOST_ASSERT(em[v[2]] == inf);
+    BOOST_ASSERT(em[v[3]] == 4);
+    BOOST_ASSERT(em[v[4]] == inf);
+    BOOST_ASSERT(radius == 4);
+    BOOST_ASSERT(diameter == 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>();
 }

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-15 08:38:03 EDT (Wed, 15 Aug 2007)
@@ -81,12 +81,12 @@
 
     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);
+    BOOST_ASSERT(cm[v[0]] == float(5)/4);
+    BOOST_ASSERT(cm[v[1]] == float(7)/4);
+    BOOST_ASSERT(cm[v[2]] == float(7)/4);
+    BOOST_ASSERT(cm[v[3]] == float(9)/4);
+    BOOST_ASSERT(cm[v[4]] == float(6)/4);
+    BOOST_ASSERT(geo == float(34)/20);
 }
 
 template <typename Graph>
@@ -125,7 +125,7 @@
     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[3]] == float(10)/4);
     BOOST_ASSERT(cm[v[4]] == inf);
     BOOST_ASSERT(geo == inf);
 }