Maximum Bipartite Matching - YaccConstructor/QuickGraph GitHub Wiki
The Maximum Bipartite Matching Algorithm problem arises in many real world situations.
It is currently implemented by transforming the input graph to a maximum flow graph, and then using the MaximumFlowEdmondsKarp algorithm
// we need a graph and two sets of vertices
IMutableVertexAndEdgeListGraph<TVertex,TEdge> graph = ...;
// sets a and b must be distinct, and their union must be equal to the set of all vertices in the graph
IEnumerable<TVertex> vertexSetA = ...;
IEnumerable<TVertex> vertexSetB = ...;
// These functions used to create new vertices and edges during the execution of the algorithm.
// All added objects are removed before the computation returns
VertexFactory<TVertex> vertexFactory = <some method which creates a new TVertex>;
EdgeFactory<TVertex, TEdge> edgeFactory = (source, target) => new Edge<TVertex>(source,target);
// computing the maximum bipartite match
var maxMatch = new MaximumBipartiteMatchingAlgorithm<TVertex, TEdge>(
graph, vertexSetA, vertexSetB, vertexFactory, edgeFactory);
// Use the MatchedEdges property to access the computed maximum match
ProcessResult(maxMatch.MatchedEdges);