[Boost-users] boost/graph/push_relabel_max_flow::is_flow() bug?

From: Arun Bhalla (bhalla_at_[hidden])
Date: 2004-03-26 21:32:34

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