
Boost : 
From: Arun Bhalla (bhalla_at_[hidden])
Date: 20040326 14:37:59
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk