org.jgrapht.alg.flow

Class MaximumFlowAlgorithmBase<V,E>

java.lang.Object

org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MaximumFlowAlgorithm<V,E>, MinimumSTCutAlgorithm<V,E>

Direct Known Subclasses:

EdmondsKarpMFImpl, PushRelabelMFImpl

public abstract class MaximumFlowAlgorithmBase<V,E>
extends java.lang.Object
implements MaximumFlowAlgorithm<V,E>, MinimumSTCutAlgorithm<V,E>

Base class backing algorithms allowing to derive maximum-flow from the supplied flow network

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>

Field Summary

Fields

Modifier and Type	Field and Description
static double	DEFAULT_EPSILON Default tolerance.

Constructor Summary

Constructors

Constructor and Description
MaximumFlowAlgorithmBase(Graph<V,E> network, double epsilon) Construct a new maximum flow

Method Summary

Modifier and Type	Method and Description
double	calculateMinCut(V source, V sink) Computes a minimum capacity s-t cut.
V	getCurrentSink() Returns current sink vertex, or null if there was no calculateMaximumFlow calls.
V	getCurrentSource() Returns current source vertex, or null if there was no calculateMaximumFlow calls.
double	getCutCapacity() Returns the capacity of the cut obtained after the last invocation of MinimumSTCutAlgorithm.calculateMinCut(Object, Object)
java.util.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 MinimumSTCutAlgorithm.calculateMinCut(Object, Object) In case of a directed graph, only the edges with their tail in S and their head in T are returned.
V	getFlowDirection(E e) Returns the direction of the flow on an edge (u,v).
java.util.Map<E,java.lang.Double>	getFlowMap() Returns maximum flow, that was calculated during last calculateMaximumFlow call, or null, if there was no calculateMaximumFlow calls.
double	getMaximumFlowValue() Returns maximum flow value, that was calculated during last calculateMaximumFlow call.
java.util.Set<V>	getSinkPartition() Returns the sink partition T, t ∈ T, of the cut obtained after the last invocation of MinimumSTCutAlgorithm.calculateMinCut(Object, Object)
java.util.Set<V>	getSourcePartition() Returns the source partition S, s ∈ S, of the cut obtained after the last invocation of MinimumSTCutAlgorithm.calculateMinCut(Object, Object)

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

buildMaximumFlow, calculateMaximumFlow, getMaximumFlow

Field Detail

DEFAULT_EPSILON

public static final double DEFAULT_EPSILON

Default tolerance.

See Also:

Constant Field Values

Constructor Detail

MaximumFlowAlgorithmBase

public MaximumFlowAlgorithmBase(Graph<V,E> network,
                                double epsilon)

Construct a new maximum flow

Parameters:

network - the network

epsilon - the tolerance for the comparison of floating point values

Method Detail

getCurrentSource

public V getCurrentSource()

Returns current source vertex, or null if there was no calculateMaximumFlow calls.

Returns:

current source

getCurrentSink

public V getCurrentSink()

Returns current sink vertex, or null if there was no calculateMaximumFlow calls.

Returns:

current sink

getMaximumFlowValue

public double getMaximumFlowValue()

Returns maximum flow value, that was calculated during last calculateMaximumFlow call.

Specified by:

getMaximumFlowValue in interface MaximumFlowAlgorithm<V,E>

Returns:

maximum flow value

getFlowMap

public java.util.Map<E,java.lang.Double> getFlowMap()

Returns maximum flow, that was calculated during last calculateMaximumFlow call, or null, if there was no calculateMaximumFlow calls.

Specified by:

getFlowMap in interface MaximumFlowAlgorithm<V,E>

Returns:

read-only mapping from edges to doubles - flow values

getFlowDirection

public V getFlowDirection(E e)

Returns the direction of the flow on an edge (u,v). In case (u,v) is a directed edge (arc), this function will always return the edge target v. However, if (u,v) is an edge in an undirected graph, flow may go through the edge in either side. If the flow goes from u to v, we return v, otherwise u. If the flow on an edge equals 0, the returned value has no meaning.

Specified by:

getFlowDirection in interface MaximumFlowAlgorithm<V,E>

Parameters:

e - edge

Returns:

the vertex where the flow leaves the edge

calculateMinCut

public double calculateMinCut(V source,
                              V sink)

Description copied from interface: MinimumSTCutAlgorithm

Computes a minimum capacity s-t cut.

Specified by:

calculateMinCut in interface MinimumSTCutAlgorithm<V,E>

Parameters:

source - s

sink - t

Returns:

capacity of the cut

getCutCapacity

public double getCutCapacity()

Description copied from interface: MinimumSTCutAlgorithm

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

Specified by:

getCutCapacity in interface MinimumSTCutAlgorithm<V,E>

Returns:

capacity of the cut

getSourcePartition

public java.util.Set<V> getSourcePartition()

Description copied from interface: MinimumSTCutAlgorithm

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

Specified by:

getSourcePartition in interface MinimumSTCutAlgorithm<V,E>

Returns:

source partition S

getSinkPartition

public java.util.Set<V> getSinkPartition()

Description copied from interface: MinimumSTCutAlgorithm

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

Specified by:

getSinkPartition in interface MinimumSTCutAlgorithm<V,E>

Returns:

source partition T

getCutEdges

public java.util.Set<E> getCutEdges()

Description copied from interface: MinimumSTCutAlgorithm

Returns the set of edges which run from S to T, in the s-t cut obtained after the last invocation of MinimumSTCutAlgorithm.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.

Specified by:

getCutEdges in interface MinimumSTCutAlgorithm<V,E>

Returns:

set of edges which run from S to T