
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Known Implementing Classes:
MaximumFlowProblem.MaximumFlowProblemImpl
public interface MaximumFlowProblem<V,E>
This class represents a maximum flow problem. Use this class for both directed and undirected maximum flow problems.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:
MaximumFlowAlgorithm


Nested Class Summary
Nested Classes Modifier and Type Interface Description static class
MaximumFlowProblem.MaximumFlowProblemImpl<V,E>
Default implementation of a Maximum Flow Problem.

Field Summary
Fields Modifier and Type Field Description static double
CAPACITY_INF

Method Summary
All Methods Instance Methods Abstract Methods Default Methods Modifier and Type Method Description default void
dumpCapacities()
Dumps the network edge capacities to the underlying graph.java.util.function.Function<E,java.lang.Double>
getCapacities()
Returns the capacity function of this problem.Graph<V,E>
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).java.util.Set<V>
getSinks()
Returns the sink set of this problem.default V
getSource()
Returns one source of this problem (a problem is guaranteed to have at least one source).java.util.Set<V>
getSources()
Returns the source set of this problem.default boolean
isSingleSourceSingleSinkProblem()
Checks if this problem is in the canonical form.MaximumFlowProblem<V,E>
toSingleSourceSingleSinkProblem()
Converts this problem to the canonical form.



Field Detail

CAPACITY_INF
static final double CAPACITY_INF
 See Also:
 Constant Field Values


Method Detail

getGraph
Graph<V,E> getGraph()
Returns the network the problem is defined on. Returns:
 the network the problem is defined on.

getSources
java.util.Set<V> getSources()
Returns the source set of this problem. Returns:
 the source set of this problem.

getSinks
java.util.Set<V> getSinks()
Returns the sink set of this problem. Returns:
 the sink set of this problem.

getSource
default V 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
default V 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
java.util.function.Function<E,java.lang.Double> 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.

