GraphAlignment/src/lap.h File Reference

Linear assignment problem solver. More...

Go to the source code of this file.

Defines
#define	BIG   2147483647
Typedefs
typedef int	row
typedef int	col
typedef int	cost
Functions
int	LAP_lap (int dim, int **assigncost, int *rowsol, int *colsol, int *u, int *v)
void	LAP_checklap (int dim, int **assigncost, int *rowsol, int *colsol, int *u, int *v)

---

Detailed Description

Linear assignment problem solver.

This module solves linear assignment problems according to:

"A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing 38, 325-340, 1987

by

R. Jonker and A. Volgenant, University of Amsterdam.

(Author: Roy Jonker, MagicLogic Optimization Inc.)

---

Define Documentation

#define BIG   2147483647

---

Typedef Documentation

typedef int col

typedef int cost

typedef int row

---

Function Documentation

void LAP_checklap	(	int	dim,
		int **	assigncost,
		int *	rowsol,
		int *	colsol,
		int *	u,
		int *	v
	)

Check linear assignment solution.

Check a linear assignment solution (?).

Parameters:

	dim	problem size
	assigncost	cost matrix
	rowsol	column assigned to row in solution
	colsol	row assigned to column in solution
	u	dual variables, row reduction numbers
	v	dual variables, column reduction numbers

int LAP_lap	(	int	dim,
		int **	assigncost,
		int *	rowsol,
		int *	colsol,
		int *	u,
		int *	v
	)

Solve linear assignment problem.

Solve a linear assignment problem.

Parameters:

	dim	problem size
	assigncost	cost matrix
	rowsol	column assigned to row in solution
	colsol	row assigned to column in solution
	u	dual variables, row reduction numbers
	v	dual variables, column reduction numbers

---