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: 2010-09-03 16:36:31 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $ 00011 * $Revision: 11390 $ 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(r, lubs, x.size()); 00069 00070 Iter::Ranges::ToValues<Iter::Ranges::NaryUnion<LubRanges<SetView> > > 00071 as(bigT); 00072 00073 while (as()) { 00074 int a = as.val(); ++as; 00075 00076 // cardSa is the number of sets that contain a in the glb 00077 int cardSa = 0; 00078 for (int i=x.size(); i--;) 00079 if (x[i].contains(a)) 00080 cardSa++; 00081 00082 // bigTa is the union of all lubs that contain a 00083 GLBndSet bigTa(home); 00084 for (int i=x.size(); i--;) { 00085 if (!x[i].notContains(a)) { 00086 LubRanges<SetView> xilub(x[i]); 00087 bigTa.includeI(home, xilub); 00088 } 00089 } 00090 00091 // maxa is the maximum number of sets that can contain a 00092 int maxa = static_cast<int>((bigTa.size() - 1) / (c - 1)); 00093 bigTa.dispose(home); 00094 00095 // Conditional Rule A: 00096 // If more sets already contain a than allowed, fail. 00097 if (maxa < cardSa) 00098 return ES_FAILED; 00099 00100 if (maxa == cardSa) { 00101 // Conditional Rule B: 00102 // All a used up. All other sets (those that don't have a in their 00103 // glb already) cannot contain a. 00104 for (int i=x.size(); i--;) { 00105 if (!x[i].contains(a)) { 00106 GECODE_ME_CHECK(x[i].exclude(home, a)); 00107 } 00108 } 00109 } else { 00110 LubRanges<SetView>* lubs2 = r.alloc<LubRanges<SetView> >(x.size()); 00111 for (int i = x.size(); i--; ) { 00112 lubs2[i].init(x[i]); 00113 } 00114 Iter::Ranges::NaryUnion<LubRanges<SetView> > bigT2(r, lubs2, x.size()); 00115 00116 GlbRanges<SetView>* glbs = r.alloc<GlbRanges<SetView> >(cardSa); 00117 int count = 0; 00118 for (int i=x.size(); i--; ) { 00119 if (x[i].contains(a)) { 00120 glbs[count].init(x[i]); 00121 count++; 00122 } 00123 } 00124 Iter::Ranges::NaryUnion<GlbRanges<SetView> > glbsa(r, glbs, cardSa); 00125 Iter::Ranges::Diff<Iter::Ranges::NaryUnion<LubRanges<SetView> >, 00126 Iter::Ranges::NaryUnion<GlbRanges<SetView> > > deltaA(bigT2, glbsa); 00127 Iter::Ranges::Cache< 00128 Iter::Ranges::Diff<Iter::Ranges::NaryUnion<LubRanges<SetView> >, 00129 Iter::Ranges::NaryUnion<GlbRanges<SetView> > > > deltaAC(r,deltaA); 00130 // deltaAC contains all elements that are not yet known to be 00131 // in a set together with a. 00132 // Formally: \cup_i lub(x_i) - \cup_i {glb(s_i) | a\in glb(s_i)} 00133 00134 00135 if (Iter::Ranges::size(deltaAC) == c - 1) { 00136 // Conditional Rule C: 00137 // If deltaA has exactly c-1 elements, all sets that are not yet 00138 // known to contain a cannot contain a if it is impossible that 00139 // they contain all of deltaA. Or the other way around: 00140 // If a is added to the glb of a set s, deltaA must be a subset of 00141 // s, because otherwise s would share at least one more element 00142 // with another set that has a in its lower bound. 00143 // Weird, eh? 00144 for (int i=x.size(); i--; ) { 00145 if (!x[i].contains(a) && !x[i].notContains(a)) { 00146 deltaAC.reset(); 00147 LubRanges<SetView> xilub(x[i]); 00148 if (!Iter::Ranges::subset(deltaAC, xilub)) { 00149 GECODE_ME_CHECK(x[i].exclude(home, a)); 00150 } 00151 } 00152 } 00153 } 00154 00155 } 00156 00157 } 00158 00159 return ES_NOFIX; 00160 } 00161 00162 }}} 00163 00164 // STATISTICS: set-prop