Subject: [Boost-commit] svn:boost r63662 - in branches/release: . boost boost/algorithm/string boost/archive boost/bimap boost/config boost/detail boost/filesystem boost/functional/hash boost/fusion boost/gil boost/graph boost/graph/detail boost/graph/distributed boost/graph/distributed/adjlist boost/integer boost/interprocess boost/intrusive boost/iostreams boost/math boost/msm boost/numeric/ublas boost/program_options boost/property_map/parallel boost/property_tree boost/python boost/range boost/regex boost/serialization boost/signals boost/signals2 boost/spirit boost/spirit/home boost/spirit/home/karma boost/spirit/home/support boost/statechart boost/system boost/thread boost/tr1 boost/type_traits boost/unordered boost/utility boost/uuid boost/variant boost/wave doc libs libs/array/doc libs/array/test libs/bimap libs/config libs/config/test libs/filesystem libs/functional/hash libs/graph/test libs/graph_parallel libs/graph_parallel/test libs/integer libs/interprocess libs/intrusive libs/iostreams libs/math libs/mpl/doc/refmanual libs/mpl/doc/src/refmanual libs/msm libs/numeric/ublas libs/numeric/ublas/doc libs/program_options libs/property_map/doc libs/property_tree libs/python libs/python/doc/v2 libs/range libs/range/doc libs/regex libs/serialization libs/signals libs/signals2 libs/spirit libs/spirit/classic/example libs/spirit/doc libs/spirit/example libs/spirit/phoenix libs/spirit/test libs/spirit/test/qi libs/statechart libs/static_assert libs/system libs/thread libs/timer libs/tr1 libs/type_traits libs/unordered libs/utility libs/utility/swap/test libs/uuid libs/wave more more/getting_started status tools tools/bcp tools/boostbook tools/build/v2 tools/build/v2/tools tools/inspect tools/jam tools/quickbook tools/regression tools/release tools/wave
From: jewillco_at_[hidden]
Date: 2010-07-05 12:17:42
Author: jewillco
Date: 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
New Revision: 63662
URL: http://svn.boost.org/trac/boost/changeset/63662
Log:
Merged various changes from trunk
Properties modified:
branches/release/ (props changed)
branches/release/INSTALL (props changed)
branches/release/Jamroot (props changed)
branches/release/LICENSE_1_0.txt (props changed)
branches/release/boost/ (props changed)
branches/release/boost-build.jam (props changed)
branches/release/boost.css (props changed)
branches/release/boost.png (props changed)
branches/release/boost/algorithm/string/ (props changed)
branches/release/boost/archive/ (props changed)
branches/release/boost/array.hpp (props changed)
branches/release/boost/bimap/ (props changed)
branches/release/boost/config/ (props changed)
branches/release/boost/config.hpp (props changed)
branches/release/boost/detail/ (props changed)
branches/release/boost/detail/endian.hpp (props changed)
branches/release/boost/filesystem/ (props changed)
branches/release/boost/functional/hash/ (props changed)
branches/release/boost/fusion/ (props changed)
branches/release/boost/gil/ (props changed)
branches/release/boost/graph/ (props changed)
branches/release/boost/integer/ (props changed)
branches/release/boost/interprocess/ (props changed)
branches/release/boost/intrusive/ (props changed)
branches/release/boost/iostreams/ (props changed)
branches/release/boost/math/ (props changed)
branches/release/boost/math_fwd.hpp (props changed)
branches/release/boost/msm/ (props changed)
branches/release/boost/numeric/ublas/ (props changed)
branches/release/boost/numeric/ublas/functional.hpp (props changed)
branches/release/boost/program_options/ (props changed)
branches/release/boost/property_tree/ (props changed)
branches/release/boost/python/ (props changed)
branches/release/boost/range/ (props changed)
branches/release/boost/regex/ (props changed)
branches/release/boost/serialization/ (props changed)
branches/release/boost/serialization/factory.hpp (props changed)
branches/release/boost/signals/ (props changed)
branches/release/boost/signals2/ (props changed)
branches/release/boost/spirit/ (props changed)
branches/release/boost/spirit/home/ (props changed)
branches/release/boost/spirit/home/karma/ (props changed)
branches/release/boost/spirit/home/support/attributes.hpp (props changed)
branches/release/boost/statechart/ (props changed)
branches/release/boost/system/ (props changed)
branches/release/boost/thread/ (props changed)
branches/release/boost/thread.hpp (props changed)
branches/release/boost/tr1/ (props changed)
branches/release/boost/type_traits/ (props changed)
branches/release/boost/unordered/ (props changed)
branches/release/boost/utility/ (props changed)
branches/release/boost/uuid/ (props changed)
branches/release/boost/variant/ (props changed)
branches/release/boost/version.hpp (props changed)
branches/release/boost/wave/ (props changed)
branches/release/bootstrap.bat (props changed)
branches/release/bootstrap.sh (props changed)
branches/release/doc/ (props changed)
branches/release/index.htm (props changed)
branches/release/index.html (props changed)
branches/release/libs/ (props changed)
branches/release/libs/array/doc/array.xml (props changed)
branches/release/libs/array/test/array0.cpp (props changed)
branches/release/libs/array/test/array2.cpp (props changed)
branches/release/libs/bimap/ (props changed)
branches/release/libs/config/ (props changed)
branches/release/libs/config/test/boost_no_com_value_init.ipp (props changed)
branches/release/libs/filesystem/ (props changed)
branches/release/libs/functional/hash/ (props changed)
branches/release/libs/graph_parallel/ (props changed)
branches/release/libs/integer/ (props changed)
branches/release/libs/interprocess/ (props changed)
branches/release/libs/intrusive/ (props changed)
branches/release/libs/iostreams/ (props changed)
branches/release/libs/libraries.htm (props changed)
branches/release/libs/maintainers.txt (props changed)
branches/release/libs/math/ (props changed)
branches/release/libs/mpl/doc/refmanual/broken-compiler-workarounds.html (props changed)
branches/release/libs/mpl/doc/refmanual/categorized-index-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/cfg-no-preprocessed-headers.html (props changed)
branches/release/libs/mpl/doc/refmanual/composition-and-argument-binding.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-miscellaneous.html (props changed)
branches/release/libs/mpl/doc/refmanual/extensible-associative-sequence.html (props changed)
branches/release/libs/mpl/doc/refmanual/inserter-class.html (props changed)
branches/release/libs/mpl/doc/refmanual/tag-dispatched-metafunction.html (props changed)
branches/release/libs/mpl/doc/refmanual/trivial-metafunctions-summary.html (props changed)
branches/release/libs/mpl/doc/src/refmanual/Iterators-Iterator.rst (props changed)
branches/release/libs/msm/ (props changed)
branches/release/libs/numeric/ublas/ (props changed)
branches/release/libs/numeric/ublas/doc/ (props changed)
branches/release/libs/program_options/ (props changed)
branches/release/libs/property_tree/ (props changed)
branches/release/libs/python/ (props changed)
branches/release/libs/python/doc/v2/args.html (props changed)
branches/release/libs/python/doc/v2/return_internal_reference.html (props changed)
branches/release/libs/range/ (props changed)
branches/release/libs/range/doc/ (props changed)
branches/release/libs/regex/ (props changed)
branches/release/libs/serialization/ (props changed)
branches/release/libs/signals/ (props changed)
branches/release/libs/signals2/ (props changed)
branches/release/libs/spirit/ (props changed)
branches/release/libs/spirit/classic/example/ (props changed)
branches/release/libs/spirit/doc/ (props changed)
branches/release/libs/spirit/example/ (props changed)
branches/release/libs/spirit/phoenix/ (props changed)
branches/release/libs/spirit/test/ (props changed)
branches/release/libs/spirit/test/qi/optional.cpp (props changed)
branches/release/libs/statechart/ (props changed)
branches/release/libs/static_assert/ (props changed)
branches/release/libs/system/ (props changed)
branches/release/libs/thread/ (props changed)
branches/release/libs/timer/ (props changed)
branches/release/libs/tr1/ (props changed)
branches/release/libs/type_traits/ (props changed)
branches/release/libs/unordered/ (props changed)
branches/release/libs/utility/ (props changed)
branches/release/libs/utility/swap.html (props changed)
branches/release/libs/utility/swap/test/std_bitset.cpp (props changed)
branches/release/libs/utility/value_init_test.cpp (props changed)
branches/release/libs/uuid/ (props changed)
branches/release/libs/wave/ (props changed)
branches/release/more/ (props changed)
branches/release/more/getting_started/ (props changed)
branches/release/rst.css (props changed)
branches/release/status/ (props changed)
branches/release/status/Jamfile.v2 (props changed)
branches/release/tools/ (props changed)
branches/release/tools/bcp/ (props changed)
branches/release/tools/boostbook/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/build/v2/tools/ (props changed)
branches/release/tools/inspect/ (props changed)
branches/release/tools/jam/ (props changed)
branches/release/tools/quickbook/ (props changed)
branches/release/tools/regression/ (props changed)
branches/release/tools/release/ (props changed)
branches/release/tools/wave/ (props changed)
Text files modified:
branches/release/boost/graph/compressed_sparse_row_graph.hpp | 4
branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp | 10
branches/release/boost/graph/distributed/adjlist/serialization.hpp | 2
branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp | 16 +-
branches/release/boost/graph/distributed/rmat_graph_generator.hpp | 3
branches/release/boost/graph/graph_concepts.hpp | 2
branches/release/boost/graph/graph_traits.hpp | 2
branches/release/boost/graph/push_relabel_max_flow.hpp | 212 +++++++++++++++++++++------------------
branches/release/boost/graph/read_dimacs.hpp | 5
branches/release/boost/graph/undirected_graph.hpp | 2
branches/release/boost/property_map/parallel/distributed_property_map.hpp | 21 +++
branches/release/libs/graph/test/csr_graph_test.cpp | 4
branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp | 6
branches/release/libs/property_map/doc/dynamic_property_map.html | 2
14 files changed, 167 insertions(+), 124 deletions(-)
Modified: branches/release/boost/graph/compressed_sparse_row_graph.hpp
==============================================================================
--- branches/release/boost/graph/compressed_sparse_row_graph.hpp (original)
+++ branches/release/boost/graph/compressed_sparse_row_graph.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -1275,8 +1275,8 @@
typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it;
EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
- return std::make_pair(it(ed(v, v_row_start)),
- it(ed(v, next_row_start)));
+ return std::make_pair(it(g, v_row_start),
+ it(g, next_row_start));
}
template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
Modified: branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp
==============================================================================
--- branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp (original)
+++ branches/release/boost/graph/detail/compressed_sparse_row_struct.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -525,18 +525,18 @@
typedef typename CSRGraph::edges_size_type EdgeIndex;
typedef typename CSRGraph::edge_descriptor edge_descriptor;
- csr_in_edge_iterator() {}
+ csr_in_edge_iterator(): m_graph(0) {}
// Implicit copy constructor OK
csr_in_edge_iterator(const CSRGraph& graph,
EdgeIndex index_in_backward_graph)
- : m_graph(graph), m_index_in_backward_graph(index_in_backward_graph) {}
+ : m_index_in_backward_graph(index_in_backward_graph), m_graph(&graph) {}
public: // See above
// iterator_facade requirements
edge_descriptor dereference() const {
return edge_descriptor(
- m_graph.m_backward.m_column[m_index_in_backward_graph],
- m_graph.m_backward.m_edge_properties[m_index_in_backward_graph]);
+ m_graph->m_backward.m_column[m_index_in_backward_graph],
+ m_graph->m_backward.m_edge_properties[m_index_in_backward_graph]);
}
bool equal(const csr_in_edge_iterator& other) const
@@ -550,7 +550,7 @@
{ return other.m_index_in_backward_graph - m_index_in_backward_graph; }
EdgeIndex m_index_in_backward_graph;
- const CSRGraph& m_graph;
+ const CSRGraph* m_graph;
friend class iterator_core_access;
};
Modified: branches/release/boost/graph/distributed/adjlist/serialization.hpp
==============================================================================
--- branches/release/boost/graph/distributed/adjlist/serialization.hpp (original)
+++ branches/release/boost/graph/distributed/adjlist/serialization.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -77,7 +77,7 @@
inline bool is_digit(char c)
{
- return std::isdigit(c);
+ return (bool)std::isdigit(c);
}
inline std::vector<int>
Modified: branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp
==============================================================================
--- branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp (original)
+++ branches/release/boost/graph/distributed/hohberg_biconnected_components.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -173,7 +173,7 @@
#endif
if (a == b) {
-#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 2
+#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2
std::cerr << local(a) << '@' << owner(a) << std::endl;
#endif
return a;
@@ -186,7 +186,7 @@
if (*last == b) { swap(a,b); break; }
if (last == first) {
-#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 2
+#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2
std::cerr << local(*first) << '@' << owner(*first) << std::endl;
#endif
return *first;
@@ -205,7 +205,7 @@
else --last;
}
-#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 2
+#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2
std::cerr << local(*last) << '@' << owner(*last) << std::endl;
#endif
// We've found b; it's the infimum.
@@ -715,7 +715,7 @@
} else if (edata.is_tree_edge) {
has_more_children_to_name = true;
}
-#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 2
+#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2
std::cerr << "M[" << local(source(e, g)) << '@' << owner(source(e, g))
<< " -> " << local(target(e, g)) << '@' << owner(target(e, g))
<< "] = ";
@@ -747,7 +747,7 @@
if (parent != graph_traits<Graph>::null_vertex()) {
Edge edge_to_parent;
-#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 1
+#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1
std::cerr << local(alpha) << '@' << owner(alpha) << " echo: parent = "
<< local(parent) << '@' << owner(parent) << ", eta = "
<< local(eta) << '@' << owner(eta) << ", Gamma = ";
@@ -759,7 +759,7 @@
if (target(e, g) == parent && parent == eta) {
edge_to_parent = e;
if (find(bicomp.begin(), bicomp.end(), alpha) == bicomp.end()) {
-#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 1
+#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1
std::cerr << local(alpha) << '@' << owner(alpha) << ' ';
#endif
bicomp.push_back(alpha);
@@ -777,7 +777,7 @@
++pos;
if (pos != edata.msg.path_or_bicomp.end()
&& find(bicomp.begin(), bicomp.end(), *pos) == bicomp.end()) {
-#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 1
+#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1
std::cerr << local(*pos) << '@' << owner(*pos) << ' ';
#endif
bicomp.push_back(*pos);
@@ -787,7 +787,7 @@
for (path_iterator i = edata.msg.path_or_bicomp.begin();
i != edata.msg.path_or_bicomp.end(); ++i) {
if (find(bicomp.begin(), bicomp.end(), *i) == bicomp.end()) {
-#if defined(PBGL_HOHBERG_DEBUG) and PBGL_HOHBERG_DEBUG > 1
+#if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1
std::cerr << local(*i) << '@' << owner(*i) << ' ';
#endif
bicomp.push_back(*i);
Modified: branches/release/boost/graph/distributed/rmat_graph_generator.hpp
==============================================================================
--- branches/release/boost/graph/distributed/rmat_graph_generator.hpp (original)
+++ branches/release/boost/graph/distributed/rmat_graph_generator.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -15,6 +15,7 @@
#include <boost/graph/parallel/algorithm.hpp>
#include <boost/graph/parallel/process_group.hpp>
+#include <math.h>
namespace boost {
@@ -59,7 +60,7 @@
if (permute_vertices)
generate_permutation_vector(gen, vertexPermutation, n);
- int SCALE = int(floor(log2(n)));
+ int SCALE = int(floor(log(n)/log(2.)));
boost::uniform_01<RandomGenerator> prob(gen);
std::map<value_type, bool> edge_map;
Modified: branches/release/boost/graph/graph_concepts.hpp
==============================================================================
--- branches/release/boost/graph/graph_concepts.hpp (original)
+++ branches/release/boost/graph/graph_concepts.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -448,6 +448,7 @@
typedef unsigned Index; // This could be Graph::vertex_index_type
Map m = get(vertex_index, g);
Index x = get(vertex_index, g, Vertex());
+ ignore_unused_variable_warning(m);
ignore_unused_variable_warning(x);
// This is relaxed
@@ -474,6 +475,7 @@
typedef unsigned Index; // This could be Graph::vertex_index_type
Map m = get(edge_index, g);
Index x = get(edge_index, g, Edge());
+ ignore_unused_variable_warning(m);
ignore_unused_variable_warning(x);
// This is relaxed
Modified: branches/release/boost/graph/graph_traits.hpp
==============================================================================
--- branches/release/boost/graph/graph_traits.hpp (original)
+++ branches/release/boost/graph/graph_traits.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -67,7 +67,7 @@
return detail::is_directed(Cat());
}
- /** Return false if the given graph is undirected. */
+ /** Return true if the given graph is undirected. */
template <typename Graph>
bool is_undirected(const Graph& g) {
return !is_directed(g);
Modified: branches/release/boost/graph/push_relabel_max_flow.hpp
==============================================================================
--- branches/release/boost/graph/push_relabel_max_flow.hpp (original)
+++ branches/release/boost/graph/push_relabel_max_flow.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -75,13 +75,13 @@
// Some helper predicates
inline bool is_admissible(vertex_descriptor u, vertex_descriptor v) {
- return distance[u] == distance[v] + 1;
+ return get(distance, u) == get(distance, v) + 1;
}
inline bool is_residual_edge(edge_descriptor a) {
- return 0 < residual_capacity[a];
+ return 0 < get(residual_capacity, a);
}
inline bool is_saturated(edge_descriptor a) {
- return residual_capacity[a] == 0;
+ return get(residual_capacity, a) == 0;
}
//=======================================================================
@@ -93,12 +93,12 @@
BOOST_USING_STD_MIN();
BOOST_USING_STD_MAX();
layer.active_vertices.push_front(u);
- max_active = max BOOST_PREVENT_MACRO_SUBSTITUTION(distance[u], max_active);
- min_active = min BOOST_PREVENT_MACRO_SUBSTITUTION(distance[u], min_active);
+ max_active = max BOOST_PREVENT_MACRO_SUBSTITUTION(get(distance, u), max_active);
+ min_active = min BOOST_PREVENT_MACRO_SUBSTITUTION(get(distance, u), min_active);
layer_list_ptr[u] = layer.active_vertices.begin();
}
void remove_from_active_list(vertex_descriptor u) {
- layers[distance[u]].active_vertices.erase(layer_list_ptr[u]);
+ layers[get(distance, u)].active_vertices.erase(layer_list_ptr[u]);
}
void add_to_inactive_list(vertex_descriptor u, Layer& layer) {
@@ -106,7 +106,7 @@
layer_list_ptr[u] = layer.inactive_vertices.begin();
}
void remove_from_inactive_list(vertex_descriptor u) {
- layers[distance[u]].inactive_vertices.erase(layer_list_ptr[u]);
+ layers[get(distance, u)].inactive_vertices.erase(layer_list_ptr[u]);
}
//=======================================================================
@@ -120,15 +120,20 @@
VertexIndexMap idx)
: g(g_), n(num_vertices(g_)), capacity(cap), src(src_), sink(sink_),
index(idx),
- excess_flow(num_vertices(g_)),
- current(num_vertices(g_), out_edges(*vertices(g_).first, g_)),
- distance(num_vertices(g_)),
- color(num_vertices(g_)),
+ excess_flow_data(num_vertices(g_)),
+ excess_flow(excess_flow_data.begin(), idx),
+ current_data(num_vertices(g_), out_edges(*vertices(g_).first, g_)),
+ current(current_data.begin(), idx),
+ distance_data(num_vertices(g_)),
+ distance(distance_data.begin(), idx),
+ color_data(num_vertices(g_)),
+ color(color_data.begin(), idx),
reverse_edge(rev),
residual_capacity(res),
layers(num_vertices(g_)),
- layer_list_ptr(num_vertices(g_),
- layers.front().inactive_vertices.end()),
+ layer_list_ptr_data(num_vertices(g_),
+ layers.front().inactive_vertices.end()),
+ layer_list_ptr(layer_list_ptr_data.begin(), idx),
push_count(0), update_count(0), relabel_count(0),
gap_count(0), gap_node_count(0),
work_since_last_update(0)
@@ -143,12 +148,12 @@
out_edge_iterator ei, e_end;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei) {
- residual_capacity[*ei] = capacity[*ei];
+ put(residual_capacity, *ei, get(capacity, *ei));
}
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
vertex_descriptor u = *u_iter;
- excess_flow[u] = 0;
+ put(excess_flow, u, 0);
current[u] = out_edges(u, g);
}
@@ -158,23 +163,25 @@
out_edge_iterator a_iter, a_end;
for (boost::tie(a_iter, a_end) = out_edges(src, g); a_iter != a_end; ++a_iter)
if (target(*a_iter, g) != src)
- test_excess += residual_capacity[*a_iter];
+ test_excess += get(residual_capacity, *a_iter);
if (test_excess > (std::numeric_limits<FlowValue>::max)())
overflow_detected = true;
if (overflow_detected)
- excess_flow[src] = (std::numeric_limits<FlowValue>::max)();
+ put(excess_flow, src, (std::numeric_limits<FlowValue>::max)());
else {
- excess_flow[src] = 0;
+ put(excess_flow, src, 0);
for (boost::tie(a_iter, a_end) = out_edges(src, g);
a_iter != a_end; ++a_iter) {
edge_descriptor a = *a_iter;
- if (target(a, g) != src) {
+ vertex_descriptor tgt = target(a, g);
+ if (tgt != src) {
++push_count;
- FlowValue delta = residual_capacity[a];
- residual_capacity[a] -= delta;
- residual_capacity[reverse_edge[a]] += delta;
- excess_flow[target(a, g)] += delta;
+ FlowValue delta = get(residual_capacity, a);
+ put(residual_capacity, a, get(residual_capacity, a) - delta);
+ edge_descriptor rev = get(reverse_edge, a);
+ put(residual_capacity, rev, get(residual_capacity, rev) + delta);
+ put(excess_flow, tgt, get(excess_flow, tgt) + delta);
}
}
}
@@ -185,16 +192,16 @@
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
vertex_descriptor u = *u_iter;
if (u == sink) {
- distance[u] = 0;
+ put(distance, u, 0);
continue;
} else if (u == src && !overflow_detected)
- distance[u] = n;
+ put(distance, u, n);
else
- distance[u] = 1;
+ put(distance, u, 1);
- if (excess_flow[u] > 0)
+ if (get(excess_flow, u) > 0)
add_to_active_list(u, layers[1]);
- else if (distance[u] < n)
+ else if (get(distance, u) < n)
add_to_inactive_list(u, layers[1]);
}
@@ -212,11 +219,11 @@
++update_count;
vertex_iterator u_iter, u_end;
for (boost::tie(u_iter,u_end) = vertices(g); u_iter != u_end; ++u_iter) {
- color[*u_iter] = ColorTraits::white();
- distance[*u_iter] = n;
+ put(color, *u_iter, ColorTraits::white());
+ put(distance, *u_iter, n);
}
- color[sink] = ColorTraits::gray();
- distance[sink] = 0;
+ put(color, sink, ColorTraits::gray());
+ put(distance, sink, 0);
for (distance_size_type l = 0; l <= max_distance; ++l) {
layers[l].active_vertices.clear();
@@ -230,20 +237,20 @@
while (! Q.empty()) {
vertex_descriptor u = Q.top();
Q.pop();
- distance_size_type d_v = distance[u] + 1;
+ distance_size_type d_v = get(distance, u) + 1;
out_edge_iterator ai, a_end;
for (boost::tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai) {
edge_descriptor a = *ai;
vertex_descriptor v = target(a, g);
- if (color[v] == ColorTraits::white()
- && is_residual_edge(reverse_edge[a])) {
- distance[v] = d_v;
- color[v] = ColorTraits::gray();
+ if (get(color, v) == ColorTraits::white()
+ && is_residual_edge(get(reverse_edge, a))) {
+ put(distance, v, d_v);
+ put(color, v, ColorTraits::gray());
current[v] = out_edges(v, g);
max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(d_v, max_distance);
- if (excess_flow[v] > 0)
+ if (get(excess_flow, v) > 0)
add_to_active_list(v, layers[d_v]);
else
add_to_inactive_list(v, layers[d_v]);
@@ -259,7 +266,7 @@
// but it is called "discharge" in the paper and in hi_pr.c.
void discharge(vertex_descriptor u)
{
- assert(excess_flow[u] > 0);
+ assert(get(excess_flow, u) > 0);
while (1) {
out_edge_iterator ai, ai_end;
for (boost::tie(ai, ai_end) = current[u]; ai != ai_end; ++ai) {
@@ -268,26 +275,26 @@
vertex_descriptor v = target(a, g);
if (is_admissible(u, v)) {
++push_count;
- if (v != sink && excess_flow[v] == 0) {
+ if (v != sink && get(excess_flow, v) == 0) {
remove_from_inactive_list(v);
- add_to_active_list(v, layers[distance[v]]);
+ add_to_active_list(v, layers[get(distance, v)]);
}
push_flow(a);
- if (excess_flow[u] == 0)
+ if (get(excess_flow, u) == 0)
break;
}
}
} // for out_edges of i starting from current
- Layer& layer = layers[distance[u]];
- distance_size_type du = distance[u];
+ Layer& layer = layers[get(distance, u)];
+ distance_size_type du = get(distance, u);
if (ai == ai_end) { // i must be relabeled
relabel_distance(u);
if (layer.active_vertices.empty()
&& layer.inactive_vertices.empty())
gap(du);
- if (distance[u] == n)
+ if (get(distance, u) == n)
break;
} else { // i is no longer active
current[u].first = ai;
@@ -309,13 +316,14 @@
BOOST_USING_STD_MIN();
FlowValue flow_delta
- = min BOOST_PREVENT_MACRO_SUBSTITUTION(excess_flow[u], residual_capacity[u_v]);
+ = min BOOST_PREVENT_MACRO_SUBSTITUTION(get(excess_flow, u), get(residual_capacity, u_v));
- residual_capacity[u_v] -= flow_delta;
- residual_capacity[reverse_edge[u_v]] += flow_delta;
+ put(residual_capacity, u_v, get(residual_capacity, u_v) - flow_delta);
+ edge_descriptor rev = get(reverse_edge, u_v);
+ put(residual_capacity, rev, get(residual_capacity, rev) + flow_delta);
- excess_flow[u] -= flow_delta;
- excess_flow[v] += flow_delta;
+ put(excess_flow, u, get(excess_flow, u) - flow_delta);
+ put(excess_flow, v, get(excess_flow, v) + flow_delta);
} // push_flow()
//=======================================================================
@@ -332,7 +340,7 @@
work_since_last_update += beta();
distance_size_type min_distance = num_vertices(g);
- distance[u] = min_distance;
+ put(distance, u, min_distance);
// Examine the residual out-edges of vertex i, choosing the
// edge whose target vertex has the minimal distance.
@@ -341,14 +349,14 @@
++work_since_last_update;
edge_descriptor a = *ai;
vertex_descriptor v = target(a, g);
- if (is_residual_edge(a) && distance[v] < min_distance) {
- min_distance = distance[v];
+ if (is_residual_edge(a) && get(distance, v) < min_distance) {
+ min_distance = get(distance, v);
min_edge_iter = ai;
}
}
++min_distance;
if (min_distance < n) {
- distance[u] = min_distance; // this is the main action
+ put(distance, u, min_distance); // this is the main action
current[u].first = min_edge_iter;
max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(min_distance, max_distance);
}
@@ -370,7 +378,7 @@
list_iterator i;
for (i = l->inactive_vertices.begin();
i != l->inactive_vertices.end(); ++i) {
- distance[*i] = n;
+ put(distance, *i, n);
++gap_node_count;
}
l->inactive_vertices.clear();
@@ -405,7 +413,7 @@
}
} // while (max_active >= min_active)
- return excess_flow[sink];
+ return get(excess_flow, sink);
} // maximum_preflow()
//=======================================================================
@@ -436,39 +444,39 @@
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ai, a_end) = out_edges(*u_iter, g); ai != a_end; ++ai)
if (target(*ai, g) == *u_iter)
- residual_capacity[*ai] = capacity[*ai];
+ put(residual_capacity, *ai, get(capacity, *ai));
// initialize
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
u = *u_iter;
- color[u] = ColorTraits::white();
+ put(color, u, ColorTraits::white());
parent[u] = u;
current[u] = out_edges(u, g);
}
// eliminate flow cycles and topologically order the vertices
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
u = *u_iter;
- if (color[u] == ColorTraits::white()
- && excess_flow[u] > 0
+ if (get(color, u) == ColorTraits::white()
+ && get(excess_flow, u) > 0
&& u != src && u != sink ) {
r = u;
- color[r] = ColorTraits::gray();
+ put(color, r, ColorTraits::gray());
while (1) {
for (; current[u].first != current[u].second; ++current[u].first) {
edge_descriptor a = *current[u].first;
- if (capacity[a] == 0 && is_residual_edge(a)) {
+ if (get(capacity, a) == 0 && is_residual_edge(a)) {
vertex_descriptor v = target(a, g);
- if (color[v] == ColorTraits::white()) {
- color[v] = ColorTraits::gray();
+ if (get(color, v) == ColorTraits::white()) {
+ put(color, v, ColorTraits::gray());
parent[v] = u;
u = v;
break;
- } else if (color[v] == ColorTraits::gray()) {
+ } else if (get(color, v) == ColorTraits::gray()) {
// find minimum flow on the cycle
- FlowValue delta = residual_capacity[a];
+ FlowValue delta = get(residual_capacity, a);
while (1) {
BOOST_USING_STD_MIN();
- delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[*current[v].first]);
+ delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, *current[v].first));
if (v == u)
break;
else
@@ -478,8 +486,9 @@
v = u;
while (1) {
a = *current[v].first;
- residual_capacity[a] -= delta;
- residual_capacity[reverse_edge[a]] += delta;
+ put(residual_capacity, a, get(residual_capacity, a) - delta);
+ edge_descriptor rev = get(reverse_edge, a);
+ put(residual_capacity, rev, get(residual_capacity, rev) + delta);
v = target(a, g);
if (v == u)
break;
@@ -489,10 +498,10 @@
restart = u;
for (v = target(*current[u].first, g); v != u; v = target(a, g)){
a = *current[v].first;
- if (color[v] == ColorTraits::white()
+ if (get(color, v) == ColorTraits::white()
|| is_saturated(a)) {
- color[target(*current[v].first, g)] = ColorTraits::white();
- if (color[v] != ColorTraits::white())
+ put(color, target(*current[v].first, g), ColorTraits::white());
+ if (get(color, v) != ColorTraits::white())
restart = v;
}
}
@@ -502,12 +511,12 @@
break;
}
} // else if (color[v] == ColorTraits::gray())
- } // if (capacity[a] == 0 ...
+ } // if (get(capacity, a) == 0 ...
} // for out_edges(u, g) (though "u" changes during loop)
if ( current[u].first == current[u].second ) {
// scan of i is complete
- color[u] = ColorTraits::black();
+ put(color, u, ColorTraits::black());
if (u != src) {
if (bos_null) {
bos = u;
@@ -533,8 +542,8 @@
if (! bos_null) {
for (u = tos; u != bos; u = topo_next[u]) {
boost::tie(ai, a_end) = out_edges(u, g);
- while (excess_flow[u] > 0 && ai != a_end) {
- if (capacity[*ai] == 0 && is_residual_edge(*ai))
+ while (get(excess_flow, u) > 0 && ai != a_end) {
+ if (get(capacity, *ai) == 0 && is_residual_edge(*ai))
push_flow(*ai);
++ai;
}
@@ -542,8 +551,8 @@
// do the bottom
u = bos;
ai = out_edges(u, g).first;
- while (excess_flow[u] > 0) {
- if (capacity[*ai] == 0 && is_residual_edge(*ai))
+ while (get(excess_flow, u) > 0) {
+ if (get(capacity, *ai) == 0 && is_residual_edge(*ai))
push_flow(*ai);
++ai;
}
@@ -561,11 +570,11 @@
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
for (boost::tie(ai, a_end) = out_edges(*u_iter, g); ai != a_end; ++ai) {
edge_descriptor a = *ai;
- if (capacity[a] > 0)
- if ((residual_capacity[a] + residual_capacity[reverse_edge[a]]
- != capacity[a] + capacity[reverse_edge[a]])
- || (residual_capacity[a] < 0)
- || (residual_capacity[reverse_edge[a]] < 0))
+ if (get(capacity, a) > 0)
+ if ((get(residual_capacity, a) + get(residual_capacity, get(reverse_edge, a))
+ != get(capacity, a) + get(capacity, get(reverse_edge, a)))
+ || (get(residual_capacity, a) < 0)
+ || (get(residual_capacity, get(reverse_edge, a)) < 0))
return false;
}
}
@@ -575,16 +584,16 @@
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
vertex_descriptor u = *u_iter;
if (u != src && u != sink) {
- if (excess_flow[u] != 0)
+ if (get(excess_flow, u) != 0)
return false;
sum = 0;
for (boost::tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai)
- if (capacity[*ai] > 0)
- sum -= capacity[*ai] - residual_capacity[*ai];
+ if (get(capacity, *ai) > 0)
+ sum -= get(capacity, *ai) - get(residual_capacity, *ai);
else
- sum += residual_capacity[*ai];
+ sum += get(residual_capacity, *ai);
- if (excess_flow[u] != sum)
+ if (get(excess_flow, u) != sum)
return false;
}
}
@@ -595,7 +604,7 @@
bool is_optimal() {
// check if mincut is saturated...
global_distance_update();
- return distance[src] >= n;
+ return get(distance, src) >= n;
}
void print_statistics(std::ostream& os) const {
@@ -613,9 +622,9 @@
out_edge_iterator ei, e_end;
for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
- if (capacity[*ei] > 0)
+ if (get(capacity, *ei) > 0)
os << *u_iter << " " << target(*ei, g) << " "
- << (capacity[*ei] - residual_capacity[*ei]) << std::endl;
+ << (get(capacity, *ei) - get(residual_capacity, *ei)) << std::endl;
os << std::endl;
}
@@ -630,17 +639,28 @@
VertexIndexMap index;
// will need to use random_access_property_map with these
- std::vector< FlowValue > excess_flow;
- std::vector< std::pair<out_edge_iterator, out_edge_iterator> > current;
- std::vector< distance_size_type > distance;
- std::vector< default_color_type > color;
+ std::vector< FlowValue > excess_flow_data;
+ iterator_property_map<typename std::vector<FlowValue>::iterator, VertexIndexMap> excess_flow;
+ std::vector< std::pair<out_edge_iterator, out_edge_iterator> > current_data;
+ iterator_property_map<
+ typename std::vector< std::pair<out_edge_iterator, out_edge_iterator> >::iterator,
+ VertexIndexMap> current;
+ std::vector< distance_size_type > distance_data;
+ iterator_property_map<
+ typename std::vector< distance_size_type >::iterator,
+ VertexIndexMap> distance;
+ std::vector< default_color_type > color_data;
+ iterator_property_map<
+ std::vector< default_color_type >::iterator,
+ VertexIndexMap> color;
// Edge Property Maps that must be interior to the graph
ReverseEdgeMap reverse_edge;
ResidualCapacityEdgeMap residual_capacity;
LayerArray layers;
- std::vector< list_iterator > layer_list_ptr;
+ std::vector< list_iterator > layer_list_ptr_data;
+ iterator_property_map<typename std::vector< list_iterator >::iterator, VertexIndexMap> layer_list_ptr;
distance_size_type max_distance; // maximal distance
distance_size_type max_active; // maximal distance with active node
distance_size_type min_active; // minimal distance with active node
Modified: branches/release/boost/graph/read_dimacs.hpp
==============================================================================
--- branches/release/boost/graph/read_dimacs.hpp (original)
+++ branches/release/boost/graph/read_dimacs.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -14,6 +14,9 @@
/* ----------------------------------------------------------------- */
+#ifndef BOOST_GRAPH_READ_DIMACS_HPP
+#define BOOST_GRAPH_READ_DIMACS_HPP
+
#include <vector>
#include <iostream>
#include <string>
@@ -280,3 +283,5 @@
/* -------------------- end of parser -------------------*/
} // namespace boost
+
+#endif // BOOST_GRAPH_READ_DIMACS_HPP
Modified: branches/release/boost/graph/undirected_graph.hpp
==============================================================================
--- branches/release/boost/graph/undirected_graph.hpp (original)
+++ branches/release/boost/graph/undirected_graph.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -94,7 +94,7 @@
{ }
inline undirected_graph(undirected_graph const& x)
- : m_graph(x), m_num_vertices(x.m_num_vertices), m_num_edges(x.m_num_edges)
+ : m_graph(x.m_graph), m_num_vertices(x.m_num_vertices), m_num_edges(x.m_num_edges)
, m_max_vertex_index(x.m_max_vertex_index), m_max_edge_index(x.m_max_edge_index)
{ }
Modified: branches/release/boost/property_map/parallel/distributed_property_map.hpp
==============================================================================
--- branches/release/boost/property_map/parallel/distributed_property_map.hpp (original)
+++ branches/release/boost/property_map/parallel/distributed_property_map.hpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -264,6 +264,23 @@
property_map_multiput
};
+ // Code from JoaquÃn M López Muñoz to work around unusual implementation of
+ // std::pair in VC++ 10:
+ template<typename First,typename Second>
+ class pair_first_extractor {
+ typedef std::pair<First,Second> value_type;
+
+ public:
+ typedef First result_type;
+ const result_type& operator()(const value_type& x) const {
+ return x.first;
+ }
+
+ result_type& operator()(value_type& x) const {
+ return x.first;
+ }
+ };
+
public:
/// The type of the ghost cells
typedef multi_index::multi_index_container<
@@ -271,9 +288,7 @@
multi_index::indexed_by<
multi_index::sequenced<>,
multi_index::hashed_unique<
- multi_index::member<std::pair<key_type, value_type>,
- key_type,
- &std::pair<key_type, value_type>::first>
+ pair_first_extractor<key_type, value_type>
>
>
> ghost_cells_type;
Modified: branches/release/libs/graph/test/csr_graph_test.cpp
==============================================================================
--- branches/release/libs/graph/test/csr_graph_test.cpp (original)
+++ branches/release/libs/graph/test/csr_graph_test.cpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -462,6 +462,10 @@
assert_graphs_equal(g, boost::identity_property_map(),
g2b, boost::identity_property_map(),
boost::identity_property_map());
+ // Check in edge access
+ typedef boost::graph_traits<BidirCSRGraphT>::in_edge_iterator in_edge_iterator;
+ std::pair<in_edge_iterator, in_edge_iterator> ie(in_edges(vertex(0, g2b), g2b));
+
std::cout << "Testing CSR graph built using add_edges" << std::endl;
// Test building a graph using add_edges on unsorted lists
CSRGraphT g3(boost::edges_are_unsorted, unsorted_edges, unsorted_edges, 6); // Empty range
Modified: branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp
==============================================================================
--- branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp (original)
+++ branches/release/libs/graph_parallel/test/distributed_shortest_paths_test.cpp 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -22,8 +22,6 @@
#include <boost/test/minimal.hpp>
#include <boost/graph/iteration_macros.hpp>
-#include <sys/time.h>
-#include <time.h>
#include <iostream>
#include <iomanip>
@@ -43,9 +41,7 @@
inline time_type get_time()
{
- timeval tp;
- gettimeofday(&tp, 0);
- return tp.tv_sec + tp.tv_usec / 1000000.0;
+ return MPI_Wtime();
}
std::string print_time(time_type t)
Modified: branches/release/libs/property_map/doc/dynamic_property_map.html
==============================================================================
--- branches/release/libs/property_map/doc/dynamic_property_map.html (original)
+++ branches/release/libs/property_map/doc/dynamic_property_map.html 2010-07-05 12:17:38 EDT (Mon, 05 Jul 2010)
@@ -5,7 +5,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
<title>Boost Dynamic Property Maps</title>
-<link rel="stylesheet" href="../../parameter/doc/html/rst.css" type="text/css" />
+<link rel="stylesheet" href="../../parameter/doc/src/rst.css" type="text/css" />
</head>
<body>
<div class="document" id="logo-dynamic-property-maps">