[Boost-users] Patch for push_relabel_max_flow

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/