1 #ifndef BLISS_PARTITION_HH
2 #define BLISS_PARTITION_HH
3
4 /*
5 Copyright (c) 2003-2015 Tommi Junttila
6 Released under the GNU Lesser General Public License version 3.
7
8 This file is part of bliss.
9
10 bliss is free software: you can redistribute it and/or modify
11 it under the terms of the GNU Lesser General Public License as published by
12 the Free Software Foundation, version 3 of the License.
13
14 bliss is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU Lesser General Public License for more details.
18
19 You should have received a copy of the GNU Lesser General Public License
20 along with bliss. If not, see <http://www.gnu.org/licenses/>.
21 */
22
23 namespace bliss_digraphs {
24 class Partition;
25 }
26
27 #include <cstdlib>
28 #include <cstdio>
29 #include <climits>
30 #include "kstack.hh"
31 #include "kqueue.hh"
32 #include "heap.hh"
33 #include "orbit.hh"
34 #include "graph.hh"
35
36
37 namespace bliss_digraphs {
38
39 /** \internal
40 * \brief A class for refinable, backtrackable ordered partitions.
41 *
42 * This is rather a data structure with some helper functions than
43 * a proper self-contained class.
44 * That is, for efficiency reasons the fields of this class are directly
45 * manipulated from bliss::AbstractGraph and its subclasses.
46 * Conversely, some methods of this class modify the fields of
47 * bliss::AbstractGraph, too.
48 */
49 class Partition
50 {
51 public:
52 /**
53 * \brief Data structure for holding information about a cell in a Partition.
54 */
55 class Cell
56 {
57 friend class Partition;
58 public:
59 unsigned int length;
60 /* Index of the first element of the cell in
61 the Partition::elements array */
62 unsigned int first;
63 unsigned int max_ival;
64 unsigned int max_ival_count;
65 private:
66 bool in_splitting_queue;
67 public:
68 bool in_neighbour_heap;
69 /* Pointer to the next cell, null if this is the last one. */
70 Cell* next;
71 Cell* prev;
72 Cell* next_nonsingleton;
73 Cell* prev_nonsingleton;
74 unsigned int split_level;
75 /** Is this a unit cell? */
is_unit() const76 bool is_unit() const {return(length == 1); }
77 /** Is this cell in splitting queue? */
is_in_splitting_queue() const78 bool is_in_splitting_queue() const {return(in_splitting_queue); }
79 };
80
81
82 private:
83
84 /** \internal
85 * Data structure for remembering information about splits in order to
86 * perform efficient backtracking over the splits.
87 */
88 class RefInfo {
89 public:
90 unsigned int split_cell_first;
91 int prev_nonsingleton_first;
92 int next_nonsingleton_first;
93 };
94 /** \internal
95 * A stack for remembering the splits, used for backtracking.
96 */
97 KStack<RefInfo> refinement_stack;
98
99 class BacktrackInfo {
100 public:
101 unsigned int refinement_stack_size;
102 unsigned int cr_backtrack_point;
103 };
104
105 /** \internal
106 * The main stack for enabling backtracking.
107 */
108 std::vector<BacktrackInfo> bt_stack;
109
110 public:
111 AbstractGraph* graph;
112
113 /* Used during equitable partition refinement */
114 KQueue<Cell*> splitting_queue;
115 void splitting_queue_add(Cell* const cell);
116 Cell* splitting_queue_pop();
117 bool splitting_queue_is_empty() const;
118 void splitting_queue_clear();
119
120
121 /** Type for backtracking points. */
122 typedef unsigned int BacktrackPoint;
123
124 /**
125 * Get a new backtrack point for the current partition
126 */
127 BacktrackPoint set_backtrack_point();
128
129 /**
130 * Backtrack to the point \a p and remove it.
131 */
132 void goto_backtrack_point(BacktrackPoint p);
133
134 /**
135 * Split the non-unit Cell \a cell = {\a element,e1,e2,...,en} containing
136 * the element \a element in two:
137 * \a cell = {e1,...,en} and \a newcell = {\a element}.
138 * @param cell a non-unit Cell
139 * @param element an element in \a cell
140 * @return the new unit Cell \a newcell
141 */
142 Cell* individualize(Cell* const cell,
143 const unsigned int element);
144
145 Cell* aux_split_in_two(Cell* const cell,
146 const unsigned int first_half_size);
147
148
149 private:
150 unsigned int N;
151 std::vector<Cell> cells_vec;
152 typedef std::vector<Cell>::iterator cell_pointer_substitute;
153 cell_pointer_substitute cells;
154 Cell* free_cells;
155 unsigned int discrete_cell_count;
156 public:
157 Cell* first_cell;
158 Cell* first_nonsingleton_cell;
159
160 typedef std::vector<unsigned int>::iterator uint_pointer_substitute;
161 typedef std::vector<unsigned int>::const_iterator
162 uint_pointer_to_const_substitute;
163 std::vector<unsigned int> elements_vec;
164 uint_pointer_substitute elements;
165 /* invariant_values[e] gives the invariant value of the element e */
166 std::vector<unsigned int> invariant_values_vec;
167 uint_pointer_substitute invariant_values;
168 /* element_to_cell_map[e] gives the cell of the element e */
169
170 typedef std::vector<Cell*>::iterator
171 cell_pointer_pointer_substitute;
172
173 std::vector<Cell*> element_to_cell_map_vec;
174 cell_pointer_pointer_substitute element_to_cell_map;
175 /** Get the cell of the element \a e */
get_cell(const unsigned int e) const176 Cell* get_cell(const unsigned int e) const {
177 return element_to_cell_map_vec[e];
178 }
179 /* in_pos[e] points to the elements array s.t. *in_pos[e] = e */
180 std::vector<uint_pointer_substitute> in_pos_vec;
181 std::vector<uint_pointer_substitute>::iterator in_pos;
182
183 Partition();
184 ~Partition();
185
186 /**
187 * Initialize the partition to the unit partition (all elements in one cell)
188 * over the \a N > 0 elements {0,...,\a N-1}.
189 */
190 void init(const unsigned int N);
191
192 /**
193 * Returns true iff the partition is discrete, meaning that all
194 * the elements are in their own cells.
195 */
is_discrete() const196 bool is_discrete() const {return(free_cells == 0); }
197
nof_discrete_cells() const198 unsigned int nof_discrete_cells() const {return(discrete_cell_count); }
199
200 /**
201 * Print the partition into the file stream \a fp.
202 */
203 size_t print(FILE* const fp, const bool add_newline = true) const;
204
205 /**
206 * Print the partition cell sizes into the file stream \a fp.
207 */
208 size_t print_signature(FILE* const fp, const bool add_newline = true) const;
209
210 /*
211 * Splits the Cell \a cell into [cell_1,...,cell_n]
212 * according to the invariant_values of the elements in \a cell.
213 * After splitting, cell_1 == \a cell.
214 * Returns the pointer to the Cell cell_n;
215 * cell_n != cell iff the Cell \a cell was actually splitted.
216 * The flag \a max_ival_info_ok indicates whether the max_ival and
217 * max_ival_count fields of the Cell \a cell have consistent values
218 * when the method is called.
219 * Clears the invariant values of elements in the Cell \a cell as well as
220 * the max_ival and max_ival_count fields of the Cell \a cell.
221 */
222 Cell *zplit_cell(Cell * const cell, const bool max_ival_info_ok);
223
224 /*
225 * Routines for component recursion
226 */
227 void cr_init();
228 void cr_free();
229 unsigned int cr_get_level(const unsigned int cell_index) const;
230 unsigned int cr_split_level(const unsigned int level,
231 const std::vector<unsigned int>& cells);
232
233 /** Clear the invariant_values of the elements in the Cell \a cell. */
234 void clear_ivs(Cell* const cell);
235
236 /* Is component recursion support in use? */
237 bool cr_enabled;
238
239 private:
240 /*
241 * Component recursion data structures
242 */
243
244
245 class CRCell {
246 public:
247 unsigned int level;
248 CRCell* next;
249 CRCell** prev_next_ptr;
detach()250 void detach() {
251 if(next)
252 next->prev_next_ptr = prev_next_ptr;
253 *(prev_next_ptr) = next;
254 level = UINT_MAX;
255 next = 0;
256 prev_next_ptr = 0;
257 }
258 };
259 typedef std::vector<CRCell>::iterator crcell_pointer_substitute;
260 std::vector<CRCell> cr_cells_vec;
261 crcell_pointer_substitute cr_cells;
262
263 typedef std::vector<CRCell*>::iterator crcell_pointer_pointer_substitute;
264 std::vector<CRCell*> cr_levels_vec;
265 crcell_pointer_pointer_substitute cr_levels;
266
267 class CR_BTInfo {
268 public:
269 unsigned int created_trail_index;
270 unsigned int splitted_level_trail_index;
271 };
272 std::vector<unsigned int> cr_created_trail;
273 std::vector<unsigned int> cr_splitted_level_trail;
274 std::vector<CR_BTInfo> cr_bt_info;
275 unsigned int cr_max_level;
276 void cr_create_at_level(const unsigned int cell_index, unsigned int level);
277 void cr_create_at_level_trailed(const unsigned int cell_index, unsigned int level);
278 unsigned int cr_get_backtrack_point();
279 void cr_goto_backtrack_point(const unsigned int btpoint);
280
281
282 /*
283 *
284 * Auxiliary routines for sorting and splitting cells
285 *
286 */
287 Cell* sort_and_split_cell1(Cell* cell);
288 Cell* sort_and_split_cell255(Cell* const cell, const unsigned int max_ival);
289 bool shellsort_cell(Cell* cell);
290 Cell* split_cell(Cell* const cell);
291
292 /*
293 * Some auxiliary stuff needed for distribution count sorting.
294 * To make the code thread-safe (modulo the requirement that each graph is
295 * only accessed in one thread at a time), the arrays are owned by
296 * the partition instance, not statically defined.
297 */
298 unsigned int dcs_count[256];
299 unsigned int dcs_start[256];
300 void dcs_cumulate_count(const unsigned int max);
301 };
302
303
304 inline Partition::Cell*
splitting_queue_pop()305 Partition::splitting_queue_pop()
306 {
307 Cell* const cell = splitting_queue.pop_front();
308 cell->in_splitting_queue = false;
309 return cell;
310 }
311
312 inline bool
splitting_queue_is_empty() const313 Partition::splitting_queue_is_empty() const
314 {
315 return splitting_queue.is_empty();
316 }
317
318
319 inline unsigned int
cr_get_level(const unsigned int cell_index) const320 Partition::cr_get_level(const unsigned int cell_index) const
321 {
322 return(cr_cells[cell_index].level);
323 }
324
325
326
327 } // namespace bliss_digraphs
328
329 #endif
330