Package com.jgalgo

Interface MinimumCutST

public interface MinimumCutST

Minimum Cut algorithm with terminal vertices (source-sink, S-T).

Given a graph \(G=(V,E)\), a cut is a partition of \(V\) into two sets \(C, \bar{C} = V \setminus C\). Given a weight function, the weight of a 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 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 cut \((C,\bar{C})\) such that the source is in \(C\) and the sink is in \(\bar{C}\). In the variant without terminal vertices we need to find the global cut, and \(C,\bar{C}\) simply must not be empty.

Algorithms implementing this interface compute the minimum cut given two terminal vertices, source (S) and sink (T).

Author:

Barak Ugav

See Also:

Wikipedia

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
Cut	computeMinimumCut(Graph g, WeightFunction w, int source, int sink)	Compute the minimum cut in a graph between two terminal vertices.
Cut	computeMinimumCut(Graph g, WeightFunction w, IntCollection sources, IntCollection sinks)	Compute the minimum cut in a graph between two sets of vertices.
static MinimumCutST.Builder	newBuilder()	Create a new minimum cut algorithm builder.
static MinimumCutST	newFromMaximumFlow(MaximumFlow maxFlowAlg)	Create a new minimum cut algorithm using a maximum flow algorithm.

Method Detail

computeMinimumCut

Cut computeMinimumCut(Graph g,
                      WeightFunction w,
                      int source,
                      int sink)

Compute the minimum cut in a graph between two terminal vertices.

Given a graph \(G=(V,E)\), a cut is a partition of \(V\) into twos sets \(C, \bar{C} = V \setminus C\). The return value of this function is the set \(C\), and \(\bar{C}\) can be computed easily by the caller if needed.

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

Cut computeMinimumCut(Graph g,
                      WeightFunction w,
                      IntCollection sources,
                      IntCollection sinks)

Compute the minimum cut in a graph between two sets of vertices.

Given a graph \(G=(V,E)\), a cut is a partition of \(V\) into twos sets \(C, \bar{C} = V \setminus C\). The return value of this function is the set \(C\), and \(\bar{C}\) can be computed easily by the caller if needed.

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

newBuilder

static MinimumCutST.Builder newBuilder()

Create a new minimum cut algorithm builder.

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

Returns:

a new builder that can build MinimumCutST objects

newFromMaximumFlow

static MinimumCutST newFromMaximumFlow(MaximumFlow maxFlowAlg)

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

By first computing a maximum flow between the source and the sink, the minimum 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 cut algorithm based on the provided maximum flow algorithm