Package com.jgalgo.alg.connect

Class MinimumEdgeCutGlobalAbstract

java.lang.Object
com.jgalgo.alg.connect.MinimumEdgeCutGlobalAbstract
All Implemented Interfaces:
MinimumEdgeCutGlobal
Direct Known Subclasses:
MinimumEdgeCutGlobalStoerWagner
public abstract class MinimumEdgeCutGlobalAbstract extends Object implements MinimumEdgeCutGlobal
Abstract class for computing the global minimum edge cut in a graph.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:
Barak Ugav

  • Constructor Details

    • MinimumEdgeCutGlobalAbstract

      public MinimumEdgeCutGlobalAbstract()
      Default constructor.

  • Method Details

    • computeMinimumCut

      public <V, E> VertexBiPartition<V,E> computeMinimumCut(Graph<V,E> g, WeightFunction<E> w)
      Description copied from interface: MinimumEdgeCutGlobal
      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.

      Specified by:
      computeMinimumCut in interface MinimumEdgeCutGlobal
      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