Interface IMaximumFlowAlgorithm<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

A maximum-flow strategy for directed graphs with non-negative edge capacities. Implementations compute the maximum flow from a source to a sink together with a certifying minimum cut.

public interface IMaximumFlowAlgorithm<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 type.

Methods

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

Computes the maximum flow from source to sink.

MaximumFlowResult<TVertex, TEdge, TWeight> FindMaximumFlow(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

MaximumFlowResult<TVertex, TEdge, TWeight>

The flow value, per-edge flows, and a minimum cut.

Exceptions

ArgumentException

Either endpoint is missing, or source equals sink.

NegativeWeightException

An edge has negative capacity.

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

Computes the maximum flow, observing cancellationToken cooperatively. The default implementation forwards to the tokenless overload and therefore ignores the token — implementations should override it to honor cancellation.

MaximumFlowResult<TVertex, TEdge, TWeight> FindMaximumFlow(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

MaximumFlowResult<TVertex, TEdge, TWeight>

The flow value, per-edge flows, and a minimum cut.

Exceptions

OperationCanceledException

The token was cancelled (honored by overriding implementations).