Package com.jgalgo.alg.flow

Class MinimumCostFlowCostScaling

java.lang.Object

com.jgalgo.alg.flow.MinimumCostFlowAbstract

com.jgalgo.alg.flow.MinimumCostFlowAbstractBasedSupply

com.jgalgo.alg.flow.MinimumCostFlowCostScaling

All Implemented Interfaces:

MinimumCostFlow

public class MinimumCostFlowCostScaling
extends MinimumCostFlowAbstractBasedSupply

Minimum-cost flow computation using the cost-scaling algorithm with partial-augmentations push-relabel variant.

The algorithm runs in $O(n^2 m \log (n C))$ where $C$ is the maximum (absolute) edge cost.

Based on 'Efficient implementations of minimum-cost flow algorithms' by Z. Kiraly, P. Kovacs (2012).

Author:

Barak Ugav

See Also:

• MaximumFlowPushRelabel

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.flow.MinimumCostFlow

MinimumCostFlow.Builder

Constructor Summary

Constructors

Constructor	Description
MinimumCostFlowCostScaling()	Create a new minimum-cost flow algorithm object.

Method Summary

Methods inherited from class com.jgalgo.alg.flow.MinimumCostFlowAbstract

computeMinCostFlow, computeMinCostFlow, computeMinCostMaxFlow, computeMinCostMaxFlow, computeMinCostMaxFlow, computeMinCostMaxFlow

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MinimumCostFlowCostScaling

public MinimumCostFlowCostScaling()

Create a new minimum-cost flow algorithm object.

Please prefer using MinimumCostFlow.newInstance() to get a default implementation for the MinimumCostFlow interface.