common
Class BipartiteMatcher

java.lang.Object
  common.BipartiteMatcher

public class BipartiteMatcher
extends java.lang.Object

An engine for finding the maximum-weight matching in a complete bipartite graph. Suppose we have two sets S and T, both of size n. For each i in S and j in T, we have a weight w_ij. A perfect matching X is a subset of S x T such that each i in S occurs in exactly one element of X, and each j in T occurs in exactly one element of X. Thus, X can be thought of as a one-to-one function from S to T. The weight of X is the sum, over (i, j) in X, of w_ij. A BipartiteMatcher takes the number n and the weights w_ij, and finds a perfect matching of maximum weight. It uses the Hungarian algorithm of Kuhn (1955), as improved and presented by E. L. Lawler in his book Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, 1976, p. 205-206). The running time is O(n³). The weights can be any finite real numbers; Lawler's algorithm assumes positive weights, so if necessary we add a constant c to all the weights before running the algorithm. This increases the weight of every perfect matching by nc, which doesn't change which perfect matchings have maximum weight. If a weight is set to Double.NEGATIVE_INFINITY, then the algorithm will behave as if that edge were not in the graph. If all the edges incident on a given node have weight Double.NEGATIVE_INFINITY, then the final result will not be a perfect matching, and an exception will be thrown.

Constructor Summary

BipartiteMatcher()
Creates a BipartiteMatcher without specifying the graph size.

BipartiteMatcher(int n)
Creates a BipartiteMatcher and prepares it to run on an n x n graph.

Method Summary

int[]	getMatching() Returns a maximum-weight perfect matching relative to the weights specified with setWeight.
static void	main(java.lang.String[] args)
void	reset(int n) Resets the BipartiteMatcher to run on an n x n graph.
void	setWeight(int i, int j, double w) Sets the weight wij to the given value w.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BipartiteMatcher

public BipartiteMatcher()

Creates a BipartiteMatcher without specifying the graph size. Calling any other method before calling reset will yield an IllegalStateException.

BipartiteMatcher

public BipartiteMatcher(int n)

Creates a BipartiteMatcher and prepares it to run on an n x n graph. All the weights are initially set to 1.

Method Detail

reset

public void reset(int n)

Resets the BipartiteMatcher to run on an n x n graph. The weights are all reset to 1.

setWeight

public void setWeight(int i,
                      int j,
                      double w)

Sets the weight w_ij to the given value w.

Throws:

java.lang.IllegalArgumentException - if i or j is outside the range [0, n).

getMatching

public int[] getMatching()

Returns a maximum-weight perfect matching relative to the weights specified with setWeight. The matching is represented as an array arr of length n, where arr[i] = j if (i,j) is in the matching.

main

public static void main(java.lang.String[] args)