de.cesr.sesamgim.aggregate
Class GWeightedPerfectMatching

java.lang.Object
  de.cesr.sesamgim.aggregate.GWeightedPerfectMatching

public class GWeightedPerfectMatching
extends Object

SesamGIM - Geographical Initialisation for Milieu Agents Gabow's implementation of Edmonds' algorithm is described in chapter 6 of Nonbipartite Matching, of Combinatorial Optimization, Networks and Matroids, authored by Eugene Lawler, published by Holt, Rinehart, and Winston, 1976.

Lawler's description is referred to in the Notes and References section of chapter 11, Weighted Matching, of Combinatorial Optimation, Algorithms and Complexity, authored by Christos Papadimitriou and Kenneth Steiglitz, published by Prentice-Hall, 1982.

The implementation here mimics Gabow's description and Rothberg's C coding of Gabow's description, making it easy for others to see the correspondence between this code, Rothberg's C code, and Gabow's English description of the algorithm, given in Appendix D of his dissertation.

Since the code mimics Gabow's description (Rothberg's C code does so even more closely), the code below is not object-oriented, much less good Java. It also violates many Java naming conventions.

Currently, the graph is assumed to be complete & symmetric.

It is unclear to me why cost values are doubled in setUp() and intialize(). I think it may have to do with the implementation being entirely integer. When I remove the doubling, the minimum weight maximum match fails on the test graph. ------ This class implements a [minimum | maximum] cost maximum matching based on an O(n^3) implementation of Edmonds' algorithm, as presented by Harold N. Gabow in his Ph.D. dissertation, Computer Science, Stanford University, 1973.

Field Summary

static boolean	MAXIMIZE The value that indicates that a maximum cost maximum match is sought.
static boolean	MINIMIZE The value that indicates that a minimum cost maximum match is sought.

Constructor Summary

GWeightedPerfectMatching(double[][] costs)
Construct a WeightedMatch object.

Method Summary

int[]	getMatched(int[] mates)
int[]	weightedMatch(boolean minimizeWeight) The int cost matrix is assumed to be square and symmetric (undirected).

Methods inherited from class java.lang.Object

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

Field Detail

MINIMIZE

public static final boolean MINIMIZE

The value that indicates that a minimum cost maximum match is sought.

See Also:

Constant Field Values

MAXIMIZE

public static final boolean MAXIMIZE

The value that indicates that a maximum cost maximum match is sought.

See Also:

Constant Field Values

Constructor Detail

GWeightedPerfectMatching

public GWeightedPerfectMatching(double[][] costs)

Construct a WeightedMatch object.

Method Detail

weightedMatch

public int[] weightedMatch(boolean minimizeWeight)

The int cost matrix is assumed to be square and symmetric (undirected). If ( minimizeWeight ) is true it performs a minimum cost maximum matching;
else it performs a maximum cost maximum matching.

Parameters:

minimizeWeight - performs a minimum cost maximum matching if true

Returns:

an array of the form vertex[i] = j, where vertex i is matched to vertex j. The numbering of vertices is 1, ..., n, where the graph has n vertices. Thus, the 0th element of the returned int[] is undefined.

getMatched

public int[] getMatched(int[] mates)