|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r73026 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2011-07-12 21:04:48
Author: jewillco
Date: 2011-07-12 21:04:47 EDT (Tue, 12 Jul 2011)
New Revision: 73026
URL: http://svn.boost.org/trac/boost/changeset/73026
Log:
Weakened property map requirements further, removing uses of [] on property maps
Text files modified:
trunk/boost/graph/boykov_kolmogorov_max_flow.hpp | 183 ++++++++++++++++++++-------------------
1 files changed, 93 insertions(+), 90 deletions(-)
Modified: trunk/boost/graph/boykov_kolmogorov_max_flow.hpp
==============================================================================
--- trunk/boost/graph/boykov_kolmogorov_max_flow.hpp (original)
+++ trunk/boost/graph/boykov_kolmogorov_max_flow.hpp 2011-07-12 21:04:47 EDT (Tue, 12 Jul 2011)
@@ -125,14 +125,14 @@
// the residual capacity equal to the capacity
edge_iterator ei, e_end;
for(boost::tie(ei, e_end) = edges(m_g); ei != e_end; ++ei) {
- m_res_cap_map[*ei] = m_cap_map[*ei];
- BOOST_ASSERT(m_rev_edge_map[m_rev_edge_map[*ei]] == *ei); //check if the reverse edge map is build up properly
+ put(m_res_cap_map, *ei, get(m_cap_map, *ei));
+ BOOST_ASSERT(get(m_rev_edge_map, get(m_rev_edge_map, *ei)) == *ei); //check if the reverse edge map is build up properly
}
//init the search trees with the two terminals
set_tree(m_source, tColorTraits::black());
set_tree(m_sink, tColorTraits::white());
- m_time_map[m_source] = 1;
- m_time_map[m_sink] = 1;
+ put(m_time_map, m_source, 1);
+ put(m_time_map, m_sink, 1);
}
tEdgeVal max_flow(){
@@ -168,8 +168,8 @@
edge_descriptor from_source = *ei;
vertex_descriptor current_node = target(from_source, m_g);
if(current_node == m_sink){
- tEdgeVal cap = m_res_cap_map[from_source];
- m_res_cap_map[from_source] = 0;
+ tEdgeVal cap = get(m_res_cap_map, from_source);
+ put(m_res_cap_map, from_source, 0);
m_flow += cap;
continue;
}
@@ -177,52 +177,52 @@
bool is_there;
boost::tie(to_sink, is_there) = lookup_edge(current_node, m_sink, m_g);
if(is_there){
- tEdgeVal cap_from_source = m_res_cap_map[from_source];
- tEdgeVal cap_to_sink = m_res_cap_map[to_sink];
+ tEdgeVal cap_from_source = get(m_res_cap_map, from_source);
+ tEdgeVal cap_to_sink = get(m_res_cap_map, to_sink);
if(cap_from_source > cap_to_sink){
set_tree(current_node, tColorTraits::black());
add_active_node(current_node);
set_edge_to_parent(current_node, from_source);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
+ put(m_dist_map, current_node, 1);
+ put(m_time_map, current_node, 1);
// add stuff to flow and update residuals. we dont need to
// update reverse_edges, as incoming/outgoing edges to/from
// source/sink don't count for max-flow
- m_res_cap_map[from_source] -= cap_to_sink;
- m_res_cap_map[to_sink] = 0;
+ put(m_res_cap_map, from_source, get(m_res_cap_map, from_source) - cap_to_sink);
+ put(m_res_cap_map, to_sink, 0);
m_flow += cap_to_sink;
} else if(cap_to_sink > 0){
set_tree(current_node, tColorTraits::white());
add_active_node(current_node);
set_edge_to_parent(current_node, to_sink);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
+ put(m_dist_map, current_node, 1);
+ put(m_time_map, current_node, 1);
// add stuff to flow and update residuals. we dont need to update
// reverse_edges, as incoming/outgoing edges to/from source/sink
// don't count for max-flow
- m_res_cap_map[to_sink] -= cap_from_source;
- m_res_cap_map[from_source] = 0;
+ put(m_res_cap_map, to_sink, get(m_res_cap_map, to_sink) - cap_from_source);
+ put(m_res_cap_map, from_source, 0);
m_flow += cap_from_source;
}
- } else if(m_res_cap_map[from_source]){
+ } else if(get(m_res_cap_map, from_source)){
// there is no sink connect, so we can't augment this path, but to
// avoid adding m_source to the active nodes, we just activate this
// node and set the approciate things
set_tree(current_node, tColorTraits::black());
set_edge_to_parent(current_node, from_source);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
+ put(m_dist_map, current_node, 1);
+ put(m_time_map, current_node, 1);
add_active_node(current_node);
}
}
for(boost::tie(ei, e_end) = out_edges(m_sink, m_g); ei != e_end; ++ei){
- edge_descriptor to_sink = m_rev_edge_map[*ei];
+ edge_descriptor to_sink = get(m_rev_edge_map, *ei);
vertex_descriptor current_node = source(to_sink, m_g);
- if(m_res_cap_map[to_sink]){
+ if(get(m_res_cap_map, to_sink)){
set_tree(current_node, tColorTraits::white());
set_edge_to_parent(current_node, to_sink);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
+ put(m_dist_map, current_node, 1);
+ put(m_time_map, current_node, 1);
add_active_node(current_node);
}
}
@@ -252,21 +252,21 @@
}
for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it) {
edge_descriptor out_edge = *m_last_grow_edge_it;
- if(m_res_cap_map[out_edge] > 0){ //check if we have capacity left on this edge
+ if(get(m_res_cap_map, out_edge) > 0){ //check if we have capacity left on this edge
vertex_descriptor other_node = target(out_edge, m_g);
if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
set_tree(other_node, tColorTraits::black()); //aquire other node to our search tree
set_edge_to_parent(other_node, out_edge); //set us as parent
- m_dist_map[other_node] = m_dist_map[current_node] + 1; //and update the distance-heuristic
- m_time_map[other_node] = m_time_map[current_node];
+ put(m_dist_map, other_node, get(m_dist_map, current_node) + 1); //and update the distance-heuristic
+ put(m_time_map, other_node, get(m_time_map, current_node));
add_active_node(other_node);
} else if(get_tree(other_node) == tColorTraits::black()) {
// we do this to get shorter paths. check if we are nearer to
// the source as its parent is
if(is_closer_to_terminal(current_node, other_node)){
set_edge_to_parent(other_node, out_edge);
- m_dist_map[other_node] = m_dist_map[current_node] + 1;
- m_time_map[other_node] = m_time_map[current_node];
+ put(m_dist_map, other_node, get(m_dist_map, current_node) + 1);
+ put(m_time_map, other_node, get(m_time_map, current_node));
}
} else{
BOOST_ASSERT(get_tree(other_node)==tColorTraits::white());
@@ -285,21 +285,21 @@
boost::tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
}
for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it){
- edge_descriptor in_edge = m_rev_edge_map[*m_last_grow_edge_it];
- if(m_res_cap_map[in_edge] > 0){ //check if there is capacity left
+ edge_descriptor in_edge = get(m_rev_edge_map, *m_last_grow_edge_it);
+ if(get(m_res_cap_map, in_edge) > 0){ //check if there is capacity left
vertex_descriptor other_node = source(in_edge, m_g);
if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
set_tree(other_node, tColorTraits::white()); //aquire that node to our search tree
set_edge_to_parent(other_node, in_edge); //set us as parent
add_active_node(other_node); //activate that node
- m_dist_map[other_node] = m_dist_map[current_node] + 1; //set its distance
- m_time_map[other_node] = m_time_map[current_node]; //and time
+ put(m_dist_map, other_node, get(m_dist_map, current_node) + 1); //set its distance
+ put(m_time_map, other_node, get(m_time_map, current_node));//and time
} else if(get_tree(other_node) == tColorTraits::white()){
if(is_closer_to_terminal(current_node, other_node)){
//we are closer to the sink than its parent is, so we "adopt" him
set_edge_to_parent(other_node, in_edge);
- m_dist_map[other_node] = m_dist_map[current_node] + 1;
- m_time_map[other_node] = m_time_map[current_node];
+ put(m_dist_map, other_node, get(m_dist_map, current_node) + 1);
+ put(m_time_map, other_node, get(m_time_map, current_node));
}
} else{
BOOST_ASSERT(get_tree(other_node)==tColorTraits::black());
@@ -340,18 +340,18 @@
//now we push the found flow through the path
//for each edge we saturate we have to look for the verts that belong to that edge, one of them becomes an orphans
//now process the connecting edge
- m_res_cap_map[e] -= bottleneck;
- BOOST_ASSERT(m_res_cap_map[e] >= 0);
- m_res_cap_map[m_rev_edge_map[e]] += bottleneck;
+ put(m_res_cap_map, e, get(m_res_cap_map, e) - bottleneck);
+ BOOST_ASSERT(get(m_res_cap_map, e) >= 0);
+ put(m_res_cap_map, get(m_rev_edge_map, e), get(m_res_cap_map, get(m_rev_edge_map, e)) + bottleneck);
//now we follow the path back to the source
vertex_descriptor current_node = source(e, m_g);
while(current_node != m_source){
edge_descriptor pred = get_edge_to_parent(current_node);
- m_res_cap_map[pred] -= bottleneck;
- BOOST_ASSERT(m_res_cap_map[pred] >= 0);
- m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
- if(m_res_cap_map[pred] == 0){
+ put(m_res_cap_map, pred, get(m_res_cap_map, pred) - bottleneck);
+ BOOST_ASSERT(get(m_res_cap_map, pred) >= 0);
+ put(m_res_cap_map, get(m_rev_edge_map, pred), get(m_res_cap_map, get(m_rev_edge_map, pred)) + bottleneck);
+ if(get(m_res_cap_map, pred) == 0){
set_no_parent(current_node);
m_orphans.push_front(current_node);
}
@@ -361,10 +361,10 @@
current_node = target(e, m_g);
while(current_node != m_sink){
edge_descriptor pred = get_edge_to_parent(current_node);
- m_res_cap_map[pred] -= bottleneck;
- BOOST_ASSERT(m_res_cap_map[pred] >= 0);
- m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
- if(m_res_cap_map[pred] == 0){
+ put(m_res_cap_map, pred, get(m_res_cap_map, pred) - bottleneck);
+ BOOST_ASSERT(get(m_res_cap_map, pred) >= 0);
+ put(m_res_cap_map, get(m_rev_edge_map, pred), get(m_res_cap_map, get(m_rev_edge_map, pred)) + bottleneck);
+ if(get(m_res_cap_map, pred) == 0){
set_no_parent(current_node);
m_orphans.push_front(current_node);
}
@@ -380,19 +380,19 @@
*/
inline tEdgeVal find_bottleneck(edge_descriptor e){
BOOST_USING_STD_MIN();
- tEdgeVal minimum_cap = m_res_cap_map[e];
+ tEdgeVal minimum_cap = get(m_res_cap_map, e);
vertex_descriptor current_node = source(e, m_g);
//first go back in the source tree
while(current_node != m_source){
edge_descriptor pred = get_edge_to_parent(current_node);
- minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, m_res_cap_map[pred]);
+ minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, get(m_res_cap_map, pred));
current_node = source(pred, m_g);
}
//then go forward in the sink-tree
current_node = target(e, m_g);
while(current_node != m_sink){
edge_descriptor pred = get_edge_to_parent(current_node);
- minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, m_res_cap_map[pred]);
+ minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, get(m_res_cap_map, pred));
current_node = target(pred, m_g);
}
return minimum_cap;
@@ -420,13 +420,13 @@
edge_descriptor new_parent_edge;
out_edge_iterator ei, e_end;
for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- const edge_descriptor in_edge = m_rev_edge_map[*ei];
+ const edge_descriptor in_edge = get(m_rev_edge_map, *ei);
BOOST_ASSERT(target(in_edge, m_g) == current_node); //we should be the target of this edge
- if(m_res_cap_map[in_edge] > 0){
+ if(get(m_res_cap_map, in_edge) > 0){
vertex_descriptor other_node = source(in_edge, m_g);
if(get_tree(other_node) == tColorTraits::black() && has_source_connect(other_node)){
- if(m_dist_map[other_node] < min_distance){
- min_distance = m_dist_map[other_node];
+ if(get(m_dist_map, other_node) < min_distance){
+ min_distance = get(m_dist_map, other_node);
new_parent_edge = in_edge;
}
}
@@ -434,15 +434,15 @@
}
if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
set_edge_to_parent(current_node, new_parent_edge);
- m_dist_map[current_node] = min_distance + 1;
- m_time_map[current_node] = m_time;
+ put(m_dist_map, current_node, min_distance + 1);
+ put(m_time_map, current_node, m_time);
} else{
- m_time_map[current_node] = 0;
+ put(m_time_map, current_node, 0);
for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- edge_descriptor in_edge = m_rev_edge_map[*ei];
+ edge_descriptor in_edge = get(m_rev_edge_map, *ei);
vertex_descriptor other_node = source(in_edge, m_g);
if(get_tree(other_node) == tColorTraits::black() && has_parent(other_node)){
- if(m_res_cap_map[in_edge] > 0){
+ if(get(m_res_cap_map, in_edge) > 0){
add_active_node(other_node);
}
if(source(get_edge_to_parent(other_node), m_g) == current_node){
@@ -464,26 +464,26 @@
tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
const edge_descriptor out_edge = *ei;
- if(m_res_cap_map[out_edge] > 0){
+ if(get(m_res_cap_map, out_edge) > 0){
const vertex_descriptor other_node = target(out_edge, m_g);
if(get_tree(other_node) == tColorTraits::white() && has_sink_connect(other_node))
- if(m_dist_map[other_node] < min_distance){
- min_distance = m_dist_map[other_node];
+ if(get(m_dist_map, other_node) < min_distance){
+ min_distance = get(m_dist_map, other_node);
new_parent_edge = out_edge;
}
}
}
if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
set_edge_to_parent(current_node, new_parent_edge);
- m_dist_map[current_node] = min_distance + 1;
- m_time_map[current_node] = m_time;
+ put(m_dist_map, current_node, min_distance + 1);
+ put(m_time_map, current_node, m_time);
} else{
- m_time_map[current_node] = 0;
+ put(m_time_map, current_node, 0);
for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
const edge_descriptor out_edge = *ei;
const vertex_descriptor other_node = target(out_edge, m_g);
if(get_tree(other_node) == tColorTraits::white() && has_parent(other_node)){
- if(m_res_cap_map[out_edge] > 0){
+ if(get(m_res_cap_map, out_edge) > 0){
add_active_node(other_node);
}
if(target(get_edge_to_parent(other_node), m_g) == current_node){
@@ -511,7 +511,7 @@
//if it has no parent, this node can't be active (if its not source or sink)
if(!has_parent(v) && v != m_source && v != m_sink){
m_active_nodes.pop();
- m_in_active_list_map[v] = false;
+ put(m_in_active_list_map, v, false);
} else{
BOOST_ASSERT(get_tree(v) == tColorTraits::black() || get_tree(v) == tColorTraits::white());
return v;
@@ -524,10 +524,10 @@
*/
inline void add_active_node(vertex_descriptor v){
BOOST_ASSERT(get_tree(v) != tColorTraits::gray());
- if(m_in_active_list_map[v]){
+ if(get(m_in_active_list_map, v)){
return;
} else{
- m_in_active_list_map[v] = true;
+ put(m_in_active_list_map, v, true);
m_active_nodes.push(v);
}
}
@@ -538,7 +538,7 @@
inline void finish_node(vertex_descriptor v){
BOOST_ASSERT(m_active_nodes.front() == v);
m_active_nodes.pop();
- m_in_active_list_map[v] = false;
+ put(m_in_active_list_map, v, false);
m_last_grow_vertex = graph_traits<Graph>::null_vertex();
}
@@ -571,23 +571,23 @@
* returns edge to parent vertex of v;
*/
inline edge_descriptor get_edge_to_parent(vertex_descriptor v) const{
- return m_pre_map[v];
+ return get(m_pre_map, v);
}
/**
* returns true if the edge stored in m_pre_map[v] is a valid entry
*/
inline bool has_parent(vertex_descriptor v) const{
- return m_has_parent_map[v];
+ return get(m_has_parent_map, v);
}
/**
* sets edge to parent vertex of v;
*/
inline void set_edge_to_parent(vertex_descriptor v, edge_descriptor f_edge_to_parent){
- BOOST_ASSERT(m_res_cap_map[f_edge_to_parent] > 0);
- m_pre_map[v] = f_edge_to_parent;
- m_has_parent_map[v] = true;
+ BOOST_ASSERT(get(m_res_cap_map, f_edge_to_parent) > 0);
+ put(m_pre_map, v, f_edge_to_parent);
+ put(m_has_parent_map, v, true);
}
/**
@@ -595,7 +595,7 @@
* entry an additional map)
*/
inline void set_no_parent(vertex_descriptor v){
- m_has_parent_map[v] = false;
+ put(m_has_parent_map, v, false);
}
/**
@@ -607,13 +607,13 @@
tDistanceVal current_distance = 0;
vertex_descriptor current_vertex = v;
while(true){
- if(m_time_map[current_vertex] == m_time){
+ if(get(m_time_map, current_vertex) == m_time){
//we found a node which was already checked this round. use it for distance calculations
- current_distance += m_dist_map[current_vertex];
+ current_distance += get(m_dist_map, current_vertex);
break;
}
if(current_vertex == m_sink){
- m_time_map[m_sink] = m_time;
+ put(m_time_map, m_sink, m_time);
break;
}
if(has_parent(current_vertex)){
@@ -626,9 +626,10 @@
}
}
current_vertex=v;
- while(m_time_map[current_vertex] != m_time){
- m_dist_map[current_vertex] = current_distance--;
- m_time_map[current_vertex] = m_time;
+ while(get(m_time_map, current_vertex) != m_time){
+ put(m_dist_map, current_vertex, current_distance);
+ --current_distance;
+ put(m_time_map, current_vertex, m_time);
current_vertex = target(get_edge_to_parent(current_vertex), m_g);
}
return true;
@@ -643,13 +644,13 @@
tDistanceVal current_distance = 0;
vertex_descriptor current_vertex = v;
while(true){
- if(m_time_map[current_vertex] == m_time){
+ if(get(m_time_map, current_vertex) == m_time){
//we found a node which was already checked this round. use it for distance calculations
- current_distance += m_dist_map[current_vertex];
+ current_distance += get(m_dist_map, current_vertex);
break;
}
if(current_vertex == m_source){
- m_time_map[m_source] = m_time;
+ put(m_time_map, m_source, m_time);
break;
}
if(has_parent(current_vertex)){
@@ -662,9 +663,10 @@
}
}
current_vertex=v;
- while(m_time_map[current_vertex] != m_time){
- m_dist_map[current_vertex] = current_distance-- ;
- m_time_map[current_vertex] = m_time;
+ while(get(m_time_map, current_vertex) != m_time){
+ put(m_dist_map, current_vertex, current_distance);
+ --current_distance;
+ put(m_time_map, current_vertex, m_time);
current_vertex = source(get_edge_to_parent(current_vertex), m_g);
}
return true;
@@ -675,7 +677,8 @@
*/
inline bool is_closer_to_terminal(vertex_descriptor p, vertex_descriptor q){
//checks the timestamps first, to build no cycles, and after that the real distance
- return (m_time_map[q] <= m_time_map[p] && m_dist_map[q] > m_dist_map[p]+1);
+ return (get(m_time_map, q) <= get(m_time_map, p) &&
+ get(m_dist_map, q) > get(m_dist_map, p)+1);
}
////////
@@ -744,11 +747,11 @@
function_requires<EdgeListGraphConcept<Graph> >(); //to have edges()
function_requires<IncidenceGraphConcept<Graph> >(); //to have source(), target() and out_edges()
function_requires<ReadablePropertyMapConcept<CapacityEdgeMap, edge_descriptor> >(); //read flow-values from edges
- function_requires<Mutable_LvaluePropertyMapConcept<ResidualCapacityEdgeMap, edge_descriptor> >(); //write flow-values to residuals
+ function_requires<ReadWritePropertyMapConcept<ResidualCapacityEdgeMap, edge_descriptor> >(); //write flow-values to residuals
function_requires<ReadablePropertyMapConcept<ReverseEdgeMap, edge_descriptor> >(); //read out reverse edges
- function_requires<Mutable_LvaluePropertyMapConcept<PredecessorMap, vertex_descriptor> >(); //store predecessor there
+ function_requires<ReadWritePropertyMapConcept<PredecessorMap, vertex_descriptor> >(); //store predecessor there
function_requires<ReadWritePropertyMapConcept<ColorMap, vertex_descriptor> >(); //write corresponding tree
- function_requires<Mutable_LvaluePropertyMapConcept<DistanceMap, vertex_descriptor> >(); //write distance to source/sink
+ function_requires<ReadWritePropertyMapConcept<DistanceMap, vertex_descriptor> >(); //write distance to source/sink
function_requires<ReadablePropertyMapConcept<IndexMap, vertex_descriptor> >(); //get index 0...|V|-1
BOOST_ASSERT(num_vertices(g) >= 2 && src != sink);
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