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 the CapacityScalingMinimumCostFlow.

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

Modifier and Type	Method	Description
private void	decreaseResidualCapacity(int value)	Decreases residual capacity of this arc by value units of flow.
(package private) double	getReducedCost()	Returns reduced cost of this arc.
private void	increaseResidualCapacity(int value)	Increases residual capacity of this arc by value units of flow.
boolean	isInfiniteCapacityArc()	Returns true if the arc has infinite capacity, false otherwise.
(package private) void	sendFlow(int value)	Sends value units of flow across this arc.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

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 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 Detail

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 Detail

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 java.lang.String toString()

Overrides:

toString in class java.lang.Object