Generated on Thu Mar 22 10:39:36 2012 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  *  Last modified:
00010  *     $Date: 2011-09-08 14:34:40 +0200 (Thu, 08 Sep 2011) $ by $Author: schulte $
00011  *     $Revision: 12395 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // Find value information for construction of view value graph
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     // Definitly not enough values
00064     if (width < static_cast<unsigned int>(n_view))
00065       return ES_FAILED;
00066 
00067     // Initialize view nodes
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       // Values are dense: use a mapping
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       // Values are sparse
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     // Stack for view nodes to be rematched
00120     typename ViewValGraph::Graph<View>::ViewNodeStack re(r,n_view);
00121     // Synchronize nodes
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();      // Matching edge
00132         Edge<View>** p = x->val_edges_ref();
00133         Edge<View>*  e = *p;
00134         do {
00135           while (e->val(x)->val() < r.min()) {
00136             // Skip edge
00137             e->unlink(); e->mark();
00138             e = e->next_edge();
00139           }
00140           *p = e;
00141           assert(r.min() == e->val(x)->val());
00142           // This edges must be kept
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           // Matching has been deleted!
00157           m->val(x)->matching(NULL);
00158           re.push(x);
00159         }
00160         x->update();
00161       } else {
00162         // Just free edges
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       // Marks all edges as used that are on simple paths in the graph
00186       // that start from a free (unmatched node) by depth-first-search
00187       Support::StaticStack<ValNode<View>*,Region> visit(r,n_val);
00188       
00189       // Insert all free nodes: they can be only value nodes as we
00190       // have a maximum matching covering all view nodes
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       // Invariant: only value nodes are on the stack!
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           // Get the value node
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     // If all view nodes have been visited, also all edges are used!
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     // Tell constraints and also eliminate nodes and edges
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 // STATISTICS: int-prop
00266