Module org.jgrapht.core
Package org.jgrapht.alg.flow.mincost
Class CapacityScalingMinimumCostFlow.Arc
java.lang.Object
org.jgrapht.alg.flow.mincost.CapacityScalingMinimumCostFlow.Arc
- Enclosing class:
CapacityScalingMinimumCostFlow<V,
E>
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 Summary
FieldsModifier and TypeFieldDescription(package private) final double
The cost of sending one unit of flow across this arc.(package private) final CapacityScalingMinimumCostFlow.Node
The head (target) of this arc.(package private) CapacityScalingMinimumCostFlow.Arc
The next arc.(package private) CapacityScalingMinimumCostFlow.Arc
The previous arc.(package private) int
The residual capacity of this arc.(package private) CapacityScalingMinimumCostFlow.Arc
The reverse counterpart of this arc. -
Constructor Summary
ConstructorsConstructorDescriptionArc
(CapacityScalingMinimumCostFlow.Node head, int residualCapacity, double cost) Creates a new arc -
Method Summary
Modifier and TypeMethodDescriptionprivate void
decreaseResidualCapacity
(int value) Decreases residual capacity of this arc byvalue
units of flow.(package private) double
Returns reduced cost of this arc.private void
increaseResidualCapacity
(int value) Increases residual capacity of this arc byvalue
units of flow.boolean
Returns true if the arc has infinite capacity, false otherwise.(package private) void
sendFlow
(int value) Sendsvalue units of flow across this arc
.toString()
-
Field Details
-
head
The head (target) of this arc. -
cost
final double costThe 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 theCapacityScalingMinimumCostFlow.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 residualCapacityThe 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 arcresidualCapacity
- its residual capacitycost
- its cost
-
-
Method Details
-
getReducedCost
double getReducedCost()Returns reduced cost of this arc.- Returns:
- reduced cost of this arc.
-
sendFlow
void sendFlow(int value) Sendsvalue 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 byvalue
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 byvalue
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
-