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

      The reverse counterpart of this 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

      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