[Boost-commit] svn:boost r7338

From: asutton_at_[hidden]
Date: 2007-07-02 13:56:14

Author: asutton
Date: 2007-07-02 13:56:13 EDT (Mon, 02 Jul 2007)
New Revision: 7338
URL: http://svn.boost.org/trac/boost/changeset/7338

Log:
Rewrote degree_distribution/histogram using Boost.Parameter, reflected
changes to movie_stats example.
Added a directory for graph concepts - just in case.

Added:
   sandbox/SOC/2007/graphs/boost/graph/concepts/
Text files modified: 
   sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp   |   223 +++++++++++++++++++++++++++++++++------ 
   sandbox/SOC/2007/graphs/libs/graph/examples/movies/Jamfile.v2 |    21 ++-                                     
   sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp  |    29 +++-                                    
   3 files changed, 217 insertions(+), 56 deletions(-)

Modified: sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp	(original)
+++ sandbox/SOC/2007/graphs/boost/graph/degree_distribution.hpp	2007-07-02 13:56:13 EDT (Mon, 02 Jul 2007)
@@ -7,56 +7,201 @@
 #ifndef BOOST_GRAPH_DEGREE_DISTRIBUTION_HXX
 #define BOOST_GRAPH_DEGREE_DISTRIBUTION_HXX
 
+#include <boost/parameter.hpp>
+
 namespace boost
 {
-    template <typename Graph, typename Distribution>
-    void
-    degree_distribution(const Graph &g, Distribution &dist)
+    BOOST_PARAMETER_NAME(graph)
+    BOOST_PARAMETER_NAME(distribution)
+    BOOST_PARAMETER_NAME(in_distribution)
+    BOOST_PARAMETER_NAME(out_distribution)
+    BOOST_PARAMETER_NAME(histogram)
+    BOOST_PARAMETER_NAME(in_histogram)
+    BOOST_PARAMETER_NAME(out_histogram)
+
+    struct not_given {};
+
+    // Helper functions for computing degree distributions, histograms. Note
+    // that when passed a not_given argumemt, all of these operations are
+    // no-ops. The effect is that the actual computations shouldn't add hidden
+    // constants at run-time.
+    namespace detail
     {
-        typedef typename graph_traits<Graph>::degree_size_type Degree;
+        template <typename Dist, typename Graph>
+        inline void
+        max_degree(Dist&, typename Graph::degree_size_type& m, typename Graph::vertex_descriptor v, const Graph& g)
+        { m = max(m, boost::degree(v, g)); }
 
-            // stash the degree of each vertex into its bucket - degree 1
-            // goes into index 1, degree 90 goes into index 90, etc.
-        typename Graph::vertex_iterator i, j;
-        for(tie(i, j) = vertices(g); i != j; ++i) {
-            Degree d = degree(*i, g);
-
-                // we may need to resize the array to accomodate the
-                // incrementation of this degrees bucket. this only looks
-                // like its an inefficient resize, but its just fine with
-                // a vector for the distribution.
-            if(d >= dist.size()) {
-                dist.resize(d + 1);
-            }
+        template <typename Graph>
+        inline void
+        max_degree(not_given, typename Graph::degree_size_type&, typename Graph::vertex_descriptor, const Graph&)
+        {}
 
-                // increment the count in that bucket
-            dist[d] += 1;
-        }
+
+        template <typename Dist, typename Graph>
+        inline void
+        max_out_degree(Dist&, typename Graph::degree_size_type& m, typename Graph::vertex_descriptor v, const Graph& g)
+        { m = max(m, boost::out_degree(v, g)); }
+
+        template <typename Graph>
+        inline void
+        max_out_degree(not_given, typename Graph::degree_size_type&, typename Graph::vertex_descriptor, const Graph&)
+        {}
+
+
+        template <typename Dist, typename Graph>
+        inline void
+        max_in_degree(Dist&, typename Graph::degree_size_type& m, typename Graph::vertex_descriptor v, const Graph& g)
+        { m = max(m, boost::in_degree(v, g)); }
+
+        template <typename Graph>
+        inline void
+        max_in_degree(not_given, typename Graph::degree_size_type&, typename Graph::vertex_descriptor, const Graph&)
+        { }
+
+
+        template <typename Dist>
+        inline void resize_distribution(Dist& d, size_t n)
+        { d.resize(n); }
+
+        inline void resize_distribution(not_given, size_t n)
+        { }
+
+
+        template <typename Dist, typename Graph>
+        inline void observe_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
+        { d[boost::degree(v, g)] += 1; }
+
+        template <typename Graph>
+        inline void observe_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
+        { }
+
+
+        template <typename Dist, typename Graph>
+        inline void observe_out_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
+        { d[boost::out_degree(v, g)] += 1; }
+
+        template <typename Graph>
+        inline void observe_out_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
+        { }
+
+
+        template <typename Dist, typename Graph>
+        inline void observe_in_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
+        { d[boost::in_degree(v, g)] += 1; }
+
+        template <typename Graph>
+        inline void observe_in_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
+        { }
+
+
+        template <typename Dist, typename Graph>
+        inline void record_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
+        { d[boost::degree(v, g)] += 1; }
+
+        template <typename Graph>
+        inline void record_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
+        { }
+
+
+        template <typename Dist, typename Graph>
+        inline void record_out_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
+        { d[boost::out_degree(v, g)] += 1; }
+
+        template <typename Graph>
+        inline void record_out_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
+        { }
+
+
+        template <typename Dist, typename Graph>
+        inline void record_in_degree(Dist& d, typename Graph::vertex_descriptor v, const Graph& g)
+        { d[boost::in_degree(v, g)] += 1; }
+
+        template <typename Graph>
+        inline void record_in_degree(not_given, typename Graph::vertex_descriptor v, const Graph& g)
+        { }
     }
 
+    // A helper function for initializing distributions and histograms
+    BOOST_PARAMETER_FUNCTION(
+        (void), initialize_distribution, tag,
+        (required (graph, *))
+        (optional
+            (out(distribution), *, not_given())
+            (out(in_distribution), *, not_given())
+            (out(out_distribution), *, not_given())
+            )
+        )
+    {
+        typename graph_type::vertex_iterator i, end;
+
+        // part 1: find the max observable degrees for the graph so we
+        // only have to resize once.
+        size_t max_d = 0, max_od = 0, max_id = 0;
+        for(tie(i, end) = vertices(graph); i != end; ++i) {
+            typename graph_type::vertex_descriptor v = *i;
+            detail::max_degree(distribution, max_d, v, graph);
+            detail::max_out_degree(out_distribution, max_od, v, graph);
+            detail::max_in_degree(in_distribution, max_id, v, graph);
+        }
+        detail::resize_distribution(distribution, max_d + 1);
+        detail::resize_distribution(out_distribution, max_od + 1);
+        detail::resize_distribution(in_distribution, max_id + 1);
+    }
 
-    template <typename Graph, typename Histogram>
-    void
-    degree_histogram(const Graph &g, Histogram &hist)
+    // the actual degree_distribution function
+    BOOST_PARAMETER_FUNCTION(
+        (void), degree_distribution, tag,
+        (required (graph, *))
+        (optional
+            (out(distribution), *, not_given())
+            (out(out_distribution), *, not_given())
+            (out(in_distribution), *, not_given())
+            )
+        )
     {
-        typedef typename graph_traits<Graph>::degree_size_type Degree;
+        typename graph_type::vertex_iterator i, end;
 
-        // stash the degree of each vertex into its bucket - degree 1
-        // goes into index 1, degree 90 goes into index 90, etc.
-        typename Graph::vertex_iterator i, j;
-        for(tie(i, j) = vertices(g); i != j; ++i) {
-            Degree d = degree(*i, g);
-
-            // we may need to resize the array to accomodate the
-            // incrementation of this degrees bucket. this only looks
-            // like its an inefficient resize, but its just fine with
-            // a vector for the distribution.
-            if(d >= hist.size()) {
-                hist.resize(d + 1);
-            }
+        // part 1: initialize distributions
+        initialize_distribution(graph,
+            _distribution = distribution,
+            _out_distribution = out_distribution,
+            _in_distribution = in_distribution);
+
+        // part 2: record observed distributions
+        for(tie(i, end) = vertices(graph); i != end; ++i) {
+            typename graph_type::vertex_descriptor v = *i;
+            detail::observe_degree(distribution, v, graph);
+            detail::observe_out_degree(out_distribution, v, graph);
+            detail::observe_in_degree(in_distribution, v, graph);
+        }
+    }
+
+    // the actual degree_distribution function
+    BOOST_PARAMETER_FUNCTION(
+        (void), degree_histogram, tag,
+        (required (graph, *))
+        (optional
+            (out(histogram), *, not_given())
+            (out(out_histogram), *, not_given())
+            (out(in_histogram), *, not_given())
+            )
+        )
+    {
+        typename graph_type::vertex_iterator i, end;
 
-            // increment the count in that bucket
-            hist[d].push_back(*i);
+        // part 1: initialize distributions
+        initialize_distribution(graph,
+            _distribution = distribution,
+            _out_distribution = out_distribution,
+            _in_distribution = in_distribution);
+
+        // part 2: record observed distributions
+        for(tie(i, end) = vertices(graph); i != end; ++i) {
+            typename graph_type::vertex_descriptor v = *i;
+            detail::record_degree(distribution, v, graph);
+            detail::record_out_degree(out_distribution, v, graph);
+            detail::record_in_degree(in_distribution, v, graph);
         }
     }
 }

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/Jamfile.v2	2007-07-02 13:56:13 EDT (Mon, 02 Jul 2007)
@@ -1,15 +1,18 @@
 
 exe kevin_bacon
-	: kevin_bacon.cpp movies.cpp
-	: <include>../../../../
-	;
+    : kevin_bacon.cpp movies.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../../
+    ;
 
 exe six_degrees
-	: six_degrees.cpp movies.cpp
-	: <include>../../../../
-	;
+    : six_degrees.cpp movies.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../../
+    ;
 
 exe movie_stats
-	: stats.cpp movies.cpp
-	: <include>../../../../
-	;
\ No newline at end of file
+    : stats.cpp movies.cpp
+    : <include>$BOOST_ROOT
+    : <include>../../../../
+    ;
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/movies/stats.cpp	2007-07-02 13:56:13 EDT (Mon, 02 Jul 2007)
@@ -12,10 +12,15 @@
 #include <boost/graph/degree_distribution.hpp>
 #include <boost/graph/connectivity.hpp>
 
+#include <typeinfo>
+#include <cxxabi.h>
+
 #include "movies.hpp"
 
 using namespace std;
 using namespace boost;
+using namespace __cxxabiv1;
+
 
 typedef vector<graph_traits<Graph>::degree_size_type> Distribution;
 typedef list<Vertex> VectorList;
@@ -30,18 +35,26 @@
     // build the movie graph from std input
     build_movie_graph(cin, g, actors);
 
-    Distribution dist;
-    Histogram hist;
-    degree_distribution(g, dist);
-    degree_histogram(g, hist);
+    vector<size_t> dist;
+    vector<size_t> out_dist;
+    vector<size_t> in_dist;
+
+    degree_distribution(g,
+        _distribution = dist,
+        _out_distribution = out_dist,
+        _in_distribution = in_dist);
 
-    cout << "vertices: " << num_vertices(g) << "\n";
-    cout << "edges: " << num_edges(g) << "\n";
     cout << "degree distribution: ";
     copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
     cout << "\n";
-    cout << "max degree: " << (dist.size() - 1) << "\n";
-    cout << "most-connected actor: " << g[hist.back().back()].name << "\n";
+
+    cout << "out distribution: ";
+    copy(out_dist.begin(), out_dist.end(), ostream_iterator<size_t>(cout, " "));
+    cout << "\n";
+
+    cout << "in distribution: ";
+    copy(in_dist.begin(), in_dist.end(), ostream_iterator<size_t>(cout, " "));
+    cout << "\n";
 
     return 0;
 }