main page namespaces classes files
ELL home

src/ell/Walk.cc

Go to the documentation of this file.

#include "ell/Walk.hh"
#include <biu/assertbiu.hh>


namespace ell
{

//STATIC Walk::walk function    
    StateCollector* 
    Walk::walk(
                const State* const start, 
                StateCollector* const scWalk,
                const NeighborGenerator* const ng, 
                const StateAcceptor* const sa, 
                const WalkAbortionCriterion* const wac,
                StateCollector* const scRej
                )
    {
        scWalk->add(*start);
        State* lastAccepted = NULL;
        
        while (!wac->abort(scWalk)) 
        {
              // clone pointer of last accepted state to ensure that the
              // neighbor list is still available when scWalk is updated
            lastAccepted = scWalk->getLastAdded()->clone();
            
            State::NeighborListPtr neighbors = ng->getNeighborList(lastAccepted);
            State::NeighborList::Iterator it = neighbors->begin();
            
            bool go = false;
            // find new neighbor
            while (neighbors->end() != it && !go) 
            {               
                if (sa->accept(scWalk, *it)) 
                {
                    scWalk->add(*it);
                    go = true;
                }
                else if (scRej!=NULL) {
                    scRej->add(*it);
                }
                ++it;
            }
            
             // clear memory
            if (lastAccepted != NULL)  {
                delete lastAccepted;
                lastAccepted = NULL;
            }
                
            if (!go) {
                // didn't find new neighbor
                break;
            }
        }
        
        return scWalk;
    }


    

// WalkAdaptive Constructor 
    WalkAdaptive::WalkAdaptive(const NeighborGenType ngt, const bool isDeg_) 
        : t(ngt), isDeg(isDeg_) { }

// STATIC walkAdaptive function of WalkAdaptive class
    StateCollector* 
    WalkAdaptive::walkAdaptive(
            const State* const s,
            StateCollector* const scWalk,
            const NeighborGenType t,
            StateCollector* const scRej,
            const bool isDegenerate) 
    {
        // Decide which kind of NeighborGenerator to use
        NeighborGenerator* ng;
        switch (t) {
            case RANDOM:
                ng = new NG_SuccessiveRandom();
                break;
            case SUCCESSIVE:
                ng = new NG_Successive();
                break;
            default:
                assertbiu(false, "NeighborGenType not supported");
                break;
        }
        
        StateAcceptor * sa = NULL;
          // check if degenerate landscape model is given and comparison on 
          // energy is not sufficient
        if (isDegenerate) {
              // Succesor State must have lesser energy or if energy is equal
              // is has to be lexicographically less in compressed representation
            sa = new SA_EC_Le();
        } else {
              // Succesor State must have lesser energy
            sa = new SA_E_Le();
        }
        
        // An adaptive walk is always finished at a local minimum,
        // there is no additional abortion criterion
        WalkAbortionCriterion* wac = new WAC_OpenEnd();
        
        // call generic walk function
        Walk::walk(s, scWalk, ng, sa, wac, scRej);
        
        delete ng;
        delete sa;
        delete wac;
        
        return scWalk;
    }

// VIRTUAL const walk function of WalkAdaptive class
    StateCollector* 
    WalkAdaptive::walk (const State* const s, 
                        StateCollector* const sc,
                        StateCollector* const scRej) 
    const
    {
        // call static function
        return WalkAdaptive::walkAdaptive(s, sc, this->t, scRej, this->isDeg);
    }; 

    
    
    
// WalkAdaptive Constructor 
    WalkGradient::WalkGradient(const bool isDeg_) 
        : isDeg(isDeg_) { }

//static    
    StateCollector* 
    WalkGradient::walkGradient(
            const State* const start, 
            StateCollector* const scWalk,
            const bool isDegenerate) 
    {
          // add start to walk
        scWalk->add(*start);
          // temporary pointers to perform gradient walk
        State * lastAdded = NULL;
        State * bestNeigh = NULL;
        
        do {
            
              // clone pointer of last accepted state to ensure that the
              // neighbor list is still available when scWalk is updated
            lastAdded = scWalk->getLastAdded()->clone();

              // treshold of best energy found so far
            double minEfound = lastAdded->getEnergy(), lastE = 0.0;
            
            State::NeighborListPtr neighbors = lastAdded->getNeighborList();
            State::NeighborList::Iterator it = neighbors->begin();

            // look for best neighbor
            if (bestNeigh != NULL) {
                delete bestNeigh;
                bestNeigh = NULL;
            }
            while (neighbors->end() != it) {
                if ( (lastE = it->getEnergy()) < minEfound
                     || (isDegenerate  // use compressed repr. as a tiebreaker for equal E
                             && lastE == minEfound
                             && it->compress() < lastAdded->compress()) ) 
                {
                    if (bestNeigh != NULL)
                        delete bestNeigh;
                    bestNeigh = it->clone();
                    minEfound = lastE;
                }
                ++it;
            }
            
            if (bestNeigh != NULL) {
                // found new gradient neighbor 
                scWalk->add(*bestNeigh);
            }

              // clear memory
            delete lastAdded;
 
        } while (bestNeigh != NULL);  // have found local minimum
        
        return scWalk;
    }
    
// virtual
    StateCollector* 
    WalkGradient::walk(
            const State* const start, 
            StateCollector* const scWalk,
            StateCollector* const scRej) 
    const
    {
        // call static function
        return WalkGradient::walkGradient(start, scWalk, this->isDeg);
    }
    
    
// constructor
    WalkMC::WalkMC( 
            const WalkAbortionCriterion* const wac, 
            const double beta) 
        : wac(wac) , beta(beta) {
    }
    
// static
StateCollector* 
    WalkMC::walkMC(
            const State* const start, 
            StateCollector* const sc, 
            const WalkAbortionCriterion* const wac, 
            const double beta,
            StateCollector* const scRej) 
    {
        NeighborGenerator* ng = new NG_Random();

        // Successor State is admitted using Metropolis criterion
        StateAcceptor* sa = new SA_Metropolis(beta);

        Walk::walk(start, sc, ng, sa, wac, scRej);

        delete ng;
        delete sa;

        return sc;
    }
    
// virtual
    StateCollector* 
    WalkMC::walk(
            const State* const start, 
            StateCollector* const sc,
            StateCollector* const scRej)
    const
    {
        // call static function
        return WalkMC::walkMC(start, sc, this->wac, this->beta, scRej);
    }
    
    
    WalkRandom::WalkRandom(
            const WalkAbortionCriterion* const wac_
            )
        : wac(wac_)
    {
    }

// static
    StateCollector* 
    WalkRandom::walkRandom(
            const State* const start, 
            StateCollector* const sc,
            const WalkAbortionCriterion* const wac, 
            StateCollector* const scRej)
    {
        NeighborGenerator* ng = new NG_SuccessiveRandom();
        // accept all states = random walk
        StateAcceptor* sa = new SA_All(); 
        
        Walk::walk(start, sc, ng, sa, wac, scRej);
        
        delete sa;
        delete ng;
        
        return sc;
    }   

// virtual
    StateCollector* 
    WalkRandom::walk(
            const State* const start, 
            StateCollector* const sc,
            StateCollector* const scRej)
    const
    {
        // call static function
        return WalkRandom::walkRandom(start, sc, this->wac, scRej);
    }   
    

}// namespace ell