Class EdmondsKarpMaximumFlow<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

The Edmonds-Karp maximum-flow algorithm: Ford-Fulkerson with breadth-first augmenting paths, giving O(V·E²) independently of capacity values. With floating-point capacities, tiny rounding residues are possible — integer or decimal capacities are exact. For large or dense networks consider DinicMaximumFlow<TVertex, TEdge, TWeight>.

public sealed class EdmondsKarpMaximumFlow<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

EdmondsKarpMaximumFlow<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

EdmondsKarpMaximumFlow(Func<TEdge, TWeight>)

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

public EdmondsKarpMaximumFlow(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 augmenting paths.

Exceptions

OperationCanceledException

The token was cancelled (honored by overriding implementations).