-
Notifications
You must be signed in to change notification settings - Fork 10
/
game.hpp
432 lines (361 loc) · 11.6 KB
/
game.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
/*
* Copyright 2017-2018 Tom van Dijk, Johannes Kepler University Linz
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef GAME_HPP
#define GAME_HPP
#include <cassert>
#include <sstream>
#include <vector>
#include <map>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <oink/bitset.hpp>
namespace pg {
/**
* The main class holding a Parity game.
*
* Edges are stored consecutively in a single array, ending with the value -1.
* For game solving, the build_in_array method creates the reverse array.
*
* There is a special vector representation of edges to allow for "random-order" modification
* or game-building:
* - vec_init() initializes the vectors with the current edges
* - vec_add_edge, vec_remove_edge, vec_has_edge to manipulate the edges
* - vec_finish() rebuilds the array representation
*
* Usage scenario for making a game (random order):
* - initialize with constructor Game(count) or using init_game(count)
* - use vec_init
* - use init_vertex, vec_add_edge to make the game
* - use vec_finish
* - use sort, renumber, write_pgsolver, et
*
* Usage scenario for making a game (streaming):
* - initialize with some number of vertices (e.g. 1000)
* - use init_vertex to initialize the vertex
* - use e_start to start adding successors of the vertex
* - use e_add to add each successor
* - use e_finish to finish adding successors of the vertex
* - use v_sizeup (or v_resize) to increase the number of vertices if needed
* - use v_resize to set the final number of vertices
*/
class Game
{
public:
/**
* Construct a new (uninitialized) parity game.
*/
Game();
/**
* Construct a new parity game for <count> vertices.
*/
Game(int count, int ecount = -1);
/**
* Construct a deep clone of an existing parity game.
* Does not clone the vector representation.
* Does not clone the <in> array.
*/
Game(const Game& other);
/**
* Deconstructor.
*/
~Game();
/**
* Initialize the game with <count> uninitialized vertices.
* After init_game(x), the state of the object is as after constructor Game(x).
*/
void init_game(int count);
/**
* Create random game with <n> vertices.
* - maximum priority <maxP>
* - allow self-loops
* - each vertex minimum 1 random edge
* - then generate at most <maxE> more edges
*/
void init_random_game(int n, long maxP, long maxE);
inline void set_random_seed(unsigned int seed) { generator.seed(seed); }
/**
* Initialize a vertex <v> with given <priority>, <owner> and <label>.
*/
void init_vertex(int v, int priority, int owner, std::string label="");
/**
* Change the priority of a vertex.
* At the end of this method, is_ordered is updated.
*/
void set_priority(int vertex, int priority);
/**
* Change the owner of a vertex.
* (zero is owner Even; non-zero is owner Odd)
*/
void set_owner(int vertex, int owner);
/**
* Change the label of a vertex.
*/
void set_label(int vertex, std::string label);
/**
* For vector-based (random order) manipulation of edges
*/
void vec_init(void); // initialize for manipulating vertices using the vectors
void vec_finish(void); // finalize
bool vec_add_edge(int from, int to); // return true if changed
bool vec_remove_edge(int from, int to); // return true if changed
bool vec_has_edge(int from, int to); // return true if exists
/**
* Check if a certain edge exists.
*/
bool has_edge(int from, int to);
/**
* Get the index of an edge in the edge array (or -1 if not found)
* NOTE: uses the edge arrays.
*/
int find_edge(int from, int to);
/**
* Parse a pgsolver game.
* After parse_pgsolver(x), the state of the object is as after constructor Game(x).
*/
void parse_pgsolver(std::istream &in, bool removeBadLoops=true);
/**
* Parse a [full or partial] pgsolver solution.
*/
void parse_solution(std::istream &in);
/**
* Write the game in pgsolver format to the stream <out>.
*/
void write_pgsolver(std::ostream &out);
/**
* Write the game as a DOT graph to the stream <out>.
*/
void write_dot(std::ostream &out);
/**
* Write the (partial) solution in pgsolver format to the stream <out>.
*/
void write_sol(std::ostream &out);
/**
* Sort the vertices in order of priority (low to high).
* If <mapping> is given as an int array of size vertexcount(),
* then it can be used with permute to reverse the procedure.
*/
void sort(int *mapping = NULL);
/**
* Ensure that vertices are ordered by priority.
*/
inline void ensure_sorted(void) { sort(NULL); }
/**
* Apply a permutation, moving each vertex <i> to position <mapping[i]>.
* Afterwards, <is_ordered> is updated.
*/
void permute(int *mapping); // undo reindex
/**
* Reassign priorities such that every vertex has a unique priority.
* Returns number of distinct priorities.
* (Only valid if vertices are ordered.)
*/
int inflate(void);
/**
* Reassign priorities such that no priority is skipped. ("compression")
* Returns number of distinct priorities.
* (Only valid if vertices are ordered.)
*/
int compress(void);
/**
* Reassign priorities in order, but do not inflate or compress.
* Returns number of distinct priorities.
* (Only valid if vertices are ordered.)
*/
int renumber(void);
/**
* Swap players (priorities and ownership) and renumbers on the fly.
* (Only valid if vertices are ordered.)
*/
void evenodd(void);
/**
* Change a max game into a min game and vice versa. Renumbers on the fly.
* (Only valid if vertices are ordered.)
*/
void minmax(void);
/**
* (re)build the <in> array for PG solving.
*/
void build_in_array(bool rebuild=false);
/**
* Dynamic size methods.
*/
void e_sizeup(void);
void v_sizeup(void);
void v_resize(size_t newsize); // does not do cleaning up..?
/**
* Edge making helpers.
*/
void e_start(int source);
void e_add(int source, int target);
void e_finish(void);
/**
* Return the number of vertices.
*/
inline long vertexcount() const { return n_vertices; }
inline long nodecount() const { return n_vertices; }
/**
* Count and return the number of edges.
*/
inline long edgecount() const { return n_edges; }
/**
* Returns whether every vertex has dominion 0 or 1.
*/
inline bool game_solved() const { return (unsigned)vertexcount() == solved.count(); }
/**
* Count and return how many vertices have dominion -1.
*/
inline long count_unsolved() const { return vertexcount() - solved.count(); }
/**
* Create a new Game of the subgame of the vertices given in <selection>.
*/
Game *extract_subgame(std::vector<int> &selection);
Game *extract_subgame(bitset mask);
/**
* Reset <solved>, <winner> and <strategy>.
*/
void reset_solution();
/**
* Copy solution (<other> must be a subgame and have the same number of vertices)
*/
void copy_solution(Game &other);
/**
* Copy the game.
*/
Game &operator=(const Game &other);
/**
* Swap with other game.
*/
void swap(Game& other);
/**
* Get the priority of a vertex
*/
inline int priority(const int vertex) const
{
return _priority[vertex];
}
/**
* Get the owner of a vertex
*/
inline int owner(const int vertex) const
{
return _owner[vertex];
}
/**
* Get the "real" label of a vertex
*/
inline std::string* rawlabel(const int vertex) const
{
return _label[vertex];
}
/**
* Bunch of methods to *read* the ingoing/outgoing edges.
*/
inline const int* outedges() const
{
return _outedges;
}
inline const int* inedges() const
{
return _inedges;
}
inline int firstout(const int vertex) const
{
return _firstouts[vertex];
}
inline int firstin(const int vertex) const
{
return _firstins[vertex];
}
inline long outcount(const int vertex) const
{
return _outcount[vertex];
}
inline long incount(const int vertex) const
{
return _incount[vertex];
}
inline const int *outs(const int vertex) const
{
return outedges() + firstout(vertex);
}
inline const int *ins(const int vertex) const
{
return inedges() + firstin(vertex);
}
inline const std::vector<int> outvec(const int vertex) const
{
return _outvec[vertex];
}
class _label_vertex;
_label_vertex label_vertex(int v)
{
return _label_vertex(*this, v);
}
_label_vertex label(int v)
{
return _label_vertex(*this, v);
}
/**
* Game fields
*/
private:
long n_vertices; // number of vertices
long n_edges; // number of edges
int *_priority; // priority of each vertex
bitset _owner; // owner of each vertex (1 for odd, 0 for even)
std::string **_label; // (optional) vertex labels
int *_outedges; // outgoing edges as array
int *_firstouts; // first outgoing edge of each vertex
int *_outcount; // outgoing edge count of each vertex
int *_inedges; // incoming edges as array
int *_firstins; // first incoming edge of each vertex
int *_incount; // incoming edge count of each vertex
std::vector<int> *_outvec; // outgoing edges as vector
bool is_ordered; // records if the game is in-order
size_t v_allocated; // number of vertices allocated as virtual memory
size_t e_allocated; // number of edges allocated as virtual memory
size_t e_size; // number of entries used in edge array
public:
bitset solved; // set true if vertex solved
bitset winner; // for solved vertices, set 1 if won by 1, else 0
int *strategy; // strategy for winning vertices
class _label_vertex
{
protected:
_label_vertex(Game &g, int v) : g(g), v(v) { }
friend class Game;
public:
friend std::ostream& operator<<(std::ostream& out, const _label_vertex &lv) {
if (lv.v < 0 or lv.v >= lv.g.nodecount()) {
out << "<N/A>";
} else {
std::string* l = lv.g.rawlabel(lv.v);
if (l == NULL or l->empty()) out << lv.v << "/" << lv.g.priority(lv.v);
else out << *l;
}
return out;
}
protected:
Game &g;
int v;
};
private:
void unsafe_permute(int *mapping); // apply a reordering
boost::random::mt19937 generator;
inline long rng(long low, long high) { return boost::random::uniform_int_distribution<> (low, high)(generator); }
};
}
#endif