Package org.jgrapht.alg.matching
Class MaximumWeightBipartiteMatching<V,E>
- java.lang.Object
-
- org.jgrapht.alg.matching.MaximumWeightBipartiteMatching<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
public class MaximumWeightBipartiteMatching<V,E> extends java.lang.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 Description MaximumWeightBipartiteMatching(Graph<V,E> graph, java.util.Set<V> partition1, java.util.Set<V> partition2)
Constructor.MaximumWeightBipartiteMatching(Graph<V,E> graph, java.util.Set<V> partition1, java.util.Set<V> partition2, java.util.function.Function<java.util.Comparator<java.math.BigDecimal>,org.jheaps.AddressableHeap<java.math.BigDecimal,V>> heapSupplier)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description MatchingAlgorithm.Matching<V,E>
getMatching()
Compute a matching for a given graph.java.math.BigDecimal
getMatchingWeight()
Get the weight of the matching.java.util.Map<V,java.math.BigDecimal>
getPotentials()
Get the vertex potentials.
-
-
-
Constructor Detail
-
MaximumWeightBipartiteMatching
public MaximumWeightBipartiteMatching(Graph<V,E> graph, java.util.Set<V> partition1, java.util.Set<V> partition2)
Constructor.- Parameters:
graph
- the input graphpartition1
- the first partition of the vertex setpartition2
- the second partition of the vertex set- Throws:
java.lang.IllegalArgumentException
- if the graph is not undirected
-
MaximumWeightBipartiteMatching
public MaximumWeightBipartiteMatching(Graph<V,E> graph, java.util.Set<V> partition1, java.util.Set<V> partition2, java.util.function.Function<java.util.Comparator<java.math.BigDecimal>,org.jheaps.AddressableHeap<java.math.BigDecimal,V>> heapSupplier)
Constructor.- Parameters:
graph
- the input graphpartition1
- the first partition of the vertex setpartition2
- the second partition of the vertex setheapSupplier
- a supplier for the addressable heap to use in the algorithm.- Throws:
java.lang.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 interfaceMatchingAlgorithm<V,E>
- Returns:
- a matching
-
getPotentials
public java.util.Map<V,java.math.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 java.math.BigDecimal getMatchingWeight()
Get the weight of the matching.- Returns:
- the weight of the matching
-
-