Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

model.h

Go to the documentation of this file.
00001 // Model implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2003 Hermann Schichl
00004 //
00005 // This file is part of the COCONUT API.  This library
00006 // is free software; you can redistribute it and/or modify it under the
00007 // terms of the Library GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // Library GNU General Public License for more details.
00015 
00016 // As a special exception, you may use this file as part of a free software
00017 // library without restriction.  Specifically, if other files instantiate
00018 // templates or use macros or inline functions from this file, or you compile
00019 // this file and link it with other files to produce an executable, this
00020 // file does not by itself cause the resulting executable to be covered by
00021 // the Library GNU General Public License.  This exception does not however
00022 // invalidate any other reasons why the executable file might be covered by
00023 // the Library GNU General Public License.
00024 
00027 #ifndef _MODEL_H_
00028 #define _MODEL_H_
00029 
00030 #include <coconut_config.h>
00031 #include <expression.h>
00032 
00033 using namespace vgtl;
00034 
00035 class model_gid;
00036 class dag_delta;
00037 
00038 class model: public dag<expression_node>
00039 {
00040 private:
00041   typedef dag<expression_node> _Base;
00042 
00043 public:
00044   typedef dag<expression_node>::walker walker;
00045   typedef dag<expression_node>::const_walker const_walker;
00046 
00047   typedef std::vector<walker>::iterator ref_iterator;
00048   typedef std::vector<walker>::const_iterator const_ref_iterator;
00049 
00050 private:
00051   std::vector<walker> node_ref;      // node reference
00052   std::vector<walker> var_ref;       // variable reference
00053   std::vector<walker> ghost_ref;     // ghost node reference
00054   model_gid* gid;               // delta of this model or NULL
00055   bool keep_gid;
00056 
00057 public:
00058   matrix<double> lin;           // matrix of linear constraints
00059   std::vector<matrix<double> > matd; // vector of double matrices
00060   std::vector<matrix<interval> > mati; // vector of interval matrices
00061   int ocoeff;                   // max (-1) or min (1) or nothing (0)?
00062   walker objective;             // pointer to the objective
00063   std::vector<walker> constraints;   // pointer to the constraints
00064 
00065 public:
00066   model(model_gid* __id = NULL, bool clone = false);
00067   model(model_gid* __id, const erased_part& _ep, bool clone = false);
00068   model(int __num_of_vars);
00069   model(const model& __m);
00070   model(model_gid* __id, const model& __m);
00071   model(const char* name, bool do_simplify = true);
00072 
00073   ~model();
00074 
00075   int next_num();
00076   int next_variable_num();
00077   int next_constraint_num();
00078 
00079   unsigned int number_of_variables() const;
00080   unsigned int number_of_nodes() const;
00081   unsigned int number_of_constraints() const;
00082   unsigned int number_of_managed_nodes() const
00083          { return node_ref.size(); }
00084   unsigned int number_of_managed_variables() const
00085          { return var_ref.size(); }
00086   unsigned int number_of_managed_constraints() const
00087          { return constraints.size(); }
00088   const walker& var(unsigned int i) const;
00089   const walker& node(unsigned int i) const;
00090   const walker& constraint(unsigned int i) const;
00091 
00092   model_gid* gid_data() const { return gid; }
00093   void detach_gid();
00094 
00095   void compress_numbers();
00096   void renumber_variables();
00097   void renumber_constraints();
00098 
00099 private:
00100   class __docompare_nodes;
00101   class __docompare_variables;
00102 
00103   class sort_constraints;
00104   class simplify_visitor_0;
00105   struct lincoeff_visitor_st;
00106   struct lincoeff_visitor_ret;
00107   class lincoeff_visitor;
00108   struct detect_0chain_visitor_st;
00109   class detect_0chain_visitor;
00110 #if 0
00111   class simplify_visitor_thin;
00112 #endif
00113   
00114   interval read_interval(char *& cp, int ln);
00115   void read(std::istream& __i);
00116   bool children_eq(walker __n1, walker __n2);
00117   
00118   bool basic_simplify_0();
00119   bool basic_simplify_1_merge(walker __s, std::list<walker>& _todo,
00120                               std::vector<int>& _combined, std::vector<bool>& _fld,
00121                               std::vector<int>& _sorted);
00122   void basic_simplify_1_flood(walker __s, std::vector<int>& _combined);
00123   bool basic_simplify_1_is_ready(walker __s, const std::vector<int>& _combined,
00124                                  bool all_finished);
00125   bool basic_simplify_1();
00126   bool basic_simplify_2();
00127 
00128   void fill_arrays(walker __w, std::vector<walker>& __n,
00129                    std::vector<walker>& __v, std::vector<walker>& __g);
00130   void copy_contents(model_gid* gid, const model& __m);
00131   void prepare_after_read();
00132 
00133 public:
00134   bool basic_simplify();
00135   void arrange_constraints();
00136   void detect_0chain();
00137   bool simplify_thin();
00138   void set_counters();
00139   void clr_sky_ground_link();
00140 
00141   void write(std::ostream& __o = std::cout) const;
00142 
00143 public:
00144   ref_iterator ghost_begin() { return ghost_ref.begin(); }
00145   const_ref_iterator ghost_begin() const { return ghost_ref.begin(); }
00146   ref_iterator ghost_end() { return ghost_ref.end(); }
00147   const_ref_iterator ghost_end() const { return ghost_ref.end(); }
00148 
00149   walker store_node(const walker& _w);
00150   walker store_variable(const walker& _w);
00151   walker store_ghost(const walker& _w);
00152   walker store_constraint(const walker& _w);
00153 
00154   void free_node_num(unsigned int _nnum);
00155   
00156   void remove_node(const walker& _w, unsigned int _nnum);
00157   void remove_node(const walker& _w);
00158   void remove_node(unsigned int __node_num);
00159   
00160   void new_variables(int _new_num_of_vars);
00161 
00162   walker ghost(unsigned int _nnum);
00163   
00164   walker constant(double _constant);
00165   walker constant(const std::vector<double>& _constant);
00166 
00167   walker variable(unsigned int _vnum);
00168 
00169   walker binary(const walker& _op1, const walker& _op2, int expr_type,
00170                 double _coeff1 = 1.0, double _coeff2 = 1.0);
00171   walker binary(const walker& _op1, const walker& _op2, int expr_type,
00172                 additional_info_u _params, double _coeff1 = 1.0,
00173                 double _coeff2 = 1.0);
00174   
00175   walker unary(const walker& _op1, int expr_type, double _coeff = 1.0);
00176   walker unary(const walker& _op1, int expr_type, additional_info_u _params,
00177       double _coeff = 1.0);
00178 
00179   walker nary(const std::vector<walker>& _op, int expr_type,
00180               const std::vector<double>& _coeffs = std::vector<double>());
00181   walker nary(const std::vector<walker>& _op, int expr_type,
00182               additional_info_u _params,
00183               const std::vector<double>& _coeffs = std::vector<double>());
00184 
00185   walker vnary(int expr_type, ...);
00186 
00187   bool is_empty(const walker& _w) const;
00188   walker empty_reference() const;
00189 
00190 public:
00191   const std::string var_name(unsigned int n) const;
00192   const std::string const_name(unsigned int n) const;
00193   const std::string obj_name() const;
00194   double obj_adj() const;
00195   double obj_mult() const;
00196   size_t n_fixed_vars() const;
00197   std::pair<const std::string, double> fixed_var(unsigned int n) const;
00198   size_t n_unused_vars() const;
00199   const std::string& unused_var(unsigned int n) const;
00200   size_t n_unused_constrs() const;
00201   const std::string& unused_constr(unsigned int n) const;
00202 
00203   bool get_const_num(unsigned int node_num, unsigned int& const_num) const;
00204 
00205 public:
00206   bool get_linear_coeffs(const walker& expr, sparse_vector<double>& coeffs,
00207       double& constant, const std::vector<interval>& _ranges);
00208   bool get_linear_coeffs(const walker& expr, sparse_vector<double>& coeffs,
00209       double& constant);
00210 
00211   friend class dag_delta;
00212   friend class dag_undelta;
00213 };
00214 
00215 class model_iddata
00216 {
00217 private:
00218   unsigned int node_num_max;
00219   unsigned int var_num_max;
00220   unsigned int const_num_max;
00221   std::vector<int> node_free;            // free list
00222   std::vector<int> var_free;             // free list
00223   std::vector<int> const_free;           // free list
00224 
00225   std::list<model_gid*> backref;
00226 
00227   std::vector<std::string> var_names;
00228   std::vector<std::pair<std::string, double> > fixed_vars;
00229   std::string obj_names;
00230   double obj_adjs, obj_mults;
00231 
00232   std::vector<std::string> unused_vars;
00233   std::vector<std::string> unused_constrs;
00234 
00235   std::vector<std::string> const_names;
00236 public:
00237   model_iddata(unsigned int n = 0) : node_num_max(0), var_num_max(n),
00238                                      const_num_max(0), node_free(), var_free(),
00239                                      const_free(), backref(),
00240                                      var_names(n, std::string()), fixed_vars(),
00241                                      obj_names(), obj_adjs(0), obj_mults(1),
00242                                      unused_vars(), unused_constrs(),
00243                                      const_names()
00244      {}
00245 
00246   ~model_iddata() {} 
00247 
00248   void new_ref(model_gid& __m) { backref.push_back(&__m); }
00249   bool delete_ref(model_gid& __m);
00250 
00251   // get
00252   unsigned int number_of_nodes() const { return node_num_max; }
00253   unsigned int number_of_variables() const { return var_num_max; }
00254   unsigned int number_of_constraints() const { return const_num_max; }
00255   // set
00256   void number_of_nodes(unsigned int _n);
00257   void number_of_variables(unsigned int _n);
00258   void number_of_constraints(unsigned int _n);
00259 
00260   unsigned int get_node_id();
00261   void remove_node_id(unsigned int n);
00262   unsigned int get_var_id();
00263   void remove_var_id(unsigned int n);
00264   unsigned int get_const_id();
00265   void remove_const_id(unsigned int n);
00266   void compress_numbers(bool renum_vars, bool renum_consts = false);
00267 
00268 public:
00269   const std::string var_name(unsigned int n) const;
00270   void var_name(unsigned int n, const std::string& vn);
00271 
00272   const std::string const_name(unsigned int n) const;
00273   void const_name(unsigned int n, const std::string& cn);
00274 
00275   const std::string obj_name() const;
00276   void obj_name(const std::string& vn);
00277   double obj_adj() const;
00278   void obj_adj(double adj);
00279   double obj_mult() const;
00280   void obj_mult(double mult);
00281 
00282   size_t n_fixed_vars() const { return fixed_vars.size(); }
00283   std::pair<const std::string, double> fixed_var(unsigned int n) const;
00284   void fixed_var(const std::string& vn, double val);
00285 
00286   size_t n_unused_vars() const { return unused_vars.size(); }
00287   const std::string& unused_var(unsigned int n) const;
00288   void unused_var(const std::string& vn);
00289   
00290   size_t n_unused_constrs() const { return unused_constrs.size(); }
00291   const std::string& unused_constr(unsigned int n) const;
00292   void unused_constr(const std::string& vn);
00293   
00294   friend class model_gid;
00295 };
00296 
00297 class model_gid
00298 {
00299 private:
00300   model_iddata* _id;
00301   model& model_ref;
00302   std::vector<model::walker> glob_ref;   // global (across all deltas) node reference
00303   std::vector<model::walker> gvar_ref;   // for the full model, and reference to all
00304                                    // ghost nodes for delta model
00305   std::vector<model::walker> gconst_ref; // global (across all deltas) constraint reference
00306   std::map<unsigned int, unsigned int> const_back_ref; // map from node numbers to constraint numbers
00307 
00308 private:
00309   void renumber_nodes(std::vector<std::pair<unsigned int,unsigned int> >& __v);
00310   void renumber_variables(std::vector<std::pair<unsigned int,unsigned int> >& __v);
00311   void renumber_constraints(std::vector<std::pair<unsigned int,unsigned int> >& __v);
00312   void upd_number_of_nodes(unsigned int _n);
00313   void upd_number_of_variables(unsigned int _n);
00314   void upd_number_of_constraints(unsigned int _n);
00315 
00316 public:
00317   void remove_node_ref(unsigned int _n)
00318     { if(glob_ref.size() == _n) glob_ref.pop_back();
00319       else glob_ref[_n] = model_ref.ground(); }
00320   void remove_var_ref(unsigned int _n)
00321     { if(gvar_ref.size() == _n) gvar_ref.pop_back();
00322       else gvar_ref[_n] = model_ref.ground(); }
00323   void remove_const_ref(unsigned int _n);
00324 
00325   model_gid(model& __m, model_iddata* __i=NULL) : model_ref(__m), glob_ref(),
00326                                                   gvar_ref(), gconst_ref(),
00327                                                   const_back_ref()
00328     {
00329       if(__i == NULL)
00330         _id = new model_iddata;
00331       else
00332         _id = __i;
00333       _id->new_ref(*this);
00334     }
00335 
00336   model_gid(model& __m, unsigned int n, model_iddata* __i = NULL)
00337                         : model_ref(__m), glob_ref(), gvar_ref(), gconst_ref(),
00338                           const_back_ref()
00339     {
00340       if(__i == NULL)
00341         _id = new model_iddata(n);
00342       else
00343         _id = __i;
00344       _id->new_ref(*this);
00345     }
00346 
00347   model_gid(model& __mr, const model_gid& __m) : _id(__m._id),
00348                                     model_ref(__mr),
00349                                     glob_ref(__m.glob_ref),
00350                                     gvar_ref(__m.gvar_ref),
00351                                     gconst_ref(__m.gconst_ref),
00352                                     const_back_ref(__m.const_back_ref)
00353     {
00354       _id->new_ref(*this);
00355       std::vector<model::walker>::iterator __x, __e;
00356       model::walker mgr(__m.model_ref.ground()), gr(__mr.ground());
00357       __e = glob_ref.end();
00358       for(__x = glob_ref.begin(); __x != __e; ++__x)
00359         if(*__x == mgr)
00360           *__x = gr;
00361       __e = gvar_ref.end();
00362       for(__x = gvar_ref.begin(); __x != __e; ++__x)
00363         if(*__x == mgr)
00364           *__x = gr;
00365       __e = gconst_ref.end();
00366       for(__x = gconst_ref.begin(); __x != __e; ++__x)
00367         if(*__x == mgr)
00368           *__x = gr;
00369     }
00370 
00371   ~model_gid() { if(_id->delete_ref(*this)) delete _id; }
00372 
00373   unsigned int number_of_nodes() const { return _id->number_of_nodes(); }
00374   unsigned int number_of_variables() const
00375         { return _id->number_of_variables(); }
00376   unsigned int number_of_constraints() const
00377         { return _id->number_of_constraints(); }
00378   void number_of_nodes(unsigned int _n) { _id->number_of_nodes(_n); }
00379   void number_of_variables(unsigned int _n) { _id->number_of_variables(_n); }
00380   void number_of_constraints(unsigned int _n) {_id->number_of_constraints(_n);}
00381 
00382   void mk_globref(unsigned int n, const model::walker& __w);
00383   void mk_gvarref(unsigned int n, const model::walker& __w);
00384   void mk_gconstref(unsigned int n, const model::walker& __w);
00385 
00386   void make_const_back_ref(unsigned int node, unsigned int cnum);
00387   
00388   unsigned int get_node_id() { return _id->get_node_id(); }
00389   void remove_node_id(unsigned int n) { _id->remove_node_id(n); }
00390   unsigned int get_var_id() { return _id->get_var_id(); }
00391   void remove_var_id(unsigned int n) { _id->remove_var_id(n); }
00392   unsigned int get_const_id() { return _id->get_const_id(); }
00393   void remove_const_id(unsigned int n) { _id->remove_const_id(n); }
00394   void compress_numbers(bool renumber_vars = false, bool renumber_const = false)
00395         { _id->compress_numbers(renumber_vars, renumber_const); }
00396 
00397   const model::walker& node(unsigned int i) const { return glob_ref[i]; }
00398   const model::walker& variable(unsigned int i) const { return gvar_ref[i]; }
00399   const model::walker& constraint(unsigned int i) const
00400                                                 { return gconst_ref[i]; }
00401 
00402   bool empty(const model::walker& __x) const
00403         { return __x == model_ref.ground(); }
00404   bool its_me(const model& __m) const { return &__m == &model_ref; }
00405   model::walker empty_reference() const { return model_ref.ground(); }
00406 
00407   bool have_glob_ref(unsigned int _nnum) const
00408         { return _nnum < glob_ref.size(); }
00409   bool have_gvar_ref(unsigned int _vnum) const
00410         { return _vnum < gvar_ref.size(); }
00411   bool have_gconst_ref(unsigned int _cnum) const
00412         { return _cnum < gconst_ref.size(); }
00413 
00414 public:
00415   const std::string var_name(unsigned int n) const { return _id->var_name(n); }
00416   void var_name(unsigned int n, const std::string& vn) { _id->var_name(n, vn); }
00417   void var_name(unsigned int n, const char* vn)
00418         { _id->var_name(n, std::string(vn)); }
00419 
00420   const std::string const_name(unsigned int n) const
00421                                                 { return _id->const_name(n); }
00422   void const_name(unsigned int n, const std::string& vn)
00423                                                 { _id->const_name(n, vn); }
00424   void const_name(unsigned int n, const char* vn)
00425         { _id->const_name(n, std::string(vn)); }
00426   bool get_const_num(unsigned int node_num, unsigned int& const_num);
00427 
00428   const std::string obj_name() const { return _id->obj_name(); }
00429   void obj_name(const std::string& vn) { _id->obj_name(vn); }
00430   void obj_name(const char* vn) { _id->obj_name(std::string(vn)); }
00431   double obj_adj() const { return _id->obj_adj(); }
00432   void obj_adj(double adj) { _id->obj_adj(adj); }
00433   double obj_mult() const { return _id->obj_mult(); }
00434   void obj_mult(double mult) { _id->obj_mult(mult); }
00435 
00436   size_t n_fixed_vars() const { return _id->n_fixed_vars(); }
00437   std::pair<const std::string, double> fixed_var(unsigned int n) const
00438         { return _id->fixed_var(n); }
00439   void fixed_var(const std::string& vn, double val) { _id->fixed_var(vn, val); }
00440   void fixed_var(const char* vn, double val)
00441         { _id->fixed_var(std::string(vn), val); }
00442   
00443   size_t n_unused_vars() const { return _id->n_unused_vars(); }
00444   const std::string& unused_var(unsigned int n) const
00445         { return _id->unused_var(n); }
00446   void unused_var(const std::string& vn) { _id->unused_var(vn); }
00447   void unused_var(const char* vn) { _id->unused_var(std::string(vn)); }
00448   
00449   size_t n_unused_constrs() const { return _id->n_unused_constrs(); }
00450   const std::string& unused_constr(unsigned int n) const
00451         { return _id->unused_constr(n); }
00452   void unused_constr(const std::string& vn) { _id->unused_constr(vn); }
00453   void unused_constr(const char* vn) { _id->unused_constr(std::string(vn)); }
00454   
00455   friend class model_iddata;
00456 };
00457 
00458 #include <model-inline.h>
00459 
00460 typedef model::walker expression_walker;
00461 typedef model::const_walker expression_const_walker;
00462 
00463 #endif /* _MODEL_H_ */

Generated on Tue Nov 4 01:57:58 2003 for COCONUT API by doxygen1.2.18