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

    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 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

      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.