Class GraphMaximumFlowExtensions

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Convenience entry points for maximum-flow queries, defaulting to Edmonds-Karp.

public static class GraphMaximumFlowExtensions

Inheritance

object

GraphMaximumFlowExtensions

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Methods

MaximumFlow<TVertex, TWeight>(IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>, TVertex, TVertex)

Computes the maximum flow from source to sink using Edmonds-Karp and the capacities carried by the graph's WeightedEdge<TVertex, TWeight> edges.

public static MaximumFlowResult<TVertex, WeightedEdge<TVertex, TWeight>, TWeight> MaximumFlow<TVertex, TWeight>(this IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>> graph, TVertex source, TVertex sink) where TVertex : notnull where TWeight : INumber<TWeight>

Parameters

graph IDirectedGraph<TVertex, WeightedEdge<TVertex, TWeight>>

The directed flow network.

source TVertex

The vertex the flow originates from.

sink TVertex

The vertex the flow drains into.

Returns

MaximumFlowResult<TVertex, WeightedEdge<TVertex, TWeight>, TWeight>

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

Type Parameters

TVertex

The vertex type.

TWeight

The numeric capacity type.

Exceptions

NegativeWeightException

An edge has negative capacity.

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

Computes the maximum flow from source to sink using Edmonds-Karp and capacitySelector to read edge capacities.

public static MaximumFlowResult<TVertex, TEdge, TWeight> MaximumFlow<TVertex, TEdge, TWeight>(this IDirectedGraph<TVertex, TEdge> graph, TVertex source, TVertex sink, Func<TEdge, TWeight> capacitySelector) 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 capacity.

Returns

MaximumFlowResult<TVertex, TEdge, TWeight>

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

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric capacity type.

Exceptions

NegativeWeightException

An edge has negative capacity.

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

Computes the maximum flow using Edmonds-Karp, observing cancellationToken between augmenting paths.

public static MaximumFlowResult<TVertex, TEdge, TWeight> MaximumFlow<TVertex, TEdge, TWeight>(this IDirectedGraph<TVertex, TEdge> graph, TVertex source, TVertex sink, Func<TEdge, TWeight> capacitySelector, 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 capacity.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

MaximumFlowResult<TVertex, TEdge, TWeight>

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

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric capacity type.

Exceptions

NegativeWeightException

An edge has negative capacity.

OperationCanceledException

The token was cancelled.