Generated on Thu Apr 11 13:59:12 2019 for Gecode by doxygen 1.6.3

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