## Class MaximumFlowAlgorithmBase<V,​E>

• ### 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
• #### 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
• #### 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.