Loading...
Searching...
No Matches
partition.hh
#pragma once
/*
Copyright (c) 2003-2021 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 <vector>
#include <climits>
#include <bliss/kqueue.hh>
#include <bliss/abstractgraph.hh>
namespace bliss {
class Partition
{
public:
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;
bool is_unit() const {return(length == 1); }
bool is_in_splitting_queue() const {return(in_splitting_queue); }
};
private:
class RefInfo {
public:
unsigned int split_cell_first;
int prev_nonsingleton_first;
int next_nonsingleton_first;
};
std::vector<RefInfo> refinement_stack;
class BacktrackInfo {
public:
unsigned int refinement_stack_size;
unsigned int cr_backtrack_point;
};
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();
typedef unsigned int BacktrackPoint;
BacktrackPoint set_backtrack_point();
void goto_backtrack_point(BacktrackPoint p);
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;
Cell* get_cell(const unsigned int e) const {
assert(e < N);
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();
void init(const unsigned int N);
bool is_discrete() const {return(free_cells == 0); }
unsigned int nof_discrete_cells() const {return(discrete_cell_count); }
size_t print(FILE* const fp, const bool add_newline = true) const;
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 the 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);
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 = nullptr;
prev_next_ptr = nullptr;
}
};
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()
{
assert(!splitting_queue.is_empty());
Cell* const cell = splitting_queue.pop_front();
assert(cell->in_splitting_queue);
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
{
assert(cr_enabled);
assert(cell_index < N);
assert(cr_cells[cell_index].level != UINT_MAX);
return(cr_cells[cell_index].level);
}
} // namespace bliss
bliss::Partition::Cell
Data structure for holding information about a cell in a Partition.
Definition partition.hh:51
bliss::Partition::Cell::is_in_splitting_queue
bool is_in_splitting_queue() const
Definition partition.hh:73
bliss::Partition::Cell::is_unit
bool is_unit() const
Definition partition.hh:71
bliss::Partition
A class for refinable, backtrackable ordered partitions.
Definition partition.hh:45
bliss::Partition::get_cell
Cell * get_cell(const unsigned int e) const
Definition partition.hh:158
bliss::Partition::is_discrete
bool is_discrete() const
Definition partition.hh:178
bliss::Partition::goto_backtrack_point
void goto_backtrack_point(BacktrackPoint p)
Definition partition.cc:161
bliss::Partition::print
size_t print(FILE *const fp, const bool add_newline=true) const
Definition partition.cc:353
bliss::Partition::clear_ivs
void clear_ivs(Cell *const cell)
Definition partition.cc:822
bliss::Partition::individualize
Cell * individualize(Cell *const cell, const unsigned int element)
Definition partition.cc:254
bliss::Partition::init
void init(const unsigned int N)
Definition partition.cc:64
bliss::Partition::print_signature
size_t print_signature(FILE *const fp, const bool add_newline=true) const
Definition partition.cc:379
bliss::Partition::set_backtrack_point
BacktrackPoint set_backtrack_point()
Definition partition.cc:147
bliss::Partition::BacktrackPoint
unsigned int BacktrackPoint
Definition partition.hh:117
bliss
Definition abstractgraph.cc:35