/*
* This file is part of libmunkres, a library to solve the
* assignment problem.
*
* input : N x N matrix with costs of N workers solving N tasks
* output: assigmentmatrix M with minimal cost
*
* based on c# implementation from http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html
* "Algorithms for Assignment and Transportation Problems", James Munkres, 
*       Journal of the Society for Industrial and Applied Mathematics Volume 5, Number 1, March, 1957
* original author: Robert A. Pilgrim - Murray State University - rpilgirm <a> murraystate <dot> edu
*
* Copyright(c) sschulz <AT> techfak.uni-bielefeld.de
* http://opensource.cit-ec.de/projects/libmunkres
*
* This file may be licensed under the terms of the
* GNU Lesser General Public License Version 3 (the ``LGPL''),
* or (at your option) any later version.
*
* Software distributed under the License is distributed
* on an ``AS IS'' basis, WITHOUT WARRANTY OF ANY KIND, either
* express or implied. See the LGPL for the specific language
* governing rights and limitations.
*
* You should have received a copy of the LGPL along with this
* program. If not, go to http://www.gnu.org/licenses/lgpl.html
* or write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* The development of this software was supported by the
* Excellence Cluster EXC 277 Cognitive Interaction Technology.
* The Excellence Cluster EXC 277 is a grant of the Deutsche
* Forschungsgemeinschaft (DFG) in the context of the German
* Excellence Initiative.
*/

#include <limits>
#include <stdlib.h>
#include <cstdio>

class Munkres{
public:
	Munkres();
	bool init_matrix(int rows, int cols, int *data);
	void run();
	int get_row_match_for_col(int c);
	int get_col_match_for_row(int row);
	void show_cost_matrix();
	
private:
	int C[30][30];
	int C_orig[30][30];
	int M[30][30];
	int path[61][2];
	int RowCover[30];
	int ColCover[30];
	int nrow;
	int ncol;
	int path_count;
	int path_row_0;
	int path_col_0;
	int asgn;
	int step;

	void resetMaskandCovers();
	void step_one(int *step);
	void step_two(int *step);
	void step_three(int *step);
	void find_a_zero(int *row, int *col);
	bool star_in_row(int row);
	void find_star_in_row(int row, int *col);
	void step_four(int *step);
	void find_star_in_col(int c, int *r);
	void find_prime_in_row(int r, int *c);
	void augment_path();
	void clear_covers();
	void erase_primes();
	void step_five(int *step);
	void find_smallest(int *minval);
	void step_six(int *step);
	void step_seven(int *step);
	void genRandomMatrix();
	void genTestMatrix();
	void show_mask_matrix();

};