btableau.imp

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/numerical/btableau.imp,v $
// $Date: 2002/09/26 17:50:52 $
// $Revision: 1.1.2.1 $
//
// DESCRIPTION:
// Implementation of base tableau classes
//
// This file is part of Gambit
// Copyright (c) 2002, The Gambit Project
//
// 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.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//

// ---------------------------------------------------------------------------
//                BaseTableau method definitions
// ---------------------------------------------------------------------------

#include "btableau.h"

template <class T>
bool BaseTableau<T>::ColIndex(int x) const
{ return MinCol()<=x && x<=MaxCol(); }

template <class T>
bool BaseTableau<T>::RowIndex(int x) const
{ return MinRow()<=x && x<=MaxRow(); }

template <class T>
bool BaseTableau<T>::ValidIndex(int x) const
{ return (ColIndex(x) || RowIndex(-x)); }

template <class T>
void BaseTableau<T>::CompPivot(int outlabel, int col)
{
  Pivot(Find(outlabel),col);
  Pivot(Find(-col),-outlabel);
}


// ---------------------------------------------------------------------------
//            TableauInterface method definitions
// ---------------------------------------------------------------------------

// Constructors and Destructor
 
template <class T> 
TableauInterface<T>::TableauInterface(const gMatrix<T> &A, const gVector<T> &b)
  : A(&A), b(&b), basis(A.MinRow(),A.MaxRow(),A.MinCol(),A.MaxCol()), 
    solution(A.MinRow(),A.MaxRow()), npivots(0), 
    artificial(A.MaxCol()+1,A.MaxCol())

{ 
  // These are the values recommended by Murtagh (1981) for 15 digit 
  // accuracy in LP problems 
  // Note: for gRational, eps1 and eps2 resolve to 0
  gEpsilon(eps1,5);
  gEpsilon(eps2);
}

template <class T> 
TableauInterface<T>::TableauInterface(const gMatrix<T> &A, 
				      const gBlock<int> &art, const gVector<T> &b)
  : A(&A), b(&b), 
    basis(A.MinRow(),A.MaxRow(),A.MinCol(),A.MaxCol()+art.Length()), 
    solution(A.MinRow(),A.MaxRow()), npivots(0),
    artificial(A.MaxCol()+1,A.MaxCol()+art.Length())
{ 
  gEpsilon(eps1,5);
  gEpsilon(eps2);
  for(int i = 0;i<art.Length();i++)
    artificial[A.MaxCol()+1+i] = art[art.First()+i];
}

template <class T>
TableauInterface<T>::TableauInterface(const TableauInterface<T> &orig) 
  : A(orig.A), b(orig.b), basis(orig.basis), solution(orig.solution),
    npivots(orig.npivots), eps1(orig.eps1), eps2(orig.eps2), 
    artificial(orig.artificial)
{ }

template <class T>
TableauInterface<T>::~TableauInterface()
{ }

template <class T>
TableauInterface<T>& TableauInterface<T>::operator=(const TableauInterface<T> &orig)
{
  if(this!= &orig) {
    A = orig.A;
    b = orig.b;
    basis= orig.basis;
    solution= orig.solution;
    npivots = orig.npivots;
    artificial = orig.artificial;
  }
  return *this;
}

// getting information

template <class T>
int TableauInterface<T>::MinRow() const { return A->MinRow(); }

template <class T>
int TableauInterface<T>::MaxRow() const { return A->MaxRow(); }

template <class T>
int TableauInterface<T>::MinCol() const { return basis.MinCol(); }

template <class T>
int TableauInterface<T>::MaxCol() const { return basis.MaxCol(); }

template <class T>
Basis & TableauInterface<T>::GetBasis(void) {return basis; }

template <class T>
const gMatrix<T> & TableauInterface<T>::Get_A(void) const {return *A; }

template <class T>
const gVector<T> & TableauInterface<T>::Get_b(void) const {return *b;}

template <class T>
bool TableauInterface<T>::Member(int i) const
{ return basis.Member(i);}

template <class T>
int TableauInterface<T>::Label(int i) const
{ return basis.Label(i);}

template <class T>
int TableauInterface<T>::Find(int i) const
{ return basis.Find(i);}

template <class T>
long TableauInterface<T>::NumPivots() const
{ return npivots; }

template <class T>
long &TableauInterface<T>::NumPivots()
{ return npivots; }

template <class T>
void TableauInterface<T>::Mark(int label)
{basis.Mark(label);}

template <class T>
void TableauInterface<T>::UnMark(int label)
{basis.UnMark(label);}

template <class T>
bool TableauInterface<T>::IsBlocked(int label) const
{
  return basis.IsBlocked(label);
}

template <class T>
void TableauInterface<T>::GetColumn(int col, gVector<T> &ret) const
{
  if(IsArtifColumn(col)) {
    ret = (T) 0;
    ret[artificial[col]] = (T)1;
  }
  else if(basis.IsRegColumn(col))
    A->GetColumn(col, ret);
  else if (basis.IsSlackColumn(col)) {
    ret = (T) 0;
    ret[-col] = (T) 1;
  }
}

template <class T>
void TableauInterface<T>::GetBasis(Basis &out) const
{
  out= basis;
}

template <class T>
BFS<T> TableauInterface<T>::GetBFS()
{
  gVector<T> sol(basis.First(),basis.Last());
  BasisVector(sol);

  BFS<T> cbfs((T) 0);
  for(int i=MinCol();i<=MaxCol();i++) 
    if(Member(i)) 
      cbfs.Define(i,sol[basis.Find(i)]);
  return cbfs;
}

template <class T>
BFS<T> TableauInterface<T>::GetBFS1() const
{
  gVector<T> sol(basis.First(),basis.Last());
  BasisVector(sol);

  BFS<T> cbfs((T) 0);
  int i;
  for(i=-MaxRow();i<=-MinRow();i++) 
    if(Member(i)) 
      cbfs.Define(i,sol[basis.Find(i)]);
  for(i=MinCol();i<=MaxCol();i++) 
    if(Member(i)) 
      cbfs.Define(i,sol[basis.Find(i)]);
  return cbfs;
}

template <class T>
void TableauInterface<T>::Dump(gOutput &to) const
{ 
  gVector<T> bb(MinRow(), MaxRow());
  BasisVector(bb);
  to << "\nBasis:\n";  
  basis.Dump(to);
  to << "\n" << bb;
}

template <class T>
void TableauInterface<T>::BigDump(gOutput &to)
{ 
  to << "\nBasis:";
  basis.Dump(to);
  gMatrix<T> AA(MinRow(),MaxRow(),MinCol(),MaxCol()+(*A).NumRows());
  gVector<T> bb(MinRow(), MaxRow());

  BasisVector(bb);
  to << "\nBasisVector:\n" << bb;

  for(int j=MinCol();j<=MaxCol();j++) {
    SolveColumn(j, bb);
    for(int i=AA.MinRow();i<=AA.MaxRow();i++) 
      AA(i,j) = bb[i];
  }
  for(int j=MinRow();j<=MaxRow();j++) {
    SolveColumn(-j, bb);
    for(int i=AA.MinRow();i<=AA.MaxRow();i++) 
      AA(i,MaxCol()+j) = bb[i];
  }
  to << "\nTableau:\n" << AA;
}

// miscellaneous functions

template <class T>
bool TableauInterface<T>::EqZero(T x) const
{ 
  return (LeZero(x) && GeZero(x));
}

template <class T>
bool TableauInterface<T>::LtZero(T x) const
{ 
  return !GeZero(x);
}

template <class T>
bool TableauInterface<T>::GtZero(T x) const
{ 
  return !LeZero(x);
}

template <class T>
bool TableauInterface<T>::LeZero(T x) const
{ 
  if(x <=eps2) return 1;
  return 0;
}

template <class T>
bool TableauInterface<T>::GeZero(T x) const
{ 
  if(x >= -eps2) return 1;
  return 0;
}

template <class T>
T TableauInterface<T>::Epsilon(int i) const
{
  if(i!=1 && i!=2) throw BadDim();
  if(i==1) return eps1;
  return eps2;
}

template <class T>
bool TableauInterface<T>::IsArtifColumn(int col) const
{
  return col>=artificial.First() && col<=artificial.Last();
}

/*
template <class T> BaseTableau<T>::BadPivot::~BadPivot()
{ }

template <class T> gText BaseTableau<T>::BadPivot::Description(void) const
{
  return "Bad Pivot in BaseTableau";
}
*/
template <class T> BaseTableau<T>::BadDim::~BadDim()
{ }

template <class T> gText BaseTableau<T>::BadDim::Description(void) const
{
  return "Bad Dimension in BaseTableau";
}