Opened 5 years ago

#13489 new Bugs

boykov_kolmogorov_max_flow produces incorrect residual edge capacity

Reported by: Nate Bird <nate@…> Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.67.0 Severity: Problem
Keywords: Cc:

Description

Greetings,

With some graphs, the boykov_kolmogorov_max_flow algorithm creates residual edge capacity maps with larger values than the graph edge capacities should allow.

I have attached code that creates a small graph to demonstrate this issue and the GraphViz plot of the automatically-generated .dot graph file for easy visual inspection of the results.

In the attached GraphViz plot, each edge is labeled with (residual capacity)/(capacity). The residual capacity should never be greater than the capacity. Thus, the labels "1/0" and "101/100" are in error.

I have run this test in Boost 1.54, 1.66, and 1.67.

Attachments (4)

main.cpp​ (3.9 KB ) - added by Nathaniel Bird <nate@…> 5 years ago.
cpp file that demonstrates problem
CMakeLists.txt​ (362 bytes ) - added by Nathaniel Bird <nate@…> 5 years ago.
CMake file
b-k_example_graph.dot​ (352 bytes ) - added by Nathaniel Bird <nate@…> 5 years ago.
Generated output .dot file.
graph1.ps​ (10.4 KB ) - added by Nathaniel Bird <nate@…> 5 years ago.
GraphViz visualization of the .dot file.

Download all attachments as: .zip

Change History (4)

by Nathaniel Bird <nate@…>, 5 years ago

Attachment: main.cpp​ added

cpp file that demonstrates problem

by Nathaniel Bird <nate@…>, 5 years ago

Attachment: CMakeLists.txt​ added

CMake file

by Nathaniel Bird <nate@…>, 5 years ago

Attachment: b-k_example_graph.dot​ added

Generated output .dot file.

by Nathaniel Bird <nate@…>, 5 years ago

Attachment: graph1.ps​ added

GraphViz visualization of the .dot file.

Note: See TracTickets for help on using tickets.