Package com.jgalgo.alg

Interface MinimumEdgeCutAllST

public interface MinimumEdgeCutAllST

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

Given a graph \(G=(V,E)\), an edge cut is a partition of \(V\) into two sets \(C, \bar{C} = V \setminus C\). Given an edge weight function, the weight of an edge-cut \((C,\bar{C})\) is the weight sum of all edges \((u,v)\) such that \(u\) is in \(C\) and \(v\) is in \(\bar{C}\). There are two variants of the problem to find a minimum weight edge-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 edge-cut \((C,\bar{C})\) such that the source is in \(C\) and the sink is in \(\bar{C}\). In the variant without terminal vertices (also called 'global edge-cut') we need to find the minimal cut among all possible cuts, and \(C,\bar{C}\) simply must not be empty.

Algorithms implementing this interface compute all minimum edge-cuts given two terminal vertices, source (S) and sink (T). For a single minimum edge-cut, use MinimumEdgeCutST. For the global variant (without terminal vertices), see MinimumEdgeCutGlobal.

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

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

Author:

Barak Ugav

See Also:

Wikipedia, MinimumEdgeCutST, MinimumEdgeCutGlobal, MinimumVertexCutST

Method Summary

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

Method Detail

minimumCutsIter

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

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

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 an iterator over all the partitions to these two sets with minimum weight.

If g is an IntGraph, the returned iterator will iterate over IVertexBiPartition 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 - a graph

w - an edge weight function

source - the source vertex

sink - the sink vertex

Returns:

an iterator over all the minimum edge-cuts

Throws:

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

allMinimumCuts

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

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

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 list containing all the partitions to these two sets with minimum weight.

If g is an IntGraph, the returned list will contain IVertexBiPartition 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 - a graph

w - an edge weight function

source - the source vertex

sink - the sink vertex

Returns:

a list of all the minimum edge-cuts

Throws:

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

newInstance

static MinimumEdgeCutAllST newInstance()

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

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

Returns:

a default implementation of MinimumEdgeCutAllST