Class CapacityScalingMinimumCostFlow.Arc

  • Enclosing class:
    CapacityScalingMinimumCostFlow<V,​E>

    private static class CapacityScalingMinimumCostFlow.Arc
    extends java.lang.Object
    Supporting data structure for the CapacityScalingMinimumCostFlow.

    Represents a directed edge (arc) in the residual flow network. Contains all information needed during the computation.

    Since:
    July 2018
    • Field Detail

      • cost

        final double cost
        The cost of sending one unit of flow across this arc. This value is positive for initial network arcs, negative - for the reverse residual arcs, and equals to the CapacityScalingMinimumCostFlow.COST_INF for the arcs used for the reduction.
      • prev

        CapacityScalingMinimumCostFlow.Arc prev
        The previous arc. This variable is used to maintain the presence of this arc in the linked list of arc which are either saturated or not.
      • next

        CapacityScalingMinimumCostFlow.Arc next
        The next arc. This variable is used to maintain the presence of this arc in the linked list of arc which are either saturated or not.
      • residualCapacity

        int residualCapacity
        The residual capacity of this arc. For forward arcs $(i, j)$ it equals $c_{i, j} - x_{i, j}$ where $x_{i, j}$ is the flow on this arc. For reverse arcs it equals $x_{i,j}$.
    • Constructor Detail

      • Arc

        Arc​(CapacityScalingMinimumCostFlow.Node head,
            int residualCapacity,
            double cost)
        Creates a new arc
        Parameters:
        head - the head (target) of this arc
        residualCapacity - its residual capacity
        cost - its cost
    • Method Detail

      • getReducedCost

        double getReducedCost()
        Returns reduced cost of this arc.
        Returns:
        reduced cost of this arc.
      • sendFlow

        void sendFlow​(int value)
        Sends value units of flow across this arc.
        Parameters:
        value - how many units of flow to send
      • decreaseResidualCapacity

        private void decreaseResidualCapacity​(int value)
        Decreases residual capacity of this arc by value units of flow. Moves this arc from list of non-saturated arc to the list of saturated arcs if necessary.
        Parameters:
        value - the value to subtract from the residual capacity of this arc
      • increaseResidualCapacity

        private void increaseResidualCapacity​(int value)
        Increases residual capacity of this arc by value units of flow. Moves this arc from list of saturated arc to the list of non-saturated arcs if necessary.
        Parameters:
        value - the value to add to the residual capacity of this arc
      • isInfiniteCapacityArc

        public boolean isInfiniteCapacityArc()
        Returns true if the arc has infinite capacity, false otherwise.
        Returns:
        true if the arc has infinite capacity, false otherwise.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object