Subject: [Boost-users] Patch for push_relabel_max_flow
From: Tim Keitt (tkeitt_at_[hidden])
Date: 2008-11-23 10:08:33
I am working with custom graph classes in the Graph library. These
classes construct out edge iterators on the fly. This caused problems
with push_relabel_max_flow as it uses repeated calls to out_edges to
retrieve the end iterator. I've modified the code to store iterator
pairs, rather than repeatedly call out_edges. Here's the diff:
124c124
< current(num_vertices(g_), out_edges(*vertices(g_).first,
g_).second),
---
> current(num_vertices(g_), out_edges(*vertices(g_).first, g_)),
152c152
< current[u] = out_edges(u, g).first;
---
> current[u] = out_edges(u, g);
243c243
< current[v] = out_edges(v, g).first;
---
> current[v] = out_edges(v, g);
265c265
< for (ai = current[u], ai_end = out_edges(u, g).second;
---
> for (ai = current[u].first, ai_end = current[u].second;
294c294
< current[u] = ai;
---
> current[u].first = ai;
353c353
< current[u] = min_edge_iter;
---
> current[u].first = min_edge_iter;
447c447
< current[u] = out_edges(u, g).first;
---
> current[u] = out_edges(u, g);
458,459c458,459
< 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;
472c472
< delta = min
BOOST_PREVENT_MACRO_SUBSTITUTION(delta,
residual_capacity[*current[v]]);
---
> delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[*current[v].first]);
476c476
< v = target(*current[v], g);
---
> v = target(*current[v].first, g);
481c481
< a = *current[v];
---
> a = *current[v].first;
491,492c491,492
< 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;
495c495
< color[target(*current[v], g)] = ColorTraits::white();
---
> color[target(*current[v].first, g)] = ColorTraits::white();
502c502
< ++current[u];
---
> ++current[u].first;
509c509
< if (current[u] == out_edges(u, g).second) {
---
> if (current[u].first == current[u].second) {
524c524
< ++current[u];
---
> ++current[u].first;
635c635
< std::vector< out_edge_iterator > current;
---
> std::vector< std::pair<out_edge_iterator, out_edge_iterator> > current;
--
Timothy H. Keitt
http://www.keittlab.org/