|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r53761 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2009-06-08 17:06:15
Author: jewillco
Date: 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
New Revision: 53761
URL: http://svn.boost.org/trac/boost/changeset/53761
Log:
Fixed issues from ticket #3151 (some using the patch there and some in other ways); fixes #3151, refs #3134
Text files modified:
trunk/boost/graph/adj_list_serialize.hpp | 17 +++++++--------
trunk/boost/graph/adjacency_list_io.hpp | 44 +++++++++++++++++++--------------------
trunk/boost/graph/bc_clustering.hpp | 8 ++++--
trunk/boost/graph/cuthill_mckee_ordering.hpp | 5 ++-
trunk/boost/graph/depth_first_search.hpp | 10 ++++++--
trunk/boost/graph/edge_connectivity.hpp | 6 +++-
trunk/boost/graph/graph_utility.hpp | 21 +++++++++++++++++++
trunk/boost/graph/howard_cycle_ratio.hpp | 3 +
trunk/boost/graph/isomorphism.hpp | 10 +++-----
trunk/boost/graph/king_ordering.hpp | 5 ++-
trunk/boost/graph/push_relabel_max_flow.hpp | 43 +++++++++++++++++++--------------------
11 files changed, 99 insertions(+), 73 deletions(-)
Modified: trunk/boost/graph/adj_list_serialize.hpp
==============================================================================
--- trunk/boost/graph/adj_list_serialize.hpp (original)
+++ trunk/boost/graph/adj_list_serialize.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -10,6 +10,7 @@
#define ADJ_LIST_SERIALIZE_HPP
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/iteration_macros.hpp>
#include <boost/pending/property_serialize.hpp>
#include <boost/config.hpp>
#include <boost/detail/workaround.hpp>
@@ -49,18 +50,16 @@
// assign indices to vertices
std::map<Vertex,int> indices;
int num = 0;
- typename graph_traits<Graph>::vertex_iterator vi;
- for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi) {
- indices[*vi] = num++;
- ar << serialization::make_nvp("vertex_property", get(vertex_all_t(), graph, *vi) );
+ BGL_FORALL_VERTICES_T(v, graph, Graph) {
+ indices[v] = num++;
+ ar << serialization::make_nvp("vertex_property", get(vertex_all_t(), graph, v) );
}
// write edges
- typename graph_traits<Graph>::edge_iterator ei;
- for (ei = edges(graph).first; ei != edges(graph).second; ++ei){
- ar << serialization::make_nvp("u" , indices[source(*ei,graph)]);
- ar << serialization::make_nvp("v" , indices[target(*ei,graph)]);
- ar << serialization::make_nvp("edge_property", get(edge_all_t(), graph, *ei) );
+ BGL_FORALL_EDGES_T(e, graph, Graph) {
+ ar << serialization::make_nvp("u" , indices[source(e,graph)]);
+ ar << serialization::make_nvp("v" , indices[target(e,graph)]);
+ ar << serialization::make_nvp("edge_property", get(edge_all_t(), graph, e) );
}
}
Modified: trunk/boost/graph/adjacency_list_io.hpp
==============================================================================
--- trunk/boost/graph/adjacency_list_io.hpp (original)
+++ trunk/boost/graph/adjacency_list_io.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -12,6 +12,7 @@
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/iteration_macros.hpp>
#include <cctype>
// Method read to parse an adjacency list from an input stream. Examples:
@@ -211,13 +212,13 @@
PropertyPrinter( const Graph& g ):graph(&g){}
- template<class Iterator>
- PropertyPrinter& operator () ( std::ostream& out, Iterator it )
+ template<class Val>
+ PropertyPrinter& operator () ( std::ostream& out, const Val& v )
{
typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
- out << ps[ *it ] <<" ";
+ out << ps[ v ] <<" ";
PropertyPrinter<Graph,Next> print(*graph);
- print(out, it);
+ print(out, v);
return (*this);
}
private:
@@ -229,10 +230,10 @@
{
PropertyPrinter( const Graph& g ):graph(&g){}
- template<class Iterator>
- PropertyPrinter& operator () ( std::ostream& out, Iterator it )
+ template<class Val>
+ PropertyPrinter& operator () ( std::ostream& out, const Val& v )
{
- out << (*graph)[ *it ] <<" ";
+ out << (*graph)[ v ] <<" ";
return (*this);
}
private:
@@ -244,13 +245,13 @@
{
PropertyPrinter( const Graph& g ):graph(&g){}
- template<class Iterator>
- PropertyPrinter& operator () ( std::ostream& out, Iterator it )
+ template<class Val>
+ PropertyPrinter& operator () ( std::ostream& out, const Val& v )
{
typename property_map<Graph,Tag>::type ps = get(Tag(), *graph);
- out << ps[ *it ] <<" ";
+ out << ps[ v ] <<" ";
PropertyPrinter<Graph,Next> print(*graph);
- print(out, it);
+ print(out, v);
return (*this);
}
private:
@@ -263,8 +264,8 @@
{
PropertyPrinter( const Graph& ){}
- template<class Iterator>
- PropertyPrinter& operator () ( std::ostream&, Iterator it ){ return *this; }
+ template<class Val>
+ PropertyPrinter& operator () ( std::ostream&, const Val& ){ return *this; }
};
// property printer
@@ -287,18 +288,16 @@
// assign indices to vertices
std::map<Vertex,int> indices;
int num = 0;
- typename graph_traits<Graph>::vertex_iterator vi;
- for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){
- indices[*vi] = num++;
+ BGL_FORALL_VERTICES_T(v, graph, Graph) {
+ indices[v] = num++;
}
// write edges
PropertyPrinter<Graph, EdgeProperty> print_Edge(graph);
out << "e" << std::endl;
- typename graph_traits<Graph>::edge_iterator ei;
- for (ei = edges(graph).first; ei != edges(graph).second; ++ei){
- out << indices[source(*ei,graph)] << " " << indices[target(*ei,graph)] << " ";
- print_Edge(out,ei);
+ BGL_FORALL_EDGES_T(e, graph, Graph) {
+ out << indices[source(e,graph)] << " " << indices[target(e,graph)] << " ";
+ print_Edge(out,e);
out << std::endl;
}
out << std::endl;
@@ -322,9 +321,8 @@
{
PropertyPrinter<Graph, V> printNode(this->graph);
out << "v"<<std::endl;
- typename graph_traits<Graph>::vertex_iterator vi;
- for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){
- printNode(out,vi);
+ BGL_FORALL_VERTICES_T(v, this->graph, Graph) {
+ printNode(out,v);
out << std::endl;
}
Modified: trunk/boost/graph/bc_clustering.hpp
==============================================================================
--- trunk/boost/graph/bc_clustering.hpp (original)
+++ trunk/boost/graph/bc_clustering.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -11,6 +11,7 @@
#include <boost/graph/betweenness_centrality.hpp>
#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_utility.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <algorithm>
#include <vector>
@@ -116,7 +117,7 @@
typedef typename graph_traits<MutableGraph>::vertices_size_type
vertices_size_type;
- if (edges(g).first == edges(g).second) return;
+ if (has_no_edges(g)) return;
// Function object that compares the centrality of edges
indirect_cmp<EdgeCentralityMap, std::less<centrality_type> >
@@ -127,10 +128,11 @@
brandes_betweenness_centrality(g,
edge_centrality_map(edge_centrality)
.vertex_index_map(vertex_index));
- edge_descriptor e = *max_element(edges(g).first, edges(g).second, cmp);
+ std::pair<edge_iterator, edge_iterator> edges_iters = edges(g);
+ edge_descriptor e = *max_element(edges_iters.first, edges_iters.second, cmp);
is_done = done(get(edge_centrality, e), e, g);
if (!is_done) remove_edge(e, g);
- } while (!is_done && edges(g).first != edges(g).second);
+ } while (!is_done && !has_no_edges(g));
}
/**
Modified: trunk/boost/graph/cuthill_mckee_ordering.hpp
==============================================================================
--- trunk/boost/graph/cuthill_mckee_ordering.hpp (original)
+++ trunk/boost/graph/cuthill_mckee_ordering.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -13,6 +13,7 @@
#include <boost/config.hpp>
#include <boost/graph/detail/sparse_ordering.hpp>
+#include <boost/graph/graph_utility.hpp>
#include <algorithm>
@@ -132,7 +133,7 @@
cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
ColorMap color, DegreeMap degree)
{
- if (vertices(G).first == vertices(G).second)
+ if (has_no_vertices(G))
return permutation;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
@@ -168,7 +169,7 @@
cuthill_mckee_ordering(const Graph& G, OutputIterator permutation,
VertexIndexMap index_map)
{
- if (vertices(G).first == vertices(G).second)
+ if (has_no_vertices(G))
return permutation;
typedef out_degree_property_map<Graph> DegreeMap;
Modified: trunk/boost/graph/depth_first_search.hpp
==============================================================================
--- trunk/boost/graph/depth_first_search.hpp (original)
+++ trunk/boost/graph/depth_first_search.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -214,10 +214,12 @@
void
depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color)
{
- if (vertices(g).first == vertices(g).second)
+ typedef typename boost::graph_traits<VertexListGraph>::vertex_iterator vi;
+ std::pair<vi, vi> verts = vertices(g);
+ if (verts.first == verts.second)
return;
- depth_first_search(g, vis, color, *vertices(g).first);
+ depth_first_search(g, vis, color, *verts.first);
}
template <class Visitors = null_visitor>
@@ -284,7 +286,9 @@
depth_first_search(const VertexListGraph& g,
const bgl_named_params<P, T, R>& params)
{
- if (vertices(g).first == vertices(g).second)
+ typedef typename boost::graph_traits<VertexListGraph>::vertex_iterator vi;
+ std::pair<vi, vi> verts = vertices(g);
+ if (verts.first == verts.second)
return;
using namespace boost::graph::keywords;
typedef bgl_named_params<P, T, R> params_type;
Modified: trunk/boost/graph/edge_connectivity.hpp
==============================================================================
--- trunk/boost/graph/edge_connectivity.hpp (original)
+++ trunk/boost/graph/edge_connectivity.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -132,7 +132,8 @@
detail::neighbors(g, S.begin(), S.end(),
std::inserter(neighbor_S, neighbor_S.begin()));
- std::set_difference(vertices(g).first, vertices(g).second,
+ tie(vi, vi_end) = vertices(g);
+ std::set_difference(vi, vi_end,
neighbor_S.begin(), neighbor_S.end(),
std::back_inserter(non_neighbor_S));
@@ -153,7 +154,8 @@
neighbor_S.insert(k);
detail::neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
non_neighbor_S.clear();
- std::set_difference(vertices(g).first, vertices(g).second,
+ tie(vi, vi_end) = vertices(g);
+ std::set_difference(vi, vi_end,
neighbor_S.begin(), neighbor_S.end(),
std::back_inserter(non_neighbor_S));
}
Modified: trunk/boost/graph/graph_utility.hpp
==============================================================================
--- trunk/boost/graph/graph_utility.hpp (original)
+++ trunk/boost/graph/graph_utility.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -445,6 +445,27 @@
add_removed_edge_capacity(Graph& g) : base(get(edge_capacity, g)) {}
};
+ template <typename Graph>
+ bool has_no_vertices(const Graph& g) {
+ typedef typename boost::graph_traits<Graph>::vertex_iterator vi;
+ std::pair<vi, vi> p = vertices(g);
+ return (p.first == p.second);
+ }
+
+ template <typename Graph>
+ bool has_no_edges(const Graph& g) {
+ typedef typename boost::graph_traits<Graph>::edge_iterator ei;
+ std::pair<ei, ei> p = edges(g);
+ return (p.first == p.second);
+ }
+
+ template <typename Graph>
+ bool has_no_out_edges(const typename boost::graph_traits<Graph>::vertex_descriptor& v, const Graph& g) {
+ typedef typename boost::graph_traits<Graph>::out_edge_iterator ei;
+ std::pair<ei, ei> p = out_edges(v, g);
+ return (p.first == p.second);
+ }
+
} // namespace graph
} /* namespace boost */
Modified: trunk/boost/graph/howard_cycle_ratio.hpp
==============================================================================
--- trunk/boost/graph/howard_cycle_ratio.hpp (original)
+++ trunk/boost/graph/howard_cycle_ratio.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -29,6 +29,7 @@
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/graph_utility.hpp>
namespace boost {
namespace detail {
@@ -172,7 +173,7 @@
}
BGL_FORALL_VERTICES_T(vd1, m_g, TGraph)
{
- if (boost::out_edges(vd1, m_g).first == boost::out_edges(vd1, m_g).second) throw bad_graph(m_vim[vd1]);
+ if (boost::graph::has_no_out_edges(vd1, m_g)) throw bad_graph(m_vim[vd1]);
mcr_edge_t ed = *boost::out_edges(vd1, m_g).first;
pi_edge_t pied = boost::add_edge(m_g2pi_g_vm[source(ed, m_g)], m_g2pi_g_vm[target(ed, m_g)], m_pi_g).first;
boost::put(boost::edge_weight, m_pi_g, pied, m_ew1m[ed]);
Modified: trunk/boost/graph/isomorphism.hpp
==============================================================================
--- trunk/boost/graph/isomorphism.hpp (original)
+++ trunk/boost/graph/isomorphism.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -439,13 +439,11 @@
return false;
#endif
- for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first;
- e1 != edges(g1).second; ++e1) {
+ BGL_FORALL_EDGES_T(e1, g1, Graph1) {
bool found_edge = false;
- for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first;
- e2 != edges(g2).second && !found_edge; ++e2) {
- if (source(*e2, g2) == get(iso_map, source(*e1, g1)) &&
- target(*e2, g2) == get(iso_map, target(*e1, g1))) {
+ BGL_FORALL_EDGES_T(e2, g2, Graph2) {
+ if (source(e2, g2) == get(iso_map, source(e1, g1)) &&
+ target(e2, g2) == get(iso_map, target(e1, g1))) {
found_edge = true;
}
}
Modified: trunk/boost/graph/king_ordering.hpp
==============================================================================
--- trunk/boost/graph/king_ordering.hpp (original)
+++ trunk/boost/graph/king_ordering.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -13,6 +13,7 @@
#include <boost/config.hpp>
#include <boost/graph/detail/sparse_ordering.hpp>
+#include <boost/graph/graph_utility.hpp>
/*
King Algorithm for matrix reordering
@@ -262,7 +263,7 @@
king_ordering(const Graph& G, OutputIterator permutation,
ColorMap color, DegreeMap degree, VertexIndexMap index_map)
{
- if (vertices(G).first == vertices(G).second)
+ if (has_no_vertices(G))
return permutation;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
@@ -298,7 +299,7 @@
king_ordering(const Graph& G, OutputIterator permutation,
VertexIndexMap index_map)
{
- if (vertices(G).first == vertices(G).second)
+ if (has_no_vertices(G))
return permutation;
typedef out_degree_property_map<Graph> DegreeMap;
Modified: trunk/boost/graph/push_relabel_max_flow.hpp
==============================================================================
--- trunk/boost/graph/push_relabel_max_flow.hpp (original)
+++ trunk/boost/graph/push_relabel_max_flow.hpp 2009-06-08 17:06:13 EDT (Mon, 08 Jun 2009)
@@ -121,7 +121,7 @@
: 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_).second),
+ current(num_vertices(g_), out_edges(*vertices(g_).first, g_)),
distance(num_vertices(g_)),
color(num_vertices(g_)),
reverse_edge(rev),
@@ -149,7 +149,7 @@
for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
vertex_descriptor u = *u_iter;
excess_flow[u] = 0;
- current[u] = out_edges(u, g).first;
+ current[u] = out_edges(u, g);
}
bool overflow_detected = false;
@@ -240,7 +240,7 @@
&& is_residual_edge(reverse_edge[a])) {
distance[v] = d_v;
color[v] = ColorTraits::gray();
- current[v] = out_edges(v, g).first;
+ current[v] = out_edges(v, g);
max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(d_v, max_distance);
if (excess_flow[v] > 0)
@@ -262,8 +262,7 @@
assert(excess_flow[u] > 0);
while (1) {
out_edge_iterator ai, ai_end;
- for (ai = current[u], ai_end = out_edges(u, g).second;
- ai != ai_end; ++ai) {
+ for (tie(ai, ai_end) = current[u]; ai != ai_end; ++ai) {
edge_descriptor a = *ai;
if (is_residual_edge(a)) {
vertex_descriptor v = target(a, g);
@@ -291,7 +290,7 @@
if (distance[u] == n)
break;
} else { // i is no longer active
- current[u] = ai;
+ current[u].first = ai;
add_to_inactive_list(u, layer);
break;
}
@@ -350,7 +349,7 @@
++min_distance;
if (min_distance < n) {
distance[u] = min_distance; // this is the main action
- current[u] = min_edge_iter;
+ current[u].first = min_edge_iter;
max_distance = max BOOST_PREVENT_MACRO_SUBSTITUTION(min_distance, max_distance);
}
return min_distance;
@@ -444,7 +443,7 @@
u = *u_iter;
color[u] = ColorTraits::white();
parent[u] = u;
- current[u] = out_edges(u, g).first;
+ current[u] = out_edges(u, g);
}
// eliminate flow cycles and topologically order the vertices
for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
@@ -455,8 +454,8 @@
r = u;
color[r] = ColorTraits::gray();
while (1) {
- for (; current[u] != out_edges(u, g).second; ++current[u]) {
- edge_descriptor a = *current[u];
+ for (; current[u].first != current[u].second; ++current[u].first) {
+ edge_descriptor a = *current[u].first;
if (capacity[a] == 0 && is_residual_edge(a)) {
vertex_descriptor v = target(a, g);
if (color[v] == ColorTraits::white()) {
@@ -469,16 +468,16 @@
FlowValue delta = residual_capacity[a];
while (1) {
BOOST_USING_STD_MIN();
- delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[*current[v]]);
+ delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[*current[v].first]);
if (v == u)
break;
else
- v = target(*current[v], g);
+ v = target(*current[v].first, g);
}
// remove delta flow units
v = u;
while (1) {
- a = *current[v];
+ a = *current[v].first;
residual_capacity[a] -= delta;
residual_capacity[reverse_edge[a]] += delta;
v = target(a, g);
@@ -488,25 +487,25 @@
// back-out of DFS to the first saturated edge
restart = u;
- for (v = target(*current[u], g); v != u; v = target(a, g)){
- a = *current[v];
+ for (v = target(*current[u].first, g); v != u; v = target(a, g)){
+ a = *current[v].first;
if (color[v] == ColorTraits::white()
|| is_saturated(a)) {
- color[target(*current[v], g)] = ColorTraits::white();
+ color[target(*current[v].first, g)] = ColorTraits::white();
if (color[v] != ColorTraits::white())
restart = v;
}
}
if (restart != u) {
u = restart;
- ++current[u];
+ ++current[u].first;
break;
}
} // else if (color[v] == ColorTraits::gray())
} // if (capacity[a] == 0 ...
} // for out_edges(u, g) (though "u" changes during loop)
- if (current[u] == out_edges(u, g).second) {
+ if ( current[u].first == current[u].second ) {
// scan of i is complete
color[u] = ColorTraits::black();
if (u != src) {
@@ -521,7 +520,7 @@
}
if (u != r) {
u = parent[u];
- ++current[u];
+ ++current[u].first;
} else
break;
}
@@ -533,8 +532,8 @@
// note that the sink is not on the stack
if (! bos_null) {
for (u = tos; u != bos; u = topo_next[u]) {
- ai = out_edges(u, g).first;
- while (excess_flow[u] > 0 && ai != out_edges(u, g).second) {
+ tie(ai, a_end) = out_edges(u, g);
+ while (excess_flow[u] > 0 && ai != a_end) {
if (capacity[*ai] == 0 && is_residual_edge(*ai))
push_flow(*ai);
++ai;
@@ -632,7 +631,7 @@
// will need to use random_access_property_map with these
std::vector< FlowValue > excess_flow;
- std::vector< out_edge_iterator > current;
+ std::vector< std::pair<out_edge_iterator, out_edge_iterator> > current;
std::vector< distance_size_type > distance;
std::vector< default_color_type > color;
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