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:

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

Direct Known Subclasses:

DinicMFImpl, EdmondsKarpMFImpl, PushRelabelMFImpl

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

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

Author:

Alexey Kudinkin, Joris Kinable

Nested Class Summary

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

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

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

FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>

Field Summary

Fields

Modifier and Type	Field and Description
protected Comparator<Double>	comparator
protected Set<E>	cutEdges
static double	DEFAULT_EPSILON Default tolerance.
protected boolean	directedGraph
protected ExtensionManager<E,? extends org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge>	edgeExtensionManager
protected Map<E,Double>	maxFlow
protected double	maxFlowValue
protected Graph<V,E>	network
protected V	sink
protected Set<V>	sinkPartition
protected V	source
protected Set<V>	sourcePartition
protected ExtensionManager<V,? extends org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.VertexExtensionBase>	vertexExtensionManager

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.
protected void	calculateSourcePartition() Calculate the set of reachable vertices from $s$ in the residual graph.
protected Map<E,Double>	composeFlow() Create a map which specifies for each edge in the input map the amount of flow that flows through it
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)
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)$.
Map<E,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.
Set<V>	getSinkPartition() Returns the sink partition $T$, $t \in T$, of the cut obtained after the last invocation of MinimumSTCutAlgorithm.calculateMinCut(Object, Object)
Set<V>	getSourcePartition() Returns the source partition $S$, $s \in S$, of the cut obtained after the last invocation of MinimumSTCutAlgorithm.calculateMinCut(Object, Object)
protected <VE extends org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.VertexExtensionBase> void	init(V source, V sink, ExtensionFactory<VE> vertexExtensionFactory, ExtensionFactory<org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionFactory) Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithms
protected void	pushFlowThrough(org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge edge, double flow) Increase flow in the direction denoted by edge $(u,v)$.

Methods inherited from class java.lang.Object

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

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

getMaximumFlow, getMaximumFlowValue

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

getFlow

Field Detail

DEFAULT_EPSILON

public static final double DEFAULT_EPSILON

Default tolerance.

See Also:

Constant Field Values

network

protected Graph<V,E> network

directedGraph

protected final boolean directedGraph

comparator

protected Comparator<Double> comparator

vertexExtensionManager

protected ExtensionManager<V,? extends org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.VertexExtensionBase> vertexExtensionManager

edgeExtensionManager

protected ExtensionManager<E,? extends org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionManager

source

protected V source

sink

protected V sink

maxFlowValue

protected double maxFlowValue

maxFlow

protected Map<E,Double> maxFlow

sourcePartition

protected Set<V> sourcePartition

sinkPartition

protected Set<V> sinkPartition

cutEdges

protected Set<E> cutEdges

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

init

protected <VE extends org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.VertexExtensionBase> void init(V source,
                                                                                                   V sink,
                                                                                                   ExtensionFactory<VE> vertexExtensionFactory,
                                                                                                   ExtensionFactory<org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionFactory)

Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithms

Type Parameters:

VE - vertex extension type

Parameters:

source - source

sink - sink

vertexExtensionFactory - vertex extension factory

edgeExtensionFactory - edge extension factory

pushFlowThrough

protected void pushFlowThrough(org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge edge,
                               double flow)

Increase flow in the direction denoted by edge $(u,v)$. Any existing flow in the reverse direction $(v,u)$ gets reduced first. More precisely, let $f_2$ be the existing flow in the direction $(v,u)$, and $f_1$ be the desired increase of flow in direction $(u,v)$. If $f_1 \geq f_2$, then the flow on $(v,u)$ becomes $0$, and the flow on $(u,v)$ becomes $f_1-f_2$. Else, if $f_1 \textlptr f_2$, the flow in the direction $(v, u)$ is reduced, i.e. the flow on $(v, u)$ becomes $f_2 - f_1$, whereas the flow on $(u,v)$ remains zero.

Parameters:

edge - desired direction in which the flow is increased

flow - increase of flow in the the direction indicated by the forwardEdge

composeFlow

protected Map<E,Double> composeFlow()

Create a map which specifies for each edge in the input map the amount of flow that flows through it

Returns:

a map which specifies for each edge in the input map the amount of flow that flows through it

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.

Returns:

maximum flow value

getFlowMap

public Map<E,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 FlowAlgorithm<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 FlowAlgorithm<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 Set<V> getSourcePartition()

Description copied from interface: MinimumSTCutAlgorithm

Returns the source partition $S$, $s \in 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 Set<V> getSinkPartition()

Description copied from interface: MinimumSTCutAlgorithm

Returns the sink partition $T$, $t \in 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 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$

calculateSourcePartition

protected void calculateSourcePartition()

Calculate the set of reachable vertices from $s$ in the residual graph.