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