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