Class 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.

    • Field Detail

      • graph

        private final Graph<V,​E> graph
      • 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
      • matchedEdge

        private java.util.Map<V,​E> matchedEdge
      • 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
      • pred

        private java.util.Map<V,​E> pred
      • 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 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 Detail

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