 # Boost :

From: Arun Bhalla (bhalla_at_[hidden])
Date: 2004-03-26 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