File: partition.hh

package info (click to toggle)
bliss 0.73-4
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 712 kB
  • sloc: cpp: 6,538; makefile: 144; sh: 6
file content (308 lines) | stat: -rw-r--r-- 8,441 bytes parent folder | download | duplicates (3)
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
#ifndef BLISS_PARTITION_HH
#define BLISS_PARTITION_HH

/*
  Copyright (c) 2003-2015 Tommi Junttila
  Released under the GNU Lesser General Public License version 3.
  
  This file is part of bliss.
  
  bliss is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation, version 3 of the License.

  bliss is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with bliss.  If not, see <http://www.gnu.org/licenses/>.
*/

namespace bliss {
  class Partition;
}

#include <cstdlib>
#include <cstdio>
#include <climits>
#include <bliss/kstack.hh>
#include <bliss/kqueue.hh>
#include <bliss/heap.hh>
#include <bliss/orbit.hh>
#include <bliss/graph.hh>


namespace bliss {

/** \internal
 * \brief A class for refinable, backtrackable ordered partitions.
 *
 * This is rather a data structure with some helper functions than
 * a proper self-contained class.
 * That is, for efficiency reasons the fields of this class are directly
 * manipulated from bliss::AbstractGraph and its subclasses.
 * Conversely, some methods of this class modify the fields of
 * bliss::AbstractGraph, too.
 */
class Partition
{
public:
  /**
   * \brief Data structure for holding information about a cell in a Partition.
   */
  class Cell
  {
    friend class Partition;
  public:
    unsigned int length;
    /* Index of the first element of the cell in
       the Partition::elements array */
    unsigned int first;
    unsigned int max_ival;
    unsigned int max_ival_count;
  private:
    bool in_splitting_queue;
  public:
    bool in_neighbour_heap;
    /* Pointer to the next cell, null if this is the last one. */
    Cell* next;
    Cell* prev;
    Cell* next_nonsingleton;
    Cell* prev_nonsingleton;
    unsigned int split_level;
    /** Is this a unit cell? */
    bool is_unit() const {return(length == 1); }
    /** Is this cell in splitting queue? */
    bool is_in_splitting_queue() const {return(in_splitting_queue); }
  };


private:

  /** \internal
   * Data structure for remembering information about splits in order to
   * perform efficient backtracking over the splits.
   */
  class RefInfo {
  public:
    unsigned int split_cell_first;
    int prev_nonsingleton_first;
    int next_nonsingleton_first;
  };
  /** \internal
   * A stack for remembering the splits, used for backtracking.
   */
  KStack<RefInfo> refinement_stack;

  class BacktrackInfo {
  public:
    unsigned int refinement_stack_size;
    unsigned int cr_backtrack_point;
  };

  /** \internal
   * The main stack for enabling backtracking.
   */
  std::vector<BacktrackInfo> bt_stack;

public:
  AbstractGraph* graph;

  /* Used during equitable partition refinement */
  KQueue<Cell*> splitting_queue;
  void  splitting_queue_add(Cell* const cell);
  Cell* splitting_queue_pop();
  bool  splitting_queue_is_empty() const;
  void  splitting_queue_clear();


  /** Type for backtracking points. */
  typedef unsigned int BacktrackPoint;

  /**
   * Get a new backtrack point for the current partition
   */
  BacktrackPoint set_backtrack_point();

  /**
   * Backtrack to the point \a p and remove it.
   */
  void goto_backtrack_point(BacktrackPoint p);

  /**
   * Split the non-unit Cell \a cell = {\a element,e1,e2,...,en} containing
   * the element \a element in two:
   * \a cell = {e1,...,en} and \a newcell = {\a element}.
   * @param cell     a non-unit Cell
   * @param element  an element in \a cell
   * @return         the new unit Cell \a newcell
   */
  Cell* individualize(Cell* const cell,
		      const unsigned int element);

  Cell* aux_split_in_two(Cell* const cell,
			 const unsigned int first_half_size);


private:
  unsigned int N;
  Cell* cells;
  Cell* free_cells;
  unsigned int discrete_cell_count;
public:
  Cell* first_cell;
  Cell* first_nonsingleton_cell;
  unsigned int *elements;
  /* invariant_values[e] gives the invariant value of the element e */
  unsigned int *invariant_values;
  /* element_to_cell_map[e] gives the cell of the element e */
  Cell **element_to_cell_map;
  /** Get the cell of the element \a e */
  Cell* get_cell(const unsigned int e) const {
    return element_to_cell_map[e];
  }
  /* in_pos[e] points to the elements array s.t. *in_pos[e] = e  */
  unsigned int **in_pos;

  Partition();
  ~Partition();

  /**
   * Initialize the partition to the unit partition (all elements in one cell)
   * over the \a N > 0 elements {0,...,\a N-1}.
   */
  void init(const unsigned int N);

  /**
   * Returns true iff the partition is discrete, meaning that all
   * the elements are in their own cells.
   */
  bool is_discrete() const {return(free_cells == 0); }

  unsigned int nof_discrete_cells() const {return(discrete_cell_count); }

  /**
   * Print the partition into the file stream \a fp.
   */
  size_t print(FILE* const fp, const bool add_newline = true) const;

  /**
   * Print the partition cell sizes into the file stream \a fp.
   */
  size_t print_signature(FILE* const fp, const bool add_newline = true) const;

  /*
   * Splits the Cell \a cell into [cell_1,...,cell_n]
   * according to the invariant_values of the elements in \a cell.
   * After splitting, cell_1 == \a cell.
   * Returns the pointer to the Cell cell_n;
   * cell_n != cell iff the Cell \a cell was actually splitted.
   * The flag \a max_ival_info_ok indicates whether the max_ival and
   * max_ival_count fields of the Cell \a cell have consistent values
   * when the method is called.
   * Clears the invariant values of elements in the Cell \a cell as well as
   * the max_ival and max_ival_count fields of the Cell \a cell.
   */
  Cell *zplit_cell(Cell * const cell, const bool max_ival_info_ok);

  /*
   * Routines for component recursion
   */
  void cr_init();
  void cr_free();
  unsigned int cr_get_level(const unsigned int cell_index) const;
  unsigned int cr_split_level(const unsigned int level,
			      const std::vector<unsigned int>& cells);

  /** Clear the invariant_values of the elements in the Cell \a cell. */
  void clear_ivs(Cell* const cell);

private:
  /*
   * Component recursion data structures
   */

  /* Is component recursion support in use? */
  bool cr_enabled;

  class CRCell {
  public:
    unsigned int level;
    CRCell* next;
    CRCell** prev_next_ptr;
    void detach() {
      if(next)
	next->prev_next_ptr = prev_next_ptr;
      *(prev_next_ptr) = next;
      level = UINT_MAX;
      next = 0;
      prev_next_ptr = 0;
    }
  };
  CRCell* cr_cells;
  CRCell** cr_levels;
  class CR_BTInfo {
  public:
    unsigned int created_trail_index;
    unsigned int splitted_level_trail_index;
  };
  std::vector<unsigned int> cr_created_trail;
  std::vector<unsigned int> cr_splitted_level_trail;
  std::vector<CR_BTInfo> cr_bt_info;
  unsigned int cr_max_level;
  void cr_create_at_level(const unsigned int cell_index, unsigned int level);
  void cr_create_at_level_trailed(const unsigned int cell_index, unsigned int level);
  unsigned int cr_get_backtrack_point();
  void cr_goto_backtrack_point(const unsigned int btpoint);


  /*
   *
   * Auxiliary routines for sorting and splitting cells
   *
   */
  Cell* sort_and_split_cell1(Cell* cell);
  Cell* sort_and_split_cell255(Cell* const cell, const unsigned int max_ival);
  bool shellsort_cell(Cell* cell);
  Cell* split_cell(Cell* const cell);

  /*
   * Some auxiliary stuff needed for distribution count sorting.
   * To make the code thread-safe (modulo the requirement that each graph is
   * only accessed in one thread at a time), the arrays are owned by
   * the partition instance, not statically defined.
   */
  unsigned int dcs_count[256];
  unsigned int dcs_start[256];
  void dcs_cumulate_count(const unsigned int max);
};


inline Partition::Cell*
Partition::splitting_queue_pop()
{
  Cell* const cell = splitting_queue.pop_front();
  cell->in_splitting_queue = false;
  return cell;
}

inline bool
Partition::splitting_queue_is_empty() const
{
  return splitting_queue.is_empty();
}


inline unsigned int
Partition::cr_get_level(const unsigned int cell_index) const
{
  return(cr_cells[cell_index].level);
}



} // namespace bliss

#endif