org.jgrapht.alg

Class MinSourceSinkCut<V,E>

java.lang.Object

org.jgrapht.alg.MinSourceSinkCut<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

Deprecated.

Use MinimumSTCutAlgorithm instead

@Deprecated
public class MinSourceSinkCut<V,E>
extends Object

Given a weighted graph G(V,E) (directed or undirected). This class computes a minimum s-t cut. For this purpose this class relies on Edmonds' Karp Maximum Flow Algorithm. 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. Runtime: O(E) Warning: this implementation cannot be used with the PushRelabel max flow implementation!

Author:

Joris Kinable

Constructor Summary

Constructors

Constructor and Description
MinSourceSinkCut(DirectedGraph<V,E> graph) Deprecated. Create a new minimum s-t cut algorithm.
MinSourceSinkCut(DirectedGraph<V,E> graph, double epsilon) Deprecated. Create a new minimum s-t cut algorithm.
MinSourceSinkCut(DirectedGraph<V,E> graph, MaximumFlowAlgorithm<V,E> maximumFlowAlgorithm, double epsilon) Deprecated. Create a new minimum s-t cut algorithm.

Method Summary

Modifier and Type	Method and Description
void	computeMinCut(V source, V sink) Deprecated. Compute a minimum s-t cut
V	getCurrentSink() Deprecated. Returns the sink of the last call
V	getCurrentSource() Deprecated. Returns the source of the last call
Set<E>	getCutEdges() Deprecated. Let S be the set containing the source, and T be the set containing the sink, i.e.
double	getCutWeight() Deprecated. Get the cut weight.
Set<V>	getSinkPartition() Deprecated. Returns the minimum cut partition containing the sink
Set<V>	getSourcePartition() Deprecated. Get the minimum cut partition containing the source.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MinSourceSinkCut

public MinSourceSinkCut(DirectedGraph<V,E> graph)

Deprecated.

Create a new minimum s-t cut algorithm.

Parameters:

graph - the input graph

MinSourceSinkCut

public MinSourceSinkCut(DirectedGraph<V,E> graph,
                        double epsilon)

Deprecated.

Create a new minimum s-t cut algorithm.

Parameters:

graph - the input graph

epsilon - tolerance used when comparing floating point values

MinSourceSinkCut

public MinSourceSinkCut(DirectedGraph<V,E> graph,
                        MaximumFlowAlgorithm<V,E> maximumFlowAlgorithm,
                        double epsilon)

Deprecated.

Create a new minimum s-t cut algorithm.

Parameters:

graph - the input graph

maximumFlowAlgorithm - the maximum flow algorithm to use

epsilon - tolerance used when comparing floating point values

Method Detail

computeMinCut

public void computeMinCut(V source,
                          V sink)

Deprecated.

Compute a minimum s-t cut

Parameters:

source - the source

sink - the sink

getSourcePartition

public Set<V> getSourcePartition()

Deprecated.

Get the minimum cut partition containing the source.

Returns:

Returns the minimum cut partition containing the source, or null if there was no call to computeMinCut(V source, V sink)

getSinkPartition

public Set<V> getSinkPartition()

Deprecated.

Returns the minimum cut partition containing the sink

Returns:

returns the minimum cut partition containing the sink

getCutWeight

public double getCutWeight()

Deprecated.

Get the cut weight. This is equal to the max s-t flow

Returns:

cut weight

getCutEdges

public Set<E> getCutEdges()

Deprecated.

Let S be the set containing the source, and T be the set containing the sink, i.e. T=V\S. This method returns the edges which have their tail in S, and their head in T

Returns:

all edges which have their tail in S, and their head in T. If computeMinCut(V source, V sink) has not been invoked, this method returns null.

getCurrentSource

public V getCurrentSource()

Deprecated.

Returns the source of the last call

Returns:

source of last minCut call, null if there was no call

getCurrentSink

public V getCurrentSink()

Deprecated.

Returns the sink of the last call

Returns:

sink of last minCut call, null if there was no call