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>
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
FieldsModifier and TypeFieldDescriptionprivate final Comparator
<BigDecimal> private Map
<V, BigDecimal> private org.jheaps.AddressableHeap
<BigDecimal, V> private final Function
<Comparator<BigDecimal>, org.jheaps.AddressableHeap<BigDecimal, V>> private BigDecimal
private Map
<V, org.jheaps.AddressableHeap.Handle<BigDecimal, V>> private Map
<V, BigDecimal> Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
Constructor Summary
ConstructorsConstructorDescriptionConstructor.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 TypeMethodDescriptionprivate void
Augment from a particular node.private void
augmentPathTo
(V v) Compute a matching for a given graph.Get the weight of the matching.Get the vertex potentials.private void
-
Field Details
-
graph
-
partition1
-
partition2
-
comparator
-
heapSupplier
private final Function<Comparator<BigDecimal>,org.jheaps.AddressableHeap<BigDecimal, heapSupplierV>> -
pot
-
matchedEdge
-
heap
-
nodeInHeap
-
pred
-
dist
-
matching
-
matchingWeight
-
-
Constructor Details
-
MaximumWeightBipartiteMatching
Constructor.- Parameters:
graph
- the input graphpartition1
- the first partition of the vertex setpartition2
- 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 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:
IllegalArgumentException
- if the graph is not undirected
-
-
Method Details
-
getMatching
Compute a matching for a given graph.- Specified by:
getMatching
in interfaceMatchingAlgorithm<V,
E> - Returns:
- a matching
-
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
Get the weight of the matching.- Returns:
- the weight of the matching
-
augment
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
-
simpleHeuristic
private void simpleHeuristic()
-