permlib  0.2.9
Library for permutation computations
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 
40 namespace permlib {
41 namespace partition {
42 
44 template<class PERM>
45 class BacktrackRefinement : public Refinement<PERM> {
46 public:
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);
61 protected:
62  virtual bool init(Partition& pi);
63 private:
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 
89 template<class PERM>
91  : Refinement<PERM>(n, Backtrack), m_alpha(-1), m_cellElementIndex(-1), m_cellIndex(-1)
92 { }
93 
94 template<class PERM>
95 BacktrackRefinement<PERM>::BacktrackRefinement(unsigned long n, unsigned long alpha_)
96  : Refinement<PERM>(n, Backtrack), m_alpha(alpha_), m_cellElementIndex(-1), m_cellIndex(-1)
97 { }
98 
99 template<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 
109 template<class PERM>
110 unsigned long BacktrackRefinement<PERM>::alpha() const {
111  return m_alpha;
112 }
113 
114 template<class PERM>
116  std::sort(Refinement<PERM>::m_backtrackRefinements.begin(), Refinement<PERM>::m_backtrackRefinements.end(), RefinementSorter(sorter, pi));
117 }
118 
119 template<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_
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