Generated on Mon Nov 30 23:53:19 2009 for Gecode by doxygen 1.6.1

base.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, 2007
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-10-14 10:56:06 +0200 (Wed, 14 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9902 $
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 namespace Gecode { namespace Graph { namespace Circuit {
00039 
00040   template<class View>
00041   forceinline
00042   Base<View>::Base(Home home, ViewArray<View>& x)
00043     : NaryPropagator<View,Int::PC_INT_DOM>(home,x), y(home,x) {
00044     home.notice(*this,AP_WEAKLY);
00045   }
00046 
00047   template<class View>
00048   forceinline
00049   Base<View>::Base(Space& home, bool share, Base<View>& p)
00050     : NaryPropagator<View,Int::PC_INT_DOM>(home,share,p) {
00051     y.update(home,share,p.y);
00052   }
00053 
00055   template<class View>
00056   class SsccInfo {
00057   public:
00058     int min, low, pre;
00059     Int::ViewValues<View> v;
00060   };
00061 
00063   template<class View>
00064   class TellInfo {
00065   public:
00066     View x; int n;
00067   };
00068 
00069   template<class View>
00070   ExecStatus
00071   Base<View>::connected(Space& home) {
00072     int n = x.size();
00073 
00075     int start = 0;
00076     while (x[start].assigned()) {
00077       start = x[start].val();
00078       if (start == 0) break;
00079     }
00080 
00082     Region r(home);
00083     SsccInfo<View>* si = r.alloc<SsccInfo<View> >(n);
00084     unsigned int n_edges = 0;
00085     for (int i=n; i--; ) {
00086       n_edges += x[i].size();
00087       si[i].pre=-1;
00088     }
00089 
00090     // Stack to remember which nodes have not been processed completely
00091     Support::StaticStack<int,Region> next(r,n);
00092 
00093     // Array to remember which mandatory tells need to be done
00094     TellInfo<View>* eq = r.alloc<TellInfo<View> >(n);
00095     int n_eq = 0;
00096 
00097     // Array to remember which edges need to be pruned
00098     TellInfo<View>* nq = r.alloc<TellInfo<View> >(n_edges);
00099     int n_nq = 0;
00100 
00101     /*
00102      * Check whether there is a single strongly connected component.
00103      * This is a downstripped version of Tarjan's algorithm as
00104      * the computation of sccs proper is not needed. In addition, it
00105      * checks a mandatory condition for a graph to be Hamiltonian
00106      * (due to Mats Carlsson).
00107      *
00108      * To quote Mats: Suppose you do a depth-first search of the graph.
00109      * In that search, the root node will have a number of child subtrees
00110      * T1, ..., Tn. By construction, if i<j then there is no edge from
00111      * Ti to Tj. The necessary condition for Hamiltonianicity is that
00112      * there be an edge from Ti+1 to Ti, for 0 < i < n.
00113      *
00114      * In addition, we do the following: if there is only a single edge
00115      * from Ti+1 to Ti, then it must be mandatory and the variable must
00116      * be assigned to that value.
00117      *
00118      * The same holds true for a back edge from T0 to the root node.
00119      *
00120      * Then, all edges that reach from Ti+k+1 to Ti can be pruned.
00121      *
00122      */
00123 
00124     // Start always at node start
00125     int i = start;
00126     // Counter for scc
00127     int cnt = 0;
00128     // Smallest preorder number of last subtree (initially, the root node)
00129     int subtree_min = 0;
00130     // Largest preorder number of last subtree (initially, the root node)
00131     int subtree_max = 0;
00132     // Number of back edges into last subtree or root
00133     int back = 0;
00134   start:
00135     si[i].min = si[i].pre = si[i].low = cnt++;
00136     si[i].v.init(x[i]);
00137     do {
00138       if (si[si[i].v.val()].pre < 0) {
00139         next.push(i);
00140         i=si[i].v.val();
00141         goto start;
00142       } else if ((subtree_min <= si[si[i].v.val()].pre) &&
00143                  (si[si[i].v.val()].pre <= subtree_max)) {
00144         back++;
00145         eq[n_eq].x = x[i];
00146         eq[n_eq].n = si[i].v.val();
00147       } else if (si[si[i].v.val()].pre < subtree_min) {
00148         nq[n_nq].x = x[i];
00149         nq[n_nq].n = si[i].v.val();
00150         n_nq++;
00151       }
00152     cont:
00153       if (si[si[i].v.val()].low < si[i].min)
00154         si[i].min = si[si[i].v.val()].low;
00155       ++si[i].v;
00156     } while (si[i].v());
00157     if (si[i].min < si[i].low) {
00158       si[i].low = si[i].min;
00159     } else if (i != start) {
00160       // If it is not the first node visited, there is more than one SCC
00161       return ES_FAILED;
00162     }
00163     if (!next.empty()) {
00164       i=next.pop();
00165       if (i == start) {
00166         // No back edge
00167         if (back == 0)
00168           return ES_FAILED;
00169         // Exactly one back edge, make it mandatory (keep topmost entry on ti)
00170         if (back == 1)
00171           n_eq++;
00172         back        = 0;
00173         subtree_min = subtree_max+1;
00174         subtree_max = cnt-1;
00175       }
00176       goto cont;
00177     }
00178     // Whether all nodes have been visited
00179     if (cnt != n)
00180       return ES_FAILED;
00181     ExecStatus es = ES_FIX;
00182     // Assign all mandatory edges
00183     while (n_eq-- > 0) {
00184       ModEvent me = eq[n_eq].x.eq(home,eq[n_eq].n);
00185       if (me_failed(me))
00186         return ES_FAILED;
00187       if (me_modified(me))
00188         es = ES_NOFIX;
00189     }
00190     // Remove all edges that would require a non-simple cycle
00191     while (n_nq-- > 0) {
00192       ModEvent me = nq[n_nq].x.nq(home,nq[n_nq].n);
00193       if (me_failed(me))
00194         return ES_FAILED;
00195       if (me_modified(me))
00196         es = ES_NOFIX;
00197     }
00198     return es;
00199   }
00200 
00201   template<class View>
00202   ExecStatus
00203   Base<View>::path(Space& home) {
00204     // Prunes that partial assigned paths are not completed to cycles
00205 
00206     int n=x.size();
00207 
00208     Region r(home);
00209 
00210     // The path starting at assigned x[i] ends at x[end[j]] which is
00211     // not assigned.
00212     int* end = r.alloc<int>(n);
00213     for (int i=n; i--; )
00214       end[i]=-1;
00215 
00216     // A stack that records all indices i such that end[i] != -1
00217     Support::StaticStack<int,Region> tell(r,n);
00218 
00219     for (int i=y.size(); i--; ) {
00220       assert(!y[i].assigned());
00221       // Non-assigned views serve as starting points for assigned paths
00222       Int::ViewValues<View> v(y[i]);
00223       // Try all connected values
00224       do {
00225         int j0=v.val();
00226         // Starting point for not yet followed assigned path found
00227         if (x[j0].assigned() && (end[j0] < 0)) {
00228           // Follow assigned path until non-assigned view:
00229           // all assigned view on the paths can be skipped, as
00230           // if x[i] is assigned to j, then x[j] will only have
00231           // x[i] as predecessor due to propagating distinct.
00232           int j = j0;
00233           do {
00234             j=x[j].val();
00235           } while (x[j].assigned());
00236           // Now there cannot be a cycle from x[j] to x[v.val()]!
00237           // However, the tell cannot be done here as j might be
00238           // equal to i and might hence kill the iterator v!
00239           end[j0]=j; tell.push(j0);
00240         }
00241         ++v;
00242       } while (v());
00243     }
00244 
00245     // Now do the tells based on the end information
00246     while (!tell.empty()) {
00247       int i = tell.pop();
00248       assert(end[i] >= 0);
00249       GECODE_ME_CHECK(x[end[i]].nq(home,i));
00250     }
00251     return ES_NOFIX;
00252   }
00253 
00254   template<class View>
00255   forceinline size_t
00256   Base<View>::dispose(Space& home) {
00257     home.ignore(*this,AP_WEAKLY);
00258     (void) NaryPropagator<View,Int::PC_INT_DOM>::dispose(home);
00259     return sizeof(*this);
00260   }
00261 
00262 }}}
00263 
00264 // STATISTICS: graph-prop
00265