Class 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 classes/interfaces inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm

FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>
• 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 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 Description
MaximumFlowAlgorithmBase​(Graph<V,​E> network, double epsilon)
Construct a new maximum flow
• Method Summary

All Methods
Modifier and Type Method 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.FlowAlgorithm

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

getMaximumFlow, getMaximumFlowValue
• Field Detail

• DEFAULT_EPSILON

public static final double DEFAULT_EPSILON
Default tolerance.
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.