layered-graph.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2004
*
* 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 <climits>
#include <algorithm>
namespace Gecode { namespace Int { namespace Extensional {
template<class Var>
class VarTraits {};
template<>
class VarTraits<IntVar> {
public:
typedef Int::IntView View;
};
template<>
class VarTraits<BoolVar> {
public:
typedef Int::BoolView View;
};
/*
* States
*/
template<class View, class Val, class Degree, class StateIdx>
forceinline void
LayeredGraph<View,Val,Degree,StateIdx>::State::init(void) {
i_deg=o_deg=0;
}
template<class View, class Val, class Degree, class StateIdx>
forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State&
LayeredGraph<View,Val,Degree,StateIdx>::i_state(int i, StateIdx is) {
return layers[i].states[is];
}
template<class View, class Val, class Degree, class StateIdx>
forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State&
LayeredGraph<View,Val,Degree,StateIdx>::i_state
(int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
return i_state(i,e.i_state);
}
template<class View, class Val, class Degree, class StateIdx>
forceinline bool
LayeredGraph<View,Val,Degree,StateIdx>::i_dec
(int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
return --i_state(i,e).o_deg == 0;
}
template<class View, class Val, class Degree, class StateIdx>
forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State&
LayeredGraph<View,Val,Degree,StateIdx>::o_state(int i, StateIdx os) {
return layers[i+1].states[os];
}
template<class View, class Val, class Degree, class StateIdx>
forceinline typename LayeredGraph<View,Val,Degree,StateIdx>::State&
LayeredGraph<View,Val,Degree,StateIdx>::o_state
(int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
return o_state(i,e.o_state);
}
template<class View, class Val, class Degree, class StateIdx>
forceinline bool
LayeredGraph<View,Val,Degree,StateIdx>::o_dec
(int i, const typename LayeredGraph<View,Val,Degree,StateIdx>::Edge& e) {
return --o_state(i,e).i_deg == 0;
}
/*
* Value iterator
*/
template<class View, class Val, class Degree, class StateIdx>
forceinline
LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::LayerValues(void) {}
template<class View, class Val, class Degree, class StateIdx>
forceinline
LayeredGraph<View,Val,Degree,StateIdx>::LayerValues
::LayerValues(const Layer& l)
: s1(l.support), s2(l.support+l.size) {}
template<class View, class Val, class Degree, class StateIdx>
forceinline void
LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::init(const Layer& l) {
s1=l.support; s2=l.support+l.size;
}
template<class View, class Val, class Degree, class StateIdx>
forceinline bool
LayeredGraph<View,Val,Degree,StateIdx>::LayerValues
::operator ()(void) const {
return s1<s2;
}
template<class View, class Val, class Degree, class StateIdx>
forceinline void
LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::operator ++(void) {
s1++;
}
template<class View, class Val, class Degree, class StateIdx>
forceinline int
LayeredGraph<View,Val,Degree,StateIdx>::LayerValues::val(void) const {
return s1->val;
}
/*
* Index advisors
*
*/
template<class View, class Val, class Degree, class StateIdx>
forceinline
LayeredGraph<View,Val,Degree,StateIdx>::Index::Index(Space& home, Propagator& p,
Council<Index>& c,
int i0)
: Advisor(home,p,c), i(i0) {}
template<class View, class Val, class Degree, class StateIdx>
forceinline
LayeredGraph<View,Val,Degree,StateIdx>::Index::Index(Space& home, Index& a)
: Advisor(home,a), i(a.i) {}
/*
* Index ranges
*
*/
template<class View, class Val, class Degree, class StateIdx>
forceinline
LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::IndexRange(void)
: _fst(INT_MAX), _lst(INT_MIN) {}
template<class View, class Val, class Degree, class StateIdx>
forceinline void
LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::reset(void) {
_fst=INT_MAX; _lst=INT_MIN;
}
template<class View, class Val, class Degree, class StateIdx>
forceinline void
LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::add(int i) {
_fst=std::min(_fst,i); _lst=std::max(_lst,i);
}
template<class View, class Val, class Degree, class StateIdx>
forceinline void
LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::add
(const typename LayeredGraph<View,Val,Degree,StateIdx>::IndexRange& ir) {
_fst=std::min(_fst,ir._fst); _lst=std::max(_lst,ir._lst);
}
template<class View, class Val, class Degree, class StateIdx>
forceinline bool
LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::empty(void) const {
return _fst>_lst;
}
template<class View, class Val, class Degree, class StateIdx>
forceinline void
LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::lshift(int n) {
if (empty())
return;
if (n > _lst) {
reset();
} else {
_fst = std::max(0,_fst-n);
_lst -= n;
}
}
template<class View, class Val, class Degree, class StateIdx>
forceinline int
LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::fst(void) const {
return _fst;
}
template<class View, class Val, class Degree, class StateIdx>
forceinline int
LayeredGraph<View,Val,Degree,StateIdx>::IndexRange::lst(void) const {
return _lst;
}
/*
* The layered graph
*
*/
template<class View, class Val, class Degree, class StateIdx>
template<class Var>
forceinline
LayeredGraph<View,Val,Degree,StateIdx>::LayeredGraph(Home home,
const VarArgArray<Var>& x,
const DFA& dfa)
: Propagator(home), c(home), n(x.size()),
max_states(static_cast<StateIdx>(dfa.n_states())) {
assert(n > 0);
}
template<class View, class Val, class Degree, class StateIdx>
forceinline void
LayeredGraph<View,Val,Degree,StateIdx>::audit(void) {
#ifdef GECODE_AUDIT
// Check states and edge information to be consistent
unsigned int n_e = 0; // Number of edges
unsigned int n_s = 0; // Number of states
StateIdx m_s = 0; // Maximal number of states per layer
for (int i=n; i--; ) {
n_s += layers[i].n_states;
m_s = std::max(m_s,layers[i].n_states);
for (ValSize j=layers[i].size; j--; )
n_e += layers[i].support[j].n_edges;
}
n_s += layers[n].n_states;
m_s = std::max(m_s,layers[n].n_states);
assert(n_e == n_edges);
assert(n_s <= n_states);
assert(m_s <= max_states);
#endif
}
template<class View, class Val, class Degree, class StateIdx>
template<class Var>
forceinline ExecStatus
LayeredGraph<View,Val,Degree,StateIdx>::initialize(Space& home,
const VarArgArray<Var>& x,
const DFA& dfa) {
Region r;
// Allocate memory for layers
layers = home.alloc<Layer>(n+1);
// Allocate temporary memory for all possible states
State* states = r.alloc<State>(max_states*(n+1));
for (int i=0; i<static_cast<int>(max_states)*(n+1); i++)
states[i].init();
for (int i=0; i<n+1; i++)
layers[i].states = states + i*max_states;
// Allocate temporary memory for edges
Edge* edges = r.alloc<Edge>(dfa.max_degree());
// Mark initial state as being reachable
i_state(0,0).i_deg = 1;
// Forward pass: add transitions
for (int i=0; i<n; i++) {
layers[i].x = x[i];
layers[i].support = home.alloc<Support>(layers[i].x.size());
ValSize j=0;
// Enter links leaving reachable states (indegree != 0)
for (ViewValues<View> nx(layers[i].x); nx(); ++nx) {
Degree n_edges=0;
for (DFA::Transitions t(dfa,nx.val()); t(); ++t)
if (i_state(i,static_cast<StateIdx>(t.i_state())).i_deg != 0) {
i_state(i,static_cast<StateIdx>(t.i_state())).o_deg++;
o_state(i,static_cast<StateIdx>(t.o_state())).i_deg++;
edges[n_edges].i_state = static_cast<StateIdx>(t.i_state());
edges[n_edges].o_state = static_cast<StateIdx>(t.o_state());
n_edges++;
}
assert(n_edges <= dfa.max_degree());
// Found support for value
if (n_edges > 0) {
Support& s = layers[i].support[j];
s.val = static_cast<Val>(nx.val());
s.n_edges = n_edges;
s.edges = Heap::copy(home.alloc<Edge>(n_edges),edges,n_edges);
j++;
}
}
if ((layers[i].size = j) == 0)
return ES_FAILED;
}
// Mark final states as reachable
for (int s=dfa.final_fst(); s<dfa.final_lst(); s++)
if (o_state(n-1,static_cast<StateIdx>(s)).i_deg != 0)
o_state(n-1,static_cast<StateIdx>(s)).o_deg = 1;
// Backward pass: prune all transitions that do not lead to final state
for (int i=n; i--; ) {
ValSize k=0;
for (ValSize j=0; j<layers[i].size; j++) {
Support& s = layers[i].support[j];
for (Degree d=s.n_edges; d--; )
if (o_state(i,s.edges[d]).o_deg == 0) {
// Adapt states
i_dec(i,s.edges[d]); o_dec(i,s.edges[d]);
// Prune edge
s.edges[d] = s.edges[--s.n_edges];
}
// Value has support, copy the support information
if (s.n_edges > 0)
layers[i].support[k++]=s;
}
if ((layers[i].size = k) == 0)
return ES_FAILED;
LayerValues lv(layers[i]);
GECODE_ME_CHECK(layers[i].x.narrow_v(home,lv,false));
if (!layers[i].x.assigned())
layers[i].x.subscribe(home, *new (home) Index(home,*this,c,i));
}
// Copy and compress states, setup other information
{
// State map for in-states
StateIdx* i_map = r.alloc<StateIdx>(max_states);
// State map for out-states
StateIdx* o_map = r.alloc<StateIdx>(max_states);
// Number of in-states
StateIdx i_n = 0;
// Initialize map for in-states (special for last layer)
// Degree for single final state
unsigned int d = 0;
for (StateIdx j=0; j<max_states; j++)
d += static_cast<unsigned int>(layers[n].states[j].i_deg);
// Check whether all final states can be joined to a single state
if (d >
static_cast<unsigned int>
(Gecode::Support::IntTypeTraits<Degree>::max)) {
// Initialize map for in-states
for (StateIdx j=max_states; j--; )
if ((layers[n].states[j].o_deg != 0) ||
(layers[n].states[j].i_deg != 0))
i_map[j]=i_n++;
} else {
i_n = 1;
for (StateIdx j=max_states; j--; ) {
layers[n].states[j].init();
i_map[j] = 0;
}
layers[n].states[0].i_deg = static_cast<Degree>(d);
layers[n].states[0].o_deg = 1;
}
layers[n].n_states = i_n;
// Total number of states
n_states = i_n;
// Total number of edges
n_edges = 0;
// New maximal number of states
StateIdx max_s = i_n;
for (int i=n; i--; ) {
// In-states become out-states
std::swap(o_map,i_map); i_n=0;
// Initialize map for in-states
for (StateIdx j=max_states; j--; )
if ((layers[i].states[j].o_deg != 0) ||
(layers[i].states[j].i_deg != 0))
i_map[j]=i_n++;
layers[i].n_states = i_n;
n_states += i_n;
max_s = std::max(max_s,i_n);
// Update states in edges
for (ValSize j=layers[i].size; j--; ) {
Support& ls = layers[i].support[j];
n_edges += ls.n_edges;
for (Degree deg=ls.n_edges; deg--; ) {
ls.edges[deg].i_state = i_map[ls.edges[deg].i_state];
ls.edges[deg].o_state = o_map[ls.edges[deg].o_state];
}
}
}
// Allocate and copy states
State* a_states = home.alloc<State>(n_states);
for (int i=n+1; i--; ) {
StateIdx k=0;
for (StateIdx j=max_states; j--; )
if ((layers[i].states[j].o_deg != 0) ||
(layers[i].states[j].i_deg != 0))
a_states[k++] = layers[i].states[j];
assert(k == layers[i].n_states);
layers[i].states = a_states;
a_states += layers[i].n_states;
}
// Update maximal number of states
max_states = max_s;
}
// Schedule if subsumption is needed
if (c.empty())
View::schedule(home,*this,ME_INT_VAL);
audit();
return ES_OK;
}
template<class View, class Val, class Degree, class StateIdx>
ExecStatus
LayeredGraph<View,Val,Degree,StateIdx>::advise(Space& home,
Advisor& _a, const Delta& d) {
// Check whether state information has already been created
if (layers[0].states == NULL) {
State* states = home.alloc<State>(n_states);
for (unsigned int i=0; i<n_states; i++)
states[i].init();
layers[n].states = states;
states += layers[n].n_states;
for (int i=n; i--; ) {
layers[i].states = states;
states += layers[i].n_states;
for (ValSize j=layers[i].size; j--; ) {
Support& s = layers[i].support[j];
for (Degree deg=s.n_edges; deg--; ) {
i_state(i,s.edges[deg]).o_deg++;
o_state(i,s.edges[deg]).i_deg++;
}
}
}
}
Index& a = static_cast<Index&>(_a);
const int i = a.i;
if (layers[i].size <= layers[i].x.size()) {
// Propagator has already done everything
if (View::modevent(d) == ME_INT_VAL) {
a.dispose(home,c);
return c.empty() ? ES_NOFIX : ES_FIX;
} else {
return ES_FIX;
}
}
bool i_mod = false;
bool o_mod = false;
if (View::modevent(d) == ME_INT_VAL) {
Val n = static_cast<Val>(layers[i].x.val());
ValSize j=0;
for (; layers[i].support[j].val < n; j++) {
Support& s = layers[i].support[j];
n_edges -= s.n_edges;
// Supported value not any longer in view
for (Degree deg=s.n_edges; deg--; ) {
// Adapt states
o_mod |= i_dec(i,s.edges[deg]);
i_mod |= o_dec(i,s.edges[deg]);
}
}
assert(layers[i].support[j].val == n);
layers[i].support[0] = layers[i].support[j++];
ValSize s=layers[i].size;
layers[i].size = 1;
for (; j<s; j++) {
Support& ls = layers[i].support[j];
n_edges -= ls.n_edges;
for (Degree deg=ls.n_edges; deg--; ) {
// Adapt states
o_mod |= i_dec(i,ls.edges[deg]);
i_mod |= o_dec(i,ls.edges[deg]);
}
}
} else if (layers[i].x.any(d)) {
ValSize j=0;
ValSize k=0;
ValSize s=layers[i].size;
for (ViewRanges<View> rx(layers[i].x); rx() && (j<s);) {
Support& ls = layers[i].support[j];
if (ls.val < static_cast<Val>(rx.min())) {
// Supported value not any longer in view
n_edges -= ls.n_edges;
for (Degree deg=ls.n_edges; deg--; ) {
// Adapt states
o_mod |= i_dec(i,ls.edges[deg]);
i_mod |= o_dec(i,ls.edges[deg]);
}
++j;
} else if (ls.val > static_cast<Val>(rx.max())) {
++rx;
} else {
layers[i].support[k++]=ls;
++j;
}
}
assert(k > 0);
layers[i].size = k;
// Remove remaining values
for (; j<s; j++) {
Support& ls=layers[i].support[j];
n_edges -= ls.n_edges;
for (Degree deg=ls.n_edges; deg--; ) {
// Adapt states
o_mod |= i_dec(i,ls.edges[deg]);
i_mod |= o_dec(i,ls.edges[deg]);
}
}
} else {
Val min = static_cast<Val>(layers[i].x.min(d));
ValSize j=0;
// Skip values smaller than min (to keep)
for (; layers[i].support[j].val < min; j++) {}
Val max = static_cast<Val>(layers[i].x.max(d));
ValSize k=j;
ValSize s=layers[i].size;
// Remove pruned values
for (; (j<s) && (layers[i].support[j].val <= max); j++) {
Support& ls=layers[i].support[j];
n_edges -= ls.n_edges;
for (Degree deg=ls.n_edges; deg--; ) {
// Adapt states
o_mod |= i_dec(i,ls.edges[deg]);
i_mod |= o_dec(i,ls.edges[deg]);
}
}
// Keep remaining values
while (j<s)
layers[i].support[k++]=layers[i].support[j++];
layers[i].size=k;
assert(k > 0);
}
audit();
bool fix = true;
if (o_mod && (i > 0)) {
o_ch.add(i-1); fix = false;
}
if (i_mod && (i+1 < n)) {
i_ch.add(i+1); fix = false;
}
if (fix) {
if (View::modevent(d) == ME_INT_VAL) {
a.dispose(home,c);
return c.empty() ? ES_NOFIX : ES_FIX;
}
return ES_FIX;
} else {
return (View::modevent(d) == ME_INT_VAL)
? home.ES_NOFIX_DISPOSE(c,a) : ES_NOFIX;
}
}
template<class View, class Val, class Degree, class StateIdx>
forceinline size_t
LayeredGraph<View,Val,Degree,StateIdx>::dispose(Space& home) {
c.dispose(home);
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class View, class Val, class Degree, class StateIdx>
void
LayeredGraph<View,Val,Degree,StateIdx>::reschedule(Space& home) {
View::schedule(home,*this,c.empty() ? ME_INT_VAL : ME_INT_DOM);
}
template<class View, class Val, class Degree, class StateIdx>
ExecStatus
LayeredGraph<View,Val,Degree,StateIdx>::propagate(Space& home,
const ModEventDelta&) {
// Forward pass
for (int i=i_ch.fst(); i<=i_ch.lst(); i++) {
bool i_mod = false;
bool o_mod = false;
ValSize j=0;
ValSize k=0;
ValSize ls=layers[i].size;
do {
Support& s=layers[i].support[j];
n_edges -= s.n_edges;
for (Degree d=s.n_edges; d--; )
if (i_state(i,s.edges[d]).i_deg == 0) {
// Adapt states
o_mod |= i_dec(i,s.edges[d]);
i_mod |= o_dec(i,s.edges[d]);
// Remove edge
s.edges[d] = s.edges[--s.n_edges];
}
n_edges += s.n_edges;
// Check whether value is still supported
if (s.n_edges == 0) {
layers[i].size--;
GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
} else {
layers[i].support[k++]=s;
}
} while (++j<ls);
assert(k > 0);
// Update modification information
if (o_mod && (i > 0))
o_ch.add(i-1);
if (i_mod && (i+1 < n))
i_ch.add(i+1);
}
// Backward pass
for (int i=o_ch.lst(); i>=o_ch.fst(); i--) {
bool o_mod = false;
ValSize j=0;
ValSize k=0;
ValSize ls=layers[i].size;
do {
Support& s=layers[i].support[j];
n_edges -= s.n_edges;
for (Degree d=s.n_edges; d--; )
if (o_state(i,s.edges[d]).o_deg == 0) {
// Adapt states
o_mod |= i_dec(i,s.edges[d]);
(void) o_dec(i,s.edges[d]);
// Remove edge
s.edges[d] = s.edges[--s.n_edges];
}
n_edges += s.n_edges;
// Check whether value is still supported
if (s.n_edges == 0) {
layers[i].size--;
GECODE_ME_CHECK(layers[i].x.nq(home,s.val));
} else {
layers[i].support[k++]=s;
}
} while (++j<ls);
assert(k > 0);
// Update modification information
if (o_mod && (i > 0))
o_ch.add(i-1);
}
a_ch.add(i_ch); i_ch.reset();
a_ch.add(o_ch); o_ch.reset();
audit();
// Check subsumption
if (c.empty())
return home.ES_SUBSUMED(*this);
else
return ES_FIX;
}
template<class View, class Val, class Degree, class StateIdx>
template<class Var>
ExecStatus
LayeredGraph<View,Val,Degree,StateIdx>::post(Home home,
const VarArgArray<Var>& x,
const DFA& dfa) {
if (x.size() == 0) {
// Check whether the start state 0 is also a final state
if ((dfa.final_fst() <= 0) && (dfa.final_lst() >= 0))
return ES_OK;
return ES_FAILED;
}
assert(x.size() > 0);
for (int i=0; i<x.size(); i++) {
DFA::Symbols s(dfa);
typename VarTraits<Var>::View xi(x[i]);
GECODE_ME_CHECK(xi.inter_v(home,s,false));
}
LayeredGraph<View,Val,Degree,StateIdx>* p =
new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,x,dfa);
return p->initialize(home,x,dfa);
}
template<class View, class Val, class Degree, class StateIdx>
forceinline
LayeredGraph<View,Val,Degree,StateIdx>
::LayeredGraph(Space& home, LayeredGraph<View,Val,Degree,StateIdx>& p)
: Propagator(home,p),
n(p.n), layers(home.alloc<Layer>(n+1)),
max_states(p.max_states), n_states(p.n_states), n_edges(p.n_edges) {
c.update(home,p.c);
// Do not allocate states, postpone to advise!
layers[n].n_states = p.layers[n].n_states;
layers[n].states = NULL;
// Allocate memory for edges
Edge* edges = home.alloc<Edge>(n_edges);
// Copy layers
for (int i=0; i<n; i++) {
layers[i].x.update(home,p.layers[i].x);
assert(layers[i].x.size() == p.layers[i].size);
layers[i].size = p.layers[i].size;
layers[i].support = home.alloc<Support>(layers[i].size);
for (ValSize j=0; j<layers[i].size; j++) {
layers[i].support[j].val = p.layers[i].support[j].val;
layers[i].support[j].n_edges = p.layers[i].support[j].n_edges;
assert(layers[i].support[j].n_edges > 0);
layers[i].support[j].edges =
Heap::copy(edges,p.layers[i].support[j].edges,
layers[i].support[j].n_edges);
edges += layers[i].support[j].n_edges;
}
layers[i].n_states = p.layers[i].n_states;
layers[i].states = NULL;
}
audit();
}
template<class View, class Val, class Degree, class StateIdx>
PropCost
LayeredGraph<View,Val,Degree,StateIdx>::cost(const Space&,
const ModEventDelta&) const {
return PropCost::linear(PropCost::HI,n);
}
template<class View, class Val, class Degree, class StateIdx>
Actor*
LayeredGraph<View,Val,Degree,StateIdx>::copy(Space& home) {
// Eliminate an assigned prefix
{
int k=0;
while (layers[k].size == 1) {
assert(layers[k].support[0].n_edges == 1);
n_states -= layers[k].n_states;
k++;
}
if (k > 0) {
/*
* The state information is always available: either the propagator
* has been created (hence, also the state information has been
* created), or the first variable become assigned and hence
* an advisor must have been run (which then has created the state
* information).
*/
// Eliminate assigned layers
n -= k; layers += k;
// Eliminate edges
n_edges -= static_cast<unsigned int>(k);
// Update advisor indices
for (Advisors<Index> as(c); as(); ++as)
as.advisor().i -= k;
// Update all change information
a_ch.lshift(k);
}
}
audit();
// Compress states
if (!a_ch.empty()) {
int f = a_ch.fst();
int l = a_ch.lst();
assert((f >= 0) && (l <= n));
Region r;
// State map for in-states
StateIdx* i_map = r.alloc<StateIdx>(max_states);
// State map for out-states
StateIdx* o_map = r.alloc<StateIdx>(max_states);
// Number of in-states
StateIdx i_n = 0;
n_states -= layers[l].n_states;
// Initialize map for in-states and compress
for (StateIdx j=0; j<layers[l].n_states; j++)
if ((layers[l].states[j].i_deg != 0) ||
(layers[l].states[j].o_deg != 0)) {
layers[l].states[i_n]=layers[l].states[j];
i_map[j]=i_n++;
}
layers[l].n_states = i_n;
n_states += layers[l].n_states;
assert(i_n > 0);
// Update in-states in edges for last layer, if any
if (l < n)
for (ValSize j=layers[l].size; j--; ) {
Support& s = layers[l].support[j];
for (Degree d=s.n_edges; d--; )
s.edges[d].i_state = i_map[s.edges[d].i_state];
}
// Update all changed layers
for (int i=l-1; i>=f; i--) {
// In-states become out-states
std::swap(o_map,i_map); i_n=0;
// Initialize map for in-states and compress
n_states -= layers[i].n_states;
for (StateIdx j=0; j<layers[i].n_states; j++)
if ((layers[i].states[j].o_deg != 0) ||
(layers[i].states[j].i_deg != 0)) {
layers[i].states[i_n]=layers[i].states[j];
i_map[j]=i_n++;
}
layers[i].n_states = i_n;
n_states += layers[i].n_states;
assert(i_n > 0);
// Update states in edges
for (ValSize j=layers[i].size; j--; ) {
Support& s = layers[i].support[j];
for (Degree d=s.n_edges; d--; ) {
s.edges[d].i_state = i_map[s.edges[d].i_state];
s.edges[d].o_state = o_map[s.edges[d].o_state];
}
}
}
// Update out-states in edges for previous layer, if any
if (f > 0)
for (ValSize j=layers[f-1].size; j--; ) {
Support& s = layers[f-1].support[j];
for (Degree d=s.n_edges; d--; )
s.edges[d].o_state = i_map[s.edges[d].o_state];
}
a_ch.reset();
}
audit();
return new (home) LayeredGraph<View,Val,Degree,StateIdx>(home,*this);
}
template<class Var>
forceinline ExecStatus
post_lgp(Home home, const VarArgArray<Var>& x, const DFA& dfa) {
Gecode::Support::IntType t_state_idx =
Gecode::Support::u_type(static_cast<unsigned int>(dfa.n_states()));
Gecode::Support::IntType t_degree =
Gecode::Support::u_type(dfa.max_degree());
Gecode::Support::IntType t_val =
std::max(Support::s_type(dfa.symbol_min()),
Support::s_type(dfa.symbol_max()));
switch (t_val) {
case Gecode::Support::IT_CHAR:
case Gecode::Support::IT_SHRT:
switch (t_state_idx) {
case Gecode::Support::IT_CHAR:
switch (t_degree) {
case Gecode::Support::IT_CHAR:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned char,unsigned char>
::post(home,x,dfa);
case Gecode::Support::IT_SHRT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned short int,unsigned char>
::post(home,x,dfa);
case Gecode::Support::IT_INT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned int,unsigned char>
::post(home,x,dfa);
default: GECODE_NEVER;
}
break;
case Gecode::Support::IT_SHRT:
switch (t_degree) {
case Gecode::Support::IT_CHAR:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned char,unsigned short int>
::post(home,x,dfa);
case Gecode::Support::IT_SHRT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned short int,unsigned short int>
::post(home,x,dfa);
case Gecode::Support::IT_INT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned int,unsigned short int>
::post(home,x,dfa);
default: GECODE_NEVER;
}
break;
case Gecode::Support::IT_INT:
switch (t_degree) {
case Gecode::Support::IT_CHAR:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned char,unsigned int>
::post(home,x,dfa);
case Gecode::Support::IT_SHRT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned short int,unsigned int>
::post(home,x,dfa);
case Gecode::Support::IT_INT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,short int,unsigned int,unsigned int>
::post(home,x,dfa);
default: GECODE_NEVER;
}
break;
default: GECODE_NEVER;
}
case Gecode::Support::IT_INT:
switch (t_state_idx) {
case Gecode::Support::IT_CHAR:
switch (t_degree) {
case Gecode::Support::IT_CHAR:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned char,unsigned char>
::post(home,x,dfa);
case Gecode::Support::IT_SHRT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned short int,unsigned char>
::post(home,x,dfa);
case Gecode::Support::IT_INT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned int,unsigned char>
::post(home,x,dfa);
default: GECODE_NEVER;
}
break;
case Gecode::Support::IT_SHRT:
switch (t_degree) {
case Gecode::Support::IT_CHAR:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned char,unsigned short int>
::post(home,x,dfa);
case Gecode::Support::IT_SHRT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned short int,unsigned short int>
::post(home,x,dfa);
case Gecode::Support::IT_INT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned int,unsigned short int>
::post(home,x,dfa);
default: GECODE_NEVER;
}
break;
case Gecode::Support::IT_INT:
switch (t_degree) {
case Gecode::Support::IT_CHAR:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned char,unsigned int>
::post(home,x,dfa);
case Gecode::Support::IT_SHRT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned short int,unsigned int>
::post(home,x,dfa);
case Gecode::Support::IT_INT:
return Extensional::LayeredGraph
<typename VarTraits<Var>::View,int,unsigned int,unsigned int>
::post(home,x,dfa);
default: GECODE_NEVER;
}
break;
default: GECODE_NEVER;
}
default: GECODE_NEVER;
}
return ES_OK;
}
}}}
// STATISTICS: int-prop
Gecode::ActorLink::init
void init(void)
Initialize links (self-linked).
Definition core.hpp:3154
Gecode::ActorLink::Space
friend class Space
Definition core.hpp:595
Gecode::ActorLink::Propagator
friend class Propagator
Definition core.hpp:591
Gecode::ActorLink::empty
bool empty(void) const
Test whether actor link is empty (points to itself).
Definition core.hpp:3175
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Actor::dispose
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Gecode::Advisor::Advisor
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:3831
Gecode::Advisor::Council
friend class Council
Definition core.hpp:1294
Gecode::Advisors
Class to iterate over advisors of a council.
Definition core.hpp:1266
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::BoolVar
Boolean integer variables.
Definition int.hh:512
Gecode::DFA::Symbols
Iterator for DFA symbols.
Definition int.hh:2092
Gecode::DFA::Transitions
Iterator for DFA transitions (sorted by symbols).
Definition int.hh:2069
Gecode::DFA
Deterministic finite automaton (DFA).
Definition int.hh:2049
Gecode::DFA::symbol_max
int symbol_max(void) const
Return largest symbol in DFA.
Definition dfa.hpp:182
Gecode::DFA::max_degree
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition dfa.hpp:157
Gecode::DFA::n_states
int n_states(void) const
Return the number of states.
Definition dfa.hpp:139
Gecode::DFA::symbol_min
int symbol_min(void) const
Return smallest symbol in DFA.
Definition dfa.hpp:175
Gecode::DFA::final_lst
int final_lst(void) const
Return the number of the last final state.
Definition dfa.hpp:169
Gecode::DFA::final_fst
int final_fst(void) const
Return the number of the first final state.
Definition dfa.hpp:163
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::Heap::copy
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition heap.hpp:583
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::IntVar
Integer variables.
Definition int.hh:371
Gecode::Int::BoolView
Boolean view for Boolean variables.
Definition view.hpp:1380
Gecode::Int::Extensional::LayeredGraph::Edge
Edge defined by in-state and out-state
Definition extensional.hh:78
Gecode::Int::Extensional::LayeredGraph::Edge::o_state
StateIdx o_state
Number of out-state.
Definition extensional.hh:81
Gecode::Int::Extensional::LayeredGraph::Edge::i_state
StateIdx i_state
Number of in-state.
Definition extensional.hh:80
Gecode::Int::Extensional::LayeredGraph::IndexRange
Range approximation of which positions have changed.
Definition extensional.hh:131
Gecode::Int::Extensional::LayeredGraph::IndexRange::reset
void reset(void)
Reset range to be empty.
Definition layered-graph.hpp:180
Gecode::Int::Extensional::LayeredGraph::IndexRange::add
void add(int i)
Add index i to range.
Definition layered-graph.hpp:185
Gecode::Int::Extensional::LayeredGraph::IndexRange::fst
int fst(void) const
Return first position.
Definition layered-graph.hpp:213
Gecode::Int::Extensional::LayeredGraph::IndexRange::lshift
void lshift(int n)
Shift index range by n elements to the left.
Definition layered-graph.hpp:201
Gecode::Int::Extensional::LayeredGraph::IndexRange::lst
int lst(void) const
Return last position.
Definition layered-graph.hpp:218
Gecode::Int::Extensional::LayeredGraph::IndexRange::empty
bool empty(void) const
Test whether range is empty.
Definition layered-graph.hpp:196
Gecode::Int::Extensional::LayeredGraph::IndexRange::IndexRange
IndexRange(void)
Initialize range as empty.
Definition layered-graph.hpp:176
Gecode::Int::Extensional::LayeredGraph::Index
Advisors for views (by position in array)
Definition extensional.hh:121
Gecode::Int::Extensional::LayeredGraph::Index::Index
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
Definition layered-graph.hpp:159
Gecode::Int::Extensional::LayeredGraph::Index::i
int i
The position of the view in the view array.
Definition extensional.hh:124
Gecode::Int::Extensional::LayeredGraph::LayerValues
Iterator for telling variable domains by scanning support.
Definition extensional.hh:102
Gecode::Int::Extensional::LayeredGraph::LayerValues::init
void init(const Layer &l)
Initialize for support of layer l.
Definition layered-graph.hpp:132
Gecode::Int::Extensional::LayeredGraph::LayerValues::operator++
void operator++(void)
Move to next supported value.
Definition layered-graph.hpp:143
Gecode::Int::Extensional::LayeredGraph::LayerValues::LayerValues
LayerValues(void)
Default constructor.
Definition layered-graph.hpp:124
Gecode::Int::Extensional::LayeredGraph::LayerValues::val
int val(void) const
Return supported value.
Definition layered-graph.hpp:148
Gecode::Int::Extensional::LayeredGraph::Layer
Layer for a view in the layered graph
Definition extensional.hh:93
Gecode::Int::Extensional::LayeredGraph::Layer::support
Support * support
Supported values.
Definition extensional.hh:99
Gecode::Int::Extensional::LayeredGraph::Layer::x
View x
Integer view.
Definition extensional.hh:95
Gecode::Int::Extensional::LayeredGraph::Layer::size
ValSize size
Number of supported values.
Definition extensional.hh:97
Gecode::Int::Extensional::LayeredGraph::Layer::n_states
StateIdx n_states
Number of states used by outgoing edges.
Definition extensional.hh:96
Gecode::Int::Extensional::LayeredGraph::State
States are described by number of incoming and outgoing edges.
Definition extensional.hh:70
Gecode::Int::Extensional::LayeredGraph::State::o_deg
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Definition extensional.hh:73
Gecode::Int::Extensional::LayeredGraph::State::i_deg
Degree i_deg
The in-degree (number of incoming edges).
Definition extensional.hh:72
Gecode::Int::Extensional::LayeredGraph::State::init
void init(void)
Definition layered-graph.hpp:78
Gecode::Int::Extensional::LayeredGraph::Support
Support information for a value
Definition extensional.hh:84
Gecode::Int::Extensional::LayeredGraph::Support::edges
Edge * edges
Supporting edges in layered graph.
Definition extensional.hh:88
Gecode::Int::Extensional::LayeredGraph::Support::n_edges
Degree n_edges
Number of supporting edges.
Definition extensional.hh:87
Gecode::Int::Extensional::LayeredGraph::Support::val
Val val
Supported value.
Definition extensional.hh:86
Gecode::Int::Extensional::LayeredGraph
Domain consistent layered graph (regular) propagator.
Definition extensional.hh:67
Gecode::Int::Extensional::LayeredGraph::initialize
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
Definition layered-graph.hpp:265
Gecode::Int::Extensional::LayeredGraph::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition layered-graph.hpp:437
Gecode::Int::Extensional::LayeredGraph::n_edges
unsigned int n_edges
Total number of edges.
Definition extensional.hh:164
Gecode::Int::Extensional::LayeredGraph::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition layered-graph.hpp:597
Gecode::Int::Extensional::LayeredGraph::ValSize
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
Definition extensional.hh:91
Gecode::Int::Extensional::LayeredGraph::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition layered-graph.hpp:745
Gecode::Int::Extensional::LayeredGraph::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear).
Definition layered-graph.hpp:738
Gecode::Int::Extensional::LayeredGraph::max_states
StateIdx max_states
Maximal number of states per layer.
Definition extensional.hh:160
Gecode::Int::Extensional::LayeredGraph::n_states
unsigned int n_states
Total number of states.
Definition extensional.hh:162
Gecode::Int::Extensional::LayeredGraph::i_dec
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
Definition layered-graph.hpp:97
Gecode::Int::Extensional::LayeredGraph::n
int n
Number of layers (and views).
Definition extensional.hh:156
Gecode::Int::Extensional::LayeredGraph::o_ch
IndexRange o_ch
Index range with out-degree modifications.
Definition extensional.hh:168
Gecode::Int::Extensional::LayeredGraph::a_ch
IndexRange a_ch
Index range for any change (for compression).
Definition extensional.hh:170
Gecode::Int::Extensional::LayeredGraph::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition layered-graph.hpp:583
Gecode::Int::Extensional::LayeredGraph::LayeredGraph
LayeredGraph(Space &home, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
Definition layered-graph.hpp:705
Gecode::Int::Extensional::LayeredGraph::audit
void audit(void)
Perform consistency check on data structures.
Definition layered-graph.hpp:242
Gecode::Int::Extensional::LayeredGraph::i_ch
IndexRange i_ch
Index range with in-degree modifications.
Definition extensional.hh:166
Gecode::Int::Extensional::LayeredGraph::c
Council< Index > c
The advisor council.
Definition extensional.hh:154
Gecode::Int::Extensional::LayeredGraph::post
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
Definition layered-graph.hpp:682
Gecode::Int::Extensional::LayeredGraph::o_state
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
Definition layered-graph.hpp:102
Gecode::Int::Extensional::LayeredGraph::o_dec
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
Definition layered-graph.hpp:114
Gecode::Int::Extensional::LayeredGraph::i_state
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
Definition layered-graph.hpp:85
Gecode::Int::Extensional::LayeredGraph::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition layered-graph.hpp:591
Gecode::Int::Extensional::LayeredGraph::layers
Layer * layers
The layers of the graph.
Definition extensional.hh:158
Gecode::Int::Extensional::VarTraits< BoolVar >::View
Int::BoolView View
The variable type of an IntView.
Definition layered-graph.hpp:69
Gecode::Int::Extensional::VarTraits< IntVar >::View
Int::IntView View
The variable type of an IntView.
Definition layered-graph.hpp:57
Gecode::Int::Extensional::VarTraits
Traits class for variables.
Definition layered-graph.hpp:46
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Int::ViewRanges
Range iterator for integer views.
Definition view.hpp:54
Gecode::Int::ViewValues
Value iterator for integer views.
Definition view.hpp:94
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::linear
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
Gecode::PropCost::HI
@ HI
Expensive.
Definition core.hpp:514
Gecode::Propagator::size
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1077
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Advisor
friend class Advisor
Definition core.hpp:1068
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2837
Gecode::Support::IntTypeTraits
Traits to for information about integer types.
Definition int-type.hpp:52
Gecode::Val
Gecode::VarArgArray
Argument array for variables.
Definition array.hpp:774
Gecode::VarArgArray::assigned
bool assigned(void) const
Test if all variables are assigned.
Definition array.hpp:1923
Gecode::Space::ES_NOFIX_DISPOSE
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:3887
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::Int::Extensional
Extensional propagators
Gecode::Int::Extensional::post_lgp
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
Definition layered-graph.hpp:852
Gecode::Int
Finite domain integers.
Gecode::Int::ME_INT_VAL
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable).
Definition var-type.hpp:56
Gecode::Int::ME_INT_DOM
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
Gecode::Support::u_type
IntType u_type(unsigned int n)
Return type required to represent n.
Definition int-type.hpp:147
Gecode::Support::s_type
IntType s_type(signed int n)
Return type required to represent n.
Gecode::Support::IntType
IntType
Description of integer types.
Definition int-type.hpp:39
Gecode::Support::IT_CHAR
@ IT_CHAR
char integer type
Definition int-type.hpp:40
Gecode::Support::IT_INT
@ IT_INT
integer type
Definition int-type.hpp:42
Gecode::Support::IT_SHRT
@ IT_SHRT
short integer type
Definition int-type.hpp:41
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::post
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition filter.cpp:138
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56