main page modules namespaces classes files
Gecode home

search for 

matching.icc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
 *
 *  Copyright:
 *     Patrick Pekczynski, 2004
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:03:26 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3512 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

namespace Gecode { namespace Int { namespace Sortedness {

  template <class View, class Tuple, bool Perm>
  forceinline bool
  glover(Space* home,
         ViewArray<Tuple>& xz,
         ViewArray<View>& y,
         int tau[],
         int phi[],
         OfflineMinItem sequence[],
         int vertices[]) {

    int xs = xz.size();
    OfflineMin seq(sequence, vertices, xs);
    int s  = 0;
    seq.makeset();

    for (int z = 0; z < xs; z++) {  // forall y nodes
      int maxy = y[z].max();
      // creating the sequence of inserts and extractions from the queue
//       for( ; s <xs && xz[s][0].min() <= maxy; s++) {
      for( ; s <xs && xz[s][0].min() <= maxy; s++) {
        seq[s].iset = z;
        seq[z].rank++;
      }
    }

    // offline-min-procedure
    for (int i = 0; i < xs; i++) {
      // the upper bound of the x-node should be minimal
      int perm = tau[i];
      // find the iteration where \tau(i) became a maching candidate
      int iter = seq[perm].iset;
      if (iter<0) {
        return false;
      }
      int j = 0;
      j = seq.find_pc(iter);
      // check whether the sequence is valid
      if (j >= xs) {
        return false;
      }
      // if there is no intersection between the matching candidate
      // and the y node then there exists NO perfect matching
      if (xz[perm][0].max() < y[j].min()) {
        return false;
      }
      phi[j]         = perm;
      seq[perm].iset = -5;           //remove from candidate set
      int sqjsucc    = seq[j].succ;
      if (sqjsucc < xs){
        seq.unite(j,sqjsucc,sqjsucc);
      } else {
        seq[seq[j].root].name = sqjsucc; // end of sequence achieved
      }

      // adjust tree list
      int pr = seq[j].pred;
      if (pr != -1) {
        seq[pr].succ = sqjsucc;
      }
      if (sqjsucc != xs) {
        seq[sqjsucc].pred = pr;
      }
    }
    return true;
  }

  template <class View, class Tuple, bool Perm>
  forceinline bool
  revglover(Space* home,
            ViewArray<Tuple>& xz,
            ViewArray<View>& y,
            int tau[],
            int phiprime[],
            OfflineMinItem sequence[],
            int vertices[]) {

    int xs = xz.size();
    OfflineMin seq(sequence, vertices, xs);
    int s  = xs - 1;
    seq.makeset();

    int miny = 0;
    for (int z = xs; z--; ) {     // forall y nodes
      miny = y[z].min();
      // creating the sequence of inserts and extractions from the queue
      for ( ; s > -1 && xz[tau[s]][0].max() >= miny; s--) {
        seq[tau[s]].iset = z;
        seq[z].rank++;
      }
    }

    // offline-min-procedure
    for (int i = xs; i--; ) {
      int perm = i;
      int iter = seq[perm].iset;
      if (iter < 0) {
        return false;
      }
      int j = 0;
      j = seq.find_pc(iter);
      if (j <= -1) {
        return false;
      }
      // if there is no intersection between the matching candidate
      // and the y node then there exists NO perfect matching
      if (xz[perm][0].min() > y[j].max()) {
        return false;
      }
      phiprime[j]    = perm;
      seq[perm].iset = -5;
      int sqjsucc    = seq[j].pred;
      if (sqjsucc >= 0) {
        seq.unite(j, sqjsucc, sqjsucc);
      } else {
        seq[seq[j].root].name = sqjsucc; // end of sequence achieved
      }

      // adjust tree list
      int pr = seq[j].succ;
      if (pr != xs) {
        seq[pr].pred = sqjsucc;
      }
      if (sqjsucc != -1) {
        seq[sqjsucc].succ = pr;
      }
    }
    return true;
  }

}}}

// STATISTICS: int-prop