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 typeE
- 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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
buildInternal()
Create internal data structuredouble
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 itprivate 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 ofMinimumSTCutAlgorithm.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 ofMinimumSTCutAlgorithm.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 ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
java.util.Set<V>
getSourcePartition()
Returns the source partition S, s ∈ S, of the cut obtained after the last invocation ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
protected <VE extends MaximumFlowAlgorithmBase.VertexExtensionBase>
voidinit(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 algorithmsprotected 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
-
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
-
-
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
- sourcesink
- sinkvertexExtensionFactory
- vertex extension factoryedgeExtensionFactory
- 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 increasedflow
- 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 interfaceMaximumFlowAlgorithm<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 interfaceMaximumFlowAlgorithm<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 interfaceMaximumFlowAlgorithm<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 interfaceMinimumSTCutAlgorithm<V,E>
- Parameters:
source
- ssink
- 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 ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
- Specified by:
getCutCapacity
in interfaceMinimumSTCutAlgorithm<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 ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
- Specified by:
getSourcePartition
in interfaceMinimumSTCutAlgorithm<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 ofMinimumSTCutAlgorithm.calculateMinCut(Object, Object)
- Specified by:
getSinkPartition
in interfaceMinimumSTCutAlgorithm<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 ofMinimumSTCutAlgorithm.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 interfaceMinimumSTCutAlgorithm<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.
-
-