Go to the documentation of this file.
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>
137 s1=
l.support; s2=
l.support+
l.size;
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>
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;
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--; ) {
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 deg=ls.
n_edges; deg--; ) {
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 deg=s.
n_edges; deg--; ) {
457 i_state(
i,s.
edges[deg]).o_deg++;
458 o_state(
i,s.
edges[deg]).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 deg=s.
n_edges; deg--; ) {
489 o_mod |= i_dec(
i,s.
edges[deg]);
490 i_mod |= o_dec(
i,s.
edges[deg]);
493 assert(layers[
i].support[j].val ==
n);
494 layers[
i].support[0] = layers[
i].support[j++];
500 for (Degree deg=ls.
n_edges; deg--; ) {
502 o_mod |= i_dec(
i,ls.
edges[deg]);
503 i_mod |= o_dec(
i,ls.
edges[deg]);
506 }
else if (layers[
i].
x.any(
d)) {
512 if (ls.
val <
static_cast<Val
>(rx.min())) {
515 for (Degree deg=ls.
n_edges; deg--; ) {
517 o_mod |= i_dec(
i,ls.
edges[deg]);
518 i_mod |= o_dec(
i,ls.
edges[deg]);
521 }
else if (ls.
val >
static_cast<Val
>(rx.max())) {
524 layers[
i].support[k++]=ls;
534 for (Degree deg=ls.
n_edges; deg--; ) {
536 o_mod |= i_dec(
i,ls.
edges[deg]);
537 i_mod |= o_dec(
i,ls.
edges[deg]);
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 deg=ls.
n_edges; deg--; ) {
554 o_mod |= i_dec(
i,ls.
edges[deg]);
555 i_mod |= o_dec(
i,ls.
edges[deg]);
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>
600 template<
class View,
class Val,
class Degree,
class StateIdx>
605 for (
int i=i_ch.fst();
i<=i_ch.lst();
i++) {
615 if (i_state(
i,s.
edges[
d]).i_deg == 0) {
628 layers[
i].support[k++]=s;
633 if (o_mod && (
i > 0))
635 if (i_mod && (
i+1 <
n))
640 for (
int i=o_ch.lst();
i>=o_ch.fst();
i--) {
649 if (o_state(
i,s.
edges[
d]).o_deg == 0) {
662 layers[
i].support[k++]=s;
667 if (o_mod && (
i > 0))
671 a_ch.add(i_ch); i_ch.reset();
672 a_ch.add(o_ch); o_ch.reset();
684 template<
class View,
class Val,
class Degree,
class StateIdx>
696 assert(
x.size() > 0);
697 for (
int i=
x.size();
i--; ) {
704 return p->initialize(home,
x,dfa);
707 template<
class View,
class Val,
class Degree,
class StateIdx>
714 max_states(
p.max_states), n_states(
p.n_states), n_edges(
p.n_edges) {
715 c.update(home,share,
p.c);
717 layers[
n].n_states =
p.layers[
n].n_states;
718 layers[
n].states = NULL;
722 for (
int i=
n;
i--; ) {
723 layers[
i].x.update(home,share,
p.layers[
i].x);
724 assert(layers[
i].
x.size() ==
p.layers[
i].size);
725 layers[
i].size =
p.layers[
i].size;
728 layers[
i].support[j].
val =
p.layers[
i].support[j].val;
729 layers[
i].support[j].n_edges =
p.layers[
i].support[j].n_edges;
730 assert(layers[
i].support[j].n_edges > 0);
731 layers[
i].support[j].edges =
733 layers[
i].support[j].n_edges);
734 edges += layers[
i].support[j].n_edges;
736 layers[
i].n_states =
p.layers[
i].n_states;
737 layers[
i].states = NULL;
742 template<
class View,
class Val,
class Degree,
class StateIdx>
749 template<
class View,
class Val,
class Degree,
class StateIdx>
755 while (layers[k].
size == 1) {
756 assert(layers[k].support[0].n_edges == 1);
757 n_states -= layers[k].n_states;
771 n_edges -=
static_cast<unsigned int>(k);
785 assert((
f >= 0) && (
l <=
n));
788 StateIdx* i_map =
r.alloc<StateIdx>(max_states);
790 StateIdx* o_map =
r.alloc<StateIdx>(max_states);
794 n_states -= layers[
l].n_states;
796 for (StateIdx j=0; j<layers[
l].n_states; j++)
797 if ((layers[
l].states[j].i_deg != 0) ||
798 (layers[
l].states[j].o_deg != 0)) {
799 layers[
l].states[i_n]=layers[
l].states[j];
802 layers[
l].n_states = i_n;
803 n_states += layers[
l].n_states;
815 for (
int i=
l-1;
i>=
f;
i--) {
819 n_states -= layers[
i].n_states;
820 for (StateIdx j=0; j<layers[
i].n_states; j++)
821 if ((layers[
i].states[j].o_deg != 0) ||
822 (layers[
i].states[j].i_deg != 0)) {
823 layers[
i].states[i_n]=layers[
i].states[j];
826 layers[
i].n_states = i_n;
827 n_states += layers[
i].n_states;
843 Support& s = layers[
f-1].support[j];
869 switch (t_state_idx) {
925 switch (t_state_idx) {
void audit(void)
Perform consistency check on data structures.
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Post propagator for SetVar x
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
void lshift(int n)
Shift index range by n elements to the left.
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
Advisors for views (by position in array)
size_t size
The size of the propagator (used during subsumption)
@ IT_SHRT
short integer type
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
int val(void) const
Return supported value.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
ExecStatus ES_SUBSUMED(Propagator &p)
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
int fst(void) const
Return first position.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Council< Index > c
The advisor council.
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Class to iterate over advisors of a council.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Value iterator for integer views.
const FloatNum min
Smallest allowed float value.
int final_fst(void) const
Return the number of the first final state.
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Edge * edges
Supporting edges in layered graph.
Base-class for both propagators and branchers.
bool assigned(void) const
Test whether view is assigned.
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
Layer * layers
The layers of the graph.
int symbol_max(void) const
Return largest symbol in DFA.
void init(const Layer &l)
Initialize for support of layer l.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Range approximation of which positions have changed.
Boolean view for Boolean variables.
Gecode toplevel namespace
Int::IntView View
The variable type of an IntView.
Support information for a value
Base-class for propagators.
Range iterator for integer views.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
LayerValues(void)
Default constructor.
Domain consistent layered graph (regular) propagator.
int lst(void) const
Return last position.
IntType u_type(unsigned int n)
Return type required to represent n.
Generic domain change information to be supplied to advisors.
Home class for posting propagators
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Traits class for variables.
int n
Number of layers (and views)
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
Iterator for telling variable domains by scanning support.
Post propagator for SetVar SetOpType SetVar SetRelType r
Boolean integer variables.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
void operator++(void)
Move to next supported value.
void reset(void)
Reset range to be empty.
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
unsigned int n_states
Total number of states.
StateIdx o_state
Number of out-state.
Iterator for DFA transitions (sorted by symbols)
LayeredGraph(Space &home, bool share, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
Int::BoolView View
The variable type of an IntView.
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Degree i_deg
The in-degree (number of incoming edges)
#define GECODE_NEVER
Assert that this command is never executed.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
int n_states(void) const
Return the number of states.
StateIdx i_state
Number of in-state.
StateIdx max_states
Maximal number of states per layer.
bool empty(void) const
Test whether actor link is empty (points to itself)
Deterministic finite automaton (DFA)
Traits to for information about integer types.
bool empty(void) const
Test whether range is empty.
States are described by number of incoming and outgoing edges.
@ IT_CHAR
char integer type
int final_lst(void) const
Return the number of the last final state.
State * states
States used by outgoing edges.
IntType
Description of integer types.
@ ES_FIX
Propagation has computed fixpoint.
Layer for a view in the layered graph
Integer view for integer variables.
virtual void reschedule(Space &home)
Schedule function.
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
IndexRange(void)
Initialize range as empty.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
virtual size_t dispose(Space &home)
Delete actor and return its size.
Degree n_edges
Number of supporting edges.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Gecode::FloatVal c(-8, 8)
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
IntType s_type(signed int n)
Return type required to represent n.
Edge defined by in-state and out-state
int n
Number of negative literals for node type.
@ ES_FAILED
Execution has resulted in failure.
Argument array for variables.
int ModEventDelta
Modification event deltas.
@ ES_NOFIX
Propagation has not computed fixpoint.
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
@ ES_OK
Execution is okay.
int p
Number of positive literals for node type.
int symbol_min(void) const
Return smallest symbol in DFA.
bool operator()(void) const
Test whether more values supported.
const FloatNum max
Largest allowed float value.
Iterator for DFA symbols.
void add(int i)
Add index i to range.
virtual size_t dispose(Space &home)
Delete propagator and return its size.