org.jgrapht.alg.matching

Class MaximumWeightBipartiteMatching<V,E>

java.lang.Object

org.jgrapht.alg.matching.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

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

MatchingAlgorithm.Matching<V,E>, MatchingAlgorithm.MatchingImpl<V,E>

Field Summary

Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

DEFAULT_EPSILON

Constructor Summary

Constructors

Constructor and Description
MaximumWeightBipartiteMatching(Graph<V,E> graph, Set<V> partition1, Set<V> partition2) Constructor.
MaximumWeightBipartiteMatching(Graph<V,E> graph, Set<V> partition1, Set<V> partition2, Function<Comparator<BigDecimal>,org.jheaps.AddressableHeap<BigDecimal,V>> heapSupplier) Constructor.

Method Summary

Modifier and Type	Method and Description
MatchingAlgorithm.Matching<V,E>	getMatching() Compute a matching for a given graph.
BigDecimal	getMatchingWeight() Get the weight of the matching.
Map<V,BigDecimal>	getPotentials() Get the vertex potentials.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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,
                                      Function<Comparator<BigDecimal>,org.jheaps.AddressableHeap<BigDecimal,V>> heapSupplier)

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

getMatching

public MatchingAlgorithm.Matching<V,E> getMatching()

Compute a matching for a given graph.

Specified by:

getMatching in interface MatchingAlgorithm<V,E>

Returns:

a matching

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