base.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 namespace Gecode { namespace Int { namespace Circuit {
00035
00036 template<class View, class Offset>
00037 forceinline
00038 Base<View,Offset>::Base(Home home, ViewArray<View>& x, Offset& o0)
00039 : NaryPropagator<View,Int::PC_INT_DOM>(home,x),
00040 start(0), y(home,x), o(o0) {
00041 home.notice(*this,AP_WEAKLY);
00042 }
00043
00044 template<class View, class Offset>
00045 forceinline
00046 Base<View,Offset>::Base(Space& home, Base<View,Offset>& p)
00047 : NaryPropagator<View,Int::PC_INT_DOM>(home,p), start(p.start) {
00048 o.update(p.o);
00049 y.update(home,p.y);
00050 }
00051
00053 template<class View>
00054 class NodeInfo {
00055 public:
00056 int min, low, pre;
00057 Int::ViewValues<View> v;
00058 };
00059
00061 template<class View>
00062 class TellInfo {
00063 public:
00064 View x; int n;
00065 };
00066
00067 template<class View, class Offset>
00068 ExecStatus
00069 Base<View,Offset>::connected(Space& home) {
00070 int n = x.size();
00071
00073 {
00074 int v = start;
00076 int m = n;
00077 while (x[v].assigned()) {
00078 m--;
00079 v = o(x[v]).val();
00080
00081 if (start == v)
00082 return (m == 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
00083 }
00084 start = v;
00085 }
00086
00088 Region r;
00089 typedef typename Offset::ViewType OView;
00090 NodeInfo<OView>* si = r.alloc<NodeInfo<OView> >(n);
00091 unsigned int n_edges = 0;
00092 for (int i=n; i--; ) {
00093 n_edges += x[i].size();
00094 si[i].pre=-1;
00095 }
00096
00097
00098 Support::StaticStack<int,Region> next(r,n);
00099
00100
00101 TellInfo<OView>* eq = r.alloc<TellInfo<OView> >(n);
00102 int n_eq = 0;
00103
00104
00105 TellInfo<OView>* nq = r.alloc<TellInfo<OView> >(n_edges);
00106 int n_nq = 0;
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131 {
00132
00133 int i = start;
00134
00135 int cnt = 0;
00136
00137 int subtree_min = 0;
00138
00139 int subtree_max = 0;
00140
00141 int back = 0;
00142 start:
00143 si[i].min = si[i].pre = si[i].low = cnt++;
00144 si[i].v.init(o(x[i]));
00145 do {
00146 if (si[si[i].v.val()].pre < 0) {
00147 next.push(i);
00148 i=si[i].v.val();
00149 goto start;
00150 } else if ((subtree_min <= si[si[i].v.val()].pre) &&
00151 (si[si[i].v.val()].pre <= subtree_max)) {
00152 back++;
00153 eq[n_eq].x = o(x[i]);
00154 eq[n_eq].n = si[i].v.val();
00155 } else if (si[si[i].v.val()].pre < subtree_min) {
00156 nq[n_nq].x = o(x[i]);
00157 nq[n_nq].n = si[i].v.val();
00158 n_nq++;
00159 }
00160 cont:
00161 if (si[si[i].v.val()].low < si[i].min)
00162 si[i].min = si[si[i].v.val()].low;
00163 ++si[i].v;
00164 } while (si[i].v());
00165 if (si[i].min < si[i].low) {
00166 si[i].low = si[i].min;
00167 } else if (i != start) {
00168
00169 return ES_FAILED;
00170 }
00171 if (!next.empty()) {
00172 i=next.pop();
00173 if (i == start) {
00174
00175 if (back == 0)
00176 return ES_FAILED;
00177
00178 if (back == 1)
00179 n_eq++;
00180 back = 0;
00181 subtree_min = subtree_max+1;
00182 subtree_max = cnt-1;
00183 }
00184 goto cont;
00185 }
00186
00187
00188 if (cnt != n)
00189 return ES_FAILED;
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199 if (subtree_min > 1) {
00200 for (Int::ViewValues<OView> v(o(x[start])); v(); ++v)
00201 if (si[v.val()].pre < subtree_min) {
00202 nq[n_nq].x = o(x[v.val()]);
00203 nq[n_nq].n = v.val();
00204 n_nq++;
00205 }
00206 }
00207
00208 ExecStatus es = ES_FIX;
00209
00210 while (n_eq-- > 0) {
00211 ModEvent me = eq[n_eq].x.eq(home,eq[n_eq].n);
00212 if (me_failed(me))
00213 return ES_FAILED;
00214 if (me_modified(me))
00215 es = ES_NOFIX;
00216 }
00217
00218
00219 while (n_nq-- > 0) {
00220 ModEvent me = nq[n_nq].x.nq(home,nq[n_nq].n);
00221 if (me_failed(me))
00222 return ES_FAILED;
00223 if (me_modified(me))
00224 es = ES_NOFIX;
00225 }
00226
00227
00228 start = o(x[start]).min();
00229
00230 return es;
00231 }
00232 }
00233
00234 template<class View, class Offset>
00235 ExecStatus
00236 Base<View,Offset>::path(Space& home) {
00237
00238
00239 int n=x.size();
00240
00241 Region r;
00242
00243
00244
00245 int* end = r.alloc<int>(n);
00246 for (int i=n; i--; )
00247 end[i]=-1;
00248
00249
00250 Support::StaticStack<int,Region> tell(r,n);
00251
00252 typedef typename Offset::ViewType OView;
00253 for (int i=y.size(); i--; ) {
00254 assert(!y[i].assigned());
00255
00256 Int::ViewValues<OView> v(o(y[i]));
00257
00258 do {
00259 int j0=v.val();
00260
00261 if (x[j0].assigned() && (end[j0] < 0)) {
00262
00263
00264
00265
00266 int j = j0;
00267 do {
00268 j=o(x[j]).val();
00269 } while (x[j].assigned());
00270
00271
00272
00273 end[j0]=j; tell.push(j0);
00274 }
00275 ++v;
00276 } while (v());
00277 }
00278
00279
00280 while (!tell.empty()) {
00281 int i = tell.pop();
00282 assert(end[i] >= 0);
00283 GECODE_ME_CHECK(o(x[end[i]]).nq(home,i));
00284 }
00285 return ES_NOFIX;
00286 }
00287
00288 template<class View, class Offset>
00289 forceinline size_t
00290 Base<View,Offset>::dispose(Space& home) {
00291 home.ignore(*this,AP_WEAKLY);
00292 (void) NaryPropagator<View,Int::PC_INT_DOM>::dispose(home);
00293 return sizeof(*this);
00294 }
00295
00296 }}}
00297
00298
00299