33 #ifndef BACKTRACKREFINEMENT_H_ 34 #define BACKTRACKREFINEMENT_H_ 36 #include <permlib/search/partition/refinement.h> 59 unsigned long alpha()
const;
64 unsigned long m_alpha;
65 unsigned int m_cellElementIndex;
66 unsigned int m_cellIndex;
68 typedef typename Refinement<PERM>::RefinementPtr RefinementPtr;
70 struct RefinementSorter :
public std::binary_function<RefinementPtr, RefinementPtr, bool> {
73 bool operator()(RefinementPtr a, RefinementPtr b)
const {
77 return m_sorter(m_pi->partition[backtrackA->m_cellElementIndex], m_pi->partition[backtrackB->m_cellElementIndex]);
79 return m_sorter(backtrackA->m_alpha, backtrackB->m_alpha);
86 static const unsigned int overrideAlphaChoiceCellSizeRatio = 8;
91 :
Refinement<PERM>(n, Backtrack), m_alpha(-1), m_cellElementIndex(-1), m_cellIndex(-1)
96 :
Refinement<PERM>(n, Backtrack), m_alpha(alpha_), m_cellElementIndex(-1), m_cellIndex(-1)
101 unsigned long singleCell[1];
102 singleCell[0] = pi.partition[m_cellElementIndex];
105 PERMLIB_DEBUG(std::cout <<
" apply bt ref alpha =" << m_alpha <<
", single cell = " << singleCell[0] <<
" @ " << m_cellIndex <<
"," << m_cellElementIndex << std::endl;)
106 return pi.
intersect(singleCell, singleCell+1, m_cellIndex);
121 unsigned int minCellSize = pi.partition.size();
122 unsigned int minCell = 0;
125 std::vector<unsigned int>::const_iterator length = pi.partitionCellLength.begin();
126 for (
unsigned int j = 0; j < pi.cellCounter; ++j) {
127 if (1 < *length && *length < minCellSize) {
128 minCellSize = *length;
133 if (m_alpha == static_cast<unsigned long>(-1)) {
134 this->m_cellElementIndex = pi.partitionCellBorder[minCell];
135 this->m_alpha = pi.partition[pi.partitionCellBorder[minCell]];
137 const unsigned int givenMinCell = pi.partitionCellOf[m_alpha];
138 const unsigned int givenMinCellSize = pi.partitionCellLength[givenMinCell];
139 if (1 < givenMinCellSize && givenMinCellSize <= overrideAlphaChoiceCellSizeRatio * minCellSize) {
140 minCell = givenMinCell;
141 minCellSize = givenMinCellSize;
142 for (
unsigned int j = pi.partitionCellBorder[minCell]; j < pi.partitionCellBorder[minCell] + pi.partitionCellLength[minCell]; ++j) {
143 if (pi.partition[j] == m_alpha) {
144 this->m_cellElementIndex = j;
149 this->m_cellElementIndex = pi.partitionCellBorder[minCell];
150 this->m_alpha = pi.partition[pi.partitionCellBorder[minCell]];
153 PERMLIB_DEBUG(std::cout <<
"minCellSize = " << minCellSize << std::endl;)
155 this->m_cellIndex = minCell;
158 for (
unsigned int i = pi.partitionCellBorder[minCell]; i < pi.partitionCellBorder[minCell] + minCellSize; ++i) {
160 br->m_cellElementIndex = i;
161 br->m_cellIndex = minCell;
162 br->m_alpha = pi.partition[i];
164 PERMLIB_DEBUG(std::cout <<
"PREP bt alpha " << br->m_alpha <<
" @ " << br->m_cellIndex <<
" // " << br->m_cellElementIndex << std::endl;)
165 typename Refinement<PERM>::RefinementPtr ref(br);
169 unsigned long singleCell[1];
170 singleCell[0] = this->m_alpha;
172 const bool inter __attribute__((unused)) = pi.
intersect(singleCell, singleCell+1, m_cellIndex);
181 #endif // -- BACKTRACKREFINEMENT_H_ virtual unsigned int apply(Partition &pi) const
applies (left-)refinement to pi which is the original partition this refinement was initialized to ...
Definition: backtrack_refinement.h:100
base class for a -refinement which is used in an R-base and bound to an initial partition ...
Definition: refinement.h:53
partition
Definition: partition.h:48
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g. a base)
Definition: base_sorter.h:113
unsigned long alpha() const
alpha point chosen for backtracking
Definition: backtrack_refinement.h:110
virtual bool init(Partition &pi)
initializes refinement
Definition: backtrack_refinement.h:120
bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j)
intersects the j-th cell of this partition with a given set
Definition: partition.h:186
backtrack refinement
Definition: backtrack_refinement.h:45
Definition: abstract_bsgs.h:49
virtual void sort(const BaseSorterByReference &sorter, const Partition *pi)
sorts siblings in the search tree
Definition: backtrack_refinement.h:115
BacktrackRefinement(unsigned long n)
constructor
Definition: backtrack_refinement.h:90