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;
        bool foundNext = true;
        
        while (foundNext && !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(lastAccepted);
            
            State::NeighborListPtr neighbors = ng->getNeighborList(lastAccepted);
            State::NeighborList::Iterator it = neighbors->begin();
            
            foundNext = false;
            // find new neighbor
            while (neighbors->end() != it) 
            {               
                if (sa->accept(scWalk, *it)) 
                {
                    scWalk->add(*it);
                    foundNext = true;
                    break;
                }
                else if (scRej!=NULL) {
                    scRej->add(*it);
                }
                ++it;
            }
            
        }
        
         // clear memory
        if (lastAccepted != NULL)  {
            delete lastAccepted;
        }
        
        return scWalk;
    }


    

// WalkAdaptive Constructor 
    WalkAdaptive::WalkAdaptive(const NeighborGenType ngt) 
        : t(ngt)
    { }

// STATIC walkAdaptive function of WalkAdaptive class
    StateCollector* 
    WalkAdaptive::walkAdaptive(
            const State* const s,
            StateCollector* const scWalk,
            const NeighborGenType t,
            StateCollector* const scRej
            ) 
    {
        // 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;
        }
        
          // Succesor State must be smaller according to State ordering
        SA_Le sa;
        
        // An adaptive walk is always finished at a local minimum,
        // there is no additional abortion criterion
        WAC_OpenEnd wac;
        
        // call generic walk function
        Walk::walk(s, scWalk, ng, &sa, &wac, scRej);
        
        delete ng;
        
        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);
    }

    
    
    
// WalkAdaptive Constructor 
    WalkGradient::WalkGradient() 
    { }

//static    
    StateCollector* 
    WalkGradient::walkGradient(
            const State* const start, 
            StateCollector* const scWalk
            ) 
    {
          // add start to walk
        scWalk->add(*start);
          // temporary pointers to perform gradient walk
        const State * lastAdded = NULL;
        State * bestNeigh = NULL;
        
        do {
            
              // pointer of last accepted state to ensure that the
              // neighbor list is still available when scWalk is updated
            lastAdded = scWalk->getLastAdded();
            assertbiu(lastAdded != NULL, "no last element in StateCollector");
              // treshold of best energy found so far
            double minEfound = lastAdded->getEnergy();
            
            State::NeighborListPtr neighbors = lastAdded->getNeighborList();
            State::NeighborList::Iterator it = neighbors->begin();

            // look for best neighbor
            bestNeigh = lastAdded->clone(bestNeigh);
            while (neighbors->end() != it) {
                if ( it->operator<(*bestNeigh) ) 
                {
                    bestNeigh = it->clone(bestNeigh);
                    minEfound = bestNeigh->getEnergy();
                }
                ++it;
            }
            
            if (State::less(bestNeigh,lastAdded)) {
                // found new gradient neighbor 
                scWalk->add(*bestNeigh);
            } else {
                delete bestNeigh;
                bestNeigh = NULL;
            }
        } 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);
    }
    
    
// constructor
    WalkMC::WalkMC( 
            const WalkAbortionCriterion* const wac_, 
            const double kT_) 
        : wac(wac_) , kT(kT_) {
    }
    
// static
StateCollector* 
    WalkMC::walkMC(
            const State* const start, 
            StateCollector* const sc, 
            const WalkAbortionCriterion* const wac, 
            const double kT,
            StateCollector* const scRej) 
    {
        NG_Random ng;

        // Successor State is admitted using Metropolis criterion
        SA_Metropolis sa(kT);

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

        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->kT, 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)
    {
        NG_SuccessiveRandom ng;
        // accept all states = random walk
        SA_All sa; 
        
        Walk::walk(start, sc, &ng, &sa, wac, scRej);
        
        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