77 template<
class View,
class Val,
class Degree,
class StateIdx>
84 template<
class View,
class Val,
class Degree,
class StateIdx>
87 return layers[i].states[is];
89 template<
class View,
class Val,
class Degree,
class StateIdx>
95 template<
class View,
class Val,
class Degree,
class StateIdx>
101 template<
class View,
class Val,
class Degree,
class StateIdx>
104 return layers[i+1].states[os];
106 template<
class View,
class Val,
class Degree,
class StateIdx>
112 template<
class View,
class Val,
class Degree,
class StateIdx>
123 template<
class View,
class Val,
class Degree,
class StateIdx>
126 template<
class View,
class Val,
class Degree,
class StateIdx>
130 : s1(l.support), s2(l.support+l.
size) {}
131 template<
class View,
class Val,
class Degree,
class StateIdx>
136 template<
class View,
class Val,
class Degree,
class StateIdx>
142 template<
class View,
class Val,
class Degree,
class StateIdx>
147 template<
class View,
class Val,
class Degree,
class StateIdx>
158 template<
class View,
class Val,
class Degree,
class StateIdx>
165 template<
class View,
class Val,
class Degree,
class StateIdx>
175 template<
class View,
class Val,
class Degree,
class StateIdx>
178 : _fst(INT_MAX), _lst(INT_MIN) {}
179 template<
class View,
class Val,
class Degree,
class StateIdx>
182 _fst=INT_MAX; _lst=INT_MIN;
184 template<
class View,
class Val,
class Degree,
class StateIdx>
187 _fst=std::min(_fst,i); _lst=std::max(_lst,i);
189 template<
class View,
class Val,
class Degree,
class StateIdx>
193 _fst=std::min(_fst,ir._fst); _lst=std::max(_lst,ir._lst);
195 template<
class View,
class Val,
class Degree,
class StateIdx>
200 template<
class View,
class Val,
class Degree,
class StateIdx>
208 _fst = std::max(0,_fst-
n);
212 template<
class View,
class Val,
class Degree,
class StateIdx>
217 template<
class View,
class Val,
class Degree,
class StateIdx>
230 template<
class View,
class Val,
class Degree,
class StateIdx>
241 template<
class View,
class Val,
class Degree,
class StateIdx>
246 unsigned int n_e = 0;
247 unsigned int n_s = 0;
249 for (
int i=
n; i--; ) {
250 n_s +=
layers[i].n_states;
263 template<
class View,
class Val,
class Degree,
class StateIdx>
273 const int n_dfa_states = dfa.
n_states();
282 unsigned char* i_reachable = r.alloc<
unsigned char>(n_dfa_states);
283 unsigned char* o_reachable = r.alloc<
unsigned char>(n_dfa_states);
284 StateIdx* i_reached = r.alloc<StateIdx>(n_dfa_states);
285 StateIdx* o_reached = r.alloc<StateIdx>(n_dfa_states);
286 for (
int i=0; i<n_dfa_states; i++)
287 i_reachable[i] = o_reachable[i] = 0;
288 unsigned int n_i_reached = 1;
289 unsigned int n_o_reached = 0;
294 for (
int i=0; i<
n; i++) {
299 for (
unsigned int k=0; k<n_o_reached; k++)
300 o_reachable[o_reached[k]] = 0;
304 unsigned int n_support_edges=0;
306 if (i_reachable[t.i_state()] != 0) {
307 edges[n_support_edges].
i_state =
308 static_cast<StateIdx
>(t.i_state());
309 edges[n_support_edges].
o_state =
310 static_cast<StateIdx
>(t.o_state());
312 if (o_reachable[t.o_state()] == 0) {
313 o_reachable[t.o_state()] = 1;
314 o_reached[n_o_reached++] =
315 static_cast<StateIdx
>(t.o_state());
320 if (n_support_edges > 0) {
322 s.
val =
static_cast<Val>(nx.val());
323 s.
n_edges =
static_cast<Degree
>(n_support_edges);
331 std::swap(i_reachable,o_reachable);
332 std::swap(i_reached,o_reached);
333 std::swap(n_i_reached,n_o_reached);
340 StateIdx* i_map = r.alloc<StateIdx>(n_dfa_states);
341 StateIdx* o_map = r.alloc<StateIdx>(n_dfa_states);
342 unsigned char* i_mapped = r.alloc<
unsigned char>(n_dfa_states);
343 unsigned char* o_mapped = r.alloc<
unsigned char>(n_dfa_states);
344 StateIdx* i_touched = r.alloc<StateIdx>(n_dfa_states);
345 StateIdx* o_touched = r.alloc<StateIdx>(n_dfa_states);
346 for (
int i=0; i<n_dfa_states; i++)
347 i_mapped[i] = o_mapped[i] = 0;
348 unsigned int n_i_mapped = 0;
349 unsigned int n_o_mapped = 0;
352 unsigned long long int final_degree = 0;
355 for (
unsigned int d=0; d<static_cast<unsigned int>(s.
n_edges); d++) {
359 if (o_mapped[os] == 0) {
361 o_map[os] =
static_cast<StateIdx
>(n_o_mapped);
362 o_touched[n_o_mapped++] =
static_cast<StateIdx
>(os);
367 if (final_degree == 0)
371 if (final_degree <=
static_cast<unsigned long long int>
374 for (
unsigned int i=0; i<n_o_mapped; i++)
375 o_map[o_touched[i]] = 0;
379 layers[
n].n_states =
static_cast<StateIdx
>(n_o_mapped);
382 unsigned long long int total_states =
layers[
n].n_states;
383 unsigned long long int total_edges = 0;
384 unsigned int max_s =
layers[
n].n_states;
387 for (
int i=
n; i--; ) {
388 for (
unsigned int j=0; j<n_i_mapped; j++)
389 i_mapped[i_touched[j]] = 0;
394 unsigned int n_support_edges=0;
395 for (
unsigned int d=0; d<static_cast<unsigned int>(s.
n_edges); d++) {
397 const int is =
static_cast<int>(e.
i_state);
398 const int os =
static_cast<int>(e.
o_state);
399 if (o_mapped[os] != 0) {
401 if (i_mapped[is] == 0) {
403 i_map[is] =
static_cast<StateIdx
>(n_i_mapped);
404 i_touched[n_i_mapped++] =
static_cast<StateIdx
>(is);
407 s.
edges[n_support_edges++] = e;
410 s.
n_edges =
static_cast<Degree
>(n_support_edges);
411 if (n_support_edges > 0) {
412 layers[i].support[n_supports++] = s;
413 total_edges += n_support_edges;
418 layers[i].n_states =
static_cast<StateIdx
>(n_i_mapped);
419 total_states += n_i_mapped;
420 max_s = std::max(max_s,n_i_mapped);
424 layers[i].x.subscribe(home, *
new (home)
Index(home,*
this,
c,i));
426 std::swap(i_map,o_map);
427 std::swap(i_mapped,o_mapped);
428 std::swap(i_touched,o_touched);
429 std::swap(n_i_mapped,n_o_mapped);
433 static_cast<unsigned long long int>
434 ((std::numeric_limits<unsigned int>::max)())) ||
436 static_cast<unsigned long long int>
437 ((std::numeric_limits<unsigned int>::max)())))
439 n_states =
static_cast<unsigned int>(total_states);
440 n_edges =
static_cast<unsigned int>(total_edges);
445 for (
unsigned int i=0; i<
n_states; i++)
447 for (
int i=
n+1; i--; ) {
448 layers[i].states = states;
449 states +=
layers[i].n_states;
453 for (
int i=0; i<
n; i++)
456 for (Degree d=s.
n_edges; d--; ) {
463 layers[0].states[0].i_deg = 1;
464 for (StateIdx i=0; i<
layers[
n].n_states; i++)
475 template<
class View,
class Val,
class Degree,
class StateIdx>
480 if (
layers[0].states ==
nullptr) {
482 for (
unsigned int i=0; i<
n_states; i++)
486 for (
int i=
n; i--; ) {
487 layers[i].states = states;
488 states +=
layers[i].n_states;
491 for (Degree deg=s.
n_edges; deg--; ) {
518 for (;
layers[i].support[j].val <
n; j++) {
522 for (Degree deg=s.
n_edges; deg--; ) {
528 assert(
layers[i].support[j].val ==
n);
535 for (Degree deg=ls.
n_edges; deg--; ) {
541 }
else if (
layers[i].x.any(d)) {
547 if (ls.
val <
static_cast<Val>(rx.min())) {
550 for (Degree deg=ls.
n_edges; deg--; ) {
556 }
else if (ls.
val >
static_cast<Val>(rx.max())) {
559 layers[i].support[k++]=ls;
569 for (Degree deg=ls.
n_edges; deg--; ) {
579 for (;
layers[i].support[j].val <
min; j++) {}
584 for (; (j<s) && (
layers[i].support[j].val <=
max); j++) {
587 for (Degree deg=ls.
n_edges; deg--; ) {
603 if (o_mod && (i > 0)) {
604 o_ch.add(i-1); fix =
false;
606 if (i_mod && (i+1 <
n)) {
607 i_ch.add(i+1); fix =
false;
621 template<
class View,
class Val,
class Degree,
class StateIdx>
626 return sizeof(*this);
629 template<
class View,
class Val,
class Degree,
class StateIdx>
635 template<
class View,
class Val,
class Degree,
class StateIdx>
640 for (
int i=
i_ch.fst(); i<=
i_ch.lst(); i++) {
649 for (Degree d=s.
n_edges; d--; )
668 if (o_mod && (i > 0))
670 if (i_mod && (i+1 <
n))
675 for (
int i=
o_ch.lst(); i>=
o_ch.fst(); i--) {
683 for (Degree d=s.
n_edges; d--; )
702 if (o_mod && (i > 0))
719 template<
class View,
class Val,
class Degree,
class StateIdx>
731 assert(x.
size() > 0);
732 for (
int i=0; i<x.
size(); i++) {
742 template<
class View,
class Val,
class Degree,
class StateIdx>
756 for (
int i=0; i<
n; i++) {
765 layers[i].support[j].edges =
767 layers[i].support[j].n_edges);
768 edges +=
layers[i].support[j].n_edges;
771 layers[i].states =
nullptr;
776 template<
class View,
class Val,
class Degree,
class StateIdx>
783 template<
class View,
class Val,
class Degree,
class StateIdx>
806 n_edges -=
static_cast<unsigned int>(k);
820 assert((f >= 0) && (l <=
n));
823 StateIdx* i_map = r.alloc<StateIdx>(
max_states);
825 StateIdx* o_map = r.alloc<StateIdx>(
max_states);
831 for (StateIdx j=0; j<
layers[l].n_states; j++)
832 if ((
layers[l].states[j].i_deg != 0) ||
833 (
layers[l].states[j].o_deg != 0)) {
845 for (Degree d=s.
n_edges; d--; )
850 for (
int i=l-1; i>=f; i--) {
852 std::swap(o_map,i_map); i_n=0;
855 for (StateIdx j=0; j<
layers[i].n_states; j++)
856 if ((
layers[i].states[j].o_deg != 0) ||
857 (
layers[i].states[j].i_deg != 0)) {
868 for (Degree d=s.
n_edges; d--; ) {
879 for (Degree d=s.
n_edges; d--; )
905 switch (t_state_idx) {
961 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.
int size(void) const
Return size of array (number of elements).
Boolean integer variables.
Iterator for DFA symbols.
Iterator for DFA transitions (sorted by symbols).
Finite automaton with deterministic construction by default.
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.
Exception: Value out of limits
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.
bool assigned(void) const
Test if all variables are 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)
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
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 .
#define GECODE_NEVER
Assert that this command is never executed.