Package com.jgalgo.alg

Interface MinimumEdgeCutST

public interface MinimumEdgeCutST

Minimum Edge-Cut algorithm with 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 the minimum edge-cut given two terminal vertices, source (S) and sink (T). To enumerate all minimum edge-cuts between two terminal vertices, use MinimumEdgeCutAllST. 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. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

See Also:

Wikipedia, MinimumEdgeCutGlobal, MinimumVertexCutST

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	MinimumEdgeCutST.Builder	A builder for MinimumEdgeCutST objects.

Method Summary

Modifier and Type	Method	Description
<V,E> VertexBiPartition<V,E>	computeMinimumCut(Graph<V,E> g, WeightFunction<E> w, Collection<V> sources, Collection<V> sinks)	Compute the minimum edge-cut in a graph between two sets of vertices.
<V,E> VertexBiPartition<V,E>	computeMinimumCut(Graph<V,E> g, WeightFunction<E> w, V source, V sink)	Compute the minimum edge-cut in a graph between two terminal vertices.
static MinimumEdgeCutST.Builder	newBuilder()	Create a new minimum edge-cut algorithm builder.
static MinimumEdgeCutST	newFromMaximumFlow(MaximumFlow maxFlowAlg)	Create a new minimum edge-cut algorithm using a maximum flow algorithm.
static MinimumEdgeCutST	newInstance()	Create a new minimum S-T edge-cut algorithm object.

Method Detail

computeMinimumCut

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

Compute the minimum edge-cut 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 partition into these two sets.

If g is an IntGraph, a IVertexBiPartition 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 - a graph

w - an edge weight function

source - a special vertex that will be in \(C\)

sink - a special vertex that will be in \(\bar{C}\)

Returns:

the cut that was computed

Throws:

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

computeMinimumCut

<V,E> VertexBiPartition<V,E> computeMinimumCut(Graph<V,E> g,
                                                           WeightFunction<E> w,
                                                           Collection<V> sources,
                                                           Collection<V> sinks)

Compute the minimum edge-cut in a graph between two sets of 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 partition into these two sets.

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

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

sources - special vertices that will be in \(C\)

sinks - special vertices that will be in \(\bar{C}\)

Returns:

the minimum cut between the two sets

Throws:

IllegalArgumentException - if a vertex is both a source and a sink, or if a vertex appear twice in the source or sinks sets

newInstance

static MinimumEdgeCutST newInstance()

Create a new minimum S-T edge-cut algorithm object.

This is the recommended way to instantiate a new MinimumEdgeCutST object. The MinimumEdgeCutST.Builder might support different options to obtain different implementations.

Returns:

a default implementation of MinimumEdgeCutST

newBuilder

static MinimumEdgeCutST.Builder newBuilder()

Create a new minimum edge-cut algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build MinimumEdgeCutST objects

newFromMaximumFlow

static MinimumEdgeCutST newFromMaximumFlow(MaximumFlow maxFlowAlg)

Create a new minimum edge-cut algorithm using a maximum flow algorithm.

By first computing a maximum flow between the source and the sink, the minimum edge-cut can be realized from the maximum flow without increasing the asymptotical running time of the maximum flow algorithm running time.

Parameters:

maxFlowAlg - a maximum flow algorithm

Returns:

a minimum edge-cut algorithm based on the provided maximum flow algorithm