Min_st_cut not always performing cut when given boykov_kolmogorov_max_flow residuals
I'm using graph-tool 2.27 with python 3.6.8, on Debian 9. I'm finding that for certain graphs, min_st_cut does not perform a cut when given residuals that are calculated using the boykov_kolmogorov_max_flow function -- it returns 1 connected component. However, when I use push_relabel_max_flow instead, I do not run into this issue. Which is strange because I believe they should return approximately the same residuals.
Here is my code:
src, tgt = pruned_graph.vertex(8717), pruned_graph.vertex(8721)
filtered_cap = pruned_graph.edge_properties["weights"]
res_bk = graph_tool.flow.boykov_kolmogorov_max_flow(pruned_graph, src, tgt, filtered_cap)
res = graph_tool.flow.push_relabel_max_flow(pruned_graph, src, tgt, filtered_cap)
part = graph_tool.flow.min_st_cut(pruned_graph, src, filtered_cap, res)
part_bk = graph_tool.flow.min_st_cut(pruned_graph, src, filtered_cap, res_bk)
Then I can see that part_bk.a has 1 component while part.a has 2:
ipdb> np.unique(part.a)
PropertyArray([0, 1], dtype=uint8)
ipdb> np.unique(part_bk.a)
PropertyArray([1], dtype=uint8)
ipdb> np.where(part.a == 0)
(array([ 10, 11, 12, ..., 20142, 20143, 20144]),)
ipdb> np.where(part.a == 1)
(array([ 0, 1, 2, ..., 20134, 20135, 20136]),)
ipdb> np.where(part_bk.a == 0)
(array([], dtype=int64),)
ipdb> np.where(part_bk.a == 1)
(array([ 0, 1, 2, ..., 20142, 20143, 20144]),)
I've attached a file with the graph here: