Generated on Mon May 5 05:53:58 2008 for Gecode by doxygen 1.5.5

matching.icc

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: 2007-11-08 15:53:26 +0100 (Thu, 08 Nov 2007) $ by $Author: tack $
00011  *     $Revision: 5219 $
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, class Tuple, bool Perm>
00058   inline bool
00059   glover(Space*,
00060          ViewArray<Tuple>& xz,
00061          ViewArray<View>& y,
00062          int tau[],
00063          int phi[],
00064          OfflineMinItem sequence[],
00065          int vertices[]) {
00066 
00067     int xs = xz.size();
00068     OfflineMin seq(sequence, vertices, xs);
00069     int s  = 0;
00070     seq.makeset();
00071 
00072     for (int z = 0; z < xs; z++) {  // forall y nodes
00073       int maxy = y[z].max();
00074       // creating the sequence of inserts and extractions from the queue
00075       for( ; s <xs && xz[s][0].min() <= maxy; s++) {
00076         seq[s].iset = z;
00077         seq[z].rank++;
00078       }
00079     }
00080 
00081     // offline-min-procedure
00082     for (int i = 0; i < xs; i++) {
00083       // the upper bound of the x-node should be minimal
00084       int perm = tau[i];
00085       // find the iteration where \tau(i) became a maching candidate
00086       int iter = seq[perm].iset;
00087       if (iter<0)
00088         return false;
00089       int j = 0;
00090       j = seq.find_pc(iter);
00091       // check whether the sequence is valid
00092       if (j >= xs)
00093         return false;
00094       // if there is no intersection between the matching candidate
00095       // and the y node then there exists NO perfect matching
00096       if (xz[perm][0].max() < y[j].min())
00097         return false;
00098       phi[j]         = perm;
00099       seq[perm].iset = -5;           //remove from candidate set
00100       int sqjsucc    = seq[j].succ;
00101       if (sqjsucc < xs) {
00102         seq.unite(j,sqjsucc,sqjsucc);
00103       } else {
00104         seq[seq[j].root].name = sqjsucc; // end of sequence achieved
00105       }
00106 
00107       // adjust tree list
00108       int pr = seq[j].pred;
00109       if (pr != -1)
00110         seq[pr].succ = sqjsucc;
00111       if (sqjsucc != xs)
00112         seq[sqjsucc].pred = pr;
00113     }
00114     return true;
00115   }
00116 
00121   template <class View, class Tuple, bool Perm>
00122   inline bool
00123   revglover(Space*,
00124             ViewArray<Tuple>& xz,
00125             ViewArray<View>& y,
00126             int tau[],
00127             int phiprime[],
00128             OfflineMinItem sequence[],
00129             int vertices[]) {
00130 
00131     int xs = xz.size();
00132     OfflineMin seq(sequence, vertices, xs);
00133     int s  = xs - 1;
00134     seq.makeset();
00135 
00136     int miny = 0;
00137     for (int z = xs; z--; ) {     // forall y nodes
00138       miny = y[z].min();
00139       // creating the sequence of inserts and extractions from the queue
00140       for ( ; s > -1 && xz[tau[s]][0].max() >= miny; s--) {
00141         seq[tau[s]].iset = z;
00142         seq[z].rank++;
00143       }
00144     }
00145 
00146     // offline-min-procedure
00147     for (int i = xs; i--; ) {
00148       int perm = i;
00149       int iter = seq[perm].iset;
00150       if (iter < 0)
00151         return false;
00152       int j = 0;
00153       j = seq.find_pc(iter);
00154       if (j <= -1)
00155         return false;
00156       // if there is no intersection between the matching candidate
00157       // and the y node then there exists NO perfect matching
00158       if (xz[perm][0].min() > y[j].max())
00159         return false;
00160       phiprime[j]    = perm;
00161       seq[perm].iset = -5;
00162       int sqjsucc    = seq[j].pred;
00163       if (sqjsucc >= 0) {
00164         seq.unite(j, sqjsucc, sqjsucc);
00165       } else {
00166         seq[seq[j].root].name = sqjsucc; // end of sequence achieved
00167       }
00168 
00169       // adjust tree list
00170       int pr = seq[j].succ;
00171       if (pr != xs)
00172         seq[pr].pred = sqjsucc;
00173       if (sqjsucc != -1)
00174         seq[sqjsucc].succ = pr;
00175     }
00176     return true;
00177   }
00178 
00179 }}}
00180 
00181 // STATISTICS: int-prop
00182