Package com.jgalgo.alg.connect

Class MinimumVertexCutGlobalAbstract

java.lang.Object
com.jgalgo.alg.connect.MinimumVertexCutGlobalAbstract
All Implemented Interfaces:
MinimumVertexCutGlobal
Direct Known Subclasses:
MinimumVertexCutGlobalEsfahanianHakimi
public abstract class MinimumVertexCutGlobalAbstract extends Object implements MinimumVertexCutGlobal
Abstract class for computing the global minimum vertex 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

    • MinimumVertexCutGlobalAbstract

      public MinimumVertexCutGlobalAbstract()
      Default constructor.

  • Method Details

    • computeMinimumCut

      public <V, E> Set<V> computeMinimumCut(Graph<V,E> g, WeightFunction<V> w)
      Description copied from interface: MinimumVertexCutGlobal
      Compute the global minimum vertex-cut in a graph.

      Given a graph \(G=(V,E)\), a vertex-cut is a set of vertices whose removal disconnect graph into more than one connected components.

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

      Specified by:
      computeMinimumCut in interface MinimumVertexCutGlobal
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      w - a vertex weight function
      Returns:
      the global minimum vertex-cut