janet.applications.utilities.graph
Class WeightedMatch

java.lang.Object
  |
  +--janet.applications.utilities.graph.WeightedMatch

public final class WeightedMatch

extends java.lang.Object

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.

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.

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

WeightedMatch()
Construct a WeightedMatch object.

Method Summary

static void	main(java.lang.String[] args) Used as a convenient repository of a simple unit test.
int[]	weightedMatch(int[][] costs, boolean minimizeWeight) The int cost matrix is assumed to be square and symmetric (undirected).

Methods inherited from class java.lang.Object

equals, 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

WeightedMatch

public WeightedMatch()

Construct a WeightedMatch object.

Method Detail

weightedMatch

public int[] weightedMatch(int[][] costs,
                           boolean minimizeWeight)

The int cost matrix is assumed to be square and symmetric (undirected).

if ( minimizeWeight )
{
performs a minimum cost maximum matching;
}
else
{
performs a minimum cost maximum matching;
}

Parameters:

costs - The int cost matrix is assumed to be square and symmetric (undirected).

minimizeWeight - if ( minimizeWeight ) { performs a minimum cost maximum matching; } else { performs a minimum cost maximum matching; }

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. I don't particularly like, this, I am just propagating custom. I may change this, at some point, so that vertices are numbered 0, ..., n-1.

main

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

Used as a convenient repository of a simple unit test.

Parameters:

args - The number of vertices and the seed for a random Euclidean graph, to use as a unit test.