Go to the documentation of this file.
37 namespace Gecode {
namespace Int {
namespace Extensional {
76 template<
class View,
class Val,
class Degree,
class StateIdx>
83 template<
class View,
class Val,
class Degree,
class StateIdx>
88 template<
class View,
class Val,
class Degree,
class StateIdx>
94 template<
class View,
class Val,
class Degree,
class StateIdx>
100 template<
class View,
class Val,
class Degree,
class StateIdx>
105 template<
class View,
class Val,
class Degree,
class StateIdx>
111 template<
class View,
class Val,
class Degree,
class StateIdx>
122 template<
class View,
class Val,
class Degree,
class StateIdx>
125 template<
class View,
class Val,
class Degree,
class StateIdx>
129 : s1(
l.support), s2(
l.support+
l.
size) {}
130 template<
class View,
class Val,
class Degree,
class StateIdx>
133 s1=
l.support; s2=
l.support+
l.size;
135 template<
class View,
class Val,
class Degree,
class StateIdx>
141 template<
class View,
class Val,
class Degree,
class StateIdx>
146 template<
class View,
class Val,
class Degree,
class StateIdx>
157 template<
class View,
class Val,
class Degree,
class StateIdx>
164 template<
class View,
class Val,
class Degree,
class StateIdx>
174 template<
class View,
class Val,
class Degree,
class StateIdx>
177 : _fst(INT_MAX), _lst(INT_MIN) {}
178 template<
class View,
class Val,
class Degree,
class StateIdx>
181 _fst=INT_MAX; _lst=INT_MIN;
183 template<
class View,
class Val,
class Degree,
class StateIdx>
188 template<
class View,
class Val,
class Degree,
class StateIdx>
194 template<
class View,
class Val,
class Degree,
class StateIdx>
199 template<
class View,
class Val,
class Degree,
class StateIdx>
211 template<
class View,
class Val,
class Degree,
class StateIdx>
216 template<
class View,
class Val,
class Degree,
class StateIdx>
229 template<
class View,
class Val,
class Degree,
class StateIdx>
240 template<
class View,
class Val,
class Degree,
class StateIdx>
245 unsigned int n_e = 0;
246 unsigned int n_s = 0;
248 for (
int i=
n;
i--; ) {
249 n_s += layers[
i].n_states;
252 n_e += layers[
i].support[j].n_edges;
254 n_s += layers[
n].n_states;
256 assert(n_e == n_edges);
257 assert(n_s <= n_states);
258 assert(m_s <= max_states);
262 template<
class View,
class Val,
class Degree,
class StateIdx>
276 for (
int i=0; i<static_cast<int>(max_states)*(
n+1);
i++)
278 for (
int i=0;
i<
n+1;
i++)
279 layers[
i].states = states +
i*max_states;
285 i_state(0,0).i_deg = 1;
288 for (
int i=0;
i<
n;
i++) {
296 if (i_state(
i,static_cast<StateIdx>(
t.i_state())).i_deg != 0) {
297 i_state(
i,static_cast<StateIdx>(
t.i_state())).o_deg++;
298 o_state(
i,static_cast<StateIdx>(
t.o_state())).i_deg++;
299 edges[n_edges].
i_state = static_cast<StateIdx>(
t.i_state());
300 edges[n_edges].
o_state = static_cast<StateIdx>(
t.o_state());
307 s.
val = static_cast<Val>(nx.val());
313 if ((layers[
i].
size = j) == 0)
319 if (o_state(
n-1,static_cast<StateIdx>(s)).i_deg != 0)
320 o_state(
n-1,static_cast<StateIdx>(s)).o_deg = 1;
323 for (
int i=
n;
i--; ) {
325 for (
ValSize j=0; j<layers[
i].size; j++) {
328 if (o_state(
i,s.
edges[
d]).o_deg == 0) {
336 layers[
i].support[k++]=s;
338 if ((layers[
i].
size = k) == 0)
343 layers[
i].
x.subscribe(home, *new (home)
Index(home,*
this,
c,
i));
349 StateIdx* i_map =
r.alloc<StateIdx>(max_states);
351 StateIdx* o_map =
r.alloc<StateIdx>(max_states);
358 for (StateIdx j=0; j<max_states; j++)
359 d += static_cast<unsigned int>(layers[
n].states[j].i_deg);
362 static_cast<unsigned int>
365 for (StateIdx j=max_states; j--; )
366 if ((layers[
n].states[j].o_deg != 0) ||
367 (layers[
n].states[j].i_deg != 0))
371 for (StateIdx j=max_states; j--; ) {
372 layers[
n].states[j].init();
375 layers[
n].states[0].i_deg = static_cast<Degree>(
d);
376 layers[
n].states[0].o_deg = 1;
378 layers[
n].n_states = i_n;
385 StateIdx max_s = i_n;
387 for (
int i=
n;
i--; ) {
391 for (StateIdx j=max_states; j--; )
392 if ((layers[
i].states[j].o_deg != 0) ||
393 (layers[
i].states[j].i_deg != 0))
395 layers[
i].n_states = i_n;
403 for (Degree deg=ls.
n_edges; deg--; ) {
412 for (
int i=
n+1;
i--; ) {
414 for (StateIdx j=max_states; j--; )
415 if ((layers[
i].states[j].o_deg != 0) ||
416 (layers[
i].states[j].i_deg != 0))
417 a_states[k++] = layers[
i].states[j];
418 assert(k == layers[
i].n_states);
419 layers[
i].states = a_states;
420 a_states += layers[
i].n_states;
435 template<
class View,
class Val,
class Degree,
class StateIdx>
440 if (layers[0].states == NULL) {
442 for (
unsigned int i=0;
i<n_states;
i++)
444 layers[
n].states = states;
445 states += layers[
n].n_states;
446 for (
int i=
n;
i--; ) {
447 layers[
i].states = states;
448 states += layers[
i].n_states;
451 for (Degree deg=s.
n_edges; deg--; ) {
452 i_state(
i,s.
edges[deg]).o_deg++;
453 o_state(
i,s.
edges[deg]).i_deg++;
462 if (layers[
i].
size <= layers[
i].
x.size()) {
476 Val
n = static_cast<Val>(layers[
i].
x.val());
478 for (; layers[
i].support[j].val <
n; j++) {
482 for (Degree deg=s.
n_edges; deg--; ) {
484 o_mod |= i_dec(
i,s.
edges[deg]);
485 i_mod |= o_dec(
i,s.
edges[deg]);
488 assert(layers[
i].support[j].val ==
n);
489 layers[
i].support[0] = layers[
i].support[j++];
495 for (Degree deg=ls.
n_edges; deg--; ) {
497 o_mod |= i_dec(
i,ls.
edges[deg]);
498 i_mod |= o_dec(
i,ls.
edges[deg]);
501 }
else if (layers[
i].
x.any(
d)) {
507 if (ls.
val < static_cast<Val>(rx.min())) {
510 for (Degree deg=ls.
n_edges; deg--; ) {
512 o_mod |= i_dec(
i,ls.
edges[deg]);
513 i_mod |= o_dec(
i,ls.
edges[deg]);
516 }
else if (ls.
val > static_cast<Val>(rx.max())) {
519 layers[
i].support[k++]=ls;
529 for (Degree deg=ls.
n_edges; deg--; ) {
531 o_mod |= i_dec(
i,ls.
edges[deg]);
532 i_mod |= o_dec(
i,ls.
edges[deg]);
536 Val
min = static_cast<Val>(layers[
i].
x.min(
d));
539 for (; layers[
i].support[j].val <
min; j++) {}
540 Val
max = static_cast<Val>(layers[
i].
x.max(
d));
544 for (; (j<s) && (layers[
i].support[j].val <=
max); j++) {
547 for (Degree deg=ls.
n_edges; deg--; ) {
549 o_mod |= i_dec(
i,ls.
edges[deg]);
550 i_mod |= o_dec(
i,ls.
edges[deg]);
555 layers[
i].support[k++]=layers[
i].support[j++];
563 if (o_mod && (
i > 0)) {
564 o_ch.add(
i-1); fix =
false;
566 if (i_mod && (
i+1 <
n)) {
567 i_ch.add(
i+1); fix =
false;
581 template<
class View,
class Val,
class Degree,
class StateIdx>
586 return sizeof(*this);
589 template<
class View,
class Val,
class Degree,
class StateIdx>
595 template<
class View,
class Val,
class Degree,
class StateIdx>
600 for (
int i=i_ch.fst();
i<=i_ch.lst();
i++) {
610 if (i_state(
i,s.
edges[
d]).i_deg == 0) {
623 layers[
i].support[k++]=s;
628 if (o_mod && (
i > 0))
630 if (i_mod && (
i+1 <
n))
635 for (
int i=o_ch.lst();
i>=o_ch.fst();
i--) {
644 if (o_state(
i,s.
edges[
d]).o_deg == 0) {
657 layers[
i].support[k++]=s;
662 if (o_mod && (
i > 0))
666 a_ch.add(i_ch); i_ch.reset();
667 a_ch.add(o_ch); o_ch.reset();
679 template<
class View,
class Val,
class Degree,
class StateIdx>
691 assert(
x.size() > 0);
692 for (
int i=0;
i<
x.size();
i++) {
699 return p->initialize(home,
x,dfa);
702 template<
class View,
class Val,
class Degree,
class StateIdx>
708 max_states(
p.max_states), n_states(
p.n_states), n_edges(
p.n_edges) {
711 layers[
n].n_states =
p.layers[
n].n_states;
712 layers[
n].states = NULL;
716 for (
int i=0;
i<
n;
i++) {
717 layers[
i].x.update(home,
p.layers[
i].x);
718 assert(layers[
i].
x.size() ==
p.layers[
i].size);
719 layers[
i].size =
p.layers[
i].size;
721 for (
ValSize j=0; j<layers[
i].size; j++) {
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--) {
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) {
919 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)
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)
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.
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.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
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
LayeredGraph(Space &home, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
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)
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.
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.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
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.
Execution has resulted in failure.
Argument array for variables.
int ModEventDelta
Modification event deltas.
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.
Gecode::IntArgs i({1, 2, 3, 4})
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
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.