/*
	This file gathers some routines for the resolution of 
	the set covering problem.

	August 25, 94		Creation: E. Mayoraz
*/

#ifndef setCovering_h
#define setCovering_h



#include <iostream.h>

#include "../Basics/basic.h"
#include "../Matrices/Matrix.h"
#include "../Matrices/binMatrix.h"



class SCTable : protected binMatrix {
      // This class handles a boolean matrix with tools for:
      //	- suppressing rows/columns
      //	- determining the # of 1 per rows/columns
      //	- determining the set of rows/columns with minimal/maximal # of 1.
      //	- suppressing all redundant rows/columns
      //	- recovering the original matrix

   public:

      SCTable 		(const binMatrix& A);
      virtual ~SCTable 		();

      SCTable&	original();	

      int	m				() const;
      int	n				() const;
      boolean	operator ()		(int row, int col) const;

      int	cardOfRow		(int row) const;
      int	cardOfCol		(int col) const;
      int	minCardOfRow	() const;
      int	maxCardOfRow	() const;
      int	minCardOfCol	() const;
      int	maxCardOfCol	() const;
      int	originalRowI	(int row) const;
      int	originalColI	(int col) const;

      int	minRows		(Matrix<int>& index) const;
      int	maxCols		(Matrix<int>& index) const;
      int	maxCols		(const Array<int>& from, Matrix<int>& index) const;
      int	rowsUnion	(const Array<int>& between, Matrix<int>& index) const;

      SCTable&	deleteRC	(const Array<int>& rowInd, const Array<int>& colInd);
      SCTable&	delRedundances	(int& colDel, int& rowDel, int& status);
      // status = -2 : nothing special, status = -1: problem impossible
      // status >= 0 : column status is enough to complete the covering
		
///////////////////////////////////////////////////////////////////////////////

   private:
      Matrix<int> rowI;
      Matrix<int> colI;
      Matrix<int> rowCard;
      Matrix<int> colCard;
      int curM;
      int curN;
      SCTable&	deleteRow		(int row);
      SCTable&	deleteCol		(int col);
};
///////////////////////////////////////////////////////////////////////////////




class setCover : private SCTable {
   public:
      setCover (const binMatrix& A);
      // Create a set covering problem where rows of A have to be covered 
      // by columns of A.

      setCover& greedy (	// simple greedy procedure
         ostream& flog,
	 float heuristic=0.5,	// choice of heuristic
	 int nbCover=1,		// number of time each row must be covered
	 boolean cleanUp=false);// reduces problem asap at each iteration
      // Meaning of heuristic:
      //
      // If heuristic is a real in [0,1]:
      // -------------------------------
      // Two basic heuristic methods are classically proposed. 
      // In the first approach, a column c* with a maximum cardinality over 
      // all columns is chosen, while in the second, the column c+ with 
      // maximal cardinality over the set of columns that covers at least 
      // one row of minimal cardinality is prefered.
      // In this implementation, c* will is chosen if 
      //		(heuristic * card(c*)) > card(c+)
      // otherwise, c+ is chosen.
      // So 	c* is always prefered if heuristic=1
      //		c+ is always prefered if heuristic=0 .
      //
      // If heuristic is a negative number:
      // ---------------------------------
      // The chosen column is that one maximizing the following criterion:
      // 		max_j { sum_i ( A_ij * B(w_i) ) },
      // where B is a bonus function of w_i the number of 1 in row i.
      // In this model we assume B quadratic decreasing and	|     \
      //	B (w_max) = 1,					|      \ 
      //	B'(w_max) = 0,					|    .  `-_.
      //	B (w_min) = max { 1 , -heuristic * #Cols }.	|   Wmin  Wmax
      // So if -heuristic is epsilon, then B(w_i)=1 for all w_i and thus
      // c* is always chosen. And bigger is -heuristic stronger is the 
      // importance accorded to small rows.
      //
      // If nbCover < 0, it is treated as abs(nbCover) except that if there
      // exist some rows that cannot be covered by abs(nbCover), no exception 
      // is raised and they are simply covered as much as possible
		

      setCover& reduce (// try to reduce a given solution
	 int upperBound=10000);	// upper bound on the size of sol. for the B&B
      // This procedure find out the best solution among the sub-solutions
      // of the current solution. So, it is assumed that the current solution
      // is not too bad, otherwise this routine could run for centuries.

      Matrix<int> 	solution();
      Matrix<int>	bestSolution();

///////////////////////////////////////////////////////////////////////////////

   private:
      Matrix<int> 	thisSol, bestSol;
      int		thisSize;
      Matrix<int>	nbCovered;
      binMatrix		mandatCol;
      void chooseMandatCols(int nbCover);
      void improveRec(Array<int>& sol, int& mandat, int bestKnown);
};




#endif