Package com.jgalgo.alg.connect

Interface MinimumEdgeCutGlobal

All Known Implementing Classes:
MinimumEdgeCutGlobalAbstract, MinimumEdgeCutGlobalStoerWagner
public interface MinimumEdgeCutGlobal
Global Minimum Edge-Cut algorithm without terminal vertices.

Given a graph \(G=(V,E)\), an edge cut is a partition of \(V\) into two sets \(C, \bar{C} = V \setminus C\). Given a 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 global minimum edge-cut without terminal vertices.

The cardinality (unweighted) global minimum edge-cut is equal to the edge connectivity of a graph.

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)
      Compute the global minimum edge-cut in a graph.

      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
      Returns:
      the cut that was computed
      Throws:
      IllegalArgumentException - if the graph has less than two vertices

    • newInstance

      static MinimumEdgeCutGlobal newInstance()
      Create a new minimum global edge-cut algorithm object.

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

      Returns:
      a default implementation of MinimumEdgeCutGlobal