Frobby  0.9.0
randomDataGenerators.cpp
Go to the documentation of this file.
1 /* Frobby: Software for monomial ideal computations.
2  Copyright (C) 2007 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 "randomDataGenerators.h"
19 
20 #include "BigIdeal.h"
21 #include "Ideal.h"
22 #include "Term.h"
23 #include "error.h"
24 #include "FrobbyStringStream.h"
25 
26 #include <limits>
27 #include <ctime>
28 #include <unistd.h>
29 
30 void generateLinkedListIdeal(BigIdeal& ideal, size_t variableCount) {
31  VarNames names(variableCount);
32  ideal.clearAndSetNames(variableCount);
33  ideal.reserve(variableCount);
34  for (size_t var = 1; var < variableCount; ++var) {
35  ideal.newLastTerm();
36  ideal.getLastTermExponentRef(var) = 1;
37  ideal.getLastTermExponentRef(var - 1) = 1;
38  }
39 }
40 
42  size_t rowCount,
43  size_t columnCount,
44  int deltaRow[],
45  int deltaColumn[],
46  size_t deltaCount) {
47  if (mpz_class(rowCount) * mpz_class(columnCount) >
48  numeric_limits<size_t>::max())
49  reportError("Number of positions on requested chess board too large.");
50 
51  // Generate names
52  VarNames names;
53  for (size_t row = 0; row < rowCount; ++row) {
54  for (size_t column = 0; column < columnCount; ++column) {
55  FrobbyStringStream name;
56  name << 'r' << (row + 1) << 'c' << (column + 1);
57  names.addVar(name);
58  }
59  }
60  bigIdeal.clearAndSetNames(names);
61  Ideal ideal(bigIdeal.getVarCount());
62 
63  // Generate ideal
64  for (size_t row = 0; row < rowCount; ++row) {
65  for (size_t column = 0; column < columnCount; ++column) {
66  for (size_t delta = 0; delta < deltaCount; ++delta) {
67  // Check that the target position is within the board.
68 
69  if (deltaRow[delta] == numeric_limits<int>::min() ||
70  (deltaRow[delta] < 0 &&
71  row < (size_t)-deltaRow[delta]) ||
72  (deltaRow[delta] > 0 &&
73  rowCount - row <= (size_t)deltaRow[delta]))
74  continue;
75 
76  if (deltaColumn[delta] == numeric_limits<int>::min() ||
77  (deltaColumn[delta] < 0 &&
78  column < (size_t)-deltaColumn[delta]) ||
79  (deltaColumn[delta] > 0 &&
80  columnCount - column <= (size_t)deltaColumn[delta]))
81  continue;
82 
83  Term chessMove(ideal.getVarCount());
84  chessMove[row * columnCount + column] = 1;
85 
86  size_t targetRow = row + deltaRow[delta];
87  size_t targetColumn = column + deltaColumn[delta];
88  ASSERT(targetRow < rowCount);
89  ASSERT(targetColumn < columnCount);
90 
91  chessMove[targetRow * columnCount + targetColumn] = 1;
92  ideal.insert(chessMove);
93  }
94  }
95  }
96 
97  ideal.sortReverseLex();
98  bigIdeal.insert(ideal);
99 }
100 
101 void generateKingChessIdeal(BigIdeal& ideal, size_t rowsAndColumns) {
102  int deltaRow[] = {-1, 0, 1, 1}; // the other moves follow by symmetry
103  int deltaColumn[] = { 1, 1, 1, 0};
104  ASSERT(sizeof(deltaRow) == sizeof(deltaColumn));
105 
106  size_t deltaCount = sizeof(deltaRow) / sizeof(int);
107 
108  generateChessIdeal(ideal, rowsAndColumns, rowsAndColumns,
109  deltaRow, deltaColumn, deltaCount);
110 }
111 
112 void generateKnightChessIdeal(BigIdeal& ideal, size_t rowsAndColumns) {
113  int deltaRow[] = {-1, 1, 2, 2}; // the other moves follow by symmetry
114  int deltaColumn[] = { 2, 2, 1, -1};
115  ASSERT(sizeof(deltaRow) == sizeof(deltaColumn));
116 
117  size_t deltaCount = sizeof(deltaRow) / sizeof(int);
118 
119  generateChessIdeal(ideal, rowsAndColumns, rowsAndColumns,
120  deltaRow, deltaColumn, deltaCount);
121 }
122 
123 namespace {
127  bool nextBitPattern(vector<char>& pattern) {
128  typedef vector<char>::iterator iterator;
129  for (iterator it = pattern.begin(); it != pattern.end(); ++it) {
130  if (*it)
131  *it = 0;
132  else {
133  *it = 1;
134  ASSERT(pattern != vector<char>(pattern.size()));
135  return true;
136  }
137  }
138 
139  ASSERT(pattern == vector<char>(pattern.size()));
140  return false;
141  }
142 }
143 
144 void generateTreeIdeal(BigIdeal& ideal, size_t varCount) {
145  ideal.clearAndSetNames(VarNames(varCount));
146 
147  // Declare outside of loop to avoid repeated initialization.
148  mpz_class exponent;
149 
150  // Using vector<char> to avoid vector<bool> which has special
151  // properties. Going through all "bit" patterns by simulating adding
152  // one at each step. pattern starts at all zero, which represents
153  // the identity, so we take the next bit pattern even in the first
154  // iteration to go past that.
155  vector<char> pattern(varCount);
156  while (nextBitPattern(pattern)) {
157  size_t setSize = 0;
158  typedef vector<char>::iterator iterator;
159  for (iterator it = pattern.begin(); it != pattern.end(); ++it)
160  setSize += (size_t)*it;
161 
162  exponent = varCount - setSize + 1;
163  ideal.newLastTerm();
164  for (size_t var = 0; var < varCount; ++var)
165  if (pattern[var])
166  ideal.getLastTermExponentRef(var) = exponent;
167  }
168 }
169 
170 void generateRookChessIdeal(BigIdeal& bigIdeal, size_t n, size_t k) {
171  if (n == 0 || k == 0)
172  reportError("One side of rook ideal has zero vertices.");
173  if (n > 1000 || k > 1000)
174  reportError("Number of variables in rook ideal too large.");
175  if (n > k)
176  std::swap(n, k);
177 
178  size_t varCount = n * k;
179  Ideal ideal(varCount);
180  Term term(varCount);
181 
182  vector<char> taken(k);
183  vector<size_t> choice(n);
184  size_t level = 0;
185  while (true) {
186  if (choice[level] == k) {
187  if (level == 0)
188  break;
189  --level;
190  ASSERT(static_cast<bool>(taken[choice[level]]) == true);
191  ASSERT(term[level * k + choice[level]] == 1);
192  taken[choice[level]] = false;
193  term[level * k + choice[level]] = 0;
194  ++choice[level];
195  continue;
196  }
197  if (taken[choice[level]]) {
198  ++choice[level];
199  continue;
200  }
201  taken[choice[level]] = true;
202  ASSERT(term[level * k + choice[level]] == 0);
203  term[level * k + choice[level]] = 1;
204 
205  if (level < n - 1) {
206  ++level;
207  choice[level] = 0;
208  } else {
209  ideal.insert(term);
210  ASSERT(static_cast<bool>(taken[choice[level]]) == true);
211  ASSERT(term[level * k + choice[level]] == 1);
212  taken[choice[level]] = false;
213  term[level * k + choice[level]] = 0;
214  ++choice[level];
215  }
216  }
217 
218  VarNames names(varCount);
219  bigIdeal.clearAndSetNames(names);
220  bigIdeal.insert(ideal);
221 }
222 
223 void generateMatchingIdeal(BigIdeal& bigIdeal, size_t n) {
224  if (n == 0)
225  reportError("Too few variables in matching ideal.");
226  if (n > 1000 || n > 1000)
227  reportError("Number of variables in matching ideal too large.");
228 
229  class State {
230  public:
231  State(size_t nodeCount):
232  _notTaken(-1), _nodes(nodeCount), _isAnchor(nodeCount) {
233  std::fill(_nodes.begin(), _nodes.end(), _notTaken);
234  const size_t varCount = nodeCount * (nodeCount - 1) / 2; // n choose 2
235  _term.reset(varCount);
236  }
237 
238  void takeEdge(size_t anchor, size_t other) {
239  ASSERT(anchor < _nodes.size());
240  ASSERT(other < _nodes.size());
241  ASSERT(!isTaken(anchor));
242  ASSERT(!isTaken(other));
243  _nodes[anchor] = other;
244  _nodes[other] = anchor;
245  _isAnchor[anchor] = true;
246 
247  const size_t var = edgeToVar(anchor, other);
248  ASSERT(_term[var] == 0);
249  _term[var] = 1;
250  }
251 
252  void takeNode(size_t node) {
253  ASSERT(node < getNodeCount());
254  ASSERT(!isTaken(node));
255  ASSERT(!isAnchor(node));
256  _nodes[node] = node;
257  }
258 
259  void dropNode(size_t node) {
260  ASSERT(node < getNodeCount());
261  ASSERT(isTaken(node));
262  ASSERT(!isAnchor(node));
263  ASSERT(_nodes[node] == node);
264  _nodes[node] = _notTaken;
265  }
266 
267  void dropEdge(size_t anchor) {
268  ASSERT(anchor < _nodes.size());
269  ASSERT(isTaken(anchor));
270  ASSERT(isAnchor(anchor));
271  _isAnchor[anchor] = false;
272  const size_t other = _nodes[anchor];
273  _nodes[other] = _notTaken;
274  _nodes[anchor] = _notTaken;
275 
276  const size_t var = edgeToVar(anchor, other);
277  ASSERT(_term[var] == 1);
278  _term[var] = 0;
279  }
280 
281  size_t getNeighbor(size_t node) const {
282  ASSERT(isTaken(node));
283  return _nodes[node];
284  }
285 
286  bool isAnchor(size_t node) const {
287  ASSERT(node < _nodes.size());
288  return _isAnchor[node];
289  }
290 
291  bool isTaken(size_t node) const {
292  ASSERT(node < _nodes.size());
293  return _nodes[node] != _notTaken;
294  }
295 
296  const Term& getTerm() const {return _term;}
297  size_t getNodeCount() const {return _nodes.size();}
298 
299  // Returns static_cast<size_t>(-1) if there are no anchors to the
300  // left (negative direction).
301  size_t getAnchorLeft(size_t node) const {
302  ASSERT(node <= getNodeCount());
303  for (--node; node != static_cast<size_t>(-1); --node)
304  if (isAnchor(node))
305  break;
306  return node;
307  }
308 
309  // returns getNodeCount() if all are taken to right (positive
310  // direction).
311  size_t getNotTakenRight(size_t node) const {
312  ASSERT(node < getNodeCount());
313  for (++node; node < getNodeCount(); ++node)
314  if (!isTaken(node))
315  break;
316  return node;
317  }
318 
319  private:
320  size_t edgeToVar(size_t a, size_t b) const {
321  ASSERT(a != b);
322  ASSERT(a < _nodes.size());
323  ASSERT(b < _nodes.size());
324  if (a < b)
325  std::swap(a, b);
326  const size_t var = (a * (a - 1)) / 2 + b;
327  ASSERT(var < _term.getVarCount());
328  return var;
329  }
330 
331  const size_t _notTaken; // cannot be static when local class
332  std::vector<size_t> _nodes;
333  std::vector<size_t> _isAnchor;
334  Term _term;
335  };
336 
337  State state(n);
338  Ideal ideal(state.getTerm().getVarCount());
339  size_t node = 0;
340 
341  // one node cannot be used in maximum matching if odd number of nodes.
342  size_t notUsed = state.getNodeCount();
343  if (state.getNodeCount() % 2 == 1) {
344  notUsed = 0;
345  state.takeNode(notUsed);
346  ++node;
347  }
348  while (true) {
349  if (node == static_cast<size_t>(-1)) {
350  if (notUsed < state.getNodeCount()) {
351  state.dropNode(notUsed);
352  ++notUsed;
353  }
354  if (notUsed == state.getNodeCount())
355  break;
356  state.takeNode(notUsed);
357  node = 0; // start over with next node unused
358  }
359  ASSERT(node <= state.getNodeCount());
360  if (node == state.getNodeCount()) {
361  ideal.insert(state.getTerm());
362  node = state.getAnchorLeft(node);
363  } else if (!state.isTaken(node)) {
364  const size_t neighbor = state.getNotTakenRight(node);
365  if (neighbor == state.getNodeCount()) {
366  node = state.getAnchorLeft(node);
367  } else {
368  state.takeEdge(node, neighbor);
369  node = state.getNotTakenRight(neighbor);
370  }
371  } else {
372  ASSERT(state.isTaken(node));
373  ASSERT(state.isAnchor(node));
374  const size_t neighbor = state.getNeighbor(node);
375  const size_t nextNeighbor = state.getNotTakenRight(neighbor);
376  state.dropEdge(node);
377  if (nextNeighbor == state.getNodeCount()) {
378  node = state.getAnchorLeft(node);
379  } else {
380  state.takeEdge(node, nextNeighbor);
381  node = state.getNotTakenRight(node);
382  }
383  }
384  }
385 
386  VarNames names(state.getTerm().getVarCount());
387  bigIdeal.clearAndSetNames(names);
388  bigIdeal.insert(ideal);
389 }
390 
392 (BigIdeal& bigIdeal, size_t variableCount, size_t generatorCount) {
393  Ideal ideal(variableCount);
394  Term term(variableCount);
395 
396  size_t generatorsToGo = generatorCount;
397  size_t triesLeft = (size_t)4 * 1000 * 1000;
398  while (generatorsToGo > 0 && triesLeft > 0) {
399  --triesLeft;
400 
401  size_t a = rand() % variableCount;
402  size_t b = rand() % variableCount;
403  if (a == b)
404  continue;
405 
406  term[a] = 1;
407  term[b] = 1;
408 
409  if (ideal.isIncomparable(term)) {
410  ideal.insert(term);
411  --generatorsToGo;
412  }
413 
414  term[a] = 0;
415  term[b] = 0;
416 
417  --triesLeft;
418  }
419 
420  VarNames names(variableCount);
421  bigIdeal.clearAndSetNames(names);
422  bigIdeal.insert(ideal);
423 
424  return generatorsToGo == 0;
425 }
426 
427 
429  size_t exponentRange,
430  size_t variableCount,
431  size_t generatorCount) {
432  Ideal ideal(variableCount);
433  Term term(variableCount);
434 
435  size_t generatorsToGo = generatorCount;
436  size_t triesLeft = (size_t)4 * 1000 * 1000;
437  while (generatorsToGo > 0 && triesLeft > 0) {
438  --triesLeft;
439 
440  for (size_t var = 0; var < variableCount; ++var) {
441  term[var] = rand();
442  if (exponentRange != numeric_limits<size_t>::max())
443  term[var] %= exponentRange + 1;
444  }
445 
446  if (ideal.isIncomparable(term)) {
447  ideal.insert(term);
448  --generatorsToGo;
449  }
450  }
451 
452  VarNames names(variableCount);
453  bigIdeal.clearAndSetNames(names);
454  bigIdeal.insert(ideal);
455 
456  return generatorsToGo == 0;
457 }
458 
459 void generateRandomFrobeniusInstance(vector<mpz_class>& instance,
460  size_t entryCount,
461  const mpz_class& maxEntry) {
462  ASSERT(entryCount >= 1);
463  ASSERT(maxEntry >= 1);
464 
465  gmp_randclass random(gmp_randinit_default);
466 
468  random.seed((unsigned long)time(0) +
469 #ifdef __GNUC__ // Only GCC defines this macro.
470  (unsigned long)getpid() +
471 #endif
472  (unsigned long)clock());
473 
474  instance.resize(entryCount);
475 
476  // Populate instance with random numbers in range [1,maxEntry].
477  for (size_t i = 0; i < entryCount; ++i)
478  instance[i] = random.get_z_range(maxEntry) + 1;
479 
480  // Calculate greatest common divisor of instance.
481  mpz_class gcd = instance[0];
482  for (size_t i = 1; i < entryCount; ++i)
483  mpz_gcd(gcd.get_mpz_t(), gcd.get_mpz_t(), instance[i].get_mpz_t());
484 
485  // Ensure that instance are relatively prime.
486  instance.front() /= gcd;
487 
488  sort(instance.begin(), instance.end());
489 }
void clearAndSetNames(const VarNames &names)
Definition: BigIdeal.cpp:222
bool isIncomparable(const Exponent *term) const
Definition: Ideal.cpp:48
void insert(const Ideal &ideal)
Definition: BigIdeal.cpp:60
mpz_class & getLastTermExponentRef(size_t var)
Definition: BigIdeal.h:126
void generateKingChessIdeal(BigIdeal &ideal, size_t rowsAndColumns)
Generate an ideal where is a generator when and indicate coordinates on a square chessboard where ...
#define ASSERT(X)
Definition: stdinc.h:85
void reserve(size_t capacity)
Definition: BigIdeal.cpp:112
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
bool generateRandomEdgeIdeal(BigIdeal &bigIdeal, size_t variableCount, size_t generatorCount)
Generate a random ideal where every edge is a product of two different variables. ...
Defines the variables of a polynomial ring and facilities IO involving them.
Definition: VarNames.h:40
bool addVar(const string &name)
Adds the variable and returns true if name is not already a variable.
Definition: VarNames.cpp:44
size_t getVarCount() const
Definition: BigIdeal.h:148
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void generateTreeIdeal(BigIdeal &ideal, size_t varCount)
Generate an ideal in varCount variables with minimal generators given by i.e.
void generateRandomFrobeniusInstance(vector< mpz_class > &instance, size_t entryCount, const mpz_class &maxEntry)
Generate a random vector of numbers whose gcd is 1.
This file contains functions that generate data.
void generateRookChessIdeal(BigIdeal &bigIdeal, size_t n, size_t k)
Generate an ideal in n*k variables.
void generateLinkedListIdeal(BigIdeal &ideal, size_t variableCount)
Generate an ideal of the form , and so on.
bool generateRandomIdeal(BigIdeal &bigIdeal, size_t exponentRange, size_t variableCount, size_t generatorCount)
Generate a random ideal with exponents in the range [0, exponentRange].
void generateKnightChessIdeal(BigIdeal &ideal, size_t rowsAndColumns)
Generate an ideal where is a generator when and indicate coordinates on a square chessboard where ...
void generateChessIdeal(BigIdeal &bigIdeal, size_t rowCount, size_t columnCount, int deltaRow[], int deltaColumn[], size_t deltaCount)
void reportError(const string &errorMsg)
Definition: error.cpp:23
void insert(const Exponent *term)
Definition: Ideal.cpp:455
A replacement for stringstream.
void generateMatchingIdeal(BigIdeal &bigIdeal, size_t n)
Generate an ideal whose facets are the maximum matchings in an n-clique.
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740
void newLastTerm()
Definition: BigIdeal.cpp:104