|
|
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 ¤t; }
+
+ 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 ¤t; }
-
- 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