Class GraphMinimumCostFlowExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Convenience entry points for minimum-cost maximum-flow queries.

public static class GraphMinimumCostFlowExtensions

Inheritance

object

GraphMinimumCostFlowExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

MinimumCostMaximumFlow<TVertex, TEdge, TWeight>(IDirectedGraph<TVertex, TEdge>, TVertex, TVertex, Func<TEdge, TWeight>, Func<TEdge, TWeight>)

Computes the maximum flow from source to sink at minimum total cost, using capacitySelector and costSelector to read each edge's capacity and per-unit cost.

public static MinimumCostFlowResult<TVertex, TEdge, TWeight> MinimumCostMaximumFlow<TVertex, TEdge, TWeight>(this IDirectedGraph<TVertex, TEdge> graph, TVertex source, TVertex sink, Func<TEdge, TWeight> capacitySelector, Func<TEdge, TWeight> costSelector) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

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.

capacitySelector Func<TEdge, TWeight>

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

costSelector Func<TEdge, TWeight>

Maps an edge to its per-unit cost.

Returns

MinimumCostFlowResult<TVertex, TEdge, TWeight>

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

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric capacity and cost type.

Exceptions

NegativeWeightException

An edge has negative capacity.

NegativeCycleException

A negative-cost cycle is reachable from the source.

MinimumCostMaximumFlow<TVertex, TEdge, TWeight>(IDirectedGraph<TVertex, TEdge>, TVertex, TVertex, Func<TEdge, TWeight>, Func<TEdge, TWeight>, CancellationToken)

Computes the maximum flow at minimum total cost, observing cancellationToken between augmenting paths.

public static MinimumCostFlowResult<TVertex, TEdge, TWeight> MinimumCostMaximumFlow<TVertex, TEdge, TWeight>(this IDirectedGraph<TVertex, TEdge> graph, TVertex source, TVertex sink, Func<TEdge, TWeight> capacitySelector, Func<TEdge, TWeight> costSelector, CancellationToken cancellationToken) where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

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.

capacitySelector Func<TEdge, TWeight>

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

costSelector Func<TEdge, TWeight>

Maps an edge to its per-unit cost.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

MinimumCostFlowResult<TVertex, TEdge, TWeight>

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

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric capacity and cost type.

Exceptions

NegativeWeightException

An edge has negative capacity.

NegativeCycleException

A negative-cost cycle is reachable from the source.

OperationCanceledException

The token was cancelled.