Class MaximumBipartiteMatchingAlgorithm<TVertex, TEdge>

Algorithm that computes a maximum bipartite matching in a graph, meaning the maximum number of edges not sharing any vertex.

Inheritance
System.Object
AlgorithmBase<IMutableVertexAndEdgeListGraph<TVertex, TEdge>>
MaximumBipartiteMatchingAlgorithm<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
Assembly: QuikGraph.dll
Syntax
public sealed class MaximumBipartiteMatchingAlgorithm<TVertex, TEdge> : AlgorithmBase<IMutableVertexAndEdgeListGraph<TVertex, TEdge>>, IAlgorithm<IMutableVertexAndEdgeListGraph<TVertex, TEdge>>, IComputation, IAlgorithmComponent where TEdge : IEdge<TVertex>
Type Parameters
Name Description
TVertex

Vertex type.
TEdge

Edge type.

Constructors

| Improve this Doc View Source

MaximumBipartiteMatchingAlgorithm(IMutableVertexAndEdgeListGraph<TVertex, TEdge>, IEnumerable<TVertex>, IEnumerable<TVertex>, VertexFactory<TVertex>, EdgeFactory<TVertex, TEdge>)

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

Declaration
public MaximumBipartiteMatchingAlgorithm(IMutableVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph, IEnumerable<TVertex> sourceToVertices, IEnumerable<TVertex> verticesToSink, VertexFactory<TVertex> vertexFactory, EdgeFactory<TVertex, TEdge> edgeFactory)
Parameters
Type Name Description
IMutableVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Collections.Generic.IEnumerable<TVertex> sourceToVertices

Vertices to which creating augmented edge from super source.
System.Collections.Generic.IEnumerable<TVertex> verticesToSink

Vertices from which creating augmented edge to super sink.
VertexFactory<TVertex> vertexFactory

Vertex factory method.
EdgeFactory<TVertex, TEdge> edgeFactory

Edge factory method.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

sourceToVertices is null.
System.ArgumentNullException

verticesToSink is null.
System.ArgumentNullException

vertexFactory is null.
System.ArgumentNullException

edgeFactory is null.

Properties

| 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

MatchedEdges

Maximal edges matching.

Declaration
public TEdge[] MatchedEdges { get; }
Property Value
Type Description
TEdge[]
| Improve this Doc View Source

SourceToVertices

Vertices to which augmented edge from super source are created with augmentation.

Declaration
public IEnumerable<TVertex> SourceToVertices { get; }
Property Value
Type Description
System.Collections.Generic.IEnumerable<TVertex>
| Improve this Doc View Source

VertexFactory

Vertex factory method.

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

VerticesToSink

Vertices from which augmented edge to super sink are created with augmentation.

Declaration
public IEnumerable<TVertex> VerticesToSink { get; }
Property Value
Type Description
System.Collections.Generic.IEnumerable<TVertex>

Methods

| Improve this Doc View Source

Initialize()

Called on algorithm initialization step.

Declaration
protected override void Initialize()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IMutableVertexAndEdgeListGraph<TVertex, TEdge>>.Initialize()
| Improve this Doc View Source

InternalCompute()

Algorithm compute step.

Declaration
protected override void InternalCompute()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IMutableVertexAndEdgeListGraph<TVertex, TEdge>>.InternalCompute()

Implements

Extension Methods