## Interface MaximumFlowProblem<V,​E>

• Type Parameters:
V - the graph vertex type
E - 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 single-source, single-sink 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
To use this reduction, see toSingleSourceSingleSinkProblem().
Author:
Timofey Chudakov
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
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
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.