main page namespaces classes files
CPSP home

src/cpsp/gecode/old_GC_Neighbored3.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_Neighbored3.hh"
#include "cpsp/gecode/GC_StlSetRangeIterator.hh"

#include <biu/assertbiu.hh>

namespace cpsp
{
  namespace gecode
  {
    
  const unsigned int GC_Neighbored3::MAXPROPSIZEINIT = 50;

    
  GC_Neighbored3::GC_Neighbored3(   Gecode::Space* home, 
                                Gecode::Int::IntView x0, 
                                Gecode::Int::IntView x1,
                                Gecode::Int::IntView x2,
                                const biu::LatticeFrame* lattice_,
                                Gecode::IntConLevel conLvl,
                                unsigned int maxPrSize,
                                bool maxPrSizeBin,
                                unsigned int minPrSize)
    : GC_TriProp(home,x0,x1,x2),
        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_Neighbored3::GC_Neighbored3(   Gecode::Space* home, 
                                bool share, 
                                GC_Neighbored3& p) :
        GC_TriProp(home,share,p),
        lattice(p.lattice), 
        neighborhood(p.neighborhood),
        conLevel(p.conLevel),
        maxPropSize(p.maxPropSize),
        maxPropSizeBin(p.maxPropSizeBin),
        minPropSize(p.minPropSize)
  {}

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


  Gecode::Actor*
  GC_Neighbored3::copy(Gecode::Space* home, bool share) {
    return new (home) GC_Neighbored3(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_Neighbored3::cost(void) const {
    if (x0.assigned() || x1.assigned() || x2.assigned()) {
        return Gecode::PC_QUADRATIC_HI;
    } 
    return Gecode::PC_CUBIC_HI;
  }

  Gecode::ExecStatus
  GC_Neighbored3::propagate(Gecode::Space* home) {

        // pruefe ob minimale propagationsschranke erreicht
        // und somit pseudo-entailed
    if (    x0.size() < minPropSize 
            && x1.size() < minPropSize 
            && x2.size() < minPropSize )
        return Gecode::ES_SUBSUMED;
    
        // pruefe ob schon zu arbeiten, wenn maxPropSizeBin == true
    if (    maxPropSizeBin &&
            (   std::max(x0.size(), x1.size()) > maxPropSize
            ||  std::max(x1.size(), x2.size()) > maxPropSize) )
        return Gecode::ES_FIX;

//      std::cout <<"vorher : "<<x0 <<" / " <<x1 <<" / " <<x2 <<std::endl;
    Gecode::ModEvent ret = Gecode::ME_GEN_NONE, ret1 = Gecode::ME_GEN_NONE;
    if (x1.assigned()) {
        ret1 = removeNonNeighbors(home,x0,x1.val());
        if (ret1 == Gecode::ME_GEN_FAILED) {            // dann x0 leer
            ret = Gecode::ME_GEN_FAILED;
        } else {
            ret = removeNonNeighbors(home,x2,x1.val());
                // nur wenn beide festgelegt, wird ME_GEN_ASSIGNED geliefert
            if (    ret == Gecode::ME_GEN_ASSIGNED 
                    && ret1 != Gecode::ME_GEN_ASSIGNED) // dann nur x1/x2 fest 
            {   ret = Gecode::Int::ME_INT_DOM; }
        }
    } else if (x0.assigned()) {
        ret1 = removeNonNeighbors(home,x1,x0.val());
        if (ret1 == Gecode::ME_GEN_FAILED) {                // dann x1 leer
            ret = Gecode::ME_GEN_FAILED;
        } else if(ret1 == Gecode::ME_GEN_ASSIGNED) {    // dann auch x1 fest
            ret = removeNonNeighbors(home,x2,x1.val());
        } else {                                        // dann nur x0 fest
            ret = removeNonNeighbors(home,x1, x2);
        }
    } else if (x2.assigned()) {
        ret1 = removeNonNeighbors(home,x1,x2.val());
        if (ret1 == Gecode::ME_GEN_FAILED) {                // dann x1 leer
            ret = Gecode::ME_GEN_FAILED;
        } else if(ret1 == Gecode::ME_GEN_ASSIGNED) {    // dann auch x1 fest
            ret = removeNonNeighbors(home,x0,x1.val());
        } else {                                        // dann nur x2 fest
            ret = removeNonNeighbors(home,x0, x1);
        }
    } else {
        ret = removeNonNeighbors(home, x0, x1, x2);
    }
//      std::cout <<"danach : "<<x0 <<" / " <<x1 <<" / " <<x2 <<std::endl;
        // pruefen auf ME_GEN_FAILED
    GECODE_ME_CHECK(ret);

    return (ret ==  Gecode::ME_GEN_ASSIGNED 
                ?   Gecode::ES_SUBSUMED
                :   Gecode::ES_FIX);
  }


    biu::IndexSet
    GC_Neighbored3::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;
    }


    Gecode::ModEvent 
    GC_Neighbored3::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_Neighbored3::removeNonNeighbors( Gecode::Space* home,
                                        Gecode::Int::IntView& xA, 
                                        Gecode::Int::IntView& xB)
    {


            // a wird referenz auf kleinere domain
        Gecode::Int::IntView* a = &xA, *b = &xB;
        if(a->size() > b->size()) {
            a = &xB, b = &xA;
        }
        
            // wenn minimale domain noch zu gross fuer propagationslevel
            // dann abbruch der propagation
        if (a->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
    }

    Gecode::ModEvent 
    GC_Neighbored3::removeNonNeighbors( Gecode::Space* home,
                                        Gecode::Int::IntView& xA, 
                                        Gecode::Int::IntView& xB, 
                                        Gecode::Int::IntView& xC)
    {

            // a wird referenz auf kleinere domain von xA und xC
        Gecode::Int::IntView* a = &xA, *b = &xB, *c = &xC;
        if(a->size() > c->size()) {
            a = &xC, c = &xA;
        }
        
            // wenn minimale domain noch zu gross fuer propagationslevel ist
            // dann abbruch der propagation
        if (    std::min(a->size(),b->size()) > maxPropSize  )
            return Gecode::ME_GEN_NONE;     // nixs passiert
        
            // alte groessen der variablen
        unsigned int aSize = a->size(), bSize = b->size(), cSize = c->size();

        if (bSize < aSize) {    // dann propagation ueber mittlere variable
            
            biu::IndexSet bRem, aInter, cInter, actNeighs;  // domain hilfsvariablen
            Gecode::Int::ViewValues<Gecode::Int::IntView> bIt(*b);
            biu::IndexSet::const_iterator neighA, neighC;
            
            while(bIt()) {  // laufe durch alle elemente in b
                
                actNeighs = getIndexedNeighbors(bIt.val());
                
                neighA = actNeighs.begin();
                    // setze neighA auf ersten nachbarn von bIt in a
                while( neighA != actNeighs.end() && !a->in(*neighA) ) {
                    neighA++;
                }
                if (neighA == actNeighs.end()) {    // kein nachbar in a
                    bRem.insert(bIt.val());         // bIt aus b zu entfernen
                    
                } else {        // mindestens ein nachbar in a vorhanden
                    neighC = actNeighs.begin();
                        // setze neighC auf ersten nachbarn von bIt in c
                    while( neighC != actNeighs.end() && !c->in(*neighC) ) {
                        neighC++;
                    }
                    if (neighC == actNeighs.end()) {    // kein nachbar in c
                        bRem.insert(bIt.val());         // bIt aus b entfernen
                        
                    } else {            // alle nachbarn aus a und c merken
                            // alle a nachbarn
                        aInter.insert(*neighA);
                        while( ++neighA != actNeighs.end()) {
                            if (a->in(*neighA))
                                aInter.insert(*neighA);
                        }
                            // alle c nachbarn
                        cInter.insert(*neighC);
                        while( ++neighC != actNeighs.end()) {
                            if (c->in(*neighC))
                                cInter.insert(*neighC);
                        }
                    }
                }
                ++bIt;
            }
            
                // alles ohne support aus b loeschen
            GC_StlSetRangeIterator domIt(&bRem);
            GECODE_ME_CHECK( b->minus(home, domIt) );
                // alles ohne support aus a loeschen
            domIt.init(&aInter);
            GECODE_ME_CHECK( a->inter(home, domIt) );
                // alles ohne support aus c loeschen
            domIt.init(&cInter);
            GECODE_ME_CHECK( c->inter(home, domIt) );
            
        } else {                // propagation von a nach c

                // domain hilfsvariablen
            biu::IndexSet aRem, bInter, cInter, actNeighsA, actNeighsB;
            Gecode::Int::ViewValues<Gecode::Int::IntView> aIt(*a);
            biu::IndexSet::const_iterator neighB, neighC;
            
                // support flag fuer c domain (ob min ein pfad von a nach c)
            bool pathFound = false;
            
            while(aIt()) {  // laufe durch alle elemente in a
                
                actNeighsA = getIndexedNeighbors(aIt.val());
                pathFound = false;
                
                for (   neighB = actNeighsA.begin(); 
                        neighB != actNeighsA.end(); 
                        neighB++) 
                {
                        // dann support in b
                    if (b->in(*neighB)) {
                        pathFound = false;
                        actNeighsB = getIndexedNeighbors(*neighB);
                        
                        for(    neighC = actNeighsB.begin(); 
                                neighC != actNeighsB.end(); 
                                neighC++) 
                        {
                            if (c->in(*neighC)) {
                                pathFound = true;
                                cInter.insert(*neighC);
                            }
                        }
                        
                        if (pathFound) {
                            bInter.insert(*neighB);
                        }
                    }
                }
                
                if (!pathFound) {   // dann aIt aus a loeschen
                    aRem.insert(aIt.val());
                }
                ++aIt;
            }

                // alles ohne support aus a loeschen
            GC_StlSetRangeIterator domIt(&aRem);
            GECODE_ME_CHECK( a->minus(home, domIt) );
                // alles ohne support aus b loeschen
            domIt.init(&bInter);
            GECODE_ME_CHECK( b->inter(home, domIt) );
                // alles ohne support aus c loeschen
            domIt.init(&cInter);
            GECODE_ME_CHECK( c->inter(home, domIt) );
            
        }

        if (a->assigned() && b->assigned() && c->assigned()) {
            return Gecode::ME_GEN_ASSIGNED;     // alles festgelegt
        }
        if (a->size() < aSize || b->size() < bSize || c->size() < cSize) {
            return Gecode::Int::ME_INT_DOM;     // min. eine domain kleiner
        }
        
        return Gecode::ME_GEN_NONE; // werte haben sich nicht geaendert
    }
  } //namespace gecode
} // namespace cpsp