Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
post.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2002
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <algorithm>
35 #include <climits>
36 
37 namespace Gecode { namespace Int { namespace Linear {
38 
39  template<class View>
40  inline void
41  estimate(Term<View>* t, int n, int c, int& l, int &u) {
42  long long int min = c;
43  long long int max = c;
44  for (int i=n; i--; ) {
45  long long int a = t[i].a;
46  if (a > 0) {
47  min += a*t[i].x.min();
48  max += a*t[i].x.max();
49  } else {
50  max += a*t[i].x.min();
51  min += a*t[i].x.max();
52  }
53  }
54  if (min < Limits::min)
55  min = Limits::min;
56  if (min > Limits::max)
57  min = Limits::max;
58  l = static_cast<int>(min);
59  if (max < Limits::min)
60  max = Limits::min;
61  if (max > Limits::max)
62  max = Limits::max;
63  u = static_cast<int>(max);
64  }
65 
67  template<class View>
68  class TermLess {
69  public:
70  forceinline bool
71  operator ()(const Term<View>& a, const Term<View>& b) {
72  return before(a.x,b.x);
73  }
74  };
75 
77  inline int
78  gcd(int a, int b) {
79  if (b > a)
80  std::swap(a,b);
81  while (b > 0) {
82  int t = b; b = a % b; a = t;
83  }
84  return a;
85  }
86 
87 
88 
113  template<class View>
114  inline bool
116  Term<View>* &t_p, int &n_p,
117  Term<View>* &t_n, int &n_n,
118  int& g) {
119  /*
120  * Join coefficients for aliased variables:
121  *
122  */
123  {
124  // Group same variables
125  TermLess<View> tl;
126  Support::quicksort<Term<View>,TermLess<View> >(t,n,tl);
127 
128  // Join adjacent variables
129  int i = 0;
130  int j = 0;
131  while (i < n) {
132  Limits::check(t[i].a,"Int::linear");
133  long long int a = t[i].a;
134  View x = t[i].x;
135  while ((++i < n) && same(t[i].x,x)) {
136  a += t[i].a;
137  Limits::check(a,"Int::linear");
138  }
139  if (a != 0) {
140  t[j].a = static_cast<int>(a); t[j].x = x; j++;
141  }
142  }
143  n = j;
144  }
145 
146  /*
147  * Partition into positive/negative coefficents
148  *
149  */
150  if (n > 0) {
151  int i = 0;
152  int j = n-1;
153  while (true) {
154  while ((t[j].a < 0) && (--j >= 0)) ;
155  while ((t[i].a > 0) && (++i < n)) ;
156  if (j <= i) break;
157  std::swap(t[i],t[j]);
158  }
159  t_p = t; n_p = i;
160  t_n = t+n_p; n_n = n-n_p;
161  } else {
162  t_p = t; n_p = 0;
163  t_n = t; n_n = 0;
164  }
165 
166  /*
167  * Make all coefficients positive
168  *
169  */
170  for (int i=n_n; i--; )
171  t_n[i].a = -t_n[i].a;
172 
173  /*
174  * Compute greatest common divisor
175  *
176  */
177  if ((n > 0) && (g > 0)) {
178  g = t[0].a;
179  for (int i=1; (g > 1) && (i < n); i++)
180  g = gcd(t[i].a,g);
181  if (g > 1)
182  for (int i=n; i--; )
183  t[i].a /= g;
184  } else {
185  g = 1;
186  }
187 
188  /*
189  * Test for unit coefficients only
190  *
191  */
192  for (int i=n; i--; )
193  if (t[i].a != 1)
194  return false;
195  return true;
196  }
197 
198 }}}
199 
200 // STATISTICS: int-post
201 
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Sort linear terms by view.
Definition: post.hpp:68
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int a
Coefficient.
Definition: linear.hh:1339
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
bool before(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:406
bool normalize(Term< View > *t, int &n, Term< View > *&t_p, int &n_p, Term< View > *&t_n, int &n_n, int &g)
Normalize linear integer constraints.
Definition: post.hpp:115
#define forceinline
Definition: config.hpp:185
const int max
Largest allowed integer value.
Definition: int.hh:112
const int min
Smallest allowed integer value.
Definition: int.hh:114
bool same(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:401
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int gcd(int a, int b)
Compute the greatest common divisor of a and b.
Definition: post.hpp:78
VarImp * x
Pointer to variable implementation.
Definition: var.hpp:50
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
void estimate(Term< View > *t, int n, int c, int &l, int &u)
Estimate lower and upper bounds.
Definition: post.hpp:41
Post propagator for SetVar x
Definition: set.hh:765
Class for describing linear term .
Definition: linear.hh:1336
Gecode toplevel namespace
bool operator()(const Term< View > &a, const Term< View > &b)
Definition: post.hpp:71
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:46
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37