 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Known Implementing Classes:
MaximumFlowProblem.MaximumFlowProblemImpl
The singlesource, singlesink maximum flow problem is defined as follows: \[ \begin{align}
\mbox{maximize}~& \sum_{e \in \delta^+(s)}f_e  \sum_{e \in \delta^(s)}f_e &\\
\mbox{s.t. }&\sum_{e\in \delta^(v)} f_e = \sum_{e\in \delta^+(v)} f_e & \forall v\in
V\setminus \{s, t\} \\ &0 \leq f_e \leq c_e & \forall e\in E \end{align} \] Here
$\delta^+(v)$ and $\delta^(v)$ denote the outgoing and incoming edges of vertex $v$
respectively. The value $f_e$ denotes the flow on edge $e$, which is bounded by $c_e$  the
capacity of the edge $e$. The vertex $s$ is a network source, the vertex $t$  network sink. The
edge capacities can be retrieved using getCapacities()
. The problem
formulation above defines a canonical maximum flow problem, i.e. with only one source and one
sink.
A maximum flow problem can be defined on a network with multiple sources and sinks. This problem can be reduced to the above problem definition as follows:
 Two special vertices are added to the graph: a super source and a super sink;
 Edges with infinite capacity are added from the super source to every source and from every sink to the super sink
toSingleSourceSingleSinkProblem()
. Author:
 Timofey Chudakov
 See Also:

Nested Class Summary
Modifier and TypeInterfaceDescriptionstatic class
Default implementation of a Maximum Flow Problem. 
Field Summary

Method Summary
Modifier and TypeMethodDescriptiondefault void
Dumps the network edge capacities to the underlying graph.Returns the capacity function of this problem.getGraph()
Returns the network the problem is defined on.default V
getSink()
Returns one sink of this problem (a problem is guaranteed to have at least one sink).getSinks()
Returns the sink set of this problem.default V
Returns one source of this problem (a problem is guaranteed to have at least one source).Returns the source set of this problem.default boolean
Checks if this problem is in the canonical form.Converts this problem to the canonical form.

Field Details

CAPACITY_INF
static final double CAPACITY_INF See Also:


Method Details

getGraph
Returns the network the problem is defined on. Returns:
 the network the problem is defined on.

getSources
Returns the source set of this problem. Returns:
 the source set of this problem.

getSinks
Returns the sink set of this problem. Returns:
 the sink set of this problem.

getSource
Returns one source of this problem (a problem is guaranteed to have at least one source). Use this method if the problem is in canonical form (only one source and one sink). Returns:
 one source of this problem.

getSink
Returns one sink of this problem (a problem is guaranteed to have at least one sink). Use this method if the problem is in canonical form (only one source and one sink). Returns:
 one sink of this problem.

getCapacities
Returns the capacity function of this problem. This function is defined for all edges of the underlying network. Returns:
 the capacity function of this problem.

toSingleSourceSingleSinkProblem
MaximumFlowProblem<V,E> toSingleSourceSingleSinkProblem()Converts this problem to the canonical form. Resulting problem is equivalent to the previous one. Returns:
 a problem in the canonical form.

isSingleSourceSingleSinkProblem
default boolean isSingleSourceSingleSinkProblem()Checks if this problem is in the canonical form. Returns:
true
if this problem is in the canonical form,false
otherwise.

dumpCapacities
default void dumpCapacities()Dumps the network edge capacities to the underlying graph.
