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
00035
00036
00037
00038 namespace Gecode { namespace Int { namespace Circuit {
00039
00040 template<class View, class Offset>
00041 forceinline
00042 Base<View,Offset>::Base(Home home, ViewArray<View>& x, Offset& o0)
00043 : NaryPropagator<View,Int::PC_INT_DOM>(home,x), y(home,x), o(o0) {
00044 home.notice(*this,AP_WEAKLY);
00045 }
00046
00047 template<class View, class Offset>
00048 forceinline
00049 Base<View,Offset>::Base(Space& home, bool share, Base<View,Offset>& p)
00050 : NaryPropagator<View,Int::PC_INT_DOM>(home,share,p) {
00051 o.update(p.o);
00052 y.update(home,share,p.y);
00053 }
00054
00056 template<class View>
00057 class SsccInfo {
00058 public:
00059 int min, low, pre;
00060 Int::ViewValues<View> v;
00061 };
00062
00064 template<class View>
00065 class TellInfo {
00066 public:
00067 View x; int n;
00068 };
00069
00070 template<class View, class Offset>
00071 ExecStatus
00072 Base<View,Offset>::connected(Space& home) {
00073 int n = x.size();
00074
00076 int start = 0;
00077 while (x[start].assigned()) {
00078 start = o(x[start]).val();
00079 if (start == 0) break;
00080 }
00081
00083 Region r(home);
00084 typedef typename Offset::ViewType OView;
00085 SsccInfo<OView>* si = r.alloc<SsccInfo<OView> >(n);
00086 unsigned int n_edges = 0;
00087 for (int i=n; i--; ) {
00088 n_edges += x[i].size();
00089 si[i].pre=-1;
00090 }
00091
00092
00093 Support::StaticStack<int,Region> next(r,n);
00094
00095
00096 TellInfo<OView>* eq = r.alloc<TellInfo<OView> >(n);
00097 int n_eq = 0;
00098
00099
00100 TellInfo<OView>* nq = r.alloc<TellInfo<OView> >(n_edges);
00101 int n_nq = 0;
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126 {
00127
00128 int i = start;
00129
00130 int cnt = 0;
00131
00132 int subtree_min = 0;
00133
00134 int subtree_max = 0;
00135
00136 int back = 0;
00137 start:
00138 si[i].min = si[i].pre = si[i].low = cnt++;
00139 si[i].v.init(o(x[i]));
00140 do {
00141 if (si[si[i].v.val()].pre < 0) {
00142 next.push(i);
00143 i=si[i].v.val();
00144 goto start;
00145 } else if ((subtree_min <= si[si[i].v.val()].pre) &&
00146 (si[si[i].v.val()].pre <= subtree_max)) {
00147 back++;
00148 eq[n_eq].x = o(x[i]);
00149 eq[n_eq].n = si[i].v.val();
00150 } else if (si[si[i].v.val()].pre < subtree_min) {
00151 nq[n_nq].x = o(x[i]);
00152 nq[n_nq].n = si[i].v.val();
00153 n_nq++;
00154 }
00155 cont:
00156 if (si[si[i].v.val()].low < si[i].min)
00157 si[i].min = si[si[i].v.val()].low;
00158 ++si[i].v;
00159 } while (si[i].v());
00160 if (si[i].min < si[i].low) {
00161 si[i].low = si[i].min;
00162 } else if (i != start) {
00163
00164 return ES_FAILED;
00165 }
00166 if (!next.empty()) {
00167 i=next.pop();
00168 if (i == start) {
00169
00170 if (back == 0)
00171 return ES_FAILED;
00172
00173 if (back == 1)
00174 n_eq++;
00175 back = 0;
00176 subtree_min = subtree_max+1;
00177 subtree_max = cnt-1;
00178 }
00179 goto cont;
00180 }
00181
00182 if (cnt != n)
00183 return ES_FAILED;
00184 ExecStatus es = ES_FIX;
00185
00186 while (n_eq-- > 0) {
00187 ModEvent me = eq[n_eq].x.eq(home,eq[n_eq].n);
00188 if (me_failed(me))
00189 return ES_FAILED;
00190 if (me_modified(me))
00191 es = ES_NOFIX;
00192 }
00193
00194 while (n_nq-- > 0) {
00195 ModEvent me = nq[n_nq].x.nq(home,nq[n_nq].n);
00196 if (me_failed(me))
00197 return ES_FAILED;
00198 if (me_modified(me))
00199 es = ES_NOFIX;
00200 }
00201 return es;
00202 }
00203 }
00204
00205 template<class View, class Offset>
00206 ExecStatus
00207 Base<View,Offset>::path(Space& home) {
00208
00209
00210 int n=x.size();
00211
00212 Region r(home);
00213
00214
00215
00216 int* end = r.alloc<int>(n);
00217 for (int i=n; i--; )
00218 end[i]=-1;
00219
00220
00221 Support::StaticStack<int,Region> tell(r,n);
00222
00223 typedef typename Offset::ViewType OView;
00224 for (int i=y.size(); i--; ) {
00225 assert(!y[i].assigned());
00226
00227 Int::ViewValues<OView> v(o(y[i]));
00228
00229 do {
00230 int j0=v.val();
00231
00232 if (x[j0].assigned() && (end[j0] < 0)) {
00233
00234
00235
00236
00237 int j = j0;
00238 do {
00239 j=o(x[j]).val();
00240 } while (x[j].assigned());
00241
00242
00243
00244 end[j0]=j; tell.push(j0);
00245 }
00246 ++v;
00247 } while (v());
00248 }
00249
00250
00251 while (!tell.empty()) {
00252 int i = tell.pop();
00253 assert(end[i] >= 0);
00254 GECODE_ME_CHECK(o(x[end[i]]).nq(home,i));
00255 }
00256 return ES_NOFIX;
00257 }
00258
00259 template<class View, class Offset>
00260 forceinline size_t
00261 Base<View,Offset>::dispose(Space& home) {
00262 home.ignore(*this,AP_WEAKLY);
00263 (void) NaryPropagator<View,Int::PC_INT_DOM>::dispose(home);
00264 return sizeof(*this);
00265 }
00266
00267 }}}
00268
00269
00270