Boost logo

Boost-Commit :

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;
 }


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk