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

        protected final boolean directed_graph
      • comparator

        protected java.util.Comparator<java.lang.Double> comparator
      • 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
    • 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

      • buildInternal

        private void buildInternal()
        Create internal data structure
      • 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 increased
        flow - 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 interface MaximumFlowAlgorithm<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 interface MaximumFlowAlgorithm<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 MaximumFlowAlgorithm<V,​E>
        Parameters:
        e - edge
        Returns:
        the vertex where the flow leaves the edge
      • 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 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.