Checking the Result of Maximum Flow Algorithms
Let G be a directed graph, s and t
nodes of G, and cap a non-negative capacity
function on the edges of G. A flow from s
to t must satisfy the capacity constraints, i.e., the flow
over an edge must not exceed its capacity, and the flow conservation constraints,
i.e., the flow out of s must be the same as the flow into
t. In a maximum flow the flow out of s is maximum
among all flows from s to t.
CHECK_MAX_FLOW_T() checks the result of a maximum
flow compuation. CHECK_MAX_FLOW_T() is a template function.
The template parameter NT is determined by the number
type used for the maximum flow computation.
Example of How
to Use CHECK_MAX_FLOW_T()
CHECK_MAX_FLOW() is the name of the preinstantiated
versions of CHECK_MAX_FLOW_T(). There is one function CHECK_MAX_FLOW()
for edge capacities of type int and one for double.
Example of How to
Use CHECK_MAX_FLOW()
Running Times
The running time of CHECK_MAX_FLOW_T() and CHECK_MAX_FLOW()
is linear in the size of the graph.
Tips
Checking the result is much easier than computing a maximum flow. Therefore,
the checking functions are less complicated and less error prone. Moreover,
checking is only linear in the size of the graph. So the overhead is quite
small. Use CHECK_MAX_FLOW_T() or CHECK_MAX_FLOW()
to ensure the correctness of your result.
|