Module org.jgrapht.core
Package org.jgrapht.generate.netgen

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
See Also:

  • Field Details

  • Method Details

    • getGraph

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

    • getSources

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

    • getSinks

      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

      Function<E,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.