NAME

int_hungarian - Minimally matches an integer-weighted bipartite graph.

SYNOPSIS

#include "graph/hungarian.h"

Example compile flags (system dependent):
  -DLINUX_X86_64 -DLINUX_X86_64_OPTERON  -DGNU_COMPILER 
   -I/home/kobus/include
   -L/home/kobus/misc/load/linux_x86_64_opteron -L/usr/lib/x86_64-linux-gnu
  -lKJB                               -lfftw3  -lgsl -lgslcblas -ljpeg  -lSVM -lstdc++                    -lpthread -lSLATEC -lg2c    -lacml -lacml_mv -lblas -lg2c      -lncursesw 


int int_hungarian
(
	const Int_matrix *cost_mp,
	Int_vector **row_assignment_vpp,
	int *cost_ptr
);

DESCRIPTION

This solves a bipartite graph matching problem for a graph with integer weights (costs), using the Hungarian algorithm, a.k.a. the Kuhn-Munkres algorithm. See http://en.wikipedia.org/wiki/Hungarian_algorithm or C. H. Papadimitriou and K. Steiglitz, _Combinatorial Algorithms_ (Prentice-Hall, 1982). Input should be an M x N matrix of weights W, where rows 1 - M correspond to the (w.l.o.g.) left set of vertices, and columns 1 - N correspond to the right set of vertices. Hence W[i,j], the entry at location (i,j), contains the cost of pairing left vertex i to right vertex j. If we assume M=N we can be more formal: a matching p is a permutation of the numbers {0,...,M-1}, which we interpret as pairing the i-th row with column p(i). Costs are additive, so the cost of a matching is defined as

 C(p) = W[1,p(1)] + W[2,p(2)] + . . . + W[M,p(M)].

This algorithm is optimal in the sense than it finds a matching p* such that C(p*) is equal to or smaller than the cost of any other matching. If M < N, then the result is not a permutation but an injection

 p:{0,...,M-1} --> {0,...,N-1}

with a similar interpretation. That means p is invertible, and (N-M) columns are skipped. If M > N then (M-N) rows are skipped. The result is a surjection

 p:{0,...,N-1} --> {-1,...,M-1}

and, informally, the above definition of cost C(p) will still hold if we're willing to imagine that W contains a phantom "column negative one," in which all entries equal a very big number, like

 W[-1,k] = max{ W[i,j] : -1<i<M, -1<j<N } for all -1<k<N.

Output is returned in an Int_vector and an int. The caller must pass in a double pointer to an Int_vector (via the usual convention), called row_assignment_vpp. The caller must also pass in a pointer to an int, called cost_ptr. Neither output pointer may equal NULL. Int_vector **row_assignment_vpp will have length M, and the i-th entry will store the assignment p(i) as described above (a value in range -1 to N-1 that indicates the matched column index). The total cost of the entire matching is returned in *cost_ptr. The return value is ERROR if unsuccessful (e.g., if memory allocation fails), otherwise NO_ERROR.

hungarian

DISCLAIMER

This software is not adequatedly tested. It is recomended that results are checked independantly where appropriate.

AUTHOR

Kobus Barnard

DOCUMENTER

Andrew Predoehl