permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
backtrack_refinement.h
1// ---------------------------------------------------------------------------
2//
3// This file is part of PermLib.
4//
5// Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6// All rights reserved.
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions
10// are met:
11// 1. Redistributions of source code must retain the above copyright
12// notice, this list of conditions and the following disclaimer.
13// 2. Redistributions in binary form must reproduce the above copyright
14// notice, this list of conditions and the following disclaimer in the
15// documentation and/or other materials provided with the distribution.
16// 3. The name of the author may not be used to endorse or promote products
17// derived from this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29//
30// ---------------------------------------------------------------------------
31
32
33#ifndef BACKTRACKREFINEMENT_H_
34#define BACKTRACKREFINEMENT_H_
35
36#include <permlib/search/partition/refinement.h>
37
38#include <list>
39
40namespace permlib {
41namespace partition {
42
44template<class PERM>
45class BacktrackRefinement : public Refinement<PERM> {
46public:
48 explicit BacktrackRefinement(unsigned long n);
50
54 BacktrackRefinement(unsigned long n, unsigned long alpha);
55
56 virtual unsigned int apply(Partition& pi) const;
57
59 unsigned long alpha() const;
60 virtual void sort(const BaseSorterByReference& sorter, const Partition* pi);
61protected:
62 virtual bool init(Partition& pi);
63private:
64 unsigned long m_alpha;
65 unsigned int m_cellElementIndex;
66 unsigned int m_cellIndex;
67
68 typedef typename Refinement<PERM>::RefinementPtr RefinementPtr;
69
70 struct RefinementSorter : public std::binary_function<RefinementPtr, RefinementPtr, bool> {
71 RefinementSorter(const BaseSorterByReference& sorter, const Partition* pi) : m_sorter(sorter), m_pi(pi) {}
72
73 bool operator()(RefinementPtr a, RefinementPtr b) const {
74 BacktrackRefinement<PERM>* backtrackA = static_cast<BacktrackRefinement<PERM>*>(a.get());
75 BacktrackRefinement<PERM>* backtrackB = static_cast<BacktrackRefinement<PERM>*>(b.get());
76 if (m_pi) {
77 return m_sorter(m_pi->partition[backtrackA->m_cellElementIndex], m_pi->partition[backtrackB->m_cellElementIndex]);
78 }
79 return m_sorter(backtrackA->m_alpha, backtrackB->m_alpha);
80 }
81 private:
82 const BaseSorterByReference& m_sorter;
83 const Partition* m_pi;
84 };
85
86 static const unsigned int overrideAlphaChoiceCellSizeRatio = 8;
87};
88
89template<class PERM>
91 : Refinement<PERM>(n, Backtrack), m_alpha(-1), m_cellElementIndex(-1), m_cellIndex(-1)
92{ }
93
94template<class PERM>
95BacktrackRefinement<PERM>::BacktrackRefinement(unsigned long n, unsigned long alpha_)
96 : Refinement<PERM>(n, Backtrack), m_alpha(alpha_), m_cellElementIndex(-1), m_cellIndex(-1)
97{ }
98
99template<class PERM>
101 unsigned long singleCell[1];
102 singleCell[0] = pi.partition[m_cellElementIndex];
103 //singleCell[0] = t / m_alpha;
104 //print_iterable(pi.partition.begin(), pi.partition.end(), 0, " partition pi");
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);
107}
108
109template<class PERM>
110unsigned long BacktrackRefinement<PERM>::alpha() const {
111 return m_alpha;
112}
113
114template<class PERM>
116 std::sort(Refinement<PERM>::m_backtrackRefinements.begin(), Refinement<PERM>::m_backtrackRefinements.end(), RefinementSorter(sorter, pi));
117}
118
119template<class PERM>
121 unsigned int minCellSize = pi.partition.size();
122 unsigned int minCell = 0;
123 //std::cout << "m_alpha " << m_alpha << std::endl;
124
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;
129 minCell = j;
130 }
131 ++length;
132 }
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]];
136 } else {
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;
145 break;
146 }
147 }
148 } else {
149 this->m_cellElementIndex = pi.partitionCellBorder[minCell];
150 this->m_alpha = pi.partition[pi.partitionCellBorder[minCell]];
151 }
152 }
153 PERMLIB_DEBUG(std::cout << "minCellSize = " << minCellSize << std::endl;)
154
155 this->m_cellIndex = minCell;
156
157 Refinement<PERM>::m_backtrackRefinements.reserve(minCellSize);
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];
163 //print_iterable(pi.partition.begin(), pi.partition.end(), 0, " partition pi");
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);
167 }
168
169 unsigned long singleCell[1];
170 singleCell[0] = this->m_alpha;
171 //TODO: write special case function to handle singleCell intersection
172 const bool inter __attribute__((unused)) = pi.intersect(singleCell, singleCell+1, m_cellIndex);
173 BOOST_ASSERT(inter);
174
175 return true;
176}
177
178}
179}
180
181#endif // -- BACKTRACKREFINEMENT_H_
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g....
Definition base_sorter.h:113
backtrack refinement
Definition backtrack_refinement.h:45
virtual bool init(Partition &pi)
initializes refinement
Definition backtrack_refinement.h:120
unsigned long alpha() const
alpha point chosen for backtracking
Definition backtrack_refinement.h:110
virtual void sort(const BaseSorterByReference &sorter, const Partition *pi)
sorts siblings in the search tree
Definition backtrack_refinement.h:115
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
BacktrackRefinement(unsigned long n)
constructor
Definition backtrack_refinement.h:90
partition
Definition partition.h:48
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
base class for a -refinement which is used in an R-base and bound to an initial partition
Definition refinement.h:53