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 EdmondsKarpMaximumFlowAlgorithm algorithm.

// We need a graph and two sets of vertices
IMutableVertexAndEdgeListGraph<TVertex, Edge<TVertex>> 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, Edge<TVertex>> 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);