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