Module org.jgrapht.core
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 type
E - 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

  • Constructor Details

    • MaximumWeightBipartiteMatching

      public MaximumWeightBipartiteMatching​(Graph<V,​E> graph, java.util.Set<V> partition1, java.util.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:
      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 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:
      java.lang.IllegalArgumentException - if the graph is not undirected

  • Method Details

    • 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 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