matching.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * 00006 * Copyright: 00007 * Patrick Pekczynski, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $ 00011 * $Revision: 9692 $ 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 Int { namespace Sorted { 00039 00057 template<class View> 00058 inline bool 00059 glover(ViewArray<View>& x, ViewArray<View>& y, 00060 int tau[], int phi[], OfflineMinItem sequence[], int vertices[]) { 00061 00062 int xs = x.size(); 00063 OfflineMin seq(sequence, vertices, xs); 00064 int s = 0; 00065 seq.makeset(); 00066 00067 for (int z = 0; z < xs; z++) { // forall y nodes 00068 int maxy = y[z].max(); 00069 // creating the sequence of inserts and extractions from the queue 00070 for( ; s <xs && x[s].min() <= maxy; s++) { 00071 seq[s].iset = z; 00072 seq[z].rank++; 00073 } 00074 } 00075 00076 // offline-min-procedure 00077 for (int i = 0; i < xs; i++) { 00078 // the upper bound of the x-node should be minimal 00079 int perm = tau[i]; 00080 // find the iteration where \tau(i) became a maching candidate 00081 int iter = seq[perm].iset; 00082 if (iter<0) 00083 return false; 00084 int j = 0; 00085 j = seq.find_pc(iter); 00086 // check whether the sequence is valid 00087 if (j >= xs) 00088 return false; 00089 // if there is no intersection between the matching candidate 00090 // and the y node then there exists NO perfect matching 00091 if (x[perm].max() < y[j].min()) 00092 return false; 00093 phi[j] = perm; 00094 seq[perm].iset = -5; //remove from candidate set 00095 int sqjsucc = seq[j].succ; 00096 if (sqjsucc < xs) { 00097 seq.unite(j,sqjsucc,sqjsucc); 00098 } else { 00099 seq[seq[j].root].name = sqjsucc; // end of sequence achieved 00100 } 00101 00102 // adjust tree list 00103 int pr = seq[j].pred; 00104 if (pr != -1) 00105 seq[pr].succ = sqjsucc; 00106 if (sqjsucc != xs) 00107 seq[sqjsucc].pred = pr; 00108 } 00109 return true; 00110 } 00111 00116 template<class View> 00117 inline bool 00118 revglover(ViewArray<View>& x, ViewArray<View>& y, 00119 int tau[], int phiprime[], OfflineMinItem sequence[], 00120 int vertices[]) { 00121 00122 int xs = x.size(); 00123 OfflineMin seq(sequence, vertices, xs); 00124 int s = xs - 1; 00125 seq.makeset(); 00126 00127 int miny = 0; 00128 for (int z = xs; z--; ) { // forall y nodes 00129 miny = y[z].min(); 00130 // creating the sequence of inserts and extractions from the queue 00131 for ( ; s > -1 && x[tau[s]].max() >= miny; s--) { 00132 seq[tau[s]].iset = z; 00133 seq[z].rank++; 00134 } 00135 } 00136 00137 // offline-min-procedure 00138 for (int i = xs; i--; ) { 00139 int perm = i; 00140 int iter = seq[perm].iset; 00141 if (iter < 0) 00142 return false; 00143 int j = 0; 00144 j = seq.find_pc(iter); 00145 if (j <= -1) 00146 return false; 00147 // if there is no intersection between the matching candidate 00148 // and the y node then there exists NO perfect matching 00149 if (x[perm].min() > y[j].max()) 00150 return false; 00151 phiprime[j] = perm; 00152 seq[perm].iset = -5; 00153 int sqjsucc = seq[j].pred; 00154 if (sqjsucc >= 0) { 00155 seq.unite(j, sqjsucc, sqjsucc); 00156 } else { 00157 seq[seq[j].root].name = sqjsucc; // end of sequence achieved 00158 } 00159 00160 // adjust tree list 00161 int pr = seq[j].succ; 00162 if (pr != xs) 00163 seq[pr].pred = sqjsucc; 00164 if (sqjsucc != -1) 00165 seq[sqjsucc].succ = pr; 00166 } 00167 return true; 00168 } 00169 00170 }}} 00171 00172 // STATISTICS: int-prop 00173