Residual flow larger than capacity for boykov_kolmogorov_max_flow
I'm running the debian/ubuntu 2.37 graph-tool package (after installing a dummy package to work around issue 690). Python 3.8.6, Ubuntu 20.10 "groovy".
When I use boykov_kolmogorov_max_flow
, I get residual flow larger than capacity on some edges. I understand that shouldn't happen. Here's a snippet that reproduces the problem.
import random
from graph_tool import collection, flow
g = collection.data['pgp-strong-2009']
capacity = g.new_edge_property('float', 1)
while True:
s, t = random.sample(range(g.num_vertices()), 2)
residual = flow.boykov_kolmogorov_max_flow(g, s, t, capacity)
for n1, n2, c, r in g.iter_edges([capacity, residual]):
assert r <= c, (c, r)
The output I get is
Traceback (most recent call last):
File "test_residual.py", line 12, in <module>
assert r <= c, (c, r)
AssertionError: (1.0, 2.0)