- 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.
-
-
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 Modifier and Type Field Description private java.util.Comparator<java.math.BigDecimal>
comparator
private java.util.Map<V,java.math.BigDecimal>
dist
private Graph<V,E>
graph
private org.jheaps.AddressableHeap<java.math.BigDecimal,V>
heap
private java.util.function.Function<java.util.Comparator<java.math.BigDecimal>,org.jheaps.AddressableHeap<java.math.BigDecimal,V>>
heapSupplier
private java.util.Map<V,E>
matchedEdge
private java.util.Set<E>
matching
private java.math.BigDecimal
matchingWeight
private java.util.Map<V,org.jheaps.AddressableHeap.Handle<java.math.BigDecimal,V>>
nodeInHeap
private java.util.Set<V>
partition1
private java.util.Set<V>
partition2
private java.util.Map<V,java.math.BigDecimal>
pot
private java.util.Map<V,E>
pred
-
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 private void
augment(V a)
Augment from a particular node.private void
augmentPathTo(V v)
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.private void
simpleHeuristic()
-
-
-
Field Detail
-
partition1
private final java.util.Set<V> partition1
-
partition2
private final java.util.Set<V> partition2
-
comparator
private final java.util.Comparator<java.math.BigDecimal> comparator
-
heapSupplier
private final java.util.function.Function<java.util.Comparator<java.math.BigDecimal>,org.jheaps.AddressableHeap<java.math.BigDecimal,V>> heapSupplier
-
pot
private java.util.Map<V,java.math.BigDecimal> pot
-
heap
private org.jheaps.AddressableHeap<java.math.BigDecimal,V> heap
-
nodeInHeap
private java.util.Map<V,org.jheaps.AddressableHeap.Handle<java.math.BigDecimal,V>> nodeInHeap
-
dist
private java.util.Map<V,java.math.BigDecimal> dist
-
matching
private java.util.Set<E> matching
-
matchingWeight
private java.math.BigDecimal matchingWeight
-
-
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
-
augment
private void augment(V a)
Augment from a particular node. The algorithm always looks for augmenting paths from nodes in partition1. In the following code partition1 is $A$ and partition2 is $B$.- Parameters:
a
- the node
-
augmentPathTo
private void augmentPathTo(V v)
-
simpleHeuristic
private void simpleHeuristic()
-
-