Class DinicMaximumFlow<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Dinic's maximum-flow algorithm: repeated BFS level graphs, each saturated by a blocking flow found with cursor-guided depth-first walks. O(V²·E) in general and substantially faster than Edmonds-Karp on large or dense networks (O(E·√V) on unit-capacity graphs); interchangeable with it behind IMaximumFlowAlgorithm<TVertex, TEdge, TWeight>.

public sealed class DinicMaximumFlow<TVertex, TEdge, TWeight> : 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.

Inheritance

object

DinicMaximumFlow<TVertex, TEdge, TWeight>

Implements

IMaximumFlowAlgorithm<TVertex, TEdge, TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Constructors

DinicMaximumFlow(Func<TEdge, TWeight>)

Initializes the algorithm with the function that reads an edge's capacity.

public DinicMaximumFlow(Func<TEdge, TWeight> capacitySelector)

Parameters

capacitySelector Func<TEdge, TWeight>

Maps an edge to its capacity.

Exceptions

ArgumentNullException

capacitySelector is null.

Methods

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

Computes the maximum flow from source to sink.

public 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.

public 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.

Remarks

Cancellation is observed between level-graph phases.

Exceptions

OperationCanceledException

The token was cancelled (honored by overriding implementations).