Package com.jgalgo.alg

Interface MinimumVertexCutAllST

public interface MinimumVertexCutAllST

Minimum Vertex-Cut algorithm that finds all minimum vertex-cuts in a graph between two terminal vertices (source-sink, S-T).

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 given two terminal vertices, source (S) and sink (T). For a single minimum vertex-cut, use MinimumVertexCutST. For the global variant (without terminal vertices), see MinimumVertexCutGlobal.

The cardinality (unweighted) minimum vertex-cut between two vertices is equal to the (local) vertex connectivity of these two vertices. If the graph is directed, the vertex connectivity between \(u\) and \(v\) is the minimum of the minimum vertex-cut between \(u\) and \(v\) and the minimum vertex-cut between \(v\) and \(u\).

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

Author:

Barak Ugav

See Also:

MinimumVertexCutST, MinimumVertexCutGlobal, MinimumEdgeCutST

Method Summary

Modifier and Type	Method	Description
default <V,E> List<Set<V>>	allMinimumCuts(Graph<V,E> g, WeightFunction<V> w, V source, V sink)	Compute all the minimum vertex-cuts in a graph between two terminal vertices.
<V,E> Iterator<Set<V>>	minimumCutsIter(Graph<V,E> g, WeightFunction<V> w, V source, V sink)	Iterate over all the minimum vertex-cuts in a graph between two terminal vertices.
static MinimumVertexCutAllST	newInstance()	Create a new minimum S-T all vertex-cuts algorithm object.

Method Detail

minimumCutsIter

<V,E> Iterator<Set<V>> minimumCutsIter(Graph<V,E> g,
                                             WeightFunction<V> w,
                                             V source,
                                             V sink)

Iterate over all the minimum vertex-cuts in a graph between two terminal vertices.

Given a graph \(G=(V,E)\), an vertex-cut is a set of vertices whose removal disconnect the source from the sink. Note that connectivity is with respect to direction from the source to the sink, and not the other way around. In undirected graphs the source and sink are interchangeable.

If the source and sink are the same vertex no vertex-cut exists and an exception will be thrown. If the source and sink and an edge exists between them, no vertex-cut exists and null will be returned.

If g is an IntGraph, an iterator of IntSet objects 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 - a vertex weight function

source - the source vertex

sink - the sink vertex

Returns:

an iterator over the sets of vertices that form the minimum vertex-cuts, or null if an edge exists between the source and the sink and therefore no vertex-cut exists

Throws:

IllegalArgumentException - if the source and the sink are the same vertex

allMinimumCuts

default <V,E> List<Set<V>> allMinimumCuts(Graph<V,E> g,
                                                WeightFunction<V> w,
                                                V source,
                                                V sink)

Compute all the minimum vertex-cuts in a graph between two terminal vertices.

Given a graph \(G=(V,E)\), an vertex-cut is a set of vertices whose removal disconnect the source from the sink. Note that connectivity is with respect to direction from the source to the sink, and not the other way around. In undirected graphs the source and sink are interchangeable.

If the source and sink are the same vertex no vertex-cut exists and an exception will be thrown. If the source and sink and an edge exists between them, no vertex-cut exists and null will be returned.

If g is an IntGraph, a list of IntSet objects 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 - a vertex weight function

source - the source vertex

sink - the sink vertex

Returns:

a list containing all the sets of vertices that form the minimum vertex-cuts, or null if an edge exists between the source and the sink and therefore no vertex-cut exists

Throws:

IllegalArgumentException - if the source and the sink are the same vertex

newInstance

static MinimumVertexCutAllST newInstance()

Create a new minimum S-T all vertex-cuts algorithm object.

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

Returns:

a default implementation of MinimumVertexCutAllST