Generated on Mon May 10 06:46:44 2010 for Gecode by doxygen 1.6.3

atmostOne.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-02-04 13:17:26 +0100 (Wed, 04 Feb 2009) $ by $Author: schulte $
00011  *     $Revision: 8137 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/set/distinct.hh>
00039 
00040 /*
00041  * These propagators implement the scheme discussed in
00042  *
00043  * Andrew Sadler and Carment Gervet: Global Reasoning on Sets.
00044  * FORMUL'01 workshop in conjunction with CP 2001.
00045  *
00046  * Todo: make the propagators incremental.
00047  */
00048 
00049 namespace Gecode { namespace Set { namespace Distinct {
00050 
00051   /*
00052    * "AtMostOneIntersection" propagator
00053    *
00054    */
00055 
00056   Actor*
00057   AtmostOne::copy(Space& home, bool share) {
00058     return new (home) AtmostOne(home,share,*this);
00059   }
00060 
00061   ExecStatus
00062   AtmostOne::propagate(Space& home, const ModEventDelta&) {
00063     Region r(home);
00064     LubRanges<SetView>* lubs = r.alloc<LubRanges<SetView> >(x.size());
00065     for (int i = x.size(); i--; ) {
00066       lubs[i].init(x[i]);
00067     }
00068     Iter::Ranges::NaryUnion<LubRanges<SetView> > bigT(lubs, x.size());
00069     Iter::Ranges::Cache<Iter::Ranges::NaryUnion<LubRanges<SetView> > >
00070       bigTC(bigT);
00071 
00072     Iter::Ranges::ToValues<Iter::Ranges::Cache<Iter::Ranges::NaryUnion<LubRanges<SetView> > > >
00073       as(bigTC);
00074 
00075     while (as()) {
00076       int a = as.val(); ++as;
00077 
00078       // cardSa is the number of sets that contain a in the glb
00079       int cardSa = 0;
00080       for (int i=x.size(); i--;)
00081         if (x[i].contains(a))
00082           cardSa++;
00083 
00084       // bigTa is the union of all lubs that contain a
00085       GLBndSet bigTa(home);
00086       for (int i=x.size(); i--;) {
00087         if (!x[i].notContains(a)) {
00088           LubRanges<SetView> xilub(x[i]);
00089           bigTa.includeI(home, xilub);
00090         }
00091       }
00092 
00093       // maxa is the maximum number of sets that can contain a
00094       int maxa = (bigTa.size() - 1) / (c - 1);
00095       bigTa.dispose(home);
00096 
00097       // Conditional Rule A:
00098       // If more sets already contain a than allowed, fail.
00099       if (maxa < cardSa)
00100         return ES_FAILED;
00101 
00102       if (maxa == cardSa) {
00103         // Conditional Rule B:
00104         // All a used up. All other sets (those that don't have a in their
00105         // glb already) cannot contain a.
00106         for (int i=x.size(); i--;) {
00107           if (!x[i].contains(a)) {
00108             GECODE_ME_CHECK(x[i].exclude(home, a));
00109           }
00110         }
00111       } else {
00112         LubRanges<SetView>* lubs2 = r.alloc<LubRanges<SetView> >(x.size());
00113         for (int i = x.size(); i--; ) {
00114           lubs2[i].init(x[i]);
00115         }
00116         Iter::Ranges::NaryUnion<LubRanges<SetView> > bigT2(lubs2, x.size());
00117 
00118         GlbRanges<SetView>* glbs = r.alloc<GlbRanges<SetView> >(cardSa);
00119         int count = 0;
00120         for (int i=x.size(); i--; ) {
00121           if (x[i].contains(a)) {
00122             glbs[count].init(x[i]);
00123             count++;
00124           }
00125         }
00126         Iter::Ranges::NaryUnion<GlbRanges<SetView> > glbsa(glbs, cardSa);
00127         Iter::Ranges::Diff<Iter::Ranges::NaryUnion<LubRanges<SetView> >,
00128           Iter::Ranges::NaryUnion<GlbRanges<SetView> > > deltaA(bigT2, glbsa);
00129         Iter::Ranges::Cache<
00130         Iter::Ranges::Diff<Iter::Ranges::NaryUnion<LubRanges<SetView> >,
00131           Iter::Ranges::NaryUnion<GlbRanges<SetView> > > > deltaAC(deltaA);
00132         // deltaAC contains all elements that are not yet known to be
00133         // in a set together with a.
00134         // Formally: \cup_i lub(x_i) - \cup_i {glb(s_i) | a\in glb(s_i)}
00135 
00136 
00137         if (Iter::Ranges::size(deltaAC) == c - 1) {
00138           // Conditional Rule C:
00139           // If deltaA has exactly c-1 elements, all sets that are not yet
00140           // known to contain a cannot contain a if it is impossible that
00141           // they contain all of deltaA. Or the other way around:
00142           // If a is added to the glb of a set s, deltaA must be a subset of
00143           // s, because otherwise s would share at least one more element
00144           // with another set that has a in its lower bound.
00145           // Weird, eh?
00146           for (int i=x.size(); i--; ) {
00147             if (!x[i].contains(a) && !x[i].notContains(a)) {
00148               deltaAC.reset();
00149               LubRanges<SetView> xilub(x[i]);
00150               if (!Iter::Ranges::subset(deltaAC, xilub)) {
00151                 GECODE_ME_CHECK(x[i].exclude(home, a));
00152               }
00153             }
00154           }
00155         }
00156 
00157       }
00158 
00159     }
00160 
00161     return ES_NOFIX;
00162   }
00163 
00164 }}}
00165 
00166 // STATISTICS: set-prop