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