Package org.jgrapht.alg.flow

Class MaximumFlowAlgorithmBase<V,​E>

    • Field Detail

      • DEFAULT_EPSILON

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

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