Class CapacityScalingMinimumCostFlow.Node

  • Enclosing class:
    CapacityScalingMinimumCostFlow<V,​E>

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

    Is used as an internal representation of the vertices of the flow network. Contains all information needed during the computation.

    Since:
    July 2018
    • Field Detail

      • nextID

        private static int nextID
        Variable for debug purposes
      • labelType

        int labelType
        The label of this node. Is used to distinguish temporarily and permanently labeled nodes during the Dijkstra's algorithm
      • excess

        int excess
        The excess of this node. If this value is positive, then this is a source node. If this value is 0, then this is a transhipment node. If this value if negative, this is a sink node.
      • potential

        double potential
        The dual variable of this node. This is used to search for an augmenting path in the residual network using the reduced costs of the arcs as arc lengths.
      • firstNonSaturated

        CapacityScalingMinimumCostFlow.Arc firstNonSaturated
        Reference of the first outgoing non-saturated arc (with positive residual capacity) incident to this node.
      • id

        private int id
        Variable for debug purposes
    • Constructor Detail

      • Node

        public Node​(int excess)
        Constructs a new node with excess
        Parameters:
        excess - the excess of this node
    • Method Detail

      • addArcTo

        CapacityScalingMinimumCostFlow.Arc addArcTo​(CapacityScalingMinimumCostFlow.Node opposite,
                                                    int capacity,
                                                    double cost)
        Adds a new arc with capacity, cost to the opposite. This method also creates a reverse arc with zero capacity and -cost.
        Parameters:
        opposite - the head of the resulting arc.
        capacity - the capacity of the resulting arc.
        cost - the cost of the resulting arc
        Returns:
        the resulting arc to the opposite node
      • toString

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