main page namespaces classes files
CPSP home

src/cpsp/gecode/old_GC_Neighbored2.cc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Martin Mann http://www.bioinf.uni-freiburg.de/~mmann/
 *
 *  Contributing authors:
 *     Sebastian Will http://www.bioinf.uni-freiburg.de/~will/
 *
 *  Copyright:
 *     Martin Mann, 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 "cpsp/gecode/GC_Neighbored2.hh"
#include "cpsp/gecode/GC_StlSetRangeIterator.hh"

#include <biu/assertbiu.hh>
namespace cpsp
{
  namespace gecode
  {


  const unsigned int GC_Neighbored2::MAXPROPSIZEINIT = 50;

    
  GC_Neighbored2::GC_Neighbored2(   Gecode::Space* home, 
                                Gecode::Int::IntView x0, 
                                Gecode::Int::IntView x1,
                                const biu::LatticeFrame* lattice_,
                                Gecode::IntConLevel conLvl,
                                unsigned int maxPrSize,
                                bool maxPrSizeBin,
                                unsigned int minPrSize)
    : GC_BinProp(home,x0,x1),
        lattice(lattice_), conLevel(conLvl), maxPropSize(maxPrSize),
        maxPropSizeBin(maxPrSizeBin), minPropSize(minPrSize)
  {
    assertbiu(lattice != NULL, "static lattice variable not initialised");
    neighborhood = lattice->getIndexedNeighborhood();
    
        // maxPropSize initialisieren
    switch (conLevel) {
        case Gecode::ICL_VAL    : maxPropSize = 1; break;
        case Gecode::ICL_DOM    : maxPropSize = UINT_MAX; break;
        case Gecode::ICL_DEF    : conLevel = Gecode::ICL_BND;
        case Gecode::ICL_BND    :
        default                 : ;     // maxPropSize init already done 
    }
  }

  GC_Neighbored2::GC_Neighbored2(   Gecode::Space* home, 
                                bool share, 
                                GC_Neighbored2& p) :
        GC_BinProp(home,share,p),
        lattice(p.lattice), 
        neighborhood(p.neighborhood),
        conLevel(p.conLevel),
        maxPropSize(p.maxPropSize),
        maxPropSizeBin(p.maxPropSizeBin),
        minPropSize(p.minPropSize)
  {}

  Gecode::ExecStatus
  GC_Neighbored2::post( Gecode::Space* home, 
                        Gecode::Int::IntView x0, Gecode::Int::IntView x1, 
                        const biu::LatticeFrame* lattice,
                        Gecode::IntConLevel conLvl,
                        unsigned int maxPrSize,
                        bool maxPrSizeBin,
                        unsigned int minPrSize)
  {
    if (same(x0,x1)) {
        return Gecode::ES_FAILED;
    } else {
        (void) new (home) GC_Neighbored2(   home,x0,x1,lattice, conLvl, 
                                            maxPrSize, maxPrSizeBin, minPrSize);
    }
    return Gecode::ES_OK;
  }


  Gecode::Actor*
  GC_Neighbored2::copy(Gecode::Space* home, bool share) {
    return new (home) GC_Neighbored2(home,share,*this);
  }

    /*
        PC_CRAZY_LO     Exponential complexity, cheap.
        PC_CRAZY_HI     Exponential complexity, expensive.
        PC_CUBIC_LO     Cubic complexity, cheap.
        PC_CUBIC_HI     Cubic complexity, expensive.
        PC_QUADRATIC_LO Quadratic complexity, cheap.
        PC_QUADRATIC_HI Quadratic complexity, expensive.
        PC_LINEAR_HI    Linear complexity, expensive.
        PC_LINEAR_LO    Linear complexity, cheap.
        PC_TERNARY_HI   Three variables, expensive.
        PC_BINARY_HI    Two variables, expensive.
        PC_TERNARY_LO   Three variables, cheap.
        PC_BINARY_LO    Two variables, cheap.
        PC_UNARY_LO     Only single variable, cheap.
        PC_UNARY_HI     Only single variable, expensive.
        PC_MAX          Maximal cost value.
    */
  Gecode::PropCost
  GC_Neighbored2::cost(void) const {
    if (x0.assigned() || x1.assigned()) {
        return Gecode::PC_LINEAR_HI;
    } 
    return Gecode::PC_QUADRATIC_HI;
  }

  Gecode::ExecStatus
  GC_Neighbored2::propagate(Gecode::Space* home) {
//      std::cout <<"vorher : "<<x0 <<" / " <<x1 <<std::endl;
        // pruefe ob minimale propagationsschranke erreicht
    if (x0.size() < minPropSize && x1.size() < minPropSize)
        return Gecode::ES_SUBSUMED;
        
    Gecode::ModEvent ret = Gecode::ME_GEN_NONE;
    if (x0.assigned()) {
        ret = removeNonNeighbors(home,x1,x0.val());
    }else if (x1.assigned()) {
        ret = removeNonNeighbors(home,x0,x1.val());
    } else {
        ret = removeNonNeighbors(home);
    }
//      std::cout <<"danach : "<<x0 <<" / " <<x1 <<std::endl;
        // pruefen auf ME_GEN_FAILED
    GECODE_ME_CHECK(ret);

    return (ret ==  Gecode::ME_GEN_ASSIGNED 
                ?   Gecode::ES_SUBSUMED
                :   Gecode::ES_FIX);
  }
  
    Gecode::ModEvent 
    GC_Neighbored2::removeNonNeighbors( Gecode::Space* home, 
                                        Gecode::Int::IntView& x, 
                                        int center) 
    {
        biu::IndexSet data = getIndexedNeighbors(center);
        GC_StlSetRangeIterator dataIt(&data);
        return x.inter(home, dataIt);
    }
    
    Gecode::ModEvent 
    GC_Neighbored2::removeNonNeighbors(Gecode::Space* home) {


            // a wird referenz auf kleinere domain
        Gecode::Int::IntView* a = &x0, *b = &x1;
        if(a->size() > b->size()) {
            a = &x1, b = &x0;
        }
        
            // wenn minimale domain noch zu gross fuer propagationslevel
            // oder wenn beide gefordert mindestens eine zu gross
            // dann abbruch der propagation
        if (    a->size() > maxPropSize 
                || (maxPropSizeBin && b->size() > maxPropSize) ) 
        {
            return Gecode::ME_GEN_NONE;     // nixs passiert
        }
        
            // alte groessen der variablen
        unsigned int aSize = a->size(), bSize = b->size();

            // aenderungsstatus der variablen
        Gecode::ModEvent    aStat = Gecode::ME_GEN_NONE, 
                            bStat = Gecode::ME_GEN_NONE;
        
            // a domain einschraenken und neue b domain (newDom) aufbauen
        Gecode::Int::ViewValues<Gecode::Int::IntView> aIt(*a);
        biu::IndexSet newDom, actNeighs, toRem;
        biu::IndexSet::const_iterator neigh;
        bool noNeighInB = true;
        while(aIt()) {  // laufe durch alle elemente von a
                // init
            actNeighs = getIndexedNeighbors(aIt.val());
            noNeighInB = true;
                // nachbarn testen
            for(neigh = actNeighs.begin(); neigh != actNeighs.end(); neigh++) {
                if (b->in(*neigh)) {    // dann nachbar in b vorhanden
                    noNeighInB = false; // merken dass nachbar gefunden
                    newDom.insert(*neigh);  // nachbar in neue domain aufnehmen
                }
            }
                // altes element loeschen wenn noetig
            if (noNeighInB) {   
                    // zu entfernendes aVal aus a merken, wenn kein nachbar in b
                toRem.insert(aIt.val());
            }
                // naechstes element via iterator
            ++aIt;
        }
            // alle elemente in a loeschen, die keine nachbarn in b haben
        GC_StlSetRangeIterator remDomIt(&toRem);
        aStat = a->minus(home,remDomIt);
        
            // b domain angleichen
        if (aStat != Gecode::ME_GEN_FAILED) {   // nur wenn a nicht leer
            GC_StlSetRangeIterator newDomIt(&newDom);
            bStat = b->inter(home,newDomIt);
        } else {
            return Gecode::ME_GEN_FAILED;   // a domain leer
        }
        
            // rueckgabewert bestimmen
        if ( bStat == Gecode::ME_GEN_FAILED ) {
            return Gecode::ME_GEN_FAILED;   // dann b domain leer geworden
        }
        if ( aSize == a->size() && bSize == b->size())
            return Gecode::ME_GEN_NONE;     // nixs passiert
        if ( aStat == Gecode::ME_GEN_ASSIGNED 
                && bStat == Gecode::ME_GEN_ASSIGNED)
            return Gecode::ME_GEN_ASSIGNED;
        return Gecode::Int::ME_INT_DOM; // werte haben sich geaendert
    }
    
    biu::IndexSet
    GC_Neighbored2::getIndexedNeighbors(
            const biu::LatticeFrame::index_type center) const 
    {
        biu::IndexSet retSet;
            // alle nachbarn generieren
        for(biu::IndexVec::const_iterator it = neighborhood.begin();
                it != neighborhood.end(); it++) {
            retSet.insert(center+(*it));
        }
        return retSet;
    }

  } // namespace gecode
} // namespace cpsp