37namespace 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>
186 _fst=std::min(_fst,i); _lst=std::max(_lst,i);
188 template<
class View,
class Val,
class Degree,
class StateIdx>
192 _fst=std::min(_fst,ir._fst); _lst=std::max(_lst,ir._lst);
194 template<
class View,
class Val,
class Degree,
class StateIdx>
199 template<
class View,
class Val,
class Degree,
class StateIdx>
207 _fst = std::max(0,_fst-
n);
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;
250 m_s = std::max(m_s,layers[i].n_states);
251 for (
ValSize j=layers[i].size; j--; )
252 n_e += layers[i].support[j].n_edges;
254 n_s += layers[
n].n_states;
255 m_s = std::max(m_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++) {
290 layers[i].support = home.
alloc<
Support>(layers[i].x.size());
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());
306 Support& s = layers[i].support[j];
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++) {
326 Support& s = layers[i].support[j];
327 for (Degree d=s.
n_edges; d--; )
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--; ) {
389 std::swap(o_map,i_map); i_n=0;
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;
397 max_s = std::max(max_s,i_n);
400 for (
ValSize j=layers[i].size; j--; ) {
401 Support& ls = layers[i].support[j];
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;
449 for (
ValSize j=layers[i].size; j--; ) {
450 Support& s = layers[i].support[j];
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++) {
479 Support& s = layers[i].support[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++];
493 Support& ls = 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)) {
506 Support& ls = layers[i].support[j];
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;
527 Support& ls=layers[i].support[j];
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++) {
545 Support& ls=layers[i].support[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++) {
607 Support& s=layers[i].support[j];
609 for (Degree d=s.
n_edges; d--; )
610 if (i_state(i,s.
edges[d]).i_deg == 0) {
612 o_mod |= i_dec(i,s.
edges[d]);
613 i_mod |= o_dec(i,s.
edges[d]);
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--) {
641 Support& s=layers[i].support[j];
643 for (Degree d=s.
n_edges; d--; )
644 if (o_state(i,s.
edges[d]).o_deg == 0) {
646 o_mod |= i_dec(i,s.
edges[d]);
647 (void) o_dec(i,s.
edges[d]);
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++) {
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) {
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);
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;
802 for (
ValSize j=layers[
l].size; j--; ) {
804 for (Degree d=s.
n_edges; d--; )
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;
825 for (
ValSize j=layers[i].size; j--; ) {
826 Support& s = layers[i].support[j];
827 for (Degree d=s.
n_edges; d--; ) {
836 for (
ValSize j=layers[f-1].size; j--; ) {
837 Support& s = layers[f-1].support[j];
838 for (Degree d=s.
n_edges; d--; )
863 switch (t_state_idx) {
919 switch (t_state_idx) {
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
bool empty(void) const
Test whether actor link is empty (points to itself)
Base-class for both propagators and branchers.
virtual size_t dispose(Space &home)
Delete actor and return its size.
Class to iterate over advisors of a council.
Boolean integer variables.
Iterator for DFA symbols.
Iterator for DFA transitions (sorted by symbols)
Deterministic finite automaton (DFA)
int symbol_max(void) const
Return largest symbol in DFA.
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
int n_states(void) const
Return the number of states.
int symbol_min(void) const
Return smallest symbol in DFA.
int final_lst(void) const
Return the number of the last final state.
int final_fst(void) const
Return the number of the first final state.
Generic domain change information to be supplied to advisors.
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Home class for posting propagators
Boolean view for Boolean variables.
Edge defined by in-state and out-state
StateIdx o_state
Number of out-state.
StateIdx i_state
Number of in-state.
Range approximation of which positions have changed.
void reset(void)
Reset range to be empty.
void add(int i)
Add index i to range.
int fst(void) const
Return first position.
void lshift(int n)
Shift index range by n elements to the left.
int lst(void) const
Return last position.
bool empty(void) const
Test whether range is empty.
IndexRange(void)
Initialize range as empty.
Advisors for views (by position in array)
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
Iterator for telling variable domains by scanning support.
void init(const Layer &l)
Initialize for support of layer l.
void operator++(void)
Move to next supported value.
LayerValues(void)
Default constructor.
int val(void) const
Return supported value.
Layer for a view in the layered graph
Support * support
Supported values.
State * states
States used by outgoing edges.
ValSize size
Number of supported values.
StateIdx n_states
Number of states used by outgoing edges.
States are described by number of incoming and outgoing edges.
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
Degree i_deg
The in-degree (number of incoming edges)
Support information for a value
Edge * edges
Supporting edges in layered graph.
Degree n_edges
Number of supporting edges.
Domain consistent layered graph (regular) propagator.
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
unsigned int n_edges
Total number of edges.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
StateIdx max_states
Maximal number of states per layer.
unsigned int n_states
Total number of states.
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
int n
Number of layers (and views)
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
LayeredGraph(Space &home, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
void audit(void)
Perform consistency check on data structures.
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.
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
virtual void reschedule(Space &home)
Schedule function.
Layer * layers
The layers of the graph.
Int::BoolView View
The variable type of an IntView.
Int::IntView View
The variable type of an IntView.
Traits class for variables.
Integer view for integer variables.
Range iterator for integer views.
Value iterator for integer views.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Base-class for propagators.
size_t size
The size of the propagator (used during subsumption)
struct Gecode::Space::@61::@63 c
Data available only during copying.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Traits to for information about integer types.
Argument array for variables.
bool assigned(void) const
Test whether view is assigned.
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 ModEventDelta
Modification event deltas.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
IntType u_type(unsigned int n)
Return type required to represent n.
IntType s_type(signed int n)
Return type required to represent n.
IntType
Description of integer types.
@ IT_CHAR
char integer type
@ IT_SHRT
short integer type
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
@ ES_OK
Execution is okay.
@ ES_FIX
Propagation has computed fixpoint.
@ ES_FAILED
Execution has resulted in failure.
@ ES_NOFIX
Propagation has not computed fixpoint.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
#define GECODE_NEVER
Assert that this command is never executed.