Frobby  0.9.0
SatBinomIdeal.cpp
Go to the documentation of this file.
1 /* Frobby: Software for monomial ideal computations.
2  Copyright (C) 2009 Bjarke Hammersholt Roune (www.broune.com)
3 
4  This program is free software; you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation; either version 2 of the License, or
7  (at your option) any later version.
8 
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with this program. If not, see http://www.gnu.org/licenses/.
16 */
17 #include "stdinc.h"
18 #include "SatBinomIdeal.h"
19 
20 #include "BigIdeal.h"
21 #include "Matrix.h"
22 
23 #include <sstream>
24 #include <limits>
25 
27 }
28 
30  _names(names) {
31 }
32 
33 void SatBinomIdeal::insert(const vector<mpz_class>& binom) {
34  ASSERT(binom.size() == getVarCount());
35 
36  _gens.push_back(binom);
37 }
38 
39 const vector<mpz_class>& SatBinomIdeal::getGenerator(size_t index) const {
40  ASSERT(index < getGeneratorCount());
41 
42  return _gens[index];
43 }
44 
46  return _gens.size();
47 }
48 
49 void SatBinomIdeal::print(FILE* out) const {
50  ostringstream tmp;
51  print(tmp);
52  fputs(tmp.str().c_str(), out);
53 }
54 
55 void SatBinomIdeal::print(ostream& out) const {
56  out << "/---- SatBinomIdeal of " << _gens.size() << " generators:\n";
57  for (vector<vector<mpz_class> >::const_iterator it = _gens.begin();
58  it != _gens.end(); ++it) {
59  for (vector<mpz_class>::const_iterator entry = it->begin();
60  entry != it->end(); ++entry)
61  out << *entry << ' ';
62  out << '\n';
63  }
64  out << "----/ End of list.\n";
65 }
66 
68  _gens.clear();
69  _names = names;
70 }
71 
73  return _names.getVarCount();
74 }
75 
76 void SatBinomIdeal::renameVars(const VarNames& names) {
77  ASSERT(names.getVarCount() == getVarCount());
78 
79  _names = names;
80 }
81 
83  return _names;
84 }
85 
87  _gens.clear();
88  _names.clear();
89 }
90 
91 void SatBinomIdeal::reserve(size_t size) {
92  _gens.reserve(size);
93 }
94 
96  size_t gen = 0;
97  while (gen < getGeneratorCount()) {
98  if (getGenerator(gen)[0] == 0) {
99  _gens[gen] = _gens.back();
100  _gens.pop_back();
101  } else
102  ++gen;
103  }
104 }
105 
107  size_t gen = 0;
108  while (gen < getGeneratorCount()) {
109  if (getGenerator(gen)[0] != 0) {
110  _gens[gen] = _gens.back();
111  _gens.pop_back();
112  } else
113  ++gen;
114  }
115 }
116 
118  ideal.clearAndSetNames(getNames());
119  ideal.reserve(getGeneratorCount());
120 
121  for (size_t gen = 0; gen < getGeneratorCount(); ++gen) {
122  ideal.newLastTerm();
123  for (size_t var = 0; var < getVarCount(); ++var)
124  if (getGenerator(gen)[var] > 0)
125  ideal.getLastTermExponentRef(var) = getGenerator(gen)[var];
126  }
127 }
128 
129 vector<mpz_class>& SatBinomIdeal::getLastBinomRef() {
130  ASSERT(!_gens.empty());
131 
132  return _gens.back();
133 }
134 
136  _gens.resize(_gens.size() + 1);
137  _gens.back().resize(_names.getVarCount());
138 }
139 
141  for (size_t gen = 0; gen < getGeneratorCount(); ++gen)
142  for (size_t var = 0; var < getVarCount(); ++var)
143  if (getGenerator(gen)[var] == 0)
144  return true;
145  return false;
146 }
147 
149  vector<mpz_class> v(getVarCount());
150 
151  for (size_t gen1 = 0; gen1 < getGeneratorCount(); ++gen1) {
152  for (size_t gen2 = gen1 + 1; gen2 < getGeneratorCount(); ++gen2) {
153  const vector<mpz_class>& g1 = getGenerator(gen1);
154  const vector<mpz_class>& g2 = getGenerator(gen2);
155 
156  // Skip if g1 and g2 are different in each entry.
157  bool sharesEntry = false;
158  for (size_t var = 0; var < getVarCount(); ++var) {
159  if (g1[var] == g2[var] && g1[var] > 0) {
160  sharesEntry = true;
161  break;
162  }
163  }
164  if (!sharesEntry)
165  continue;
166 
167  if (isPointFreeBody(g1, g2))
168  return false;
169  }
170  }
171 
172  return true;
173 }
174 
175 bool SatBinomIdeal::isPointFreeBody(const vector<mpz_class>& a,
176  const vector<mpz_class>& b) const {
177  ASSERT(a.size() == getVarCount());
178  ASSERT(b.size() == getVarCount());
179 
180  vector<mpz_class> rhs(getVarCount());
181 
182  // Set rhs to max(0,g1,g2)-1.
183  for (size_t var = 0; var < getVarCount(); ++var) {
184  rhs[var] = a[var] > b[var] ? a[var] : b[var];
185  if (rhs[var] < 0)
186  rhs[var] = 0;
187  rhs[var] -= 1;
188  }
189 
190  return !isDominating(rhs);
191 }
192 
193 bool SatBinomIdeal::isPointFreeBody(const vector<mpz_class>& a,
194  const vector<mpz_class>& b,
195  const vector<mpz_class>& c) const {
196  ASSERT(a.size() == getVarCount());
197  ASSERT(b.size() == getVarCount());
198 
199  vector<mpz_class> rhs(getVarCount());
200 
201  // Set rhs to max(0,g1,g1+g2)-1.
202  for (size_t var = 0; var < getVarCount(); ++var) {
203  rhs[var] = a[var] > b[var] ? a[var] : b[var];
204  rhs[var] = rhs[var] > c[var] ? rhs[var] : c[var];
205  if (rhs[var] < 0)
206  rhs[var] = 0;
207  rhs[var] -= 1;
208  }
209 
210  return !isDominating(rhs);
211 }
212 
213 bool SatBinomIdeal::isInterior(const vector<mpz_class>& a,
214  const vector<mpz_class>& b) const {
215  ASSERT(a.size() == b.size());
216 
217  if (!isPointFreeBody(a, b))
218  return false;
219 
220  for (size_t var = 1; var < a.size(); ++var)
221  if (a[var] <= 0 && b[var] <= 0)
222  return false;
223  return true;
224 }
225 
226 namespace {
227  bool hasCycle(size_t gen, vector<char>& color, const SatBinomIdeal& ideal) {
228  // 0 = Not seen before.
229  // 1 = Exploring now.
230  // 2 = Already explored. Does not lead to cycle.
231  if (color[gen] == 1)
232  return true;
233  if (color[gen] == 2)
234  return false;
235  color[gen] = 1;
236  for (size_t g = 0; g < ideal.getGeneratorCount(); ++g)
237  if (ideal.isInteriorEdge(gen, g) &&
238  !ideal.isTerminatingEdge(gen, g) &&
239  hasCycle(g, color, ideal))
240  return true;
241  color[gen] = 2;
242  return false;
243  }
244 }
245 
247  // check the graph satisifies what we think it should.
248 
249  bool generic = !hasZeroEntry();
250  if (!generic)
251  return true;
252 
253  // termination.
254  vector<char> color(getGeneratorCount());
255  for (size_t gen = 0; gen < getGeneratorCount(); ++gen)
256  if (hasCycle(gen, color, *this))
257  return false;
258 
259  // out-degree 1 when generic
260  for (size_t from = 0; from < getGeneratorCount(); ++from) {
261  const vector<mpz_class>& fromGen = getGenerator(from);
262 
263  size_t outDegree = 0;
264  for (size_t to = 0; to < getGeneratorCount(); ++to) {
265  if (isInteriorEdge(from, to))
266  ++outDegree;
267  }
268  if (isInterior(fromGen, fromGen)) {
269  if (outDegree != 0)
270  return false;
271  } else {
272  if (outDegree != 1)
273  return false;
274  }
275  }
276 
277  return true;
278 }
279 
280 bool SatBinomIdeal::isInteriorEdge(size_t from, size_t to) const {
281  const vector<mpz_class>& fromGen = getGenerator(from);
282  const vector<mpz_class>& toGen = getGenerator(to);
283 
284  if (isInterior(fromGen, fromGen))
285  return false;
286  if (isInterior(toGen, toGen))
287  return false;
288 
289  vector<mpz_class> sum(fromGen.size());
290  for (size_t var = 0; var < fromGen.size(); ++var)
291  sum[var] = fromGen[var] + toGen[var];
292  return isInterior(toGen, sum);
293 }
294 
295 bool SatBinomIdeal::isTerminatingEdge(size_t from, size_t to) const {
296  if (!isInteriorEdge(from, to))
297  return false;
298 
299  const vector<mpz_class> fromGen = getGenerator(from);
300  const vector<mpz_class> toGen = getGenerator(to);
301 
302  vector<mpz_class> sum(fromGen.size());
303  for (size_t var = 0; var < fromGen.size(); ++var)
304  sum[var] = fromGen[var] + toGen[var];
305  return isPointFreeBody(fromGen, sum);
306 }
307 
308 void SatBinomIdeal::getDoubleTriangleCount(mpz_class& count) const {
309  vector<mpz_class> sum(getVarCount());
310 
311  count = 0;
312  for (size_t gen1 = 0; gen1 < getGeneratorCount(); ++gen1) {
313  for (size_t gen2 = gen1 + 1; gen2 < getGeneratorCount(); ++gen2) {
314  const vector<mpz_class>& g1 = getGenerator(gen1);
315  const vector<mpz_class>& g2 = getGenerator(gen2);
316 
317  // Set sum = g1 + g2.
318  for (size_t var = 0; var < getVarCount(); ++var)
319  sum[var] = g1[var] + g2[var];
320 
321  if (isPointFreeBody(g1, sum) && isPointFreeBody(g2, sum))
322  ++count;
323  }
324  }
325 }
326 
329 }
330 
332  _gens = ideal._gens;
333  _names = ideal._names;
334  return *this;
335 }
336 
337 bool SatBinomIdeal::isDominating(const vector<mpz_class>& v) const {
338  for (size_t gen = 0; gen < getGeneratorCount(); ++gen) {
339  bool dom = true;
340  for (size_t var = 0; var < getVarCount(); ++var) {
341  if (v[var] < getGenerator(gen)[var]) {
342  dom = false;
343  break;
344  }
345  }
346  if (dom)
347  return true;
348  }
349  return false;
350 }
351 
353 (const vector<mpz_class>& v) const {
354  for (size_t gen = 0; gen < getGeneratorCount(); ++gen)
355  if (getGenerator(gen) == v)
356  return true;
357  return false;
358 }
359 
360 void SatBinomIdeal::projectVar(size_t var) {
361  ASSERT(var < getVarCount());
362 
363  for (size_t gen = 0; gen < getGeneratorCount(); ++gen)
364  _gens[gen].erase(_gens[gen].begin() + var);
365  _names.projectVar(var);
366 }
367 
368 void SatBinomIdeal::getMatrix(Matrix& matrix) const {
369  matrix.resize(getGeneratorCount(), getVarCount());
370  for (size_t gen = 0; gen < getGeneratorCount(); ++gen)
371  for (size_t var = 0; var < getVarCount(); ++var)
372  matrix(gen, var) = _gens[gen][var];
373 }
void clearAndSetNames(const VarNames &names)
Definition: BigIdeal.cpp:222
vector< vector< mpz_class > > _gens
Represents a saturated binomial ideal.
Definition: SatBinomIdeal.h:28
void projectVar(size_t index)
Definition: VarNames.cpp:161
void print(FILE *file) const
const vector< mpz_class > & getGenerator(size_t index) const
size_t getVarCount() const
Returns the current number of variables.
Definition: VarNames.h:112
mpz_class & getLastTermExponentRef(size_t var)
Definition: BigIdeal.h:126
void clear()
Resets the number of variables to zero.
Definition: VarNames.cpp:106
#define ASSERT(X)
Definition: stdinc.h:85
void reserve(size_t capacity)
Definition: BigIdeal.cpp:112
bool initialIdealIsWeaklyGeneric() const
Returns true if the initial ideal is weakly generic.
void removeGeneratorsWithoutLeadingZero()
Defines the variables of a polynomial ring and facilities IO involving them.
Definition: VarNames.h:40
void projectVar(size_t var)
bool isTerminatingEdge(size_t from, size_t to) const
Returns wehther {from,to+from} is an interior edge of Top and also {to,to+from} is an edge of Top (no...
bool isInteriorEdge(size_t from, size_t to) const
Returns whether {to,to+from} is an interior edge of Top.
bool isInterior(const vector< mpz_class > &a, const vector< mpz_class > &b) const
Returns true if max(0,a,b) is strictly positive in every element.
void resize(size_t rowCount, size_t colCount)
Set the number of rows and columns.
Definition: Matrix.cpp:61
bool hasZeroEntry() const
Returns true if any generator does not involve every variable, i.e.
bool isGeneric() const
Returns true if the generating set is generic, i.e.
bool validate() const
Temporary.
VarNames _names
bool isPointFreeBody(const vector< mpz_class > &a, const vector< mpz_class > &b) const
Returns true if the smallest body containing zero, a and b has no generator in its interior...
void renameVars(const VarNames &names)
Requires that names.getVarCount() equals getVarCount().
bool isDominating(const vector< mpz_class > &v) const
Returns true if any generator, considered as an integer vector, is dominated by v.
Definition: Matrix.h:26
void reserve(size_t size)
const VarNames & getNames() const
size_t getVarCount() const
void clearAndSetNames(const VarNames &names)
void getDoubleTriangleCount(mpz_class &count) const
Returns the number of pairs of generators a and b such that {0,a,a+b} and {0,b,a+b} are both interior...
SatBinomIdeal & operator=(const SatBinomIdeal &ideal)
void getInitialIdeal(BigIdeal &ideal) const
void getMatrix(Matrix &matrix) const
void removeGeneratorsWithLeadingZero()
void insert(const vector< mpz_class > &binom)
bool isGenerator(const vector< mpz_class > &v) const
Returns true if v is a generator.
vector< mpz_class > & getLastBinomRef()
void newLastTerm()
Definition: BigIdeal.cpp:104
size_t getGeneratorCount() const