Package com.jgalgo.alg

Interface MinimumEdgeCutGlobal

public interface MinimumEdgeCutGlobal

Global Minimum Edge-Cut algorithm without terminal vertices.

Given a graph \(G=(V,E)\), an edge cut is a partition of \(V\) into two sets \(C, \bar{C} = V \setminus C\). Given a 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 global minimum edge-cut without terminal vertices.

The cardinality (unweighted) global minimum edge-cut is equal to the edge connectivity of a graph.

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, MinimumEdgeCutST

Nested Class Summary

Nested Classes

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

Method Summary

Modifier and Type	Method	Description
<V,E> VertexBiPartition<V,E>	computeMinimumCut(Graph<V,E> g, WeightFunction<E> w)	Compute the global minimum edge-cut in a graph.
static MinimumEdgeCutGlobal.Builder	newBuilder()	Create a new global minimum edge-cut algorithm builder.
static MinimumEdgeCutGlobal	newInstance()	Create a new minimum global edge-cut algorithm object.

Method Detail

computeMinimumCut

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

Compute the global minimum edge-cut in a graph.

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

Returns:

the cut that was computed

Throws:

IllegalArgumentException - if the graph has less than two vertices

newInstance

static MinimumEdgeCutGlobal newInstance()

Create a new minimum global edge-cut algorithm object.

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

Returns:

a default implementation of MinimumEdgeCutGlobal

newBuilder

static MinimumEdgeCutGlobal.Builder newBuilder()

Create a new global minimum edge-cut algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build MinimumEdgeCutGlobal objects