permlib  0.2.9
Library for permutation computations
refinement_family.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 REFIMENET_FAMILY_H
34 #define REFIMENET_FAMILY_H
35 
36 #include <permlib/search/partition/group_refinement.h>
37 #include <permlib/search/partition/set_stabilize_refinement.h>
38 #include <permlib/search/partition/set_image_refinement.h>
39 #include <permlib/search/partition/matrix_refinement2.h>
40 
41 namespace permlib {
42 namespace partition {
43 
45 
48 template<class PERM>
50 public:
51  typedef typename Refinement<PERM>::RefinementPtr RefinementPtr;
52  typedef boost::shared_ptr<Partition> PartitionPtr;
53 
55  virtual ~RefinementFamily() {}
56 
58 
62  virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const = 0;
63 };
64 
66 template<class PERM,class TRANS>
68 public:
69  typedef typename RefinementFamily<PERM>::RefinementPtr RefinementPtr;
70  typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr;
71 
73  explicit GroupRefinementFamily(const BSGSCore<PERM,TRANS>& bsgs) : m_bsgs(bsgs) {}
74 
75  virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const {
76  RefinementPtr ref(new GroupRefinement<PERM,TRANS>(m_bsgs));
77  GroupRefinement<PERM,TRANS> *gref = static_cast<GroupRefinement<PERM,TRANS>*>(ref.get());
78  bool strictRefinement = gref->initializeAndApply(pi);
79  if (strictRefinement)
80  return std::make_pair(PartitionPtr(new Partition(pi)), ref);
81  else
82  return std::make_pair(PartitionPtr(), RefinementPtr());
83  }
84 private:
85  const BSGSCore<PERM,TRANS>& m_bsgs;
86 };
87 
89 template<class PERM>
91 public:
92  typedef typename RefinementFamily<PERM>::RefinementPtr RefinementPtr;
93  typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr;
94 
96 
101  template<class InputIterator>
102  SetStabilizeRefinementFamily(unsigned long n, InputIterator begin, InputIterator end) : m_n(n), toStab(begin, end)
103  {}
104 
105  virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const {
106  RefinementPtr ref(new SetStabilizeRefinement<PERM>(m_n, toStab.begin(), toStab.end()));
107  SetStabilizeRefinement<PERM> *gref = static_cast<SetStabilizeRefinement<PERM>*>(ref.get());
108  bool strictRefinement = gref->initializeAndApply(pi);
109  if (strictRefinement)
110  return std::make_pair(PartitionPtr(new Partition(pi)), ref);
111  else
112  return std::make_pair(PartitionPtr(), RefinementPtr());
113  }
114 private:
115  unsigned long m_n;
116  std::vector<unsigned long> toStab;
117 };
118 
120 template<class PERM>
122 public:
123  typedef typename RefinementFamily<PERM>::RefinementPtr RefinementPtr;
124  typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr;
125 
127 
134  template<class InputIterator>
135  SetImageRefinementFamily(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg)
136  : m_n(n), delta(begin, end), phi(beginImg, endImg)
137  {}
138 
139  virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const {
140  RefinementPtr ref(new SetImageRefinement<PERM>(m_n, delta.begin(), delta.end(), phi.begin(), phi.end()));
141  SetImageRefinement<PERM> *gref = static_cast<SetImageRefinement<PERM>*>(ref.get());
142  bool strictRefinement = gref->initializeAndApply(pi);
143  if (strictRefinement)
144  return std::make_pair(PartitionPtr(new Partition(pi)), ref);
145  else
146  return std::make_pair(PartitionPtr(), RefinementPtr());
147  }
148 private:
149  unsigned long m_n;
150  std::vector<unsigned long> delta;
151  std::vector<unsigned long> phi;
152 };
153 
155 template<class PERM,class MATRIX>
157 public:
158  typedef typename RefinementFamily<PERM>::RefinementPtr RefinementPtr;
159  typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr;
160 
162 
166  MatrixAutomorphismRefinementFamily(unsigned long n, const MATRIX& matrix) : m_n(n), m_matrix(matrix)
167  {}
168 
169  virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const {
170  RefinementPtr ref(new MatrixRefinement2<PERM,MATRIX>(m_n, m_matrix));
171  MatrixRefinement2<PERM,MATRIX> *gref = static_cast<MatrixRefinement2<PERM,MATRIX>*>(ref.get());
172  bool strictRefinement = gref->initializeAndApply(pi);
173  if (strictRefinement)
174  return std::make_pair(PartitionPtr(new Partition(pi)), ref);
175  else
176  return std::make_pair(PartitionPtr(), RefinementPtr());
177  }
178 private:
179  unsigned long m_n;
180  const MATRIX& m_matrix;
181 };
182 
183 }
184 }
185 
186 #endif // -- REFIMENET_FAMILY_H
bool initializeAndApply(Partition &pi)
applies (left-)refinement to partition and initializes refinement for future use in R-base ...
Definition: refinement.h:136
Definition: set_image_refinement.h:51
virtual ~RefinementFamily()
virtual destructor
Definition: refinement_family.h:55
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const
tries to initialize a suitable Refinement<PERM> for given partition
Definition: refinement_family.h:169
SetStabilizeRefinementFamily(unsigned long n, InputIterator begin, InputIterator end)
refinement family for set stabilization of given set
Definition: refinement_family.h:102
concrete -refinements for set stabilization
Definition: set_stabilize_refinement.h:50
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const =0
tries to initialize a suitable Refinement<PERM> for given partition
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const
tries to initialize a suitable Refinement<PERM> for given partition
Definition: refinement_family.h:139
partition
Definition: partition.h:48
MatrixAutomorphismRefinementFamily(unsigned long n, const MATRIX &matrix)
refinement family for symmetric matrix automorphisms
Definition: refinement_family.h:166
core data of a base and strong generating set (BSGS)
Definition: bsgs_core.h:42
SetImageRefinementFamily(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg)
refinement family for set stabilization of given set
Definition: refinement_family.h:135
-refinements for group membership
Definition: refinement_family.h:67
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const
tries to initialize a suitable Refinement<PERM> for given partition
Definition: refinement_family.h:105
-refinements for set stabilization
Definition: refinement_family.h:121
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const
tries to initialize a suitable Refinement<PERM> for given partition
Definition: refinement_family.h:75
concrete -refinements for group membership
Definition: group_refinement.h:44
concrete -refinement for symmetric matrix automorphisms
Definition: matrix_refinement2.h:49
-refinements for symmetric matrix automorphisms
Definition: refinement_family.h:156
represents a class of -refinements for a given problem
Definition: refinement_family.h:49
-refinements for set stabilization
Definition: refinement_family.h:90
GroupRefinementFamily(const BSGSCore< PERM, TRANS > &bsgs)
refinement family for group membership in given group
Definition: refinement_family.h:73
Definition: abstract_bsgs.h:49