76 template<
class View,
class Val,
class Degree,
class StateIdx>
83 template<
class View,
class Val,
class Degree,
class StateIdx>
86 return layers[i].states[is];
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>
103 return layers[i+1].states[os];
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>
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;
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++)
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++;
307 s.
val =
static_cast<Val>(nx.val());
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--; ) {
327 for (Degree d=s.
n_edges; d--; )
343 layers[i].x.subscribe(home, *
new (home)
Index(home,*
this,
c,i));
359 d +=
static_cast<unsigned int>(
layers[
n].states[j].i_deg);
362 static_cast<unsigned int>
366 if ((
layers[
n].states[j].o_deg != 0) ||
367 (
layers[
n].states[j].i_deg != 0))
375 layers[
n].states[0].i_deg =
static_cast<Degree
>(d);
385 StateIdx max_s = i_n;
387 for (
int i=
n; i--; ) {
389 std::swap(o_map,i_map); i_n=0;
392 if ((
layers[i].states[j].o_deg != 0) ||
393 (
layers[i].states[j].i_deg != 0))
397 max_s = std::max(max_s,i_n);
403 for (Degree deg=ls.
n_edges; deg--; ) {
412 for (
int i=
n+1; i--; ) {
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];
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++)
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--; ) {
478 for (;
layers[i].support[j].val <
n; j++) {
482 for (Degree deg=s.
n_edges; deg--; ) {
488 assert(
layers[i].support[j].val ==
n);
495 for (Degree deg=ls.
n_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--; ) {
516 }
else if (ls.
val >
static_cast<Val>(rx.max())) {
519 layers[i].support[k++]=ls;
529 for (Degree deg=ls.
n_edges; deg--; ) {
539 for (;
layers[i].support[j].val <
min; j++) {}
544 for (; (j<s) && (
layers[i].support[j].val <=
max); j++) {
547 for (Degree deg=ls.
n_edges; deg--; ) {
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++) {
609 for (Degree d=s.
n_edges; d--; )
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--) {
643 for (Degree d=s.
n_edges; d--; )
662 if (o_mod && (i > 0))
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>
716 for (
int i=0; i<
n; i++) {
725 layers[i].support[j].edges =
727 layers[i].support[j].n_edges);
728 edges +=
layers[i].support[j].n_edges;
736 template<
class View,
class Val,
class Degree,
class StateIdx>
743 template<
class View,
class Val,
class Degree,
class StateIdx>
765 n_edges -=
static_cast<unsigned int>(k);
779 assert((f >= 0) && (l <=
n));
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)) {
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;
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)) {
827 for (Degree d=s.
n_edges; d--; ) {
838 for (Degree d=s.
n_edges; d--; )
863 switch (t_state_idx) {
919 switch (t_state_idx) {
void init(void)
Initialize links (self-linked)
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.
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
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.
int i
The position of the view in the view array.
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.
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.
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
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)
IndexRange o_ch
Index range with out-degree modifications.
IndexRange a_ch
Index range for any change (for compression)
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.
IndexRange i_ch
Index range with in-degree modifications.
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.
size_t size
The size of the propagator (used during subsumption)
Propagator(Home home)
Constructor for posting.
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.
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)
Propagator p is subsumed
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.