Maximum Bipartite Matching

Maximum Bipartite Matching

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 vertexSetA = ...; IEnumerable 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 vertexFactory = ; EdgeFactory<TVertex, TEdge> edgeFactory = (source, target) => new Edge(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);

}}