org.jgrapht.alg.interfaces

Interface MinimumSTCutAlgorithm<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Known Implementing Classes:

EdmondsKarpMFImpl, GusfieldGomoryHuCutTree, MaximumFlowAlgorithmBase, PushRelabelMFImpl

public interface MinimumSTCutAlgorithm<V,E>

Given a weighted graph G(V,E) (directed or undirected). This class computes a minimum s-t cut. A cut is a partitioning of the vertices into two disjoint sets S, T such that s ∈ S, t ∈ T, and that S ∪ T = V. The capacity of a cut is defined as the sum of the weights of the edges from S to T. In case of a directed graph, only the edges with their tail in S and their head in T are counted. In cased of a undirected graph, all edges with one endpoint in S and one endpoint in T are counted. For a given s and t, this class computes two partitions S and T such that the capacity of the cut is minimized. When each edge has equal weight, by definition this class minimizes the number of edges from S to T. Note: it is not recommended to use this class to calculate the overall minimum cut in a graph by iteratively invoking this class for all source-sink pairs. This is computationally expensive. Instead, use the StoerWagnerMinimumCut implementation.

Author:

Joris Kinable

Method Summary

Modifier and Type	Method and Description
double	calculateMinCut(V source, V sink) Computes a minimum capacity s-t cut.
double	getCutCapacity() Returns the capacity of the cut obtained after the last invocation of calculateMinCut(Object, Object)
Set<E>	getCutEdges() Returns the set of edges which run from S to T, in the s-t cut obtained after the last invocation of calculateMinCut(Object, Object) In case of a directed graph, only the edges with their tail in S and their head in T are returned.
Set<V>	getSinkPartition() Returns the sink partition T, t ∈ T, of the cut obtained after the last invocation of calculateMinCut(Object, Object)
Set<V>	getSourcePartition() Returns the source partition S, s ∈ S, of the cut obtained after the last invocation of calculateMinCut(Object, Object)

Method Detail

calculateMinCut

double calculateMinCut(V source,
                       V sink)

Computes a minimum capacity s-t cut.

Parameters:

source - s

sink - t

Returns:

capacity of the cut

getCutCapacity

double getCutCapacity()

Returns the capacity of the cut obtained after the last invocation of calculateMinCut(Object, Object)

Returns:

capacity of the cut

getSourcePartition

Set<V> getSourcePartition()

Returns the source partition S, s ∈ S, of the cut obtained after the last invocation of calculateMinCut(Object, Object)

Returns:

source partition S

getSinkPartition

Set<V> getSinkPartition()

Returns the sink partition T, t ∈ T, of the cut obtained after the last invocation of calculateMinCut(Object, Object)

Returns:

source partition T

getCutEdges

Set<E> getCutEdges()

Returns the set of edges which run from S to T, in the s-t cut obtained after the last invocation of calculateMinCut(Object, Object) In case of a directed graph, only the edges with their tail in S and their head in T are returned. In cased of a undirected graph, all edges with one endpoint in S and one endpoint in T are returned.

Returns:

set of edges which run from S to T