---

model.h

Go to the documentation of this file.

// Model implementation -*- C++ -*-

// Copyright (C) 2001-2003 Hermann Schichl
//
// This file is part of the COCONUT API.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library 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
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#ifndef _MODEL_H_
#define _MODEL_H_

#include <coconut_config.h>
#include <expression.h>

using namespace vgtl;

class model_gid;
class dag_delta;

class model: public dag<expression_node>
{
private:
  typedef dag<expression_node> _Base;

public:
  typedef dag<expression_node>::walker walker;
  typedef dag<expression_node>::const_walker const_walker;

  typedef std::vector<walker>::iterator ref_iterator;
  typedef std::vector<walker>::const_iterator const_ref_iterator;

private:
  std::vector<walker> node_ref;      // node reference
  std::vector<walker> var_ref;       // variable reference
  std::vector<walker> ghost_ref;     // ghost node reference
  model_gid* gid;               // delta of this model or NULL
  bool keep_gid;

public:
  matrix<double> lin;           // matrix of linear constraints
  std::vector<matrix<double> > matd; // vector of double matrices
  std::vector<matrix<interval> > mati; // vector of interval matrices
  int ocoeff;                   // max (-1) or min (1) or nothing (0)?
  walker objective;             // pointer to the objective
  std::vector<walker> constraints;   // pointer to the constraints

public:
  model(model_gid* __id = NULL, bool clone = false);
  model(model_gid* __id, const erased_part& _ep, bool clone = false);
  model(int __num_of_vars);
  model(const model& __m);
  model(model_gid* __id, const model& __m);
  model(const char* name, bool do_simplify = true);

  ~model();

  int next_num();
  int next_variable_num();
  int next_constraint_num();

  unsigned int number_of_variables() const;
  unsigned int number_of_nodes() const;
  unsigned int number_of_constraints() const;
  unsigned int number_of_managed_nodes() const
         { return node_ref.size(); }
  unsigned int number_of_managed_variables() const
         { return var_ref.size(); }
  unsigned int number_of_managed_constraints() const
         { return constraints.size(); }
  const walker& var(unsigned int i) const;
  const walker& node(unsigned int i) const;
  const walker& constraint(unsigned int i) const;

  model_gid* gid_data() const { return gid; }
  void detach_gid();

  void compress_numbers();
  void renumber_variables();
  void renumber_constraints();

private:
  class __docompare_nodes;
  class __docompare_variables;

  class sort_constraints;
  class simplify_visitor_0;
  struct lincoeff_visitor_st;
  struct lincoeff_visitor_ret;
  class lincoeff_visitor;
  struct detect_0chain_visitor_st;
  class detect_0chain_visitor;
#if 0
  class simplify_visitor_thin;
#endif
  
  interval read_interval(char *& cp, int ln);
  void read(std::istream& __i);
  bool children_eq(walker __n1, walker __n2);
  
  bool basic_simplify_0();
  bool basic_simplify_1_merge(walker __s, std::list<walker>& _todo,
                              std::vector<int>& _combined, std::vector<bool>& _fld,
                              std::vector<int>& _sorted);
  void basic_simplify_1_flood(walker __s, std::vector<int>& _combined);
  bool basic_simplify_1_is_ready(walker __s, const std::vector<int>& _combined,
                                 bool all_finished);
  bool basic_simplify_1();
  bool basic_simplify_2();

  void fill_arrays(walker __w, std::vector<walker>& __n,
                   std::vector<walker>& __v, std::vector<walker>& __g);
  void copy_contents(model_gid* gid, const model& __m);
  void prepare_after_read();

public:
  bool basic_simplify();
  void arrange_constraints();
  void detect_0chain();
  bool simplify_thin();
  void set_counters();
  void clr_sky_ground_link();

  void write(std::ostream& __o = std::cout) const;

public:
  ref_iterator ghost_begin() { return ghost_ref.begin(); }
  const_ref_iterator ghost_begin() const { return ghost_ref.begin(); }
  ref_iterator ghost_end() { return ghost_ref.end(); }
  const_ref_iterator ghost_end() const { return ghost_ref.end(); }

  walker store_node(const walker& _w);
  walker store_variable(const walker& _w);
  walker store_ghost(const walker& _w);
  walker store_constraint(const walker& _w);

  void free_node_num(unsigned int _nnum);
  
  void remove_node(const walker& _w, unsigned int _nnum);
  void remove_node(const walker& _w);
  void remove_node(unsigned int __node_num);
  
  void new_variables(int _new_num_of_vars);

  walker ghost(unsigned int _nnum);
  
  walker constant(double _constant);
  walker constant(const std::vector<double>& _constant);

  walker variable(unsigned int _vnum);

  walker binary(const walker& _op1, const walker& _op2, int expr_type,
                double _coeff1 = 1.0, double _coeff2 = 1.0);
  walker binary(const walker& _op1, const walker& _op2, int expr_type,
                additional_info_u _params, double _coeff1 = 1.0,
                double _coeff2 = 1.0);
  
  walker unary(const walker& _op1, int expr_type, double _coeff = 1.0);
  walker unary(const walker& _op1, int expr_type, additional_info_u _params,
      double _coeff = 1.0);

  walker nary(const std::vector<walker>& _op, int expr_type,
              const std::vector<double>& _coeffs = std::vector<double>());
  walker nary(const std::vector<walker>& _op, int expr_type,
              additional_info_u _params,
              const std::vector<double>& _coeffs = std::vector<double>());

  walker vnary(int expr_type, ...);

  bool is_empty(const walker& _w) const;
  walker empty_reference() const;

public:
  const std::string var_name(unsigned int n) const;
  const std::string const_name(unsigned int n) const;
  const std::string obj_name() const;
  double obj_adj() const;
  double obj_mult() const;
  size_t n_fixed_vars() const;
  std::pair<const std::string, double> fixed_var(unsigned int n) const;
  size_t n_unused_vars() const;
  const std::string& unused_var(unsigned int n) const;
  size_t n_unused_constrs() const;
  const std::string& unused_constr(unsigned int n) const;

  bool get_const_num(unsigned int node_num, unsigned int& const_num) const;

public:
  bool get_linear_coeffs(const walker& expr, sparse_vector<double>& coeffs,
      double& constant, const std::vector<interval>& _ranges);
  bool get_linear_coeffs(const walker& expr, sparse_vector<double>& coeffs,
      double& constant);

  friend class dag_delta;
  friend class dag_undelta;
};

class model_iddata
{
private:
  unsigned int node_num_max;
  unsigned int var_num_max;
  unsigned int const_num_max;
  std::vector<int> node_free;            // free list
  std::vector<int> var_free;             // free list
  std::vector<int> const_free;           // free list

  std::list<model_gid*> backref;

  std::vector<std::string> var_names;
  std::vector<std::pair<std::string, double> > fixed_vars;
  std::string obj_names;
  double obj_adjs, obj_mults;

  std::vector<std::string> unused_vars;
  std::vector<std::string> unused_constrs;

  std::vector<std::string> const_names;
public:
  model_iddata(unsigned int n = 0) : node_num_max(0), var_num_max(n),
                                     const_num_max(0), node_free(), var_free(),
                                     const_free(), backref(),
                                     var_names(n, std::string()), fixed_vars(),
                                     obj_names(), obj_adjs(0), obj_mults(1),
                                     unused_vars(), unused_constrs(),
                                     const_names()
     {}

  ~model_iddata() {} 

  void new_ref(model_gid& __m) { backref.push_back(&__m); }
  bool delete_ref(model_gid& __m);

  // get
  unsigned int number_of_nodes() const { return node_num_max; }
  unsigned int number_of_variables() const { return var_num_max; }
  unsigned int number_of_constraints() const { return const_num_max; }
  // set
  void number_of_nodes(unsigned int _n);
  void number_of_variables(unsigned int _n);
  void number_of_constraints(unsigned int _n);

  unsigned int get_node_id();
  void remove_node_id(unsigned int n);
  unsigned int get_var_id();
  void remove_var_id(unsigned int n);
  unsigned int get_const_id();
  void remove_const_id(unsigned int n);
  void compress_numbers(bool renum_vars, bool renum_consts = false);

public:
  const std::string var_name(unsigned int n) const;
  void var_name(unsigned int n, const std::string& vn);

  const std::string const_name(unsigned int n) const;
  void const_name(unsigned int n, const std::string& cn);

  const std::string obj_name() const;
  void obj_name(const std::string& vn);
  double obj_adj() const;
  void obj_adj(double adj);
  double obj_mult() const;
  void obj_mult(double mult);

  size_t n_fixed_vars() const { return fixed_vars.size(); }
  std::pair<const std::string, double> fixed_var(unsigned int n) const;
  void fixed_var(const std::string& vn, double val);

  size_t n_unused_vars() const { return unused_vars.size(); }
  const std::string& unused_var(unsigned int n) const;
  void unused_var(const std::string& vn);
  
  size_t n_unused_constrs() const { return unused_constrs.size(); }
  const std::string& unused_constr(unsigned int n) const;
  void unused_constr(const std::string& vn);
  
  friend class model_gid;
};

class model_gid
{
private:
  model_iddata* _id;
  model& model_ref;
  std::vector<model::walker> glob_ref;   // global (across all deltas) node reference
  std::vector<model::walker> gvar_ref;   // for the full model, and reference to all
                                   // ghost nodes for delta model
  std::vector<model::walker> gconst_ref; // global (across all deltas) constraint reference
  std::map<unsigned int, unsigned int> const_back_ref; // map from node numbers to constraint numbers

private:
  void renumber_nodes(std::vector<std::pair<unsigned int,unsigned int> >& __v);
  void renumber_variables(std::vector<std::pair<unsigned int,unsigned int> >& __v);
  void renumber_constraints(std::vector<std::pair<unsigned int,unsigned int> >& __v);
  void upd_number_of_nodes(unsigned int _n);
  void upd_number_of_variables(unsigned int _n);
  void upd_number_of_constraints(unsigned int _n);

public:
  void remove_node_ref(unsigned int _n)
    { if(glob_ref.size() == _n) glob_ref.pop_back();
      else glob_ref[_n] = model_ref.ground(); }
  void remove_var_ref(unsigned int _n)
    { if(gvar_ref.size() == _n) gvar_ref.pop_back();
      else gvar_ref[_n] = model_ref.ground(); }
  void remove_const_ref(unsigned int _n);

  model_gid(model& __m, model_iddata* __i=NULL) : model_ref(__m), glob_ref(),
                                                  gvar_ref(), gconst_ref(),
                                                  const_back_ref()
    {
      if(__i == NULL)
        _id = new model_iddata;
      else
        _id = __i;
      _id->new_ref(*this);
    }

  model_gid(model& __m, unsigned int n, model_iddata* __i = NULL)
                        : model_ref(__m), glob_ref(), gvar_ref(), gconst_ref(),
                          const_back_ref()
    {
      if(__i == NULL)
        _id = new model_iddata(n);
      else
        _id = __i;
      _id->new_ref(*this);
    }

  model_gid(model& __mr, const model_gid& __m) : _id(__m._id),
                                    model_ref(__mr),
                                    glob_ref(__m.glob_ref),
                                    gvar_ref(__m.gvar_ref),
                                    gconst_ref(__m.gconst_ref),
                                    const_back_ref(__m.const_back_ref)
    {
      _id->new_ref(*this);
      std::vector<model::walker>::iterator __x, __e;
      model::walker mgr(__m.model_ref.ground()), gr(__mr.ground());
      __e = glob_ref.end();
      for(__x = glob_ref.begin(); __x != __e; ++__x)
        if(*__x == mgr)
          *__x = gr;
      __e = gvar_ref.end();
      for(__x = gvar_ref.begin(); __x != __e; ++__x)
        if(*__x == mgr)
          *__x = gr;
      __e = gconst_ref.end();
      for(__x = gconst_ref.begin(); __x != __e; ++__x)
        if(*__x == mgr)
          *__x = gr;
    }

  ~model_gid() { if(_id->delete_ref(*this)) delete _id; }

  unsigned int number_of_nodes() const { return _id->number_of_nodes(); }
  unsigned int number_of_variables() const
        { return _id->number_of_variables(); }
  unsigned int number_of_constraints() const
        { return _id->number_of_constraints(); }
  void number_of_nodes(unsigned int _n) { _id->number_of_nodes(_n); }
  void number_of_variables(unsigned int _n) { _id->number_of_variables(_n); }
  void number_of_constraints(unsigned int _n) {_id->number_of_constraints(_n);}

  void mk_globref(unsigned int n, const model::walker& __w);
  void mk_gvarref(unsigned int n, const model::walker& __w);
  void mk_gconstref(unsigned int n, const model::walker& __w);

  void make_const_back_ref(unsigned int node, unsigned int cnum);
  
  unsigned int get_node_id() { return _id->get_node_id(); }
  void remove_node_id(unsigned int n) { _id->remove_node_id(n); }
  unsigned int get_var_id() { return _id->get_var_id(); }
  void remove_var_id(unsigned int n) { _id->remove_var_id(n); }
  unsigned int get_const_id() { return _id->get_const_id(); }
  void remove_const_id(unsigned int n) { _id->remove_const_id(n); }
  void compress_numbers(bool renumber_vars = false, bool renumber_const = false)
        { _id->compress_numbers(renumber_vars, renumber_const); }

  const model::walker& node(unsigned int i) const { return glob_ref[i]; }
  const model::walker& variable(unsigned int i) const { return gvar_ref[i]; }
  const model::walker& constraint(unsigned int i) const
                                                { return gconst_ref[i]; }

  bool empty(const model::walker& __x) const
        { return __x == model_ref.ground(); }
  bool its_me(const model& __m) const { return &__m == &model_ref; }
  model::walker empty_reference() const { return model_ref.ground(); }

  bool have_glob_ref(unsigned int _nnum) const
        { return _nnum < glob_ref.size(); }
  bool have_gvar_ref(unsigned int _vnum) const
        { return _vnum < gvar_ref.size(); }
  bool have_gconst_ref(unsigned int _cnum) const
        { return _cnum < gconst_ref.size(); }

public:
  const std::string var_name(unsigned int n) const { return _id->var_name(n); }
  void var_name(unsigned int n, const std::string& vn) { _id->var_name(n, vn); }
  void var_name(unsigned int n, const char* vn)
        { _id->var_name(n, std::string(vn)); }

  const std::string const_name(unsigned int n) const
                                                { return _id->const_name(n); }
  void const_name(unsigned int n, const std::string& vn)
                                                { _id->const_name(n, vn); }
  void const_name(unsigned int n, const char* vn)
        { _id->const_name(n, std::string(vn)); }
  bool get_const_num(unsigned int node_num, unsigned int& const_num);

  const std::string obj_name() const { return _id->obj_name(); }
  void obj_name(const std::string& vn) { _id->obj_name(vn); }
  void obj_name(const char* vn) { _id->obj_name(std::string(vn)); }
  double obj_adj() const { return _id->obj_adj(); }
  void obj_adj(double adj) { _id->obj_adj(adj); }
  double obj_mult() const { return _id->obj_mult(); }
  void obj_mult(double mult) { _id->obj_mult(mult); }

  size_t n_fixed_vars() const { return _id->n_fixed_vars(); }
  std::pair<const std::string, double> fixed_var(unsigned int n) const
        { return _id->fixed_var(n); }
  void fixed_var(const std::string& vn, double val) { _id->fixed_var(vn, val); }
  void fixed_var(const char* vn, double val)
        { _id->fixed_var(std::string(vn), val); }
  
  size_t n_unused_vars() const { return _id->n_unused_vars(); }
  const std::string& unused_var(unsigned int n) const
        { return _id->unused_var(n); }
  void unused_var(const std::string& vn) { _id->unused_var(vn); }
  void unused_var(const char* vn) { _id->unused_var(std::string(vn)); }
  
  size_t n_unused_constrs() const { return _id->n_unused_constrs(); }
  const std::string& unused_constr(unsigned int n) const
        { return _id->unused_constr(n); }
  void unused_constr(const std::string& vn) { _id->unused_constr(vn); }
  void unused_constr(const char* vn) { _id->unused_constr(std::string(vn)); }
  
  friend class model_iddata;
};

#include <model-inline.h>

typedef model::walker expression_walker;
typedef model::const_walker expression_const_walker;

#endif /* _MODEL_H_ */

---