Package com.jgalgo.alg.connect

Interface MinimumVertexCutAllGlobal

  • All Known Implementing Classes:
    MinimumVertexCutAllGlobalAbstract, MinimumVertexCutAllGlobalKanevsky
    public interface MinimumVertexCutAllGlobal
    Minimum Vertex-Cut algorithm that finds all minimum vertex-cuts in a graph (global vertex-cut).

    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 all minimum vertex-cuts without terminal vertices. For a single minimum cut global cut, use MinimumVertexCutGlobal. For the variant with terminal vertices, see MinimumVertexCutSt or MinimumVertexCutAllSt.

    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:
    MinimumVertexCutGlobal, MinimumVertexCutAllSt, MinimumVertexCutSt

    • Method Detail

      • minimumCutsIter

        <V,​E> Iterator<Set<V>> minimumCutsIter​(Graph<V,​E> g,
                                             WeightFunction<V> w)
        Iterate over all the minimum vertex-cuts 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, the returned iterator will iterate over IntSet 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 - the graph
        w - a vertex weight function
        Returns:
        an iterator over all the minimum vertex-cuts in a graph

      • allMinimumCuts

        default <V,​E> List<Set<V>> allMinimumCuts​(Graph<V,​E> g,
                                                WeightFunction<V> w)
        Find all the minimum vertex-cuts 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, the returned list will contain IntSet 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 - the graph
        w - a vertex weight function
        Returns:
        a list of all the minimum vertex-cuts in a graph