Package 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

Modifier and Type	Class	Description
(package private) class	MaximumFlowAlgorithmBase.AnnotatedFlowEdge
(package private) class	MaximumFlowAlgorithmBase.VertexExtensionBase

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

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

Field Summary

Fields

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

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
private void	buildInternal()	Create internal data structure
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 java.util.Map<E,java.lang.Double>	composeFlow()	Create a map which specifies for each edge in the input map the amount of flow that flows through it
private MaximumFlowAlgorithmBase.AnnotatedFlowEdge	createBackwardEdge(MaximumFlowAlgorithmBase.AnnotatedFlowEdge forwardEdge)
private MaximumFlowAlgorithmBase.AnnotatedFlowEdge	createEdge(MaximumFlowAlgorithmBase.VertexExtensionBase source, MaximumFlowAlgorithmBase.VertexExtensionBase target, E e, double weight)
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)
protected <VE extends MaximumFlowAlgorithmBase.VertexExtensionBase> void	init(V source, V sink, ExtensionFactory<VE> vertexExtensionFactory, ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionFactory)	Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithms
protected void	pushFlowThrough(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

buildMaximumFlow, calculateMaximumFlow, getMaximumFlow

Field Detail

DEFAULT_EPSILON

public static final double DEFAULT_EPSILON

Default tolerance.

See Also:

Constant Field Values

network

protected Graph<V,E> network

directed_graph

protected final boolean directed_graph

comparator

protected java.util.Comparator<java.lang.Double> comparator

vertexExtensionManager

protected ExtensionManager<V,? extends MaximumFlowAlgorithmBase.VertexExtensionBase> vertexExtensionManager

edgeExtensionManager

protected ExtensionManager<E,? extends MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionManager

source

protected V source

sink

protected V sink

maxFlowValue

protected double maxFlowValue

maxFlow

protected java.util.Map<E,java.lang.Double> maxFlow

sourcePartition

protected java.util.Set<V> sourcePartition

sinkPartition

protected java.util.Set<V> sinkPartition

cutEdges

protected java.util.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 MaximumFlowAlgorithmBase.VertexExtensionBase> void init(V source,
                                                                              V sink,
                                                                              ExtensionFactory<VE> vertexExtensionFactory,
                                                                              ExtensionFactory<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

buildInternal

private void buildInternal()

Create internal data structure

createEdge

private MaximumFlowAlgorithmBase.AnnotatedFlowEdge createEdge(MaximumFlowAlgorithmBase.VertexExtensionBase source,
                                                              MaximumFlowAlgorithmBase.VertexExtensionBase target,
                                                              E e,
                                                              double weight)

createBackwardEdge

private MaximumFlowAlgorithmBase.AnnotatedFlowEdge createBackwardEdge(MaximumFlowAlgorithmBase.AnnotatedFlowEdge forwardEdge)

pushFlowThrough

protected void pushFlowThrough(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 f2 be the existing flow in the direction (v,u), and f1 be the desired increase of flow in direction (u,v). If f1 >= f2, then the flow on (v,u) becomes 0, and the flow on (u,v) becomes f1-f2. Else, if f1<f2, the flow in the direction (v,u) is reduced, i.e. the flow on (v,u) becomes f2-f1, 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 java.util.Map<E,java.lang.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.

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

calculateSourcePartition

protected void calculateSourcePartition()

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