Package com.jgalgo.alg.connect

Interface MinimumVertexCutGlobal

All Known Implementing Classes:
MinimumVertexCutGlobalAbstract, MinimumVertexCutGlobalEsfahanianHakimi
public interface MinimumVertexCutGlobal
Minimum Vertex-Cut algorithm without terminal vertices.

Given a graph \(G=(V,E)\), a vertex cut (or separating set) is a set of vertices \(C\) whose removal transforms \(G\) into a disconnected graph. In case the graph is a clique of size \(k\), any vertex set of size \(k-1\) is considered by convention a vertex cut of the graph. Given a vertex weight function, the weight of a vertex-cut \(C\) is the weight sum of all vertices in \(C\). There are two variants of the problem to find a minimum weight vertex-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 vertex-cut \(C\) such that such that the source and the sink are not in the same connected components after the removal of the vertices of \(C\). In the variant without terminal vertices (also called 'global vertex-cut') we need to find the minimal cut among all possible cuts, and the removal of the vertices of \(C\) should simply disconnect the graph (or make it trivial, containing a single vertex).

Algorithms implementing this interface compute the global minimum vertex-cut without terminal vertices.

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

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

Author:
Barak Ugav
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    <V, E> Set<V>
    computeMinimumCut(Graph<V,E> g, WeightFunction<V> w)
    Compute the global minimum vertex-cut in a graph.
    static <V, E> boolean
    isCut(Graph<V,E> g, Collection<V> cut)
    Check whether the given vertices form a vertex cut in the graph.
    static MinimumVertexCutGlobal
    newInstance()
    Create a new minimum global vertex-cut algorithm object.

  • Method Details

    • computeMinimumCut

      <V, E> Set<V> computeMinimumCut(Graph<V,E> g, WeightFunction<V> w)
      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.

      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

    • newInstance

      static MinimumVertexCutGlobal newInstance()
      Create a new minimum global vertex-cut algorithm object.

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

      Returns:
      a default implementation of MinimumVertexCutGlobal

    • isCut

      static <V, E> boolean isCut(Graph<V,E> g, Collection<V> cut)
      Check whether the given vertices form a vertex cut in the graph.

      The method removes the given set of vertices, and than checks if the graph is (strongly) connected or not. If the graph was not connected in the first place, this may yield confusing results. The set of all vertices of the graph is not considered a vertex cut. The empty set is considered a vertex cut if the graph is not (strongly) connected in the first place. The set that contains all vertices except one is considered a vertex cut.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      cut - a set of vertices
      Returns:
      true if cut is a vertex cut in g
      Throws:
      IllegalArgumentException - if cut contains duplicate vertices