graph.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 #include <climits>
00039
00040 namespace Gecode { namespace Int { namespace Distinct {
00041
00042 template<class View>
00043 forceinline
00044 Graph<View>::Graph(void) {}
00045
00046 template<class View>
00047 forceinline ExecStatus
00048 Graph<View>::init(Space& home, ViewArray<View>& x) {
00049 using namespace ViewValGraph;
00050 n_view = x.size();
00051 view = home.alloc<ViewNode<View>*>(n_view);
00052
00053
00054 int min = x[n_view-1].min();
00055 int max = x[n_view-1].max();
00056 for (int i=n_view-1; i--; ) {
00057 min = std::min(min,x[i].min());
00058 max = std::max(max,x[i].max());
00059 }
00060
00061 unsigned int width = static_cast<unsigned int>(max-min+1);
00062
00063
00064 if (width < static_cast<unsigned int>(n_view))
00065 return ES_FAILED;
00066
00067
00068 for (int i=n_view; i--; )
00069 view[i] = new (home) ViewNode<View>(x[i]);
00070
00071 Region r(home);
00072
00073 if (static_cast<unsigned int>(n_view)*4 >= width) {
00074
00075 ValNode<View>** val2node = r.alloc<ValNode<View>* >(width);
00076
00077 for (unsigned int i=width; i--; )
00078 val2node[i]=NULL;
00079
00080 for (int i=n_view; i--; ) {
00081 Edge<View>** edge_p = view[i]->val_edges_ref();
00082 for (ViewValues<View> xi(x[i]); xi(); ++xi) {
00083 if (val2node[xi.val()-min] == NULL)
00084 val2node[xi.val()-min] = new (home) ValNode<View>(xi.val());
00085 *edge_p = new (home) Edge<View>(val2node[xi.val()-min],view[i]);
00086 edge_p = (*edge_p)->next_edge_ref();
00087 }
00088 *edge_p = NULL;
00089 }
00090
00091 for (unsigned int i=width; i--; )
00092 if (val2node[i] != NULL) {
00093 val2node[i]->next_val(val);
00094 val = val2node[i];
00095 n_val++;
00096 }
00097
00098 } else {
00099
00100 for (int i=n_view; i--; )
00101 ViewValGraph::Graph<View>::init(home,view[i]);
00102 }
00103
00104 if (n_val < n_view)
00105 return ES_FAILED;
00106
00107 typename ViewValGraph::Graph<View>::ViewNodeStack m(r,n_view);
00108 for (int i = n_view; i--; )
00109 if (!match(m,view[i]))
00110 return ES_FAILED;
00111 return ES_OK;
00112 }
00113
00114 template<class View>
00115 forceinline bool
00116 Graph<View>::sync(Space& home) {
00117 using namespace ViewValGraph;
00118 Region r(home);
00119
00120 typename ViewValGraph::Graph<View>::ViewNodeStack re(r,n_view);
00121
00122 for (int i = n_view; i--; ) {
00123 ViewNode<View>* x = view[i];
00124 if (x->view().assigned()) {
00125 x->edge_fst()->val(x)->matching(NULL);
00126 for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00127 e->unlink();
00128 view[i] = view[--n_view];
00129 } else if (x->changed()) {
00130 ViewRanges<View> r(x->view());
00131 Edge<View>* m = x->edge_fst();
00132 Edge<View>** p = x->val_edges_ref();
00133 Edge<View>* e = *p;
00134 do {
00135 while (e->val(x)->val() < r.min()) {
00136
00137 e->unlink(); e->mark();
00138 e = e->next_edge();
00139 }
00140 *p = e;
00141 assert(r.min() == e->val(x)->val());
00142
00143 for (unsigned int j=r.width(); j--; ) {
00144 e->free();
00145 p = e->next_edge_ref();
00146 e = e->next_edge();
00147 }
00148 ++r;
00149 } while (r());
00150 *p = NULL;
00151 while (e != NULL) {
00152 e->unlink(); e->mark();
00153 e = e->next_edge();
00154 }
00155 if (m->marked()) {
00156
00157 m->val(x)->matching(NULL);
00158 re.push(x);
00159 }
00160 x->update();
00161 } else {
00162
00163 for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00164 e->free();
00165 }
00166 }
00167
00168 typename ViewValGraph::Graph<View>::ViewNodeStack m(r,n_view);
00169 while (!re.empty())
00170 if (!match(m,re.pop()))
00171 return false;
00172 return true;
00173 }
00174
00175
00176 template<class View>
00177 forceinline bool
00178 Graph<View>::mark(Space& home) {
00179 using namespace ViewValGraph;
00180
00181 Region r(home);
00182
00183 int n_view_visited = 0;
00184 {
00185
00186
00187 Support::StaticStack<ValNode<View>*,Region> visit(r,n_val);
00188
00189
00190
00191 count++;
00192 {
00193 ValNode<View>** v = &val;
00194 while (*v != NULL)
00195 if (!(*v)->matching()) {
00196 if ((*v)->empty()) {
00197 *v = (*v)->next_val();
00198 n_val--;
00199 } else {
00200 (*v)->min = count;
00201 visit.push(*v);
00202 v = (*v)->next_val_ref();
00203 }
00204 } else {
00205 v = (*v)->next_val_ref();
00206 }
00207 }
00208
00209
00210 while (!visit.empty()) {
00211 ValNode<View>* n = visit.pop();
00212 for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e=e->next()) {
00213
00214 e->use();
00215 ViewNode<View>* x = e->view(n);
00216 if (x->min < count) {
00217 n_view_visited++;
00218 x->min = count;
00219 assert(x->edge_fst()->next() == x->edge_lst());
00220 ValNode<View>* m = x->edge_fst()->val(x);
00221 x->edge_fst()->use();
00222 if (m->min < count) {
00223 m->min = count;
00224 visit.push(m);
00225 }
00226 }
00227 }
00228 }
00229 }
00230
00231
00232 if (n_view_visited < n_view) {
00233 scc(home);
00234 return true;
00235 } else {
00236 return false;
00237 }
00238 }
00239
00240 template<class View>
00241 forceinline ExecStatus
00242 Graph<View>::prune(Space& home, bool& assigned) {
00243 using namespace ViewValGraph;
00244 assigned = false;
00245
00246 for (int i = n_view; i--; ) {
00247 ViewNode<View>* x = view[i];
00248 if (!x->edge_fst()->used(x)) {
00249 GECODE_ME_CHECK(x->view().eq(home,x->edge_fst()->val(x)->val()));
00250 x->edge_fst()->val(x)->matching(NULL);
00251 for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00252 e->unlink();
00253 view[i] = view[--n_view];
00254 assigned = true;
00255 } else {
00256 IterPruneVal<View> pv(view[i]);
00257 GECODE_ME_CHECK(view[i]->view().minus_v(home,pv,false));
00258 }
00259 }
00260 return ES_OK;
00261 }
00262
00263 }}}
00264
00265
00266