Module org.jgrapht.core
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:
FlowAlgorithm<V,E>, MaximumFlowAlgorithm<V,E>, MinimumSTCutAlgorithm<V,E>
Direct Known Subclasses:
BoykovKolmogorovMFImpl, 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

  • Field Details

    • DEFAULT_EPSILON

      public static final double DEFAULT_EPSILON
      Default tolerance.
      See Also:

    • network

      protected Graph<V,E> network

    • directedGraph

      protected final boolean directedGraph

    • comparator

      protected Comparator<Double> comparator

    • vertexExtensionManager

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

    • edgeExtensionManager

      protected ExtensionManager<E,? extends MaximumFlowAlgorithmBase<V,E>.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 Details

    • 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 Details

    • init

      protected <VE extends MaximumFlowAlgorithmBase<V, E>.org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.VertexExtensionBase> void init(V source, V sink, ExtensionFactory<VE> vertexExtensionFactory, ExtensionFactory<MaximumFlowAlgorithmBase<V,E>.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(MaximumFlowAlgorithmBase<V,E>.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.