41 namespace Gecode {
namespace Int {
namespace Extensional {
80 template<
class View,
class Val,
class Degree,
class StateIdx>
87 template<
class View,
class Val,
class Degree,
class StateIdx>
92 template<
class View,
class Val,
class Degree,
class StateIdx>
98 template<
class View,
class Val,
class Degree,
class StateIdx>
104 template<
class View,
class Val,
class Degree,
class StateIdx>
109 template<
class View,
class Val,
class Degree,
class StateIdx>
115 template<
class View,
class Val,
class Degree,
class StateIdx>
126 template<
class View,
class Val,
class Degree,
class StateIdx>
129 template<
class View,
class Val,
class Degree,
class StateIdx>
133 : s1(l.support), s2(l.support+l.
size) {}
134 template<
class View,
class Val,
class Degree,
class StateIdx>
139 template<
class View,
class Val,
class Degree,
class StateIdx>
145 template<
class View,
class Val,
class Degree,
class StateIdx>
150 template<
class View,
class Val,
class Degree,
class StateIdx>
161 template<
class View,
class Val,
class Degree,
class StateIdx>
168 template<
class View,
class Val,
class Degree,
class StateIdx>
172 :
Advisor(home,share,a), i(a.i) {}
179 template<
class View,
class Val,
class Degree,
class StateIdx>
182 : _fst(INT_MAX), _lst(INT_MIN) {}
183 template<
class View,
class Val,
class Degree,
class StateIdx>
186 _fst=INT_MAX; _lst=INT_MIN;
188 template<
class View,
class Val,
class Degree,
class StateIdx>
193 template<
class View,
class Val,
class Degree,
class StateIdx>
199 template<
class View,
class Val,
class Degree,
class StateIdx>
204 template<
class View,
class Val,
class Degree,
class StateIdx>
216 template<
class View,
class Val,
class Degree,
class StateIdx>
221 template<
class View,
class Val,
class Degree,
class StateIdx>
234 template<
class View,
class Val,
class Degree,
class StateIdx>
245 template<
class View,
class Val,
class Degree,
class StateIdx>
250 unsigned int n_e = 0;
251 unsigned int n_s = 0;
253 for (
int i=
n; i--; ) {
254 n_s += layers[
i].n_states;
255 m_s =
std::max(m_s,layers[i].n_states);
257 n_e += layers[i].support[j].n_edges;
259 n_s += layers[
n].n_states;
261 assert(n_e == n_edges);
262 assert(n_s <= n_states);
263 assert(m_s <= max_states);
267 template<
class View,
class Val,
class Degree,
class StateIdx>
281 for (
int i=static_cast<int>(max_states)*(
n+1); i--; )
283 for (
int i=
n+1; i--; )
284 layers[i].states = states + i*max_states;
290 i_state(0,0).i_deg = 1;
293 for (
int i=0; i<
n; i++) {
301 if (i_state(i,static_cast<StateIdx>(
t.i_state())).i_deg != 0) {
302 i_state(i,static_cast<StateIdx>(
t.i_state())).o_deg++;
303 o_state(i,static_cast<StateIdx>(
t.o_state())).i_deg++;
304 edges[n_edges].
i_state =
static_cast<StateIdx
>(
t.i_state());
305 edges[n_edges].
o_state =
static_cast<StateIdx
>(
t.o_state());
312 s.
val =
static_cast<Val
>(nx.val());
318 if ((layers[i].
size = j) == 0)
324 if (o_state(n-1,static_cast<StateIdx>(s)).i_deg != 0)
325 o_state(n-1,static_cast<StateIdx>(s)).o_deg = 1;
328 for (
int i=n; i--; ) {
330 for (
ValSize j=0; j<layers[
i].size; j++) {
333 if (o_state(i,s.
edges[
d]).o_deg == 0) {
341 layers[
i].support[k++]=s;
343 if ((layers[i].
size = k) == 0)
348 layers[i].x.subscribe(home, *new (home)
Index(home,*
this,
c,i));
354 StateIdx* i_map = r.
alloc<StateIdx>(max_states);
356 StateIdx* o_map = r.
alloc<StateIdx>(max_states);
363 for (StateIdx j=max_states; j--; )
364 d += static_cast<unsigned int>(layers[n].states[j].i_deg);
367 static_cast<unsigned int>
370 for (StateIdx j=max_states; j--; )
371 if ((layers[n].states[j].o_deg != 0) ||
372 (layers[
n].states[j].i_deg != 0))
376 for (StateIdx j=max_states; j--; ) {
377 layers[
n].states[j].init();
380 layers[
n].states[0].i_deg =
static_cast<Degree
>(
d);
381 layers[
n].states[0].o_deg = 1;
383 layers[
n].n_states = i_n;
390 StateIdx max_s = i_n;
392 for (
int i=n; i--; ) {
394 std::swap(o_map,i_map); i_n=0;
396 for (StateIdx j=max_states; j--; )
397 if ((layers[i].states[j].o_deg != 0) ||
398 (layers[i].states[j].i_deg != 0))
400 layers[
i].n_states = i_n;
408 for (Degree d=s.
n_edges; d--; ) {
417 for (
int i=n+1; i--; ) {
419 for (StateIdx j=max_states; j--; )
420 if ((layers[i].states[j].o_deg != 0) ||
421 (layers[
i].states[j].i_deg != 0))
422 a_states[k++] = layers[
i].states[j];
423 assert(k == layers[i].n_states);
424 layers[
i].states = a_states;
425 a_states += layers[
i].n_states;
440 template<
class View,
class Val,
class Degree,
class StateIdx>
445 if (layers[0].states == NULL) {
447 for (
unsigned int i=n_states; i--; )
449 layers[
n].states = states;
450 states += layers[
n].n_states;
451 for (
int i=
n; i--; ) {
452 layers[
i].states = states;
453 states += layers[
i].n_states;
456 for (Degree d=s.
n_edges; d--; ) {
457 i_state(i,s.
edges[d]).o_deg++;
458 o_state(i,s.
edges[d]).i_deg++;
467 if (layers[i].
size <= layers[i].
x.size()) {
481 Val
n =
static_cast<Val
>(layers[
i].x.val());
483 for (; layers[
i].support[j].val <
n; j++) {
487 for (Degree d=s.
n_edges; d--; ) {
489 o_mod |= i_dec(i,s.
edges[d]);
490 i_mod |= o_dec(i,s.
edges[d]);
493 assert(layers[i].support[j].val == n);
494 layers[
i].support[0] = layers[
i].support[j++];
500 for (Degree d=s.
n_edges; d--; ) {
502 o_mod |= i_dec(i,s.
edges[d]);
503 i_mod |= o_dec(i,s.
edges[d]);
506 }
else if (layers[i].
x.any(d)) {
512 if (s.
val < static_cast<Val>(rx.min())) {
515 for (Degree d=s.
n_edges; d--; ) {
517 o_mod |= i_dec(i,s.
edges[d]);
518 i_mod |= o_dec(i,s.
edges[d]);
521 }
else if (s.
val > static_cast<Val>(rx.max())) {
524 layers[
i].support[k++]=s;
534 for (Degree d=s.
n_edges; d--; ) {
536 o_mod |= i_dec(i,s.
edges[d]);
537 i_mod |= o_dec(i,s.
edges[d]);
541 Val
min =
static_cast<Val
>(layers[
i].x.min(d));
544 for (; layers[
i].support[j].val <
min; j++) {}
545 Val
max =
static_cast<Val
>(layers[
i].x.max(d));
549 for (; (j<s) && (layers[i].support[j].val <= max); j++) {
552 for (Degree d=s.
n_edges; d--; ) {
554 o_mod |= i_dec(i,s.
edges[d]);
555 i_mod |= o_dec(i,s.
edges[d]);
560 layers[
i].support[k++]=layers[
i].support[j++];
568 if (o_mod && (i > 0)) {
569 o_ch.add(i-1); fix =
false;
571 if (i_mod && (i+1 <
n)) {
572 i_ch.add(i+1); fix =
false;
586 template<
class View,
class Val,
class Degree,
class StateIdx>
591 return sizeof(*this);
594 template<
class View,
class Val,
class Degree,
class StateIdx>
599 for (
int i=i_ch.fst(); i<=i_ch.lst(); i++) {
609 if (i_state(i,s.
edges[
d]).i_deg == 0) {
611 o_mod |= i_dec(i,s.
edges[
d]);
612 i_mod |= o_dec(i,s.
edges[
d]);
622 layers[
i].support[k++]=s;
627 if (o_mod && (i > 0))
629 if (i_mod && (i+1 <
n))
634 for (
int i=o_ch.lst(); i>=o_ch.fst(); i--) {
643 if (o_state(i,s.
edges[
d]).o_deg == 0) {
645 o_mod |= i_dec(i,s.
edges[
d]);
646 (void) o_dec(i,s.
edges[
d]);
656 layers[
i].support[k++]=s;
661 if (o_mod && (i > 0))
665 a_ch.add(i_ch); i_ch.reset();
666 a_ch.add(o_ch); o_ch.reset();
678 template<
class View,
class Val,
class Degree,
class StateIdx>
690 assert(x.
size() > 0);
691 for (
int i=x.
size(); i--; ) {
701 template<
class View,
class Val,
class Degree,
class StateIdx>
707 n(p.
n), layers(home.alloc<
Layer>(
n+1)),
708 max_states(p.max_states), n_states(p.n_states), n_edges(p.n_edges) {
709 c.update(home,share,p.
c);
711 layers[
n].n_states = p.
layers[
n].n_states;
712 layers[
n].states = NULL;
716 for (
int i=
n; i--; ) {
717 layers[
i].x.update(home,share,p.
layers[i].x);
718 assert(layers[i].
x.size() == p.
layers[
i].size);
722 layers[
i].support[j].
val = p.
layers[
i].support[j].val;
723 layers[
i].support[j].n_edges = p.
layers[
i].support[j].n_edges;
724 assert(layers[i].support[j].n_edges > 0);
725 layers[
i].support[j].edges =
727 layers[i].support[j].n_edges);
728 edges += layers[
i].support[j].n_edges;
730 layers[
i].n_states = p.
layers[
i].n_states;
731 layers[
i].states = NULL;
736 template<
class View,
class Val,
class Degree,
class StateIdx>
743 template<
class View,
class Val,
class Degree,
class StateIdx>
749 while (layers[k].
size == 1) {
750 assert(layers[k].support[0].n_edges == 1);
751 n_states -= layers[k].n_states;
765 n_edges -=
static_cast<unsigned int>(k);
779 assert((f >= 0) && (l <=
n));
782 StateIdx* i_map = r.
alloc<StateIdx>(max_states);
784 StateIdx* o_map = r.
alloc<StateIdx>(max_states);
788 n_states -= layers[
l].n_states;
790 for (StateIdx j=0; j<layers[
l].n_states; j++)
791 if ((layers[l].states[j].i_deg != 0) ||
792 (layers[
l].states[j].o_deg != 0)) {
793 layers[
l].states[i_n]=layers[
l].states[j];
796 layers[
l].n_states = i_n;
797 n_states += layers[
l].n_states;
809 for (
int i=l-1; i>=f; i--) {
811 std::swap(o_map,i_map); i_n=0;
813 n_states -= layers[
i].n_states;
814 for (StateIdx j=0; j<layers[
i].n_states; j++)
815 if ((layers[i].states[j].o_deg != 0) ||
816 (layers[i].states[j].i_deg != 0)) {
817 layers[
i].states[i_n]=layers[
i].states[j];
820 layers[
i].n_states = i_n;
821 n_states += layers[
i].n_states;
837 Support& s = layers[f-1].support[j];
863 switch (t_state_idx) {
872 <
typename VarTraits<Var>::View,
short int,
unsigned short int,
unsigned char>
876 <
typename VarTraits<Var>::View,
short int,
unsigned int,
unsigned char>
889 <
typename VarTraits<Var>::View,
short int,
unsigned short int,
unsigned short int>
893 <
typename VarTraits<Var>::View,
short int,
unsigned int,
unsigned short int>
906 <
typename VarTraits<Var>::View,
short int,
unsigned short int,
unsigned int>
910 <
typename VarTraits<Var>::View,
short int,
unsigned int,
unsigned int>
919 switch (t_state_idx) {
928 <
typename VarTraits<Var>::View,int,
unsigned short int,
unsigned char>
932 <
typename VarTraits<Var>::View,int,
unsigned int,
unsigned char>
945 <
typename VarTraits<Var>::View,int,
unsigned short int,
unsigned short int>
949 <
typename VarTraits<Var>::View,int,
unsigned int,
unsigned short int>
962 <
typename VarTraits<Var>::View,int,
unsigned short int,
unsigned int>
966 <
typename VarTraits<Var>::View,int,
unsigned int,
unsigned int>
int lst(void) const
Return last position.
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
void audit(void)
Perform consistency check on data structures.
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Edge defined by in-state and out-state
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Council< Index > c
The advisor council.
Iterator for DFA symbols.
int final_fst(void) const
Return the number of the first final state.
ExecStatus ES_SUBSUMED(Propagator &p)
const FloatNum max
Largest allowed float value.
int val(void) const
Return supported value.
int n
Number of layers (and views)
Iterator for telling variable domains by scanning support.
int final_lst(void) const
Return the number of the last final state.
int size(void) const
Return size of array (number of elements)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Traits class for variables.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
unsigned int n_states
Total number of states.
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
IntType u_type(unsigned int n)
Return type required to represent n.
void init(const Layer &l)
Initialize for support of layer l.
StateIdx i_state
Number of in-state.
Base-class for propagators.
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
Class to iterate over advisors of a council.
Value iterator for integer views.
void lshift(int n)
Shift index range by n elements to the left.
Propagation has computed fixpoint.
Int::IntView View
The variable type of an IntView.
Support information for a value
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
Base-class for both propagators and branchers.
Range iterator for integer views.
IntType s_type(signed int n)
Return type required to represent n.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
ValSize size
Number of supported values.
Gecode::FloatVal c(-8, 8)
StateIdx o_state
Number of out-state.
Deterministic finite automaton (DFA)
int p
Number of positive literals for node type.
const FloatNum min
Smallest allowed float value.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
void operator++(void)
Move to next supported value.
Support * support
Supported values.
Execution has resulted in failure.
Range approximation of which positions have changed.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Layer for a view in the layered graph
Degree n_edges
Number of supporting edges.
unsigned int size(I &i)
Size of all ranges of range iterator i.
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
LayeredGraph(Space &home, bool share, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
size_t size
The size of the propagator (used during subsumption)
bool operator()(void) const
Test whether more values supported.
Layer * layers
The layers of the graph.
int fst(void) const
Return first position.
StateIdx max_states
Maximal number of states per layer.
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
void reset(void)
Reset range to be empty.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Traits to for information about integer types.
bool empty(void) const
Test whether actor link is empty (points to itself)
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
State * states
States used by outgoing edges.
Boolean integer variables.
Domain consistent layered graph (regular) propagator.
LayerValues(void)
Default constructor.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Integer view for integer variables.
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
Node * x
Pointer to corresponding Boolean expression node.
Generic domain change information to be supplied to advisors.
Advisors for views (by position in array)
virtual size_t dispose(Space &home)
Delete actor and return its size.
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
IndexRange(void)
Initialize range as empty.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Iterator for DFA transitions (sorted by symbols)
int n_states(void) const
Return the number of states.
Propagation has not computed fixpoint.
void add(int i)
Add index i to range.
Edge * edges
Supporting edges in layered graph.
Int::BoolView View
The variable type of an IntView.
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
Gecode toplevel namespace
Argument array for variables.
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
States are described by number of incoming and outgoing edges.
Degree i_deg
The in-degree (number of incoming edges)
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
IntType
Description of integer types.
int symbol_min(void) const
Return smallest symbol in DFA.
int symbol_max(void) const
Return largest symbol in DFA.
int ModEventDelta
Modification event deltas.
Home class for posting propagators
bool empty(void) const
Test whether range is empty.
#define GECODE_NEVER
Assert that this command is never executed.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
bool assigned(void) const
Test if all variables are assigned.
int i
The position of the view in the view array.
Boolean view for Boolean variables.