Re: [boost] boost/graph/push_relabel_max_flow::is_flow() bug?

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-04-04 09:09:00

Hi Arun,

Thanks for the bug report. I agree with your assessment of the problem.
I've checked in your fix.

Cheers,
Jeremy

On Mar 26, 2004, at 2:37 PM, Arun Bhalla wrote:
> Hi,
>
> I'm not really a user of Boost, but I've been referring to the Boost 
> Graph
> Library code for another project.  In particular, I've been looking
> at push_relabel_max_flow.hpp.
>
> I was writing a unit test which followed the same ideas of the 
> is_flow()
> test, and it was failing on what should be a flow network with a valid
> maximum flow.
>
> The code in question:
>             // a is an edge_descriptor
>             if (capacity[a] > 0)
>               if ((residual_capacity[a] + 
> residual_capacity[reverse_edge[a]]
>                    != capacity[a])
>                   || (residual_capacity[a] < 0)
>                   || (residual_capacity[reverse_edge[a]] < 0))
>               return false;
>
> I contend the test should actually be:
>             // a is an edge_descriptor
>             if (capacity[a] > 0)
>               if ((residual_capacity[a] + 
> residual_capacity[reverse_edge[a]]
> !                   != capacity[a] + capacity[reverse_edge[a]])
>                   || (residual_capacity[a] < 0)
>                   || (residual_capacity[reverse_edge[a]] < 0))
>               return false;
>
>
> I refer to an example network in CLR (1st ed.), p.589.
> There are several vertices, but I focus on vertices v1 and v2.
> In this graph, we have capacities
>   c(v1,v2) = 10
>   c(v2,v1) = 4
> and residual capacities
>   cf(v1,v2) = 11
>   cf(v2,v1) = 3
>
> With the above (original) test, it would fail because 11 + 3 (the sum 
> of
> residual capacities) != the capacity of either edge.  This would hold
> true if the sum of residual capacities were compared with the sum of
> capacities.  Ordinarily this test would work if reverse_edge[a] has
> a capacity of 0, which would be the case if the edge (a) is in the flow
> network, but its reverse is not.
>
> I'm not a graph theory expert, though, so I defer to anyone who is. :)
>
> Thanks,
> Arun
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
Graduating in August 2004 and looking for work
C++ Booster (http://www.boost.org)
_______________________________________________