Package com.jgalgo.alg.flow

Class MinimumCostFlowCycleCanceling

java.lang.Object

com.jgalgo.alg.flow.MinimumCostFlowAbstract

com.jgalgo.alg.flow.MinimumCostFlowAbstractBasedSourceSink

com.jgalgo.alg.flow.MinimumCostFlowCycleCanceling

All Implemented Interfaces:

MinimumCostFlow

public class MinimumCostFlowCycleCanceling
extends MinimumCostFlowAbstractBasedSourceSink

Compute the minimum-cost (max) flow in a flow network using cycle canceling.

Firstly, a maximum flow is computed using MaximumFlow. Then, the residual graph is constructed from the max flow (containing only non-saturated edges), and negative cycles (with respect to the cost function) are eliminated from it repeatedly until no negative cycles remain.

The algorithm runs in $O(CC) \cdot O(mCU)$, where $O(CC)$ is the running time of the algorithm used to find a cycle in the residual graph, $C$ is the maximum (absolute) edge cost and $U$ is the maximum edge capacity.

Based on 'A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems' by M Klein (1966).

Author:

Barak Ugav

Nested Class Summary

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

MinimumCostFlow.Builder

Constructor Summary

Constructors

Constructor	Description
MinimumCostFlowCycleCanceling()	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 Detail

MinimumCostFlowCycleCanceling

public MinimumCostFlowCycleCanceling()

Create a new minimum-cost flow algorithm object.

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