Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r52110 - in trunk/boost: . graph graph/detail
From: jewillco_at_[hidden]
Date: 2009-04-01 12:03:24


Author: jewillco
Date: 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
New Revision: 52110
URL: http://svn.boost.org/trac/boost/changeset/52110

Log:
First batch of merges from Parallel BGL
Text files modified:
   trunk/boost/graph/adjacency_list.hpp | 5
   trunk/boost/graph/betweenness_centrality.hpp | 6
   trunk/boost/graph/breadth_first_search.hpp | 9 -
   trunk/boost/graph/compressed_sparse_row_graph.hpp | 27 ++++++
   trunk/boost/graph/depth_first_search.hpp | 3
   trunk/boost/graph/detail/adjacency_list.hpp | 8
   trunk/boost/graph/dijkstra_shortest_paths.hpp | 8
   trunk/boost/graph/erdos_renyi_generator.hpp | 46 +++++-----
   trunk/boost/graph/fruchterman_reingold.hpp | 6 +
   trunk/boost/graph/graph_utility.hpp | 27 ++++++
   trunk/boost/graph/graphviz.hpp | 2
   trunk/boost/graph/named_function_params.hpp | 5 +
   trunk/boost/graph/plod_generator.hpp | 180 ++++++++++++++++++++++++++++++---------
   trunk/boost/graph/properties.hpp | 52 +++++++----
   trunk/boost/property_map.hpp | 30 +++---
   15 files changed, 288 insertions(+), 126 deletions(-)

Modified: trunk/boost/graph/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/adjacency_list.hpp (original)
+++ trunk/boost/graph/adjacency_list.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -285,14 +285,13 @@
     typedef typename parallel_edge_traits<OutEdgeListS>::type
       edge_parallel_category;
 
+ typedef std::size_t vertices_size_type;
     typedef void* vertex_ptr;
     typedef typename mpl::if_<is_rand_access,
- std::size_t, vertex_ptr>::type vertex_descriptor;
+ vertices_size_type, vertex_ptr>::type vertex_descriptor;
     typedef detail::edge_desc_impl<directed_category, vertex_descriptor>
       edge_descriptor;
 
- typedef std::size_t vertices_size_type;
-
   private:
     // Logic to figure out the edges_size_type
     struct dummy {};

Modified: trunk/boost/graph/betweenness_centrality.hpp
==============================================================================
--- trunk/boost/graph/betweenness_centrality.hpp (original)
+++ trunk/boost/graph/betweenness_centrality.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -417,6 +417,7 @@
                                            WeightMap weight_map,
                                            VertexIndexMap vertex_index)
   {
+ typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
     typedef typename mpl::if_c<(is_same<CentralityMap,
@@ -431,7 +432,7 @@
     std::vector<std::vector<edge_descriptor> > incoming(V);
     std::vector<centrality_type> distance(V);
     std::vector<centrality_type> dependency(V);
- std::vector<unsigned long long> path_count(V);
+ std::vector<degree_size_type> path_count(V);
 
     brandes_betweenness_centrality(
       g, centrality, edge_centrality_map,
@@ -452,6 +453,7 @@
                                            EdgeCentralityMap edge_centrality_map,
                                            VertexIndexMap vertex_index)
   {
+ typedef typename graph_traits<Graph>::degree_size_type degree_size_type;
     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
     typedef typename mpl::if_c<(is_same<CentralityMap,
@@ -466,7 +468,7 @@
     std::vector<std::vector<edge_descriptor> > incoming(V);
     std::vector<centrality_type> distance(V);
     std::vector<centrality_type> dependency(V);
- std::vector<unsigned long long> path_count(V);
+ std::vector<degree_size_type> path_count(V);
 
     brandes_betweenness_centrality(
       g, centrality, edge_centrality_map,

Modified: trunk/boost/graph/breadth_first_search.hpp
==============================================================================
--- trunk/boost/graph/breadth_first_search.hpp (original)
+++ trunk/boost/graph/breadth_first_search.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -21,6 +21,7 @@
 #include <boost/graph/graph_concepts.hpp>
 #include <boost/graph/visitors.hpp>
 #include <boost/graph/named_function_params.hpp>
+#include <boost/graph/two_bit_color_map.hpp>
 
 namespace boost {
 
@@ -219,16 +220,14 @@
        const bgl_named_params<P, T, R>& params,
        detail::error_property_not_found)
       {
- std::vector<default_color_type> color_vec(num_vertices(g));
- default_color_type c = white_color;
         null_visitor null_vis;
 
         bfs_helper
           (g, s,
- make_iterator_property_map
- (color_vec.begin(),
+ make_two_bit_color_map
+ (num_vertices(g),
             choose_const_pmap(get_param(params, vertex_index),
- g, vertex_index), c),
+ g, vertex_index)),
            choose_param(get_param(params, graph_visitor),
                         make_bfs_visitor(null_vis)),
            params);

Modified: trunk/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- trunk/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ trunk/boost/graph/compressed_sparse_row_graph.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -27,6 +27,7 @@
 #include <boost/mpl/if.hpp>
 #include <boost/graph/graph_selectors.hpp>
 #include <boost/static_assert.hpp>
+#include <boost/functional/hash.hpp>
 
 #ifdef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 # error The Compressed Sparse Row graph only supports bundled properties.
@@ -157,6 +158,15 @@
     : m_rowstart(1, EdgeIndex(0)), m_column(0), m_property(),
       m_last_source(0) {}
 
+ // With numverts vertices
+ compressed_sparse_row_graph(vertices_size_type numverts)
+ : inherited_vertex_properties(numverts), m_rowstart(numverts + 1),
+ m_column(0), m_last_source(numverts)
+ {
+ for (Vertex v = 0; v < numverts + 1; ++v)
+ m_rowstart[v] = 0;
+ }
+
   // From number of vertices and sorted list of edges
   template<typename InputIterator>
   compressed_sparse_row_graph(InputIterator edge_begin, InputIterator edge_end,
@@ -339,6 +349,23 @@
   bool operator>(const csr_edge_descriptor& e) const {return idx > e.idx;}
   bool operator<=(const csr_edge_descriptor& e) const {return idx <= e.idx;}
   bool operator>=(const csr_edge_descriptor& e) const {return idx >= e.idx;}
+
+ template<typename Archiver>
+ void serialize(Archiver& ar, const unsigned int /*version*/)
+ {
+ ar & src & idx;
+ }
+};
+
+template<typename Vertex, typename EdgeIndex>
+struct hash<csr_edge_descriptor<Vertex, EdgeIndex> >
+{
+ std::size_t operator()(csr_edge_descriptor<Vertex, EdgeIndex> const& x) const
+ {
+ std::size_t hash = hash_value(x.src);
+ hash_combine(hash, x.idx);
+ return hash;
+ }
 };
 
 // Construction functions

Modified: trunk/boost/graph/depth_first_search.hpp
==============================================================================
--- trunk/boost/graph/depth_first_search.hpp (original)
+++ trunk/boost/graph/depth_first_search.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -19,7 +19,6 @@
 #include <boost/graph/properties.hpp>
 #include <boost/graph/visitors.hpp>
 #include <boost/graph/named_function_params.hpp>
-
 #include <boost/ref.hpp>
 #include <boost/implicit_cast.hpp>
 
@@ -357,8 +356,6 @@
     vis.start_vertex(u, g);
     detail::depth_first_visit_impl(g, u, vis, color, func);
   }
-
-
 } // namespace boost
 
 

Modified: trunk/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/detail/adjacency_list.hpp (original)
+++ trunk/boost/graph/detail/adjacency_list.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -387,7 +387,7 @@
           ++first;
         incidence_iterator i = first;
         if (first != last)
- for (; i != last; ++i)
+ for (++i; i != last; ++i)
             if (!pred(*i)) {
               *first.base() = *i.base();
               ++first;
@@ -786,14 +786,14 @@
         typedef typename EdgeList::value_type StoredEdge;
         typename EdgeList::iterator i = el.begin(), end = el.end();
         for (; i != end; ++i) {
- if((*i).get_target() == v) {
+ if ((*i).get_target() == v) {
             // NOTE: Wihtout this skip, this loop will double-delete properties
             // of loop edges. This solution is based on the observation that
             // the incidence edges of a vertex with a loop are adjacent in the
             // out edge list. This *may* actually hold for multisets also.
             bool skip = (next(i) != end && i->get_iter() == next(i)->get_iter());
             g.m_edges.erase((*i).get_iter());
- if(skip) ++i;
+ if (skip) ++i;
           }
         }
         detail::erase_from_incidence_list(el, v, cat);
@@ -2297,7 +2297,7 @@
         // VertexList and vertex_iterator
         typedef typename container_gen<VertexListS,
           vertex_ptr>::type SeqVertexList;
- typedef boost::integer_range<std::size_t> RandVertexList;
+ typedef boost::integer_range<vertices_size_type> RandVertexList;
         typedef typename mpl::if_<is_rand_access,
           RandVertexList, SeqVertexList>::type VertexList;
 

Modified: trunk/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths.hpp (original)
+++ trunk/boost/graph/dijkstra_shortest_paths.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -127,7 +127,7 @@
       template <class Edge, class Graph>
       void examine_edge(Edge e, Graph& g) {
         if (m_compare(get(m_weight, e), m_zero))
- throw negative_edge();
+ boost::throw_exception(negative_edge());
         m_vis.examine_edge(e, g);
       }
       template <class Edge, class Graph>
@@ -165,7 +165,7 @@
     struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> {
       typedef boost::vector_property_map<Value, IndexMap> type;
       static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
- return make_vector_property_map(index);
+ return boost::make_vector_property_map<Value>(index);
       }
     };
 
@@ -200,7 +200,7 @@
     struct default_color_map_generator_helper<Graph, IndexMap, false> {
       typedef boost::vector_property_map<boost::two_bit_color_type, IndexMap> type;
       static type build(const Graph& g, const IndexMap& index) {
- return make_vector_property_map(index);
+ return boost::make_vector_property_map<boost::two_bit_color_type>(index);
       }
     };
 
@@ -291,7 +291,7 @@
       typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>
         MutableQueue;
       MutableQueue Q(distance, index_in_heap, compare);
-#endif
+#endif // Relaxed heap
 
     detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
       PredecessorMap, DistanceMap, Combine, Compare>

Modified: trunk/boost/graph/erdos_renyi_generator.hpp
==============================================================================
--- trunk/boost/graph/erdos_renyi_generator.hpp (original)
+++ trunk/boost/graph/erdos_renyi_generator.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -123,16 +123,16 @@
 
     sorted_erdos_renyi_iterator()
       : gen(), rand_vertex(0.5), n(0), allow_self_loops(false),
- src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0) {}
+ src((std::numeric_limits<vertices_size_type>::max)()), tgt(0), prob(0) {}
     sorted_erdos_renyi_iterator(RandomGenerator& gen, vertices_size_type n,
- double prob = 0.0,
+ double prob = 0.0,
                                 bool allow_self_loops = false)
       : gen(),
         // The "1.0 - prob" in the next line is to work around a Boost.Random
         // (and TR1) bug in the specification of geometric_distribution. It
         // should be replaced by "prob" when the issue is fixed.
         rand_vertex(1.0 - prob),
- n(n), allow_self_loops(allow_self_loops), src(0), tgt(0), prob(prob)
+ n(n), allow_self_loops(allow_self_loops), src(0), tgt(0), prob(prob)
     {
       this->gen.reset(new uniform_01<RandomGenerator>(gen));
 
@@ -182,27 +182,27 @@
       vertices_size_type increment = rand_vertex(*gen);
       tgt += increment;
       if (is_undirected) {
- // Update src and tgt based on position of tgt
- // Basically, we want the greatest src_increment such that (in \bbQ):
- // src_increment * (src + allow_self_loops + src_increment - 1/2) <= tgt
- // The result of the LHS of this, evaluated with the computed
- // src_increment, is then subtracted from tgt
- double src_minus_half = (src + allow_self_loops) - 0.5;
- double disc = src_minus_half * src_minus_half + 2 * tgt;
- double src_increment_fp = floor(sqrt(disc) - src_minus_half);
- vertices_size_type src_increment = vertices_size_type(src_increment_fp);
- if (src + src_increment >= n) {
- src = n;
- } else {
- tgt -= (src + allow_self_loops) * src_increment +
- src_increment * (src_increment - 1) / 2;
- src += src_increment;
- }
+ // Update src and tgt based on position of tgt
+ // Basically, we want the greatest src_increment such that (in \bbQ):
+ // src_increment * (src + allow_self_loops + src_increment - 1/2) <= tgt
+ // The result of the LHS of this, evaluated with the computed
+ // src_increment, is then subtracted from tgt
+ double src_minus_half = (src + allow_self_loops) - 0.5;
+ double disc = src_minus_half * src_minus_half + 2 * tgt;
+ double src_increment_fp = floor(sqrt(disc) - src_minus_half);
+ vertices_size_type src_increment = vertices_size_type(src_increment_fp);
+ if (src + src_increment >= n) {
+ src = n;
+ } else {
+ tgt -= (src + allow_self_loops) * src_increment +
+ src_increment * (src_increment - 1) / 2;
+ src += src_increment;
+ }
       } else {
- // Number of out edge positions possible from each vertex in this graph
- vertices_size_type possible_out_edges = n - (allow_self_loops ? 0 : 1);
- src += (std::min)(n - src, tgt / possible_out_edges);
- tgt %= possible_out_edges;
+ // Number of out edge positions possible from each vertex in this graph
+ vertices_size_type possible_out_edges = n - (allow_self_loops ? 0 : 1);
+ src += (std::min)(n - src, tgt / possible_out_edges);
+ tgt %= possible_out_edges;
       }
       // Set end of graph code so (src, tgt) will be the same as for the end
       // sorted_erdos_renyi_iterator

Modified: trunk/boost/graph/fruchterman_reingold.hpp
==============================================================================
--- trunk/boost/graph/fruchterman_reingold.hpp (original)
+++ trunk/boost/graph/fruchterman_reingold.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -95,7 +95,7 @@
 #ifndef BOOST_NO_STDC_NAMESPACE
     using std::sqrt;
 #endif // BOOST_NO_STDC_NAMESPACE
- two_k = Dim(2) * sqrt(width*height / num_vertices(g));
+ two_k = Dim(2) * sqrt(width * height / num_vertices(g));
   }
 
   template<typename Graph, typename ApplyForce >
@@ -106,6 +106,10 @@
     typedef std::list<vertex_descriptor> bucket_t;
     typedef std::vector<bucket_t> buckets_t;
 
+#ifndef BOOST_NO_STDC_NAMESPACE
+ using std::sqrt;
+#endif // BOOST_NO_STDC_NAMESPACE
+
     std::size_t columns = std::size_t(width / two_k + Dim(1));
     std::size_t rows = std::size_t(height / two_k + Dim(1));
     buckets_t buckets(rows * columns);

Modified: trunk/boost/graph/graph_utility.hpp
==============================================================================
--- trunk/boost/graph/graph_utility.hpp (original)
+++ trunk/boost/graph/graph_utility.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -420,6 +420,33 @@
   make_list(const T1& t1, const T2& t2, const T3& t3, const T4& t4, const T5& t5)
     { return std::make_pair(t1, std::make_pair(t2, std::make_pair(t3, std::make_pair(t4, t5)))); }
 
+ namespace graph {
+
+ // Functor for remove_parallel_edges: edge property of the removed edge is added to the remaining
+ template <typename EdgeProperty>
+ struct add_removed_edge_property
+ {
+ add_removed_edge_property(EdgeProperty ep) : ep(ep) {}
+
+ template <typename Edge>
+ void operator() (Edge stay, Edge away)
+ {
+ put(ep, stay, get(ep, stay) + get(ep, away));
+ }
+ EdgeProperty ep;
+ };
+
+ // Same as above: edge property is capacity here
+ template <typename Graph>
+ struct add_removed_edge_capacity
+ : add_removed_edge_property<typename property_map<Graph, edge_capacity_t>::type>
+ {
+ typedef add_removed_edge_property<typename property_map<Graph, edge_capacity_t>::type> base;
+ add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
+ };
+
+ } // namespace graph
+
 } /* namespace boost */
 
 #endif /* BOOST_GRAPH_UTILITY_HPP*/

Modified: trunk/boost/graph/graphviz.hpp
==============================================================================
--- trunk/boost/graph/graphviz.hpp (original)
+++ trunk/boost/graph/graphviz.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -725,7 +725,7 @@
     
     if(!result.second) {
       // In the case of no parallel edges allowed
- throw bad_parallel_edge(source, target);
+ boost::throw_exception(bad_parallel_edge(source, target));
     } else {
       bgl_edges.insert(std::make_pair(edge, result.first));
     }

Modified: trunk/boost/graph/named_function_params.hpp
==============================================================================
--- trunk/boost/graph/named_function_params.hpp (original)
+++ trunk/boost/graph/named_function_params.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -646,6 +646,11 @@
     return Params(c);
   }
 
+ namespace detail {
+ struct unused_tag_type {};
+ }
+ typedef bgl_named_params<char, detail::unused_tag_type> no_named_parameters;
+
   //===========================================================================
   // Functions for extracting parameters from bgl_named_params
 

Modified: trunk/boost/graph/plod_generator.hpp
==============================================================================
--- trunk/boost/graph/plod_generator.hpp (original)
+++ trunk/boost/graph/plod_generator.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -1,4 +1,4 @@
-// Copyright 2004 The Trustees of Indiana University.
+// Copyright 2004-2006 The Trustees of Indiana University.
 
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt or copy at
@@ -17,27 +17,112 @@
 #include <vector>
 #include <map>
 #include <boost/config/no_tr1/cmath.hpp>
+#include <boost/mpl/if.hpp>
 
 namespace boost {
+ template<typename RandomGenerator>
+ class out_directed_plod_iterator
+ {
+ public:
+ typedef std::forward_iterator_tag iterator_category;
+ typedef std::pair<std::size_t, std::size_t> value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef std::ptrdiff_t difference_type;
+
+ out_directed_plod_iterator() : gen(0), at_end(true) { }
+
+ out_directed_plod_iterator(RandomGenerator& gen, std::size_t n,
+ double alpha, double beta,
+ bool allow_self_loops)
+ : gen(&gen), n(n), alpha(alpha), beta(beta),
+ allow_self_loops(allow_self_loops), at_end(false), degree(0),
+ current(0, 0)
+ {
+ using std::pow;
 
- template<typename RandomGenerator, typename Graph>
- class plod_iterator
+ uniform_int<std::size_t> x(0, n-1);
+ std::size_t xv = x(gen);
+ degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
+ }
+
+ reference operator*() const { return current; }
+ pointer operator->() const { return &current; }
+
+ out_directed_plod_iterator& operator++()
+ {
+ using std::pow;
+
+ uniform_int<std::size_t> x(0, n-1);
+
+ // Continue stepping through source nodes until the
+ // (out)degree is > 0
+ while (degree == 0) {
+ // Step to the next source node. If we've gone past the
+ // number of nodes we're responsible for, we're done.
+ if (++current.first >= n) {
+ at_end = true;
+ return *this;
+ }
+
+ std::size_t xv = x(*gen);
+ degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
+ }
+
+ do {
+ current.second = x(*gen);
+ } while (current.first == current.second && !allow_self_loops);
+ --degree;
+
+ return *this;
+ }
+
+ out_directed_plod_iterator operator++(int)
+ {
+ out_directed_plod_iterator temp(*this);
+ ++(*this);
+ return temp;
+ }
+
+ bool operator==(const out_directed_plod_iterator& other) const
+ {
+ return at_end == other.at_end;
+ }
+
+ bool operator!=(const out_directed_plod_iterator& other) const
+ {
+ return !(*this == other);
+ }
+
+ private:
+ RandomGenerator* gen;
+ std::size_t n;
+ double alpha;
+ double beta;
+ bool allow_self_loops;
+ bool at_end;
+ std::size_t degree;
+ value_type current;
+ };
+
+ template<typename RandomGenerator>
+ class undirected_plod_iterator
   {
     typedef std::vector<std::pair<std::size_t, std::size_t> > out_degrees_t;
- typedef typename graph_traits<Graph>::directed_category directed_category;
 
   public:
- typedef std::input_iterator_tag iterator_category;
- typedef std::pair<std::size_t, std::size_t> value_type;
- typedef const value_type& reference;
- typedef const value_type* pointer;
- typedef void difference_type;
+ typedef std::input_iterator_tag iterator_category;
+ typedef std::pair<std::size_t, std::size_t> value_type;
+ typedef const value_type& reference;
+ typedef const value_type* pointer;
+ typedef std::ptrdiff_t difference_type;
 
- plod_iterator()
+ undirected_plod_iterator()
       : gen(0), out_degrees(), degrees_left(0), allow_self_loops(false) { }
 
- plod_iterator(RandomGenerator& gen, std::size_t n,
- double alpha, double beta, bool allow_self_loops = false)
+ undirected_plod_iterator(RandomGenerator& gen, std::size_t n,
+ double alpha, double beta,
+ bool allow_self_loops = false)
       : gen(&gen), n(n), out_degrees(new out_degrees_t),
         degrees_left(0), allow_self_loops(allow_self_loops)
     {
@@ -46,60 +131,42 @@
       uniform_int<std::size_t> x(0, n-1);
       for (std::size_t i = 0; i != n; ++i) {
         std::size_t xv = x(gen);
- std::size_t degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
- if (degree != 0) {
- out_degrees->push_back(std::make_pair(i, degree));
- }
+ std::size_t degree = (xv == 0? 0 : std::size_t(beta * pow(xv, -alpha)));
+ if (degree == 0) degree = 1;
+ else if (degree >= n) degree = n-1;
+ out_degrees->push_back(std::make_pair(i, degree));
         degrees_left += degree;
       }
 
- next(directed_category());
+ next();
     }
 
     reference operator*() const { return current; }
     pointer operator->() const { return &current; }
-
- plod_iterator& operator++()
+
+ undirected_plod_iterator& operator++()
     {
- next(directed_category());
+ next();
       return *this;
     }
 
- plod_iterator operator++(int)
+ undirected_plod_iterator operator++(int)
     {
- plod_iterator temp(*this);
+ undirected_plod_iterator temp(*this);
       ++(*this);
       return temp;
     }
 
- bool operator==(const plod_iterator& other) const
+ bool operator==(const undirected_plod_iterator& other) const
     {
       return degrees_left == other.degrees_left;
     }
 
- bool operator!=(const plod_iterator& other) const
+ bool operator!=(const undirected_plod_iterator& other) const
     { return !(*this == other); }
 
   private:
- void next(directed_tag)
- {
- uniform_int<std::size_t> x(0, out_degrees->size()-1);
- std::size_t source;
- do {
- source = x(*gen);
- } while ((*out_degrees)[source].second == 0);
- current.first = (*out_degrees)[source].first;
- do {
- current.second = x(*gen);
- } while (current.first == current.second && !allow_self_loops);
- --degrees_left;
- if (--(*out_degrees)[source].second == 0) {
- (*out_degrees)[source] = out_degrees->back();
- out_degrees->pop_back();
- }
- }
-
- void next(undirected_tag)
+ void next()
     {
       std::size_t source, target;
       while (true) {
@@ -107,7 +174,7 @@
            new edges, so we just add some random edge and set the
            degrees left = 0 to signal termination. */
         if (out_degrees->size() < 2) {
- uniform_int<std::size_t> x(0, n);
+ uniform_int<std::size_t> x(0, n-1);
           current.first = x(*gen);
           do {
             current.second = x(*gen);
@@ -156,6 +223,31 @@
     value_type current;
   };
 
+
+ template<typename RandomGenerator, typename Graph>
+ class plod_iterator
+ : public mpl::if_<is_convertible<
+ typename graph_traits<Graph>::directed_category,
+ directed_tag>,
+ out_directed_plod_iterator<RandomGenerator>,
+ undirected_plod_iterator<RandomGenerator> >::type
+ {
+ typedef typename mpl::if_<
+ is_convertible<
+ typename graph_traits<Graph>::directed_category,
+ directed_tag>,
+ out_directed_plod_iterator<RandomGenerator>,
+ undirected_plod_iterator<RandomGenerator> >::type
+ inherited;
+
+ public:
+ plod_iterator() : inherited() { }
+
+ plod_iterator(RandomGenerator& gen, std::size_t n,
+ double alpha, double beta, bool allow_self_loops = false)
+ : inherited(gen, n, alpha, beta, allow_self_loops) { }
+ };
+
 } // end namespace boost
 
 #endif // BOOST_GRAPH_PLOD_GENERATOR_HPP

Modified: trunk/boost/graph/properties.hpp
==============================================================================
--- trunk/boost/graph/properties.hpp (original)
+++ trunk/boost/graph/properties.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -15,7 +15,10 @@
 #include <boost/property_map.hpp>
 #include <boost/graph/graph_traits.hpp>
 #include <boost/type_traits/is_convertible.hpp>
-
+#include <boost/limits.hpp>
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/mpl/if.hpp>
 
 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
 // Stay out of the way of the concept checking class
@@ -35,12 +38,12 @@
     static default_color_type red() { return red_color; }
     static default_color_type black() { return black_color; }
   };
-
+
   // These functions are now obsolete, replaced by color_traits.
   inline default_color_type white(default_color_type) { return white_color; }
   inline default_color_type gray(default_color_type) { return gray_color; }
   inline default_color_type green(default_color_type) { return green_color; }
- inline default_color_type red(default_color_type) { return red_color; }
+ inline default_color_type red(default_color_type) { return red_color; }
   inline default_color_type black(default_color_type) { return black_color; }
 
 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
@@ -90,22 +93,29 @@
   BOOST_DEF_PROPERTY(vertex, name);
   BOOST_DEF_PROPERTY(graph, name);
   BOOST_DEF_PROPERTY(vertex, distance);
+ BOOST_DEF_PROPERTY(vertex, distance2);
   BOOST_DEF_PROPERTY(vertex, color);
   BOOST_DEF_PROPERTY(vertex, degree);
   BOOST_DEF_PROPERTY(vertex, in_degree);
   BOOST_DEF_PROPERTY(vertex, out_degree);
   BOOST_DEF_PROPERTY(vertex, current_degree);
- BOOST_DEF_PROPERTY(vertex, priority);
+ BOOST_DEF_PROPERTY(vertex, priority);
   BOOST_DEF_PROPERTY(vertex, discover_time);
   BOOST_DEF_PROPERTY(vertex, finish_time);
   BOOST_DEF_PROPERTY(vertex, predecessor);
   BOOST_DEF_PROPERTY(vertex, rank);
   BOOST_DEF_PROPERTY(vertex, centrality);
   BOOST_DEF_PROPERTY(vertex, lowpoint);
+ BOOST_DEF_PROPERTY(vertex, potential);
+ BOOST_DEF_PROPERTY(vertex, update);
   BOOST_DEF_PROPERTY(edge, reverse);
   BOOST_DEF_PROPERTY(edge, capacity);
+ BOOST_DEF_PROPERTY(edge, flow);
   BOOST_DEF_PROPERTY(edge, residual_capacity);
   BOOST_DEF_PROPERTY(edge, centrality);
+ BOOST_DEF_PROPERTY(edge, discover_time);
+ BOOST_DEF_PROPERTY(edge, update);
+ BOOST_DEF_PROPERTY(edge, finished);
   BOOST_DEF_PROPERTY(graph, visitor);
 
   // These tags are used for property bundles
@@ -223,7 +233,7 @@
   template <class Graph, class Property>
   class graph_property {
   public:
- typedef typename property_value<typename Graph::graph_property_type,
+ typedef typename property_value<typename Graph::graph_property_type,
       Property>::type type;
   };
 
@@ -239,9 +249,9 @@
   };
 
   template <typename Graph>
- class degree_property_map
+ class degree_property_map
     : public put_get_helper<typename graph_traits<Graph>::degree_size_type,
- degree_property_map<Graph> >
+ degree_property_map<Graph> >
   {
   public:
     typedef typename graph_traits<Graph>::vertex_descriptor key_type;
@@ -262,7 +272,7 @@
   }
 
   //========================================================================
- // Iterator Property Map Generating Functions contributed by
+ // Iterator Property Map Generating Functions contributed by
   // Kevin Vanhorn. (see also the property map generating functions
   // in boost/property_map.hpp)
 
@@ -281,8 +291,8 @@
   make_iterator_vertex_map(RandomAccessIterator iter, const PropertyGraph& g)
   {
     return make_iterator_property_map(iter, get(vertex_index, g));
- }
-
+ }
+
   // Use this next function when vertex_descriptor is known to be an
   // integer type, with values ranging from 0 to num_vertices(g).
   //
@@ -297,7 +307,7 @@
   make_iterator_vertex_map(RandomAccessIterator iter)
   {
     return make_iterator_property_map(iter, identity_property_map());
- }
+ }
 #endif
 
   template <class PropertyGraph, class RandomAccessContainer>
@@ -312,7 +322,7 @@
   {
     assert(c.size() >= num_vertices(g));
     return make_iterator_vertex_map(c.begin(), g);
- }
+ }
 
   template <class RandomAccessContainer> inline
   iterator_property_map<
@@ -329,17 +339,17 @@
 #if defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
 # define BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 #endif
-
+
 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
   template<typename Graph, typename Descriptor, typename Bundle, typename T>
   struct bundle_property_map
     : put_get_helper<T&, bundle_property_map<Graph, Descriptor, Bundle, T> >
   {
     typedef Descriptor key_type;
- typedef T value_type;
+ typedef typename remove_const<T>::type value_type;
     typedef T& reference;
     typedef lvalue_property_map_tag category;
-
+
     bundle_property_map() { }
     bundle_property_map(Graph* g_, T Bundle::* pm_) : g(g_), pm(pm_) {}
 
@@ -351,11 +361,15 @@
 
   namespace detail {
     template<typename VertexBundle, typename EdgeBundle, typename Bundle>
- struct is_vertex_bundle : is_convertible<VertexBundle*, Bundle*> {};
+ struct is_vertex_bundle
+ : mpl::and_<is_convertible<Bundle*, VertexBundle*>,
+ mpl::and_<mpl::not_<is_void<VertexBundle> >,
+ mpl::not_<is_same<VertexBundle, no_property> > > >
+ { };
   }
-
+
   template <typename Graph, typename T, typename Bundle>
- struct property_map<Graph, T Bundle::*>
+ struct property_map<Graph, T Bundle::*>
   {
   private:
     typedef graph_traits<Graph> traits;
@@ -376,7 +390,6 @@
       const_type;
   };
 #endif
-
 } // namespace boost
 
 #if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
@@ -385,5 +398,4 @@
 # undef RandomAccessIterator
 #endif
 
-
 #endif /* BOOST_GRAPH_PROPERTIES_HPPA */

Modified: trunk/boost/property_map.hpp
==============================================================================
--- trunk/boost/property_map.hpp (original)
+++ trunk/boost/property_map.hpp 2009-04-01 12:03:21 EDT (Wed, 01 Apr 2009)
@@ -500,22 +500,20 @@
   //=========================================================================
   // A property map that always returns a reference to the same object.
   //
-template <typename KeyType, typename ValueType>
-class ref_property_map :
- public
- boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> >
-{
- ValueType* value;
-public:
- typedef KeyType key_type;
- typedef ValueType value_type;
- typedef ValueType& reference;
- typedef lvalue_property_map_tag category;
- ref_property_map(ValueType& v) : value(&v) {}
- ValueType& operator[](key_type const&) const { return *value; }
-
-};
-
+ template <typename KeyType, typename ValueType>
+ class ref_property_map :
+ public
+ boost::put_get_helper<ValueType&,ref_property_map<KeyType,ValueType> >
+ {
+ ValueType* value;
+ public:
+ typedef KeyType key_type;
+ typedef ValueType value_type;
+ typedef ValueType& reference;
+ typedef lvalue_property_map_tag category;
+ ref_property_map(ValueType& v) : value(&v) {}
+ ValueType& operator[](key_type const&) const { return *value; }
+ };
 
   //=========================================================================
   // A property map that applies the identity function to integers


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