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