Package com.jgalgo.alg.connect

Interface MinimumEdgeCutAllSt

All Known Implementing Classes:
MinimumEdgeCutAllStAbstract, MinimumEdgeCutAllStPicardQueyranne
public interface MinimumEdgeCutAllSt
Minimum Edge-Cut algorithm that finds all minimum edge-cuts in a graph between two 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 all minimum edge-cuts given two terminal vertices, source (S) and sink (T). For a single minimum edge-cut, use MinimumEdgeCutSt. 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

    • minimumCutsIter

      <V, E> Iterator<VertexBiPartition<V,E>> minimumCutsIter(Graph<V,E> g, WeightFunction<E> w, V source, V sink)
      Iterate over all the minimum edge-cuts 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 an iterator over all the partitions to these two sets with minimum weight.

      If g is an IntGraph, the returned iterator will iterate over IVertexBiPartition objects. 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 - the source vertex
      sink - the sink vertex
      Returns:
      an iterator over all the minimum edge-cuts
      Throws:
      IllegalArgumentException - if the source and the sink are the same vertex

    • allMinimumCuts

      default <V, E> List<VertexBiPartition<V,E>> allMinimumCuts(Graph<V,E> g, WeightFunction<E> w, V source, V sink)
      Compute all the minimum edge-cuts 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 list containing all the partitions to these two sets with minimum weight.

      If g is an IntGraph, the returned list will contain IVertexBiPartition objects. 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 - the source vertex
      sink - the sink vertex
      Returns:
      a list of all the minimum edge-cuts
      Throws:
      IllegalArgumentException - if the source and the sink are the same vertex

    • newInstance

      static MinimumEdgeCutAllSt newInstance()
      Create a new minimum S-T all edge-cuts algorithm object.

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

      Returns:
      a default implementation of MinimumEdgeCutAllSt