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>
private static class CapacityScalingMinimumCostFlow.Arc extends java.lang.Object
Supporting data structure for theCapacityScalingMinimumCostFlow
.Represents a directed edge (arc) in the residual flow network. Contains all information needed during the computation.
- Since:
- July 2018
-
-
Field Summary
Fields Modifier and Type Field Description (package private) double
cost
The cost of sending one unit of flow across this arc.(package private) CapacityScalingMinimumCostFlow.Node
head
The head (target) of this arc.(package private) CapacityScalingMinimumCostFlow.Arc
next
The next arc.(package private) CapacityScalingMinimumCostFlow.Arc
prev
The previous arc.(package private) int
residualCapacity
The residual capacity of this arc.(package private) CapacityScalingMinimumCostFlow.Arc
revArc
The reverse counterpart of this arc.
-
Constructor Summary
Constructors Constructor Description Arc(CapacityScalingMinimumCostFlow.Node head, int residualCapacity, double cost)
Creates a new arc
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
decreaseResidualCapacity(int value)
Decreases residual capacity of this arc byvalue
units of flow.(package private) double
getReducedCost()
Returns reduced cost of this arc.private void
increaseResidualCapacity(int value)
Increases residual capacity of this arc byvalue
units of flow.boolean
isInfiniteCapacityArc()
Returns true if the arc has infinite capacity, false otherwise.(package private) void
sendFlow(int value)
Sendsvalue units of flow across this arc
.java.lang.String
toString()
-
-
-
Field Detail
-
head
final CapacityScalingMinimumCostFlow.Node head
The head (target) of this arc.
-
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 theCapacityScalingMinimumCostFlow.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 Detail
-
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 Detail
-
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
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-