Generated on Fri Oct 19 11:25:04 2018 for Gecode by doxygen 1.6.3

graph.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <climits>
00035 
00036 namespace Gecode { namespace Int { namespace Distinct {
00037 
00038   template<class View>
00039   forceinline
00040   Graph<View>::Graph(void) {}
00041 
00042   template<class View>
00043   forceinline ExecStatus
00044   Graph<View>::init(Space& home, ViewArray<View>& x) {
00045     using namespace ViewValGraph;
00046     n_view = x.size();
00047     view = home.alloc<ViewNode<View>*>(n_view);
00048 
00049     // Find value information for construction of view value graph
00050     int min = x[0].min();
00051     int max = x[0].max();
00052     for (int i=1; i<n_view; i++) {
00053       min = std::min(min,x[i].min());
00054       max = std::max(max,x[i].max());
00055     }
00056 
00057     unsigned int width = static_cast<unsigned int>(max-min+1);
00058 
00059     // Definitly not enough values
00060     if (width < static_cast<unsigned int>(n_view))
00061       return ES_FAILED;
00062 
00063     // Initialize view nodes
00064     for (int i=0; i<n_view; i++)
00065       view[i] = new (home) ViewNode<View>(x[i]);
00066 
00067     Region r;
00068 
00069     if (static_cast<unsigned int>(n_view)*4 >= width) {
00070       // Values are dense: use a mapping
00071       ValNode<View>** val2node = r.alloc<ValNode<View>* >(width);
00072 
00073       for (unsigned int i=0U; i<width; i++)
00074         val2node[i]=NULL;
00075 
00076       for (int i=0; i<n_view; i++) {
00077         Edge<View>** edge_p = view[i]->val_edges_ref();
00078         for (ViewValues<View> xi(x[i]); xi(); ++xi) {
00079           if (val2node[xi.val()-min] == NULL)
00080             val2node[xi.val()-min] = new (home) ValNode<View>(xi.val());
00081           *edge_p = new (home) Edge<View>(val2node[xi.val()-min],view[i]);
00082           edge_p = (*edge_p)->next_edge_ref();
00083         }
00084         *edge_p = NULL;
00085       }
00086 
00087       for (unsigned int i=width; i--; )
00088         if (val2node[i] != NULL) {
00089           val2node[i]->next_val(val);
00090           val = val2node[i];
00091           n_val++;
00092         }
00093 
00094     } else {
00095       // Values are sparse
00096       for (int i=0; i<n_view; i++)
00097         ViewValGraph::Graph<View>::init(home,view[i]);
00098     }
00099 
00100     if (n_val < n_view)
00101       return ES_FAILED;
00102 
00103     typename ViewValGraph::Graph<View>::ViewNodeStack m(r,n_view);
00104     for (int i=0; i<n_view; i++)
00105       if (!match(m,view[i]))
00106         return ES_FAILED;
00107     return ES_OK;
00108   }
00109 
00110   template<class View>
00111   forceinline bool
00112   Graph<View>::sync(void) {
00113     using namespace ViewValGraph;
00114     Region r;
00115     // Stack for view nodes to be rematched
00116     typename ViewValGraph::Graph<View>::ViewNodeStack re(r,n_view);
00117     // Synchronize nodes
00118     for (int i = n_view; i--; ) {
00119       ViewNode<View>* x = view[i];
00120       GECODE_ASSUME(x != NULL);
00121       if (x->view().assigned()) {
00122         x->edge_fst()->val(x)->matching(NULL);
00123         for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00124           e->unlink();
00125         view[i] = view[--n_view];
00126       } else if (x->changed()) {
00127         ViewRanges<View> rx(x->view());
00128         Edge<View>*  m = x->edge_fst();      // Matching edge
00129         Edge<View>** p = x->val_edges_ref();
00130         Edge<View>*  e = *p;
00131         GECODE_ASSUME(e != NULL);
00132         do {
00133           while (e->val(x)->val() < rx.min()) {
00134             // Skip edge
00135             e->unlink(); e->mark();
00136             e = e->next_edge();
00137           }
00138           *p = e;
00139           assert(rx.min() == e->val(x)->val());
00140           // This edges must be kept
00141           for (unsigned int j=rx.width(); j--; ) {
00142             e->free();
00143             p = e->next_edge_ref();
00144             e = e->next_edge();
00145           }
00146           ++rx;
00147         } while (rx());
00148         *p = NULL;
00149         while (e != NULL) {
00150           e->unlink(); e->mark();
00151           e = e->next_edge();
00152         }
00153         if (m->marked()) {
00154           // Matching has been deleted!
00155           m->val(x)->matching(NULL);
00156           re.push(x);
00157         }
00158         x->update();
00159       } else {
00160         // Just free edges
00161         for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00162           e->free();
00163       }
00164     }
00165 
00166     typename ViewValGraph::Graph<View>::ViewNodeStack m(r,n_view);
00167     while (!re.empty())
00168       if (!match(m,re.pop()))
00169         return false;
00170     return true;
00171   }
00172 
00173 
00174   template<class View>
00175   forceinline bool
00176   Graph<View>::mark(void) {
00177     using namespace ViewValGraph;
00178 
00179     Region r;
00180 
00181     int n_view_visited = 0;
00182     {
00183       // Marks all edges as used that are on simple paths in the graph
00184       // that start from a free (unmatched node) by depth-first-search
00185       Support::StaticStack<ValNode<View>*,Region> visit(r,n_val);
00186 
00187       // Insert all free nodes: they can be only value nodes as we
00188       // have a maximum matching covering all view nodes
00189       count++;
00190       {
00191         ValNode<View>** v = &val;
00192         while (*v != NULL)
00193           if (!(*v)->matching()) {
00194             if ((*v)->empty()) {
00195               *v = (*v)->next_val();
00196               n_val--;
00197             } else {
00198               (*v)->min = count;
00199               visit.push(*v);
00200               v = (*v)->next_val_ref();
00201             }
00202           } else {
00203             v = (*v)->next_val_ref();
00204           }
00205       }
00206 
00207       // Invariant: only value nodes are on the stack!
00208       while (!visit.empty()) {
00209         ValNode<View>* n = visit.pop();
00210         for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e=e->next()) {
00211           // Get the value node
00212           e->use();
00213           ViewNode<View>* x = e->view(n);
00214           if (x->min < count) {
00215             n_view_visited++;
00216             x->min = count;
00217             assert(x->edge_fst()->next() == x->edge_lst());
00218             ValNode<View>* m = x->edge_fst()->val(x);
00219             x->edge_fst()->use();
00220             if (m->min < count) {
00221               m->min = count;
00222               visit.push(m);
00223             }
00224           }
00225         }
00226       }
00227     }
00228 
00229     // If all view nodes have been visited, also all edges are used!
00230     if (n_view_visited < n_view) {
00231       scc();
00232       return true;
00233     } else {
00234       return false;
00235     }
00236   }
00237 
00238   template<class View>
00239   forceinline ExecStatus
00240   Graph<View>::prune(Space& home, bool& assigned) {
00241     using namespace ViewValGraph;
00242     assigned = false;
00243     // Tell constraints and also eliminate nodes and edges
00244     for (int i = n_view; i--; ) {
00245       ViewNode<View>* x = view[i];
00246       if (!x->edge_fst()->used(x)) {
00247         GECODE_ME_CHECK(x->view().eq(home,x->edge_fst()->val(x)->val()));
00248         x->edge_fst()->val(x)->matching(NULL);
00249         for (Edge<View>* e = x->val_edges(); e != NULL; e = e->next_edge())
00250           e->unlink();
00251         view[i] = view[--n_view];
00252         assigned = true;
00253       } else {
00254         IterPruneVal<View> pv(view[i]);
00255         GECODE_ME_CHECK(view[i]->view().minus_v(home,pv,false));
00256       }
00257     }
00258     return ES_OK;
00259   }
00260 
00261 }}}
00262 
00263 // STATISTICS: int-prop
00264