Re: [Boost-users] [BGL] Question about push_relabel_max_flow

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-03-02 14:51:41

On Feb 25, 2005, at 4:50 AM, Matthias Linkenheil wrote:

> Hello,
>
> I used the edmunds_karp_max_flow algorithm in my project and it worked 
> fine.
> Then I changed it to the push_relabel_max_flow algorithm but it 
> doesn't work.
> I get an access violation at line 562 in the push_relabel_max_flow.hpp 
> .
>
> Have anyone an idea where the problem could be?
>
> Line 558 - line 565 of push_relabel_max_flow.hpp :     // do the bottom
>    u = bos;
>    ai = out_edges(u, g).first;
>    while (excess_flow[u] > 0) {
>        if (capacity[*ai] == 0 && is_residual_edge(*ai))
>            push_flow(*ai);
>        ++ai;
>    }

That's an odd bit of code... "ai" is never checked against the end 
iterator (out_edges(u, g).second). Could you put in "assert(ai != 
out_edges(u, g).second);"  as the first line of the while loop, to see 
if that's what's happening?

        Doug