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