Interface MinimumEdgeCutSt

All Known Implementing Classes:
MaximumFlowAbstract, MaximumFlowAbstractWithoutResidualNet, MaximumFlowAbstractWithResidualNet, MaximumFlowDinic, MaximumFlowDinicDynamicTrees, MaximumFlowEdmondsKarp, MaximumFlowPushRelabel, MaximumFlowPushRelabelDynamicTrees, MinimumEdgeCutStAbstract
public interface MinimumEdgeCutSt
Minimum Edge-Cut algorithm with terminal vertices (source-sink, S-T).

Given a graph \(G=(V,E)\), an edge cut is a partition of \(V\) into two sets \(C, \bar{C} = V \setminus C\). Given an edge weight function, the weight of an edge-cut \((C,\bar{C})\) is the weight sum of all edges \((u,v)\) such that \(u\) is in \(C\) and \(v\) is in \(\bar{C}\). There are two variants of the problem to find a minimum weight edge-cut: (1) With terminal vertices, and (2) without terminal vertices. In the variant with terminal vertices, we are given two special vertices source (S) and sink (T) and we need to find the minimum edge-cut \((C,\bar{C})\) such that the source is in \(C\) and the sink is in \(\bar{C}\). In the variant without terminal vertices (also called 'global edge-cut') we need to find the minimal cut among all possible cuts, and \(C,\bar{C}\) simply must not be empty.

Algorithms implementing this interface compute the minimum edge-cut given two terminal vertices, source (S) and sink (T). To enumerate all minimum edge-cuts between two terminal vertices, use MinimumEdgeCutAllSt. For the global variant (without terminal vertices), see MinimumEdgeCutGlobal.

The cardinality (unweighted) minimum edge-cut between two vertices is equal to the (local) edge connectivity of these two vertices. If the graph is directed, the edge connectivity between \(u\) and \(v\) is the minimum of the minimum edge-cut between \(u\) and \(v\) and the minimum edge-cut between \(v\) and \(u\).

Use newInstance() to get a default implementation of this interface.

Author:
Barak Ugav
See Also:

  • Method Details

    • computeMinimumCut

      <V, E> VertexBiPartition<V,E> computeMinimumCut(Graph<V,E> g, WeightFunction<E> w, V source, V sink)
      Compute the minimum edge-cut in a graph between two terminal vertices.

      Given a graph \(G=(V,E)\), an edge-cut is a partition of \(V\) into twos sets \(C, \bar{C} = V \setminus C\). The return value of this function is a partition into these two sets.

      If g is an IntGraph, a IVertexBiPartition object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      w - an edge weight function
      source - a special vertex that will be in \(C\)
      sink - a special vertex that will be in \(\bar{C}\)
      Returns:
      the cut that was computed
      Throws:
      IllegalArgumentException - if the source and the sink are the same vertex

    • computeMinimumCut

      <V, E> VertexBiPartition<V,E> computeMinimumCut(Graph<V,E> g, WeightFunction<E> w, Collection<V> sources, Collection<V> sinks)
      Compute the minimum edge-cut in a graph between two sets of vertices.

      Given a graph \(G=(V,E)\), an edge-cut is a partition of \(V\) into twos sets \(C, \bar{C} = V \setminus C\). The return value of this function is a partition into these two sets.

      If g is an IntGraph, a IVertexBiPartition object will be returned. In that case, its better to pass a IWeightFunction as w, and IntCollection as sources and sinks to avoid boxing/unboxing.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      w - an edge weight function
      sources - special vertices that will be in \(C\)
      sinks - special vertices that will be in \(\bar{C}\)
      Returns:
      the minimum cut between the two sets
      Throws:
      IllegalArgumentException - if a vertex is both a source and a sink, or if a vertex appear twice in the source or sinks sets

    • newInstance

      static MinimumEdgeCutSt newInstance()
      Create a new minimum S-T edge-cut algorithm object.

      This is the recommended way to instantiate a new MinimumEdgeCutSt object.

      Returns:
      a default implementation of MinimumEdgeCutSt

    • newFromMaximumFlow

      static MinimumEdgeCutSt newFromMaximumFlow(MaximumFlow maxFlowAlg)
      Create a new minimum edge-cut algorithm using a maximum flow algorithm.

      By first computing a maximum flow between the source and the sink, the minimum edge-cut can be realized from the maximum flow without increasing the asymptotical running time of the maximum flow algorithm running time.

      Parameters:
      maxFlowAlg - a maximum flow algorithm
      Returns:
      a minimum edge-cut algorithm based on the provided maximum flow algorithm