Class MinCostMaximumFlow<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Minimum-cost maximum-flow via successive shortest augmenting paths with vertex potentials: Bellman-Ford establishes initial potentials (so negative edge costs are supported), then every augmentation runs Dijkstra on reduced costs. The result carries the maximum flow at the smallest possible total cost. As a special case this solves the assignment problem on unit capacities.

public sealed class MinCostMaximumFlow<TVertex, TEdge, TWeight> where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric capacity and cost type.

Inheritance

object

MinCostMaximumFlow<TVertex, TEdge, TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Constructors

MinCostMaximumFlow(Func<TEdge, TWeight>, Func<TEdge, TWeight>)

Initializes the algorithm with the functions that read an edge's capacity and cost.

public MinCostMaximumFlow(Func<TEdge, TWeight> capacitySelector, Func<TEdge, TWeight> costSelector)

Parameters

capacitySelector Func<TEdge, TWeight>

Maps an edge to its (non-negative) capacity.

costSelector Func<TEdge, TWeight>

Maps an edge to its per-unit cost; negative costs are allowed as long as no negative-cost cycle is reachable from the source.

Exceptions

ArgumentNullException

A selector is null.

Methods

FindMinimumCostMaximumFlow(IDirectedGraph<TVertex, TEdge>, TVertex, TVertex)

Computes the maximum flow from source to sink at minimum total cost.

public MinimumCostFlowResult<TVertex, TEdge, TWeight> FindMinimumCostMaximumFlow(IDirectedGraph<TVertex, TEdge> graph, TVertex source, TVertex sink)

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed flow network.

source TVertex

The vertex the flow originates from.

sink TVertex

The vertex the flow drains into.

Returns

MinimumCostFlowResult<TVertex, TEdge, TWeight>

The flow value, its total cost, and per-edge flows.

Exceptions

NegativeWeightException

An edge has negative capacity.

NegativeCycleException

A negative-cost cycle is reachable from the source.

FindMinimumCostMaximumFlow(IDirectedGraph<TVertex, TEdge>, TVertex, TVertex, CancellationToken)

Computes the maximum flow from source to sink at minimum total cost, observing cancellationToken between augmenting paths.

public MinimumCostFlowResult<TVertex, TEdge, TWeight> FindMinimumCostMaximumFlow(IDirectedGraph<TVertex, TEdge> graph, TVertex source, TVertex sink, CancellationToken cancellationToken)

Parameters

graph IDirectedGraph<TVertex, TEdge>

The directed flow network.

source TVertex

The vertex the flow originates from.

sink TVertex

The vertex the flow drains into.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

MinimumCostFlowResult<TVertex, TEdge, TWeight>

The flow value, its total cost, and per-edge flows.

Exceptions

NegativeWeightException

An edge has negative capacity.

NegativeCycleException

A negative-cost cycle is reachable from the source.

OperationCanceledException

The token was cancelled.