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)