Class MaximumFlowAlgorithm<TVertex, TEdge>

Base class for all maximum flow algorithms.

Inheritance
System.Object
AlgorithmBase<IMutableVertexAndEdgeListGraph<TVertex, TEdge>>
MaximumFlowAlgorithm<TVertex, TEdge>
EdmondsKarpMaximumFlowAlgorithm<TVertex, TEdge>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: QuikGraph.Algorithms.MaximumFlow
Assembly: QuikGraph.dll
Syntax
public abstract class MaximumFlowAlgorithm<TVertex, TEdge> : AlgorithmBase<IMutableVertexAndEdgeListGraph<TVertex, TEdge>>, IAlgorithm<IMutableVertexAndEdgeListGraph<TVertex, TEdge>>, IComputation, IAlgorithmComponent, IVertexColorizerAlgorithm<TVertex> where TEdge : IEdge<TVertex>
Type Parameters
Name Description
TVertex

Vertex type.
TEdge

Edge type.

Constructors

| Improve this Doc View Source

MaximumFlowAlgorithm(IAlgorithmComponent, IMutableVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>, EdgeFactory<TVertex, TEdge>)

Initializes a new instance of the MaximumFlowAlgorithm<TVertex, TEdge> class.

Declaration
protected MaximumFlowAlgorithm(IAlgorithmComponent host, IMutableVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph, Func<TEdge, double> capacities, EdgeFactory<TVertex, TEdge> edgeFactory)
Parameters
Type Name Description
IAlgorithmComponent host

Host to use if set, otherwise use this reference.
IMutableVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Func<TEdge, System.Double> capacities

Function that given an edge return the capacity of this edge.
EdgeFactory<TVertex, TEdge> edgeFactory

Edge factory method.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

capacities is null.
System.ArgumentNullException

edgeFactory is null.

Properties

| Improve this Doc View Source

Capacities

Function that given an edge return the capacity of this edge.

Declaration
public Func<TEdge, double> Capacities { get; }
Property Value
Type Description
System.Func<TEdge, System.Double>
| Improve this Doc View Source

EdgeFactory

Edge factory method.

Declaration
public EdgeFactory<TVertex, TEdge> EdgeFactory { get; }
Property Value
Type Description
EdgeFactory<TVertex, TEdge>
| Improve this Doc View Source

MaxFlow

Maximal flow value.

Declaration
public double MaxFlow { get; protected set; }
Property Value
Type Description
System.Double
| Improve this Doc View Source

Predecessors

Flow vertices predecessors.

Declaration
public Dictionary<TVertex, TEdge> Predecessors { get; }
Property Value
Type Description
System.Collections.Generic.Dictionary<TVertex, TEdge>
| Improve this Doc View Source

ResidualCapacities

Residual capacities per edge.

Declaration
public Dictionary<TEdge, double> ResidualCapacities { get; }
Property Value
Type Description
System.Collections.Generic.Dictionary<TEdge, System.Double>
| Improve this Doc View Source

ReversedEdges

Graph reversed edges.

Declaration
public IDictionary<TEdge, TEdge> ReversedEdges { get; protected set; }
Property Value
Type Description
System.Collections.Generic.IDictionary<TEdge, TEdge>
Remarks

Should be not null but may be empty.

| Improve this Doc View Source

Sink

Flow sink vertex.

Declaration
public TVertex Sink { get; set; }
Property Value
Type Description
TVertex
Remarks

Must not be null to run the algorithm.

| Improve this Doc View Source

Source

Flow source vertex.

Declaration
public TVertex Source { get; set; }
Property Value
Type Description
TVertex
Remarks

Must not be null to run the algorithm.

| Improve this Doc View Source

VerticesColors

Stores vertices associated to their colors (treatment state).

Declaration
public IDictionary<TVertex, GraphColor> VerticesColors { get; }
Property Value
Type Description
System.Collections.Generic.IDictionary<TVertex, GraphColor>

Methods

| Improve this Doc View Source

Compute(TVertex, TVertex)

Computes the maximum flow value.

Declaration
public double Compute(TVertex source, TVertex sink)
Parameters
Type Name Description
TVertex source

Flow source vertex.
TVertex sink

Flow sink vertex.
Returns
Type Description
System.Double

Maximum flow value.
Exceptions
Type Condition
System.ArgumentNullException

source is null.
System.ArgumentNullException

sink is null.
System.InvalidOperationException

Something went wrong when running the algorithm.
VertexNotFoundException

source is not part of VisitedGraph.
VertexNotFoundException

sink is not part of VisitedGraph.
| Improve this Doc View Source

GetVertexColor(TVertex)

Gets the GraphColor associated to the given vertex.

Declaration
public GraphColor GetVertexColor(TVertex vertex)
Parameters
Type Name Description
TVertex vertex

The vertex.
Returns
Type Description
GraphColor

The vertex GraphColor.
Exceptions
Type Condition
System.ArgumentNullException

vertex is null.
VertexNotFoundException

vertex has no associated color.

Implements

Extension Methods