Class CapacityScalingMinimumCostFlow.Arc

java.lang.Object
org.jgrapht.alg.flow.mincost.CapacityScalingMinimumCostFlow.Arc
Enclosing class:
CapacityScalingMinimumCostFlow<V,E>
private static class CapacityScalingMinimumCostFlow.Arc extends 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 Details

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

    • revArc

      CapacityScalingMinimumCostFlow.Arc revArc
      The reverse counterpart of this arc.

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

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

    • 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 String toString()
      Overrides:
      toString in class Object