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 {
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 {
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 Cell* cells;
152 Cell* free_cells;
153 unsigned int discrete_cell_count;
154 public:
155 Cell* first_cell;
156 Cell* first_nonsingleton_cell;
157 unsigned int *elements;
158 /* invariant_values[e] gives the invariant value of the element e */
159 unsigned int *invariant_values;
160 /* element_to_cell_map[e] gives the cell of the element e */
161 Cell **element_to_cell_map;
162 /** Get the cell of the element \a e */
get_cell(const unsigned int e) const163 Cell* get_cell(const unsigned int e) const {
164 return element_to_cell_map[e];
165 }
166 /* in_pos[e] points to the elements array s.t. *in_pos[e] = e */
167 unsigned int **in_pos;
168
169 Partition();
170 ~Partition();
171
172 /**
173 * Initialize the partition to the unit partition (all elements in one cell)
174 * over the \a N > 0 elements {0,...,\a N-1}.
175 */
176 void init(const unsigned int N);
177
178 /**
179 * Returns true iff the partition is discrete, meaning that all
180 * the elements are in their own cells.
181 */
is_discrete() const182 bool is_discrete() const {return(free_cells == 0); }
183
nof_discrete_cells() const184 unsigned int nof_discrete_cells() const {return(discrete_cell_count); }
185
186 /**
187 * Print the partition into the file stream \a fp.
188 */
189 size_t print(FILE* const fp, const bool add_newline = true) const;
190
191 /**
192 * Print the partition cell sizes into the file stream \a fp.
193 */
194 size_t print_signature(FILE* const fp, const bool add_newline = true) const;
195
196 /*
197 * Splits the Cell \a cell into [cell_1,...,cell_n]
198 * according to the invariant_values of the elements in \a cell.
199 * After splitting, cell_1 == \a cell.
200 * Returns the pointer to the Cell cell_n;
201 * cell_n != cell iff the Cell \a cell was actually splitted.
202 * The flag \a max_ival_info_ok indicates whether the max_ival and
203 * max_ival_count fields of the Cell \a cell have consistent values
204 * when the method is called.
205 * Clears the invariant values of elements in the Cell \a cell as well as
206 * the max_ival and max_ival_count fields of the Cell \a cell.
207 */
208 Cell *zplit_cell(Cell * const cell, const bool max_ival_info_ok);
209
210 /*
211 * Routines for component recursion
212 */
213 void cr_init();
214 void cr_free();
215 unsigned int cr_get_level(const unsigned int cell_index) const;
216 unsigned int cr_split_level(const unsigned int level,
217 const std::vector<unsigned int>& cells);
218
219 /** Clear the invariant_values of the elements in the Cell \a cell. */
220 void clear_ivs(Cell* const cell);
221
222 private:
223 /*
224 * Component recursion data structures
225 */
226
227 /* Is component recursion support in use? */
228 bool cr_enabled;
229
230 class CRCell {
231 public:
232 unsigned int level;
233 CRCell* next;
234 CRCell** prev_next_ptr;
detach()235 void detach() {
236 if(next)
237 next->prev_next_ptr = prev_next_ptr;
238 *(prev_next_ptr) = next;
239 level = UINT_MAX;
240 next = 0;
241 prev_next_ptr = 0;
242 }
243 };
244 CRCell* cr_cells;
245 CRCell** cr_levels;
246 class CR_BTInfo {
247 public:
248 unsigned int created_trail_index;
249 unsigned int splitted_level_trail_index;
250 };
251 std::vector<unsigned int> cr_created_trail;
252 std::vector<unsigned int> cr_splitted_level_trail;
253 std::vector<CR_BTInfo> cr_bt_info;
254 unsigned int cr_max_level;
255 void cr_create_at_level(const unsigned int cell_index, unsigned int level);
256 void cr_create_at_level_trailed(const unsigned int cell_index, unsigned int level);
257 unsigned int cr_get_backtrack_point();
258 void cr_goto_backtrack_point(const unsigned int btpoint);
259
260
261 /*
262 *
263 * Auxiliary routines for sorting and splitting cells
264 *
265 */
266 Cell* sort_and_split_cell1(Cell* cell);
267 Cell* sort_and_split_cell255(Cell* const cell, const unsigned int max_ival);
268 bool shellsort_cell(Cell* cell);
269 Cell* split_cell(Cell* const cell);
270
271 /*
272 * Some auxiliary stuff needed for distribution count sorting.
273 * To make the code thread-safe (modulo the requirement that each graph is
274 * only accessed in one thread at a time), the arrays are owned by
275 * the partition instance, not statically defined.
276 */
277 unsigned int dcs_count[256];
278 unsigned int dcs_start[256];
279 void dcs_cumulate_count(const unsigned int max);
280 };
281
282
283 inline Partition::Cell*
splitting_queue_pop()284 Partition::splitting_queue_pop()
285 {
286 Cell* const cell = splitting_queue.pop_front();
287 cell->in_splitting_queue = false;
288 return cell;
289 }
290
291 inline bool
splitting_queue_is_empty() const292 Partition::splitting_queue_is_empty() const
293 {
294 return splitting_queue.is_empty();
295 }
296
297
298 inline unsigned int
cr_get_level(const unsigned int cell_index) const299 Partition::cr_get_level(const unsigned int cell_index) const
300 {
301 return(cr_cells[cell_index].level);
302 }
303
304
305
306 } // namespace bliss
307
308 #endif
309