permlib  0.2.9
Library for permutation computations
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 REFINEMENT_H_
34 #define REFINEMENT_H_
35 
36 #include <vector>
37 #include <boost/shared_ptr.hpp>
38 
39 #include <permlib/search/partition/partition.h>
40 
41 namespace permlib {
42 namespace partition {
43 
45 enum RefinementType {
46  Default,
47  Backtrack,
48  Group
49 };
50 
52 template<class PERM>
53 class Refinement {
54 public:
56  Refinement(unsigned long n, RefinementType type);
58  virtual ~Refinement();
59 
61 
64  bool initializeAndApply(Partition& pi);
66 
71  virtual unsigned int apply(Partition& pi) const = 0;
72 
74 
79  virtual unsigned int apply2(Partition& pi, const PERM& t) const;
80 
82  void undo(Partition& pi, unsigned int count) const;
83 
84  typedef typename boost::shared_ptr<Refinement<PERM> > RefinementPtr;
85  typedef typename std::vector<RefinementPtr>::const_iterator RefinementPtrIterator;
86 
88  RefinementType type() const;
90  unsigned int alternatives() const;
92  RefinementPtrIterator backtrackBegin() const { return m_backtrackRefinements.begin(); }
94  RefinementPtrIterator backtrackEnd() const { return m_backtrackRefinements.end(); }
95 
97  virtual bool init(Partition& pi) = 0;
98 
100  virtual void sort(const BaseSorterByReference&, const Partition*) { }
101 protected:
103  unsigned long m_n;
105  std::vector<RefinementPtr> m_backtrackRefinements;
107  std::list<int> m_cellPairs;
108 
110  bool initialized() const;
111 private:
112  bool m_initialized;
113  RefinementType m_type;
114 };
115 
116 template<class PERM>
117 Refinement<PERM>::Refinement(unsigned long n_, RefinementType type_)
118  : m_n(n_), m_initialized(false), m_type(type_)
119 { }
120 
121 template<class PERM>
123 { }
124 
125 template<class PERM>
126 unsigned int Refinement<PERM>::alternatives() const {
127  return m_backtrackRefinements.size();
128 }
129 
130 template<class PERM>
131 RefinementType Refinement<PERM>::type() const {
132  return m_type;
133 }
134 
135 template<class PERM>
137  if (!m_initialized) {
138  m_initialized = true;
139  return init(pi);
140  }
141  return false;
142 }
143 
144 template<class PERM>
146  return m_initialized;
147 }
148 
149 template<class PERM>
150 void Refinement<PERM>::undo(Partition& pi, unsigned int count) const {
151  for (unsigned int i=0; i<count; ++i)
152  pi.undoIntersection();
153 }
154 
155 template<class PERM>
156 unsigned int Refinement<PERM>::apply2(Partition& pi, const PERM& t) const {
157  return this->apply(pi);
158 }
159 
160 }
161 }
162 
163 #endif // -- REFINEMENT_H_
bool initializeAndApply(Partition &pi)
applies (left-)refinement to partition and initializes refinement for future use in R-base ...
Definition: refinement.h:136
std::vector< RefinementPtr > m_backtrackRefinements
refinement siblings in the search tree
Definition: refinement.h:105
virtual unsigned int apply2(Partition &pi, const PERM &t) const
applies (right-)refinement to pi which is the image of the original partition this refinement was ini...
Definition: refinement.h:156
virtual bool init(Partition &pi)=0
initializes refinement
bool initialized() const
true iff refinement is initalized
Definition: refinement.h:145
RefinementPtrIterator backtrackBegin() const
iterator to begin of refinement siblings in the search tree
Definition: refinement.h:92
base class for a -refinement which is used in an R-base and bound to an initial partition ...
Definition: refinement.h:53
virtual void sort(const BaseSorterByReference &, const Partition *)
sorts siblings in the search tree
Definition: refinement.h:100
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 m_n
length of partitions to work with
Definition: refinement.h:103
unsigned int alternatives() const
number of sibling of this refinement in the search tree
Definition: refinement.h:126
Refinement(unsigned long n, RefinementType type)
constructor
Definition: refinement.h:117
virtual unsigned int apply(Partition &pi) const =0
applies (left-)refinement to pi which is the original partition this refinement was initialized to ...
RefinementPtrIterator backtrackEnd() const
iterator to end of refinement siblings in the search tree
Definition: refinement.h:94
RefinementType type() const
the type of this refinement
Definition: refinement.h:131
virtual ~Refinement()
destructor
Definition: refinement.h:122
bool undoIntersection()
reverts the last intersection if there is one
Definition: partition.h:277
void undo(Partition &pi, unsigned int count) const
reverts the last count elementary intersections of partition pi
Definition: refinement.h:150
std::list< int > m_cellPairs
indices of elementary intersections to apply during refinement application
Definition: refinement.h:107
Definition: abstract_bsgs.h:49