/***************************************************************************
                          balance.c  -  description
                             -------------------
    begin                : Wed Mar 13 2002
    copyright            : (C) 2002 by Sven Klauke
    email                : sklauke@wiwi.uni-bielefeld.de
                           Institute of Mathematical Economics (IMW)
                           University of Bielefeld, Germany
                           http://www.wiwi.uni-bielefeld.de/~imw/
***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/
#include "setoper.h"
#include "cdd.h"
#include <stdio.h>
#include <stdlib.h>
#include "balance.h"
#include <gmp.h>

/*
  linear_span:
  - returns 1, if the profile vector of one coalition is in the linear span
  of the profile vectors of other coalitions (data in *p[]), return 0 otherwise
  - uses the cdd library (see the documention: Acknowledgements)
  - called from check_linspan in func.cpp
*/

int linear_span(int nplayer, int ncoalition, int *p[])
{
  int i,j;
  dd_ErrorType err=dd_NoError;
  dd_MatrixPtr A;
  dd_PolyhedraPtr poly;
  dd_MatrixPtr vert;
  dd_rowrange m;
  dd_colrange n;
  dd_NumberType numb;
  dd_set_global_constants();
  numb=dd_Rational;
  m=nplayer;
  n=ncoalition;
  A=dd_CreateMatrix(m,n);
  for(i=0;i<nplayer;i++)
    {
      for(j=0;j<ncoalition;j++)
	dd_set_si(A->matrix[i][j],p[i][j]);
    }
  for(i=0;i<nplayer;i++)
    set_addelem(A->linset,i+1);
  A->representation=dd_Inequality;
  poly=dd_DDMatrix2Poly(A,&err);
  dd_FreeMatrix(A);
  vert=dd_CopyGenerators(poly);
  for(i=0;i<vert->rowsize;i++)
    {
      if(mpq_sgn(vert->matrix[i][0])==1)
	{
	  dd_FreeMatrix(vert);
	  return 1;
	}
    }
  dd_FreePolyhedra(poly);
  dd_FreeMatrix(vert);
  return 0;
}

/*
  balance:
  - returns 1, if the coalitions in *p[] are balanced, returns 0 otherwise
  - uses the cdd library (see the documention: Acknowledgements)
  - calculates all the vertices of the solution region of the system of
  linear equalities \sum_{S\in *p[]}\delta_s 1_S=1_N
  - calculates the mid point of this region to see if there is a strictly
  positive solution
*/

int balance(int nplayer,int ncoalition,int *p[])
{
  int ii,jj;
  dd_ErrorType err=dd_NoError;
  dd_PolyhedraPtr poly;
  dd_MatrixPtr vert;
  dd_rowrange m;
  dd_colrange n;
  dd_NumberType numb;
  dd_MatrixPtr A;
  dd_colrange j;
  mpq_t z;
  mpq_t zdiv;
  dd_set_global_constants();
  numb=dd_Rational;
  m=nplayer+ncoalition;
  n=ncoalition+1;
  A=dd_CreateMatrix(m,n);
  for(ii=0;ii<ncoalition;ii++)
    {
      for(jj=0;jj<ncoalition+1;jj++)
	dd_set_si(A->matrix[ii][jj],p[ii][jj]);
    }
  for(ii=0;ii<nplayer;ii++)
    {
      for(jj=0;jj<ncoalition+1;jj++)
	dd_set_si(A->matrix[ncoalition+ii][jj],p[ncoalition+ii][jj]);
    }
  for(ii=0;ii<nplayer;ii++)
    set_addelem(A->linset,ii+ncoalition+1);
  A->representation=dd_Inequality;
  poly=dd_DDMatrix2Poly(A,&err);
  dd_FreeMatrix(A);
  vert=dd_CopyGenerators(poly);
  dd_FreePolyhedra(poly);
  mpq_init(z);
  mpq_init(zdiv);
  mpq_set_d(zdiv,vert->rowsize);
  for(ii=1;ii<vert->colsize;ii++)
    {
      mpq_set_ui(z,0,1);
      for(jj=0;jj<vert->rowsize;jj++)
	{
	  mpq_add(z,z,vert->matrix[jj][ii]);
	  mpq_canonicalize(z);
	}
      mpq_div(z,z,zdiv);
      mpq_canonicalize(z);
      mpq_out_str(stdout,10,z);
      if(mpq_sgn(z)==0)
	{
	  dd_FreeMatrix(vert);
	  return 0;
	}
      printf("\n");
    }
  dd_FreeMatrix(vert);
  return 1;
}