dag_delta.cc

Go to the documentation of this file.

// DAG Delta implementation -*- C++ -*-

// $Id: dag_delta.cc 561 2008-04-14 10:49:29Z schilly $
// Copyright (C) 2001-2004 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.

#include <coconut_config.h>
#include <dag_delta.h>
#include <api_debug.h>

namespace coco {

void dag_delta::help_apply_p(work_node& x, expression_walker& _x, model* nm) const
{
  expression_walker _parent, _nonghost;
  unsigned int nn;

  nn = _x->node_num; 
  _nonghost = x.get_model_ptr()->node(nn);
  while(_x.n_parents() > 0)
  {
    _parent = _x << _x.parent_begin();
    if(_parent == nm->ground())
      return; // nothing to do here
    if(_nonghost.is_root())
      x.get_model_ptr()->remove_edge_and_deattach(x.get_model_ptr()->ground(),
          _nonghost);
    nm->replace_edge_to_child(_parent, _x, _nonghost);
    _nonghost->n_parents++;
  }
}

void dag_delta::help_apply_s(work_node& x, model* nm) const
{
  expression_walker _w, _x(nm->sky());
  std::vector<expression_walker> __v;

  while(_x.n_parents() > 0)
  {
    _w = _x << _x.parent_begin();
    if(_w == nm->ground())
      break; // nothing to do here
    nm->remove_edge_and_deattach(_w, _x);
    __v.push_back(_w);
  }
  for(std::vector<expression_walker>::iterator __m = __v.begin(); __m != __v.end();
      ++__m)
    x.get_model_ptr()->add_edge_back(*__m, x.get_model_ptr()->sky());
}

void dag_delta::help_apply_c(work_node& x, expression_walker& _x, model* nm) const
{
  expression_walker _child, _nonghost;
  unsigned int nn;

  nn = _x->node_num; 
  _nonghost = x.get_model_ptr()->node(nn);
  while(_x.n_children() > 0)
  {
    _child = _x << _x.child_begin();
    if(_child == nm->sky())
      return; // nothing to do here
    if(_nonghost.is_leaf())
      x.get_model_ptr()->remove_edge_and_deattach(_nonghost,
          x.get_model_ptr()->sky());
    nm->replace_edge_to_parent(_x, _nonghost, _child);
    _nonghost->n_children++;
  }
}

void dag_delta::help_apply_g(work_node& x, model* nm) const
{
  expression_walker _w, _x(nm->ground());
  std::vector<expression_walker> __v;

  while(_x.n_children() > 0)
  {
    _w = _x >> _x.child_begin();
    if(_w == nm->sky())
      break;
    nm->remove_edge_and_deattach(_x, _w);
    __v.push_back(_w);
  }
  for(std::vector<expression_walker>::iterator __m = __v.begin(); __m != __v.end();
      ++__m)
    x.get_model_ptr()->add_edge_back(x.get_model_ptr()->ground(), *__m);
}

bool dag_delta::apply(work_node& x, undelta_base*& u, const delta_id& _did) const
{ 
  expression_walker _x;
  unsigned int nn;

  if(is_full_delta)
  {
    if(!new_constraints.get() || new_constraints->empty()) return true;
    
    model* nm = new model(*new_constraints);
    gptr<model>* old_model = x._m;

    x._m = new ptr<model>(nm);
    x.make_node_ranges(false);
    x.make_node_order();
    x.init_cnumbers();
    u = (undelta_base*) new dag_undelta(old_model);
    return true;
  }
  else
  {
    dag_undelta *uu;
    model* xm = x.get_model_ptr();
    model* nm(NULL);
    u = (undelta_base*) (uu = new dag_undelta(false));

    if(new_constraints.get() && !new_constraints->empty())
    {
      std::vector<unsigned int> addnod, addvar, addgh, addcnst;
      model::ref_iterator _xic, _xie;

      nm = new model(xm->gid_data(), *new_constraints);

      addnod.reserve(nm->node_ref.size());
      for(_xie = nm->node_ref.end(), _xic = nm->node_ref.begin(); _xic != _xie;
          ++_xic)
        addnod.push_back((*_xic)->node_num);
      addvar.reserve(nm->var_ref.size());
      for(_xie = nm->var_ref.end(), _xic = nm->var_ref.begin(); _xic != _xie;
          ++_xic)
        addvar.push_back((*_xic)->node_num);
      addgh.reserve(nm->ghost_ref.size());
      for(_xie = nm->ghost_ref.end(), _xic = nm->ghost_ref.begin(); _xic != _xie;
          ++_xic)
        addgh.push_back((*_xic)->node_num);
      addcnst.reserve(nm->constraints.size());
      for(_xie = nm->constraints.end(), _xic = nm->constraints.begin(); _xic != _xie;
          ++_xic)
        addcnst.push_back((*_xic)->node_num);
#if __DEBUG_DAG_DELTA
      std::cout << "After model-copy: start" << std::endl;
      nm->write();
      std::cout << "After model-copy: end" << std::endl;
#endif
      // first add the new constraints
      // we do not duplicate all nodes in new_constraints
      // we rather remove all the edges to the ghost nodes and
      // replace them with edges to the real nodes.
      for(model::ref_iterator __x = nm->ghost_begin();
          __x != nm->ghost_end(); ++__x)
      {
        _x = *__x;
        // change the f_bounds according to the ghosts and keep old bounds
        if(!_x->f_bounds.is_entire())
        {
          uu->bounds_chgd[_x->node_num] = xm->node(_x->node_num)->f_bounds;
          xm->node(_x->node_num)->f_bounds.intersectwith(_x->f_bounds);
        }
        help_apply_p(x, _x, nm);
        help_apply_c(x, _x, nm);
      }
#if __DEBUG_DAG_DELTA
      std::cout << "Removing GHOSTS!" << std::endl;
#endif
      // remove ghosts
      for(model::ref_iterator __x = nm->ghost_begin();
          __x != nm->ghost_end(); __x = nm->ghost_begin())
      {
#if __DEBUG_DAG_DELTA
        std::cout << "Removing GHOST " << (*__x)->node_num;
#endif
        nm->remove_node(*__x);
#if __DEBUG_DAG_DELTA
        std::cout << " : " << nm->ground().n_children() << std::endl;
#endif
      }
      
      help_apply_s(x, nm);
      help_apply_g(x, nm);

      x.reset_node_ranges();

      uu->added_nodes.reserve(addnod.size());
      for(std::vector<unsigned int>::iterator _xit = addnod.begin();
          _xit != addnod.end(); ++_xit)
        uu->added_nodes.push_back(xm->node(*_xit));
      uu->added_constraints.reserve(addcnst.size());
      for(std::vector<unsigned int>::iterator _xit = addcnst.begin();
          _xit != addcnst.end(); ++_xit)
        uu->added_constraints.push_back(xm->node(*_xit));
      std::sort(uu->added_constraints.begin(), uu->added_constraints.end(),
                model::__docompare_nodes());
#if 0
      uu->added_ghosts.reserve(addgh.size());
      for(std::vector<unsigned int>::iterator _xit = addgh.begin();
          _xit != addgh.end(); ++_xit)
        uu->added_ghosts.push_back(xm->ghost(*_xit));
#else
      uu->added_ghosts.clear();
#endif
      uu->added_vars.reserve(addvar.size());
      for(std::vector<unsigned int>::iterator _xit = addvar.begin();
          _xit != addvar.end(); ++_xit)
        uu->added_vars.push_back(xm->node(*_xit));

      // transfer node refs
      std::vector<expression_walker>& nr(xm->node_ref);
      nn = nr.size();
      nr.insert(nr.end(), nm->node_ref.begin(), nm->node_ref.end());
          inplace_merge(nr.begin(), nr.begin()+nn, nr.end(),
                    model::__docompare_nodes());
      
      // transfer variable refs
      std::vector<expression_walker>& vr(xm->var_ref);
      nn = vr.size();
      vr.insert(vr.end(), nm->var_ref.begin(), nm->var_ref.end());
      inplace_merge(vr.begin(), vr.begin()+nn, vr.end(),
                    model::__docompare_variables());
      
      // transfer ghost refs
      std::vector<expression_walker>& gr(xm->ghost_ref);
      nn = gr.size();
      gr.insert(gr.end(), nm->ghost_ref.begin(), nm->ghost_ref.end());
      inplace_merge(gr.begin(), gr.begin()+nn, gr.end(),
                    model::__docompare_nodes());
      
      xm->constraints.insert(xm->constraints.end(), nm->constraints.begin(),
                             nm->constraints.end());

      /***********************************************************
       *
       * ATTENTION: Here the proper change of lin, matd, and mati
       *            is still missing!
       *
       ***********************************************************/
    }

    if(!rm_nodes.empty())
    {
      model::erased_part me = xm->erase_minimal_subgraph(rm_nodes);
      uu->rm_dag = new model(xm->gid_data(), me);
      uu->rm_e = me.second;

      // remove the elements taken out from the arrays
      std::vector<walker> _nn;
      std::swap(_nn, xm->node_ref);
      std::set_difference(_nn.begin(), _nn.end(), uu->rm_dag->node_ref.begin(),
                          uu->rm_dag->node_ref.end(),
                          back_inserter(xm->node_ref),
                          model::__docompare_nodes());

      _nn.erase(_nn.begin(), _nn.end());
      std::swap(_nn, xm->var_ref);
      std::set_difference(_nn.begin(), _nn.end(), uu->rm_dag->var_ref.begin(),
                          uu->rm_dag->var_ref.end(), back_inserter(xm->var_ref),
                          model::__docompare_variables());

      _nn.erase(_nn.begin(), _nn.end());
      std::swap(_nn, xm->ghost_ref);
      std::set_difference(_nn.begin(), _nn.end(), uu->rm_dag->ghost_ref.begin(),
                          uu->rm_dag->ghost_ref.end(),
                          back_inserter(xm->ghost_ref),
                          model::__docompare_nodes());

      // get rid of the constraints taken out
      std::vector<walker>::iterator _i =
           std::stable_partition(xm->constraints.begin(), xm->constraints.end(),
                     __check_nodes(uu->rm_dag->node_ref));
      std::copy(_i, xm->constraints.end(), uu->rm_dag->constraints.end());
      xm->constraints.erase(_i, xm->constraints.end());

      /***********************************************************
       *
       * ATTENTION: Here the proper change of lin, matd, and mati
       *            is still missing!
       *
       ***********************************************************/

      x.reset_node_ranges();
    }
    else if(nm)
      uu->rm_dag = new model(xm->gid_data());

    if(nm)
    {
      uu->rm_dag->objective = xm->objective;
      if(!nm->is_empty(nm->objective))
        xm->objective = nm->objective;
        
      uu->rm_dag->ocoeff = xm->ocoeff;
      if(nm->ocoeff != MAXINT)
        xm->ocoeff = nm->ocoeff;
    }

    x.make_node_ranges(true);
    x.make_node_order();
    x.init_cnumbers();
    if(nm)
    {
       nm->add_edge_back(nm->ground(),nm->sky());
       delete nm;
    }
    return true;
  }
}

bool dag_undelta::unapply(work_node& x, const delta_id& _did) const
{
  if(is_full_undelta)
  {
    x._m = old_model;
    x.make_node_ranges(false);
    x.make_node_order();
    x.init_cnumbers();
    return true;
  }
  else
  {
    model* xm = x.get_model_ptr();

    // restore deleted parts
    std::vector<model::enhanced_edge>::const_iterator eei, eee(rm_e.end());

    // reconstruct edges
    for(eei = rm_e.begin(); eei != eee; ++eei)
    {
      if((*eei).second)
      {
        if((*eei).first.second.is_root())
          xm->remove_edge(xm->ground(), (*eei).first.second);
        if((*eei).first.first.is_leaf())
          xm->remove_edge((*eei).first.first, xm->sky());
      }
      xm->add_edge_back((*eei).first.first, (*eei).first.second);
    }
    // now we detach all nodes from rm_dag
    if(rm_dag.get() && !rm_dag->empty())
    {
      expression_walker _sg(rm_dag->sky());
      for(model::parents_iterator _w = _sg.parent_begin();
          _w != _sg.parent_end(); ++_w)
        rm_dag->remove_edge_and_deattach(_sg << _w, _sg);
      _sg = rm_dag->ground();
      for(model::children_iterator _w = _sg.child_begin();
          _w != _sg.child_end(); ++_w)
        rm_dag->remove_edge_and_deattach(_sg, _sg >> _w);
      rm_dag->add_edge_back(rm_dag->ground(), rm_dag->sky());
    }

    // first correct all global references
    std::vector<expression_walker>::const_iterator __x, __e;
    for(__x = added_nodes.begin(), __e = added_nodes.end(); __x != __e; ++__x)
      xm->gid_data()->mk_globref((*__x)->node_num, xm->empty_reference());
    for(__x = added_vars.begin(), __e = added_vars.end(); __x != __e; ++__x)
      xm->gid_data()->mk_gvarref((*__x)->params.nn(), xm->empty_reference());
    unsigned int const_num;
    for(__x = added_constraints.begin(), __e = added_constraints.end();
        __x != __e; ++__x)
    {
      bool ok = xm->gid_data()->get_const_num((*__x)->node_num, const_num);
      if(ok)
        xm->gid_data()->remove_const_ref(const_num);
    }
    
    // remove all previously added nodes
    model::erased_part me(xm->erase_minimal_subgraph(added_nodes));

    if(!added_nodes.empty())
    {
      // remove the elements previously added
      std::vector<walker> _nn;
      std::swap(_nn, xm->node_ref);
      std::set_difference(_nn.begin(), _nn.end(), added_nodes.begin(),
                          added_nodes.end(), back_inserter(xm->node_ref),
                          model::__docompare_nodes());
    }

    std::vector<expression_walker> _nn;
    if(!added_vars.empty())
    {
      _nn.erase(_nn.begin(), _nn.end());
      std::swap(_nn, xm->var_ref);
      std::set_difference(_nn.begin(), _nn.end(), added_vars.begin(),
                          added_vars.end(), back_inserter(xm->var_ref),
                          model::__docompare_variables());
    }

    if(!added_ghosts.empty())
    {
      _nn.erase(_nn.begin(), _nn.end());
      std::swap(_nn, xm->ghost_ref);
      std::set_difference(_nn.begin(), _nn.end(), added_ghosts.begin(),
                          added_ghosts.end(), back_inserter(xm->ghost_ref),
                          model::__docompare_nodes());
    }

    if(!added_constraints.empty())
    {
      // get rid of the constraints previously added
      std::vector<walker>::iterator _i =
           std::stable_partition(xm->constraints.begin(), xm->constraints.end(),
                                 __check_walkers(added_constraints));
      xm->constraints.erase(_i, xm->constraints.end());
    }
    
    xm->clear_erased_part(me);

    // restore the old f_bounds of all changed nodes
    for(std::map<unsigned int, interval>::const_iterator __b = 
        bounds_chgd.begin(); __b != bounds_chgd.end(); ++__b)
      xm->node(__b->first)->f_bounds = __b->second;

    x.get_model()->set_counters();
    x.make_node_order();

    return true;
  }
}

} // namespace coco

---