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

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