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) {
bool empty(void) const
Test whether actor link is empty (points to itself)
int fst(void) const
Return first position.
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
int final_fst(void) const
Return the number of the first final state.
void audit(void)
Perform consistency check on data structures.
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.
ExecStatus ES_SUBSUMED(Propagator &p)
const FloatNum max
Largest allowed float value.
int n
Number of layers (and views)
Iterator for telling variable domains by scanning support.
Traits class for variables.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool assigned(void) const
Test whether view is assigned.
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
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.
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
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.
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)
int lst(void) const
Return last position.
Layer for a view in the layered graph
Degree n_edges
Number of supporting edges.
int symbol_max(void) const
Return largest symbol in DFA.
unsigned int size(I &i)
Size of all ranges of range iterator i.
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)
Layer * layers
The layers of the graph.
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.
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.
Post propagator for SetVar SetOpType SetVar SetRelType r
LayerValues(void)
Default constructor.
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
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.
Generic domain change information to be supplied to advisors.
bool empty(void) const
Test whether range is empty.
Advisors for views (by position in array)
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
virtual size_t dispose(Space &home)
Delete actor and return its size.
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
IndexRange(void)
Initialize range as empty.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Iterator for DFA transitions (sorted by symbols)
Post propagator for SetVar x
Propagation has not computed fixpoint.
int n_states(void) const
Return the number of states.
bool operator()(void) const
Test whether more values supported.
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.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
Gecode toplevel namespace
Argument array for variables.
int symbol_min(void) const
Return smallest symbol in DFA.
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)
virtual void reschedule(Space &home)
Schedule function.
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 final_lst(void) const
Return the number of the last final state.
int ModEventDelta
Modification event deltas.
Home class for posting propagators
#define GECODE_NEVER
Assert that this command is never executed.
int val(void) const
Return supported value.
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.
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Boolean view for Boolean variables.