permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
41namespace permlib {
42namespace partition {
43
45enum RefinementType {
46 Default,
47 Backtrack,
48 Group
49};
50
52template<class PERM>
54public:
56 Refinement(unsigned long n, RefinementType type);
58 virtual ~Refinement();
59
61
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*) { }
101protected:
103 unsigned long m_n;
105 std::vector<RefinementPtr> m_backtrackRefinements;
107 std::list<int> m_cellPairs;
108
110 bool initialized() const;
111private:
112 bool m_initialized;
113 RefinementType m_type;
114};
115
116template<class PERM>
117Refinement<PERM>::Refinement(unsigned long n_, RefinementType type_)
118 : m_n(n_), m_initialized(false), m_type(type_)
119{ }
120
121template<class PERM>
124
125template<class PERM>
126unsigned int Refinement<PERM>::alternatives() const {
127 return m_backtrackRefinements.size();
128}
129
130template<class PERM>
131RefinementType Refinement<PERM>::type() const {
132 return m_type;
133}
134
135template<class PERM>
137 if (!m_initialized) {
138 m_initialized = true;
139 return init(pi);
140 }
141 return false;
142}
143
144template<class PERM>
146 return m_initialized;
147}
148
149template<class PERM>
150void Refinement<PERM>::undo(Partition& pi, unsigned int count) const {
151 for (unsigned int i=0; i<count; ++i)
152 pi.undoIntersection();
153}
154
155template<class PERM>
156unsigned int Refinement<PERM>::apply2(Partition& pi, const PERM& t) const {
157 return this->apply(pi);
158}
159
160}
161}
162
163#endif // -- REFINEMENT_H_
A sorter that sorts a sequence (e.g. ) with respect to a given input ordering (e.g....
Definition base_sorter.h:113
partition
Definition partition.h:48
bool undoIntersection()
reverts the last intersection if there is one
Definition partition.h:277
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
unsigned long m_n
Definition refinement.h:103
std::vector< RefinementPtr > m_backtrackRefinements
Definition refinement.h:105
bool initialized() const
true iff refinement is initalized
Definition refinement.h:145
virtual unsigned int apply(Partition &pi) const =0
applies (left-)refinement to pi which is the original partition this refinement was initialized to
void undo(Partition &pi, unsigned int count) const
reverts the last count elementary intersections of partition pi
Definition refinement.h:150
virtual void sort(const BaseSorterByReference &, const Partition *)
sorts siblings in the search tree
Definition refinement.h:100
virtual ~Refinement()
destructor
Definition refinement.h:122
bool initializeAndApply(Partition &pi)
applies (left-)refinement to partition and initializes refinement for future use in R-base
Definition refinement.h:136
Refinement(unsigned long n, RefinementType type)
constructor
Definition refinement.h:117
std::list< int > m_cellPairs
Definition refinement.h:107
RefinementPtrIterator backtrackEnd() const
iterator to end of refinement siblings in the search tree
Definition refinement.h:94
unsigned int alternatives() const
number of sibling of this refinement in the search tree
Definition refinement.h:126
virtual bool init(Partition &pi)=0
initializes refinement
RefinementType type() const
RefinementPtrIterator backtrackBegin() const
iterator to begin of refinement siblings in the search tree
Definition refinement.h:92