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.
MAX_FLOW_T() is the LEDA function for computing a
maximum flow in a directed graph. MAX_FLOW_T() is a template
function. The template parameter NT can be instantiated with
any number type.
Example of How
to Use MAX_FLOW_T()
Additionally, LEDA provides several specialized (template) functions
for maximum flow that allow to study the effect of different heuristics
and of different selection rules on the preflow push method. These functions
are mainly intended for specialists. A list of available functions can
be found on the Manual
Page of Maximum Flow.
MAX_FLOW() is the name of the preinstantiated versions
of MAX_FLOW_T(). There is one function MAX_FLOW()
for edge capacities of type int and one for double.
Example of How to
Use MAX_FLOW()
Important Notice: MAX_FLOW() only performs correctly
if all arithmetic is performed without rounding errors and without overflows.
If you are not sure about this, you should use MAX_FLOW_T()
with one of the LEDA number types. MAX_FLOW() for int
issues a warning if incorrect results are possible. MAX_FLOW()
for double computes a maximum flow for modified edge capacities
in order to avoid internal arithmetic problems. Details can be found in
the LEDA Book. Using
the following function you can do the capacity modification explicitely.
MAX_FLOW_SCALE_CAPS() modifies the edge capacities
in order to avoid internal arithmetic problems. The function returns false
if it changed some edge capacities and true otherwise.
Running Times
The running time of MAX_FLOW_T() and MAX_FLOW()
is cubic in the number of nodes of the graph (O(|V|3)).
MAX_FLOW_SCALE_CAPS() is linear in the size of the graph.
Tips
- Use
MAX_FLOW_T()to compute a maximum flow.
- If you are determined to use
MAX_FLOW()be aware of the
arithmetic problems that may arise. In case of double edge
capacities use MAX_FLOW_SCALE_CAPS() to modify the edge
capacities explicitely.
|