main page namespaces classes files
CPSP home

src/cpsp/gecode/symm-break.icc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Sebastian Will http://www.bioinf.uni-freiburg.de/~will/
 *
 *  Contributing authors:
 *     Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/
 *
 *  Copyright:
 *     Sebastian Will, 2007
 *
 *  This file is part of the CPSP-tools package:
 *     http://www.bioinf.uni-freiburg.de/sw/cpsp/
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */


#include <gecode/kernel.hh>

namespace Gecode {

   namespace Search {

       /*
    * Symmetry Breaker
    *
    */

       template<class View, class Val>
       void
       SymmBreaker<View,Val>::updateCps(Space *home, ViewArray<View> &x, int pos, Val val) {
       
       BoolVarArray new_cps(home,cps.size(),0,1);
       
       for (int i=0; i<cps.size(); i++) {
           BoolVar sc = reifySymm(home,symOf[i],x,pos,val);
           new_cps[i] = post(home, cps[i] && sc);
       }
       cps = new_cps; // overwrite cps with new cp
       }
              
       template<class View, class Val>
       void
       SymmBreaker<View,Val>::postImplications(Space *home, ViewArray<View> &x, int pos, Val val) const {
       for (int i=0; i<cps.size(); i++) {
           BoolVar sc = reifySymm(home,symOf[i],x,pos,val);
           //post( home, imp(cps[i], sc==0));
           // alternative:
           BoolVar negSc(home,0,1);
           bool_not( home, sc, negSc);
           bool_imp( home, cps[i], negSc, true );
       }
       }

       template<class View, class Val>
       void SymmBreaker<View,Val>::tell(Space *home, int a, ViewArray<View> &x, int pos, Val val) {
       //std::cout <<"tell: "<< a << " " << pos << " " << val << std::endl;
       if (a==0) {
           tellSymm(home,0,x,pos,val);  // apply identity "symmetry"
           updateCps(home,x,pos,val);
       } else {
           postImplications(home,x,pos,val);
       }
       }

       template<class View, class Val>
       void
       SymmBreaker<View,Val>::print(void) const {
       std::cout << "Cps: { ";
       for (int i = 0; i < cps.size(); i++) {
           std::cout << cps[i] << ", ";
           if ((i+1) % 15 == 0)
           std::cout << std::endl << "\t       ";
       }
       std::cout << "};" << std::endl;
       }



  /*
   * Generic branching based on variable/value selection
   *
   */

  template <class View, class Val, class ViewSel, class ValSel, class SymmBreaker>
  forceinline
  SBViewValBranching<View,Val,ViewSel,ValSel,SymmBreaker>
  ::SBViewValBranching(Space* home, ViewArray<View>& x0)
    : ViewValBranching<View,Val,ViewSel,ValSel>(home,x0), symmetries(home) {
  }

  template <class View, class Val, class ViewSel, class ValSel, class SymmBreaker>
  forceinline
  SBViewValBranching<View,Val,ViewSel,ValSel,SymmBreaker>
  ::SBViewValBranching(Space* home, ViewArray<View>& x0, SymmBreaker &sym)
    : ViewValBranching<View,Val,ViewSel,ValSel>(home,x0), symmetries(sym) {
  }


  template <class View, class Val, class ViewSel, class ValSel, class SymmBreaker>
  forceinline
  SBViewValBranching<View,Val,ViewSel,ValSel,SymmBreaker>
  ::SBViewValBranching(Space* home, bool share, SBViewValBranching& b)
    : ViewValBranching<View,Val,ViewSel,ValSel>(home,share,b),
      symmetries(home,share,b.symmetries)
  {
      //std::cout << "Copy construct SBViewValBranching"<<std::endl;
  }

  template <class View, class Val, class ViewSel, class ValSel, class SymmBreaker>
  Actor*
  SBViewValBranching<View,Val,ViewSel,ValSel,SymmBreaker>::copy(Space* home, bool share) {
    return new (home)
      SBViewValBranching<View,Val,ViewSel,ValSel,SymmBreaker>(home,share,*this);
  }

  template <class View, class Val, class ViewSel, class ValSel, class SymmBreaker>
  bool
  SBViewValBranching<View,Val,ViewSel,ValSel,SymmBreaker>
  ::status(const Space *home) const {
      
      if ( ! symmetries.status(home) ) return false;
      
      return ViewValBranching<View,Val,ViewSel,ValSel>::status(home);
  }


  template <class View, class Val, class ViewSel, class ValSel, class SymmBreaker>
  ExecStatus
  SBViewValBranching<View,Val,ViewSel,ValSel,SymmBreaker>
  ::commit(Space* home, const BranchingDesc* d, unsigned int a) {
    const PosValDesc<Val>* pvd = static_cast<const PosValDesc<Val>*>(d);
    

    // The base class ViewValBranching<View,Val,ViewSel,ValSel> drops assigned views at the beginning of
    // the view array during the enumeration.
    // We turn this off!
    // The position described by pvd is pvd->pos()+pvd->start() !
    // (The latter changed in the dds branch since 1.3.0)
    
    // Eliminate views from x[0] ... x[start-1]
    // x.drop_fst(pvd->start()); start = 0;
//    symmetries.tell(home,a,ViewValBranching<View,Val,ViewSel,ValSel>::x,pvd->pos()+pvd->start(),pvd->val());
    symmetries.tell(home,a,ViewValBranching<View,Val,ViewSel,ValSel>::x,pvd->pos(),pvd->val());
    return ES_OK;
  }
  
  
  

} // namespace Search

} // namespace Gecode

// STATISTICS: kernel-other