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

java.lang.Object
  extended by org.jgrapht.alg.MinSourceSinkCut<V,E>

public class MinSourceSinkCut<V,E>
extends Object

Given a directed, weighted graph G(V,E). This class computes a minimum s-t cut. For this, it relies on the EdmondsKarpMaximumFlow implementation. 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

Constructor Summary
MinSourceSinkCut(DirectedGraph<V,E> graph)
           
MinSourceSinkCut(DirectedGraph<V,E> graph, double epsilon)
           
 
Method Summary
 void computeMinCut(V source, V sink)
          Compute a minimum s-t cut
 V getCurrentSink()
          Returns the sink of the last call
 V getCurrentSource()
          Returns the source of the last call
 Set<E> getCutEdges()
          Let S be the set containing the source, and T be the set containing the sink, i.e.
 double getCutWeight()
          Get the cut weight.
 Set<V> getSinkPartition()
          Returns the min cut partition containing the sink
 Set<V> getSourcePartition()
           
 
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)

MinSourceSinkCut

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

computeMinCut

public void computeMinCut(V source,
                          V sink)
Compute a minimum s-t cut

Parameters:
source -
sink -

getSourcePartition

public Set<V> getSourcePartition()
Returns:
Returns the min cut partition containing the source, or null if there was no call to computeMinCut(V source, V sink)

getSinkPartition

public Set<V> getSinkPartition()
Returns the min cut partition containing the sink

Returns:
returns the min cut partition containing the sink

getCutWeight

public double getCutWeight()
Get the cut weight. This is equal to the max s-t flow

Returns:
cut weight

getCutEdges

public Set<E> getCutEdges()
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()
Returns the source of the last call

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

getCurrentSink

public V getCurrentSink()
Returns the sink of the last call

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


Copyright © 2013. All rights reserved.