Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
atmostOne.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Copyright:
7 * Guido Tack, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
35
36/*
37 * These propagators implement the scheme discussed in
38 *
39 * Andrew Sadler and Carment Gervet: Global Reasoning on Sets.
40 * FORMUL'01 workshop in conjunction with CP 2001.
41 *
42 * Todo: make the propagators incremental.
43 */
44
45namespace Gecode { namespace Set { namespace Distinct {
46
47 /*
48 * "AtMostOneIntersection" propagator
49 *
50 */
51
52 Actor*
54 return new (home) AtmostOne(home,*this);
55 }
56
59 Region r;
60 LubRanges<SetView>* lubs = r.alloc<LubRanges<SetView> >(x.size());
61 for (int i = x.size(); i--; ) {
62 lubs[i].init(x[i]);
63 }
64 Iter::Ranges::NaryUnion bigT(r, lubs, x.size());
65
67 as(bigT);
68
69 while (as()) {
70 int a = as.val(); ++as;
71
72 // cardSa is the number of sets that contain a in the glb
73 int cardSa = 0;
74 for (int i=x.size(); i--;)
75 if (x[i].contains(a))
76 cardSa++;
77
78 // bigTa is the union of all lubs that contain a
79 GLBndSet bigTa(home);
80 for (int i=x.size(); i--;) {
81 if (!x[i].notContains(a)) {
82 LubRanges<SetView> xilub(x[i]);
83 bigTa.includeI(home, xilub);
84 }
85 }
86
87 // maxa is the maximum number of sets that can contain a
88 int maxa = static_cast<int>((bigTa.size() - 1) / (c - 1));
89 bigTa.dispose(home);
90
91 // Conditional Rule A:
92 // If more sets already contain a than allowed, fail.
93 if (maxa < cardSa)
94 return ES_FAILED;
95
96 if (maxa == cardSa) {
97 // Conditional Rule B:
98 // All a used up. All other sets (those that don't have a in their
99 // glb already) cannot contain a.
100 for (int i=x.size(); i--;) {
101 if (!x[i].contains(a)) {
102 GECODE_ME_CHECK(x[i].exclude(home, a));
103 }
104 }
105 } else {
106 LubRanges<SetView>* lubs2 = r.alloc<LubRanges<SetView> >(x.size());
107 for (int i = x.size(); i--; ) {
108 lubs2[i].init(x[i]);
109 }
110 Iter::Ranges::NaryUnion bigT2(r, lubs2, x.size());
111
112 GlbRanges<SetView>* glbs = r.alloc<GlbRanges<SetView> >(cardSa);
113 int count = 0;
114 for (int i=x.size(); i--; ) {
115 if (x[i].contains(a)) {
116 glbs[count].init(x[i]);
117 count++;
118 }
119 }
120 Iter::Ranges::NaryUnion glbsa(r, glbs, cardSa);
122 Iter::Ranges::NaryUnion> deltaA(bigT2, glbsa);
123 Iter::Ranges::Cache deltaAC(r,deltaA);
124 // deltaAC contains all elements that are not yet known to be
125 // in a set together with a.
126 // Formally: \cup_i lub(x_i) - \cup_i {glb(s_i) | a\in glb(s_i)}
127
128
129 if (Iter::Ranges::size(deltaAC) == c - 1) {
130 // Conditional Rule C:
131 // If deltaA has exactly c-1 elements, all sets that are not yet
132 // known to contain a cannot contain a if it is impossible that
133 // they contain all of deltaA. Or the other way around:
134 // If a is added to the glb of a set s, deltaA must be a subset of
135 // s, because otherwise s would share at least one more element
136 // with another set that has a in its lower bound.
137 // Weird, eh?
138 for (int i=x.size(); i--; ) {
139 if (!x[i].contains(a) && !x[i].notContains(a)) {
140 deltaAC.reset();
141 LubRanges<SetView> xilub(x[i]);
142 if (!Iter::Ranges::subset(deltaAC, xilub)) {
143 GECODE_ME_CHECK(x[i].exclude(home, a));
144 }
145 }
146 }
147 }
148
149 }
150
151 }
152
153 return ES_NOFIX;
154 }
155
156}}}
157
158// STATISTICS: set-prop
Range iterator cache
Range iterator for computing set difference.
Range iterator for union of iterators.
void reset(void)
Reset iterator to start.
Value iterator from range iterator.
int val(void) const
Return current value.
friend class Space
Definition core.hpp:1068
Handle to region.
Definition region.hpp:55
unsigned int size(void) const
Return size.
void dispose(Space &home)
Free memory used by this set.
AtmostOne(Space &home, AtmostOne &p)
Constructor for cloning p.
Definition atmostOne.hpp:46
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition atmostOne.cpp:53
unsigned int c
Cardinality of the sets.
Definition distinct.hh:55
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition atmostOne.cpp:58
Growing sets of integers.
Definition var-imp.hpp:205
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
Range iterator for the least upper bound.
Definition var-imp.hpp:317
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
bool subset(I &i, J &j)
Check whether range iterator i is subset of range iterator j.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Propagators for global distinctness constraints.
Definition distinct.hh:39
Finite integer sets.
Definition var-imp.hpp:137
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
ExecStatus
Definition core.hpp:472
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475