Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
9.8 kB · 324 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Christian Schulte <schulte@gecode.org> * * Copyright: * Christian Schulte, 2011 * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */
#include <gecode/int/distinct.hh>
namespace Gecode { namespace Int { namespace NValues {
template<class VY> forceinline IntBase<VY>::IntBase(Home home, ValSet& vs0, ViewArray<IntView>& x, VY y) : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home,x,y), vs(vs0) {}
template<class VY> forceinline IntBase<VY>::IntBase(Space& home, IntBase<VY>& p) : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home, p) { vs.update(home, p.vs); }
template<class VY> forceinline size_t IntBase<VY>::dispose(Space& home) { vs.dispose(home); (void) MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND> ::dispose(home); return sizeof(*this); }
template<class VY> PropCost IntBase<VY>::cost(const Space&, const ModEventDelta&) const { return PropCost::quadratic(PropCost::HI, x.size()); }
template<class VY> void IntBase<VY>::add(Space& home) { int n=x.size(); for (int i=n; i--; ) if (x[i].assigned()) { vs.add(home, x[i].val()); x[i] = x[--n]; } x.size(n); }
template<class VY> void IntBase<VY>::disjoint(Space& home, Region& r, int*& dis, int& n_dis) { // Compute positions of disjoint views int n=x.size(); dis = r.alloc<int>(n); n_dis = 0;
int i=0; while (i < n) switch (vs.compare(x[i])) { case Iter::Ranges::CS_SUBSET: // All values are already contained in vs, eliminate x[i] x[i].cancel(home, *this, PC_INT_DOM); x[i] = x[--n]; break; case Iter::Ranges::CS_DISJOINT: dis[n_dis++] = i++; break; case Iter::Ranges::CS_NONE: i++; break; default: GECODE_NEVER; } x.size(n); }
template<class VY> void IntBase<VY>::eliminate(Space& home) { int n=x.size(); for (int i=n; i--; ) if (vs.subset(x[i])) { // All values are already contained in vs, eliminate x[i] x[i].cancel(home, *this, PC_INT_DOM); x[i] = x[--n]; } x.size(n); }
template<class VY> ExecStatus IntBase<VY>::all_in_valset(Space& home) { for (int i=x.size(); i--; ) { ValSet::Ranges vsr(vs); GECODE_ME_CHECK(x[i].inter_r(home, vsr, false)); } return home.ES_SUBSUMED(*this); }
template<class VY> ExecStatus IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) { assert(n_dis > 0);
// At least one more value will be needed GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
Region r;
// Only one additional value is allowed if (y.max() == vs.size() + 1) { // Compute possible values ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis); for (int i=n_dis; i--; ) r_dis[i] = ViewRanges<IntView>(x[dis[i]]); Iter::Ranges::NaryInter iv(r, r_dis, n_dis); // Is there a common value at all? if (!iv()) return ES_FAILED; ValSet::Ranges vsr(vs); Iter::Ranges::NaryUnion pv(r,iv,vsr); // Enforce common values for (int i=x.size(); i--; ) { pv.reset(); GECODE_ME_CHECK(x[i].inter_r(home, pv, false)); } return ES_OK; }
// Compute independent set for lower bound // ovl is a bit-matrix defining whether two views overlap SymBitMatrix ovl(r,x.size()); // deg[i] is the degree of x[i] int* deg = r.alloc<int>(x.size()); // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i] int** ovl_i = r.alloc<int*>(x.size()); // n_ovl_i[i] defines how many integers are stored for ovl_i[i] int* n_ovl_i = r.alloc<int>(x.size()); {#ifndef NDEBUG // Initialize all to null pointers so that things crash ;-) for (int i=x.size(); i--; ) ovl_i[i] = nullptr;#endif // For each i there can be at most n_dis-1 entries in ovl_i[i] int* m = r.alloc<int>(n_dis*(n_dis-1)); for (int i=n_dis; i--; ) { deg[dis[i]] = 0; ovl_i[dis[i]] = m; m += n_dis-1; } }
// Initialize overlap matrix by analyzing the view ranges { // Compute how many events are needed // One event for the end marker int n_re = 1; // Two events for each range for (int i=n_dis; i--; ) for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) n_re += 2;
// Allocate and initialize events RangeEvent* re = r.alloc<RangeEvent>(n_re); { int j=0; for (int i=n_dis; i--; ) for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) { // Event when a range starts re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++; // Event when a range ends re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++; } // Make this the last event re[j].ret=RET_END; re[j].val=Int::Limits::infinity; assert(j+1 == n_re); } // Sort and process events Support::quicksort(re,n_re);
// Current views with a range being active Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size())); // Process all events for (int i=0; true; i++) switch (re[i].ret) { case RET_FST: // Process all overlapping views for (Iter::Values::BitSet<Support::BitSet<Region> > j(cur); j(); ++j) { int di = re[i].view, dj = j.val(); if (!ovl.get(di,dj)) { ovl.set(di,dj); ovl_i[di][deg[di]++] = dj; ovl_i[dj][deg[dj]++] = di; } } cur.set(static_cast<unsigned int>(re[i].view)); break; case RET_LST: cur.clear(static_cast<unsigned int>(re[i].view)); break; case RET_END: goto done; default: GECODE_NEVER; } done: r.free<RangeEvent>(re,n_re); }
// While deg changes, n_ovl_i remains unchanged and is needed, so copy it for (int i=n_dis; i--; ) { assert(deg[dis[i]] < n_dis); n_ovl_i[dis[i]] = deg[dis[i]]; }
// Views in the independent set int* ind = r.alloc<int>(n_dis); int n_ind = 0;
while (n_dis > 0) { int i_min = n_dis-1; int d_min = deg[dis[i_min]]; unsigned int s_min = x[dis[i_min]].size();
// Find view with smallest (degree,size) for (int i=n_dis-1; i--; ) if ((d_min > deg[dis[i]]) || ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) { i_min = i; d_min = deg[dis[i]]; s_min = x[dis[i]].size(); }
// i_min refers to view with smallest (degree,size) ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
// Filter out non disjoint views for (int i=n_dis; i--; ) if (ovl.get(dis[i],ind[n_ind-1])) { // Update degree information for (int j=n_ovl_i[dis[i]]; j--; ) deg[ovl_i[dis[i]][j]]--; // Eliminate view dis[i] = dis[--n_dis]; } } // Enforce lower bound GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
// Prune, if possible if (vs.size() + n_ind == y.max()) { // Only values from the indepent set a can be taken ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind); for (int i=n_ind; i--; ) r_ind[i] = ViewRanges<IntView>(x[ind[i]]); Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind); ValSet::Ranges vsr(vs); v_ind |= vsr; for (int i=x.size(); i--; ) { v_ind.reset(); GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false)); } } return ES_OK; }
template<class VY> forceinline ExecStatus IntBase<VY>::prune_upper(Space& home, Graph& g) { if (!g) { g.init(home,vs,x); } else { g.purge(); g.sync(); } GECODE_ME_CHECK(y.lq(home, g.size())); if (y.min() == g.size()) { // All values must be taken on if (vs.size() + x.size() == g.size()) { // This is in fact a distinct, simplify and rewrite for (int i=x.size(); i--; ) { ValSet::Ranges vsr(vs); GECODE_ME_CHECK(x[i].minus_r(home, vsr, false)); } GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home(*this),x)); } if (g.mark()) GECODE_ES_CHECK(g.prune(home)); } return ES_OK; }
}}}
// STATISTICS: int-prop