org.jgrapht.alg.matching

## Class MaximumWeightBipartiteMatching<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
MatchingAlgorithm<V,E>

public class MaximumWeightBipartiteMatching<V,E>
extends Object
implements MatchingAlgorithm<V,E>
Maximum weight matching in bipartite graphs.

Running time is $O(n(m+n \log n))$ where n is the number of vertices and m the number of edges of the input graph. Uses exact arithmetic and produces a certificate of optimality in the form of a tight vertex potential function.

This is the algorithm and implementation described in the LEDA book. See the LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press, 1999.

Author:
Dimitrios Michail
• ### Constructor Detail

• #### MaximumWeightBipartiteMatching

public MaximumWeightBipartiteMatching(Graph<V,E> graph,
Set<V> partition1,
Set<V> partition2)
Constructor.
Parameters:
graph - the input graph
partition1 - the first partition of the vertex set
partition2 - the second partition of the vertex set
Throws:
IllegalArgumentException - if the graph is not undirected
• #### MaximumWeightBipartiteMatching

public MaximumWeightBipartiteMatching(Graph<V,E> graph,
Set<V> partition1,
Set<V> partition2,
Constructor.
Parameters:
graph - the input graph
partition1 - the first partition of the vertex set
partition2 - the second partition of the vertex set
heapSupplier - a supplier for the addressable heap to use in the algorithm.
Throws:
IllegalArgumentException - if the graph is not undirected
• ### Method Detail

• #### getPotentials

public Map<V,BigDecimal> getPotentials()
Get the vertex potentials.

This is a tight non-negative potential function which proves the optimality of the maximum weight matching. See any standard textbook about linear programming duality.

Returns:
the vertex potentials
• #### getMatchingWeight

public BigDecimal getMatchingWeight()
Get the weight of the matching.
Returns:
the weight of the matching