tableau.imp

Gambit 是一个游戏库理论软件

  return *this;
}

// Aligns the column indexes

int Tableau<gRational>::remap(int col_index) const
{
  int i = nonbasic.First(); 
  while(i <= nonbasic.Last() && nonbasic[i] !=col_index) { i++;}
  if(i > nonbasic.Last()) throw BadDim();
  return i;
}

gMatrix<gRational> Tableau<gRational>::GetInverse()
{
  gVector<gRational> mytmpcol(tmpcol.First(),tmpcol.Last());
  gMatrix<gRational> inv(MinRow(),MaxRow(),MinRow(),MaxRow());
  for(int i=inv.MinCol();i<=inv.MaxCol();i++){
    MySolveColumn(-i,mytmpcol);
    inv.SetColumn(i,mytmpcol);
  }
  return inv;
}


// pivoting operations

int Tableau<gRational>::CanPivot(int outlabel, int col)
{
  MySolveColumn(col,tmpcol);
  gRational val = tmpcol[basis.Find(outlabel)];
  if(val == (gRational)0) return 0;
  //   if(val <=eps2 && val >= -eps2) return 0;
  return 1;  
}

void Tableau<gRational>::Pivot(int outrow,int in_col)
{
  // gout << "\nIn Tableau<gRational>::Pivot() ";
  // gout << " outrow:" << outrow;
  // gout << " inlabel: " << in_col;
  if(!RowIndex(outrow) || !ValidIndex(in_col)) 
    throw BadPivot();
  int outlabel = Label(outrow);

  // gout << "\noutrow:" << outrow;
  // gout << " outlabel: " << outlabel;
  // gout << " inlabel: " << in_col;

  // BigDump(gout);
  // gout << "\ndenom: " << denom << " totdenom: " << totdenom;
  // gout << " product: " << denom*totdenom;
  // gout << "\nTabdat: loc 1\n " << Tabdat;
  // gout << "\nInverse: loc 1\n " << GetInverse();

  int col;
  int row(outrow);
  int i,j; // loop-control variables

  col = remap(in_col);

  // Pivot Algorithm:
  // i* denotes Pivot Row
  // j* denotes Pivot Column
  // C is the Tableau
  // Cij is the (i,j)th component of C
  // X denotes multiplication
  // d is the denominator (initially 1)
  //
  // 1: Copy row i (don't need to implement this)
  // 2: Zero column j excepting the Pivot Element (done second)
  // 3: Cij=(Ci*j*XCij-Ci*jXCij*)/d for all other elements (done first)
  // 4: d=Ci*j* (done last)

  // Step 3
  
  for(i=Tabdat.MinRow();i<=Tabdat.MaxRow();++i){
    if(i!=row){
      for(j=Tabdat.MinCol();j<=Tabdat.MaxCol();++j){
	if(j!=col){
	  Tabdat(i,j) = (Tabdat(row,col)*Tabdat(i,j)-Tabdat(row,j)*Tabdat(i,col))/denom;
	}
      }
      Coeff[i] = (Tabdat(row,col)*Coeff[i]-Coeff[row]*Tabdat(i,col))/denom;
    }
  }
  // Step 2
  // Note: here we are moving the old basis column into column 'col'
  for(i=Tabdat.MinRow();i<=Tabdat.MaxRow();++i){
    if(i!=row)
      Tabdat(i,col)=-Tabdat(i,col);
  }
  // Step 4
  gInteger old_denom = denom;
  denom=Tabdat(row,col);
  Tabdat(row,col)=old_denom;
  // BigDump(gout);
  npivots++;

  basis.Pivot(outrow,in_col);
  nonbasic[col] = outlabel;
  
  for (i = solution.First();i<=solution.Last();i++) 
    //** solution[i] = (gRational)(Coeff[i])/(gRational)(denom*totdenom);
    solution[i] = gRational(Coeff[i]*sign(denom*totdenom));

  //gout << "Bottom \n" << Tabdat << '\n';
  // BigDump(gout);
  // gout << "\ndenom: " << denom << " totdenom: " << totdenom;
  // gout << "\nTabdat: loc 2\n " << Tabdat;
  // gout << "\nInverse: loc 2\n " << GetInverse();
  
  // Refactor();
}

void Tableau<gRational>::SolveColumn(int in_col, gVector<gRational> &out)
{
  gVector<gInteger> tempcol(tmpcol.First(),tmpcol.Last());
  if(Member(in_col)) {
    out = (gRational)0;
    out[Find(in_col)] = gRational(abs(denom));
  }
  else {
    int col = remap(in_col);
    Tabdat.GetColumn(col,tempcol);
    for(int i=tempcol.First();i<=tempcol.Last();i++)
      out[i] = (gRational)(tempcol[i]) * (gRational)(sign(denom*totdenom));
  }
  out=out/(gRational)abs(denom);
  if(in_col < 0) out*=totdenom;
  for(int i=out.First();i<=out.Last();i++) 
    if(Label(i)<0) out[i]=(gRational)out[i]/(gRational)totdenom;
}

void Tableau<gRational>::MySolveColumn(int in_col, gVector<gRational> &out)
{
  gVector<gInteger> tempcol(tmpcol.First(),tmpcol.Last());
  if(Member(in_col)) {
    out = (gRational)0;
    out[Find(in_col)] = gRational(abs(denom));
  }
  else {
    int col = remap(in_col);
    Tabdat.GetColumn(col,tempcol);
    for(int i=tempcol.First();i<=tempcol.Last();i++)
      out[i] = (gRational)(tempcol[i]) * (gRational)(sign(denom*totdenom));
  }
}

void Tableau<gRational>::GetColumn(int col, gVector<gRational> &out) const
{
  TableauInterface<gRational>::GetColumn(col,out);
  if(col>=0) out*=gRational(totdenom);

}

void Tableau<gRational>::Refactor()
{ 
  gVector<gRational> mytmpcol(tmpcol);
  //BigDump(gout);
  //** Note -- we may need to recompute totdenom here, if A and b have changed. 
  //gout << "\ndenom: " << denom << " totdenom: " << totdenom;
  totdenom = lcm(find_lcd(*A),find_lcd(*b));
  if(totdenom<=0) throw BadDenom();
  // gout << "\ndenom: " << denom << " totdenom: " << totdenom;

  int i,j;
  gMatrix<gRational> inv(GetInverse());
  gMatrix<gRational> Tabnew(Tabdat.MinRow(),Tabdat.MaxRow(),Tabdat.MinCol(),Tabdat.MaxCol());
  for(i=nonbasic.First();i<=nonbasic.Last();i++) {
    GetColumn(nonbasic[i],mytmpcol);
    //    if(nonbasic[i]>=0) mytmpcol*=gRational(totdenom);
    Tabnew.SetColumn(i,inv * mytmpcol * (gRational)sign(denom*totdenom));
    //gout << "\nMyTmpCol \n" << mytmpcol;
  }

  //gout << "\nInv: \n" << inv;
  //gout << "\nTabdat:\n" << Tabdat;
  //gout << "\nTabnew:\n" << Tabnew;

  gVector<gRational> Coeffnew(Coeff.First(),Coeff.Last());
  Coeffnew = inv * (*b) * totdenom * (gRational)sign(denom*totdenom);

  //gout << "\nCoeff:\n" << Coeff;
  //gout << "\nCoeffew:\n" << Coeffnew;

  for(i=Tabdat.MinRow();i<=Tabdat.MaxRow();i++) {
    if(Coeffnew[i].denominator() != 1) throw BadDenom();
    Coeff[i] = Coeffnew[i].numerator();
    for(j=Tabdat.MinCol();j<=Tabdat.MaxCol();j++) {
      if(Tabnew(i,j).denominator() != 1) throw BadDenom();
      Tabdat(i,j) = Tabnew(i,j).numerator();
    }
  }
  //BigDump(gout);
}
  
void Tableau<gRational>::SetRefactor(int)
{ }

void Tableau<gRational>::SetConst(const gVector<gRational> &bnew)
{
  b=&bnew;
  Refactor();
}


//** this function is not currently used.  Drop it?
void Tableau<gRational>::SetBasis(const Basis &in)
{
  basis= in;
  //** this has to be changed -- Need to start over and pivot to new basis.  
  // B.refactor();
  // B.solve(*b, solution);
}

 // solve M x = b
void Tableau<gRational>::Solve(const gVector<gRational> &b, gVector<gRational> &x)
{
  // Here, we do x = V * b, where V = M inverse
  x = (GetInverse() * b )/(gRational)abs(denom);
}

 // solve y M = c
void Tableau<gRational>::SolveT(const gVector<gRational> &c, gVector<gRational> &y)
{
  // Here we do y = c * V, where V = M inverse
  y = (c * GetInverse()) /(gRational)abs(denom);
}

bool Tableau<gRational>::IsFeasible()
{
  for(int i=solution.First();i<=solution.Last();i++)
    if(solution[i]>=eps2) return false;
  return true;
}

bool Tableau<gRational>::IsLexMin()
{
  int i,j;
  for(i=MinRow();i<=MaxRow();i++)
    if(EqZero(solution[i]))
      for(j=-MaxRow();j<Label(i);j++) if(j!=0){
	SolveColumn(j,tmpcol);
	if(LtZero(tmpcol[i]))
	  return 0;
      }
  return 1;
}

gOutput &operator<<(gOutput &to, const Tableau<gRational> &v)
{
  v.Dump(to); return to;
}

void Tableau<gRational>::BigDump(gOutput &out)
{
  TableauInterface<gRational>::BigDump(out);
  // gout << "\ndenom: " << denom << " totdenom: " << totdenom;
  // gout << "\nnonbasic: " << nonbasic;
  // gout << "\nTabdat:\n" << Tabdat;
  // gout << "\nCoeff:\n" << Coeff;
}

void Tableau<gRational>::BasisVector(gVector<gRational> &out) const
{
  out = solution;
  out= out/(gRational)abs(denom) ;
  for(int i=out.First();i<=out.Last();i++) 
    if(Label(i)<0) out[i]=out[i]/(gRational)totdenom;
}

gInteger Tableau<gRational>::TotDenom() const
{
return totdenom;
}

Tableau<gRational>::BadDenom::~BadDenom()
{ }

gText Tableau<gRational>::BadDenom::Description(void) const
{
  return "Bad Denominator in Tableau";
}