permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
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
41namespace permlib {
42namespace partition {
43
45
48template<class PERM>
50public:
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
66template<class PERM,class TRANS>
68public:
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 }
84private:
85 const BSGSCore<PERM,TRANS>& m_bsgs;
86};
87
89template<class PERM>
91public:
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 }
114private:
115 unsigned long m_n;
116 std::vector<unsigned long> toStab;
117};
118
120template<class PERM>
122public:
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 }
148private:
149 unsigned long m_n;
150 std::vector<unsigned long> delta;
151 std::vector<unsigned long> phi;
152};
153
155template<class PERM,class MATRIX>
157public:
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 }
178private:
179 unsigned long m_n;
180 const MATRIX& m_matrix;
181};
182
183}
184}
185
186#endif // -- REFIMENET_FAMILY_H
GroupRefinementFamily(const BSGSCore< PERM, TRANS > &bsgs)
refinement family for group membership in given group
Definition refinement_family.h:73
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
MatrixAutomorphismRefinementFamily(unsigned long n, const MATRIX &matrix)
refinement family for symmetric matrix automorphisms
Definition refinement_family.h:166
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const
tries to initialize a suitable Refinement<PERM> for given partition
Definition refinement_family.h:169
concrete -refinement for symmetric matrix automorphisms
Definition matrix_refinement2.h:49
partition
Definition partition.h:48
represents a class of -refinements for a given problem
Definition refinement_family.h:49
virtual ~RefinementFamily()
virtual destructor
Definition refinement_family.h:55
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const =0
tries to initialize a suitable Refinement<PERM> for given partition
bool initializeAndApply(Partition &pi)
applies (left-)refinement to partition and initializes refinement for future use in R-base
Definition refinement.h:136
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const
tries to initialize a suitable Refinement<PERM> for given partition
Definition refinement_family.h:139
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
Definition set_image_refinement.h:51
virtual std::pair< PartitionPtr, RefinementPtr > apply(Partition &pi) const
tries to initialize a suitable Refinement<PERM> for given partition
Definition refinement_family.h:105
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
core data of a base and strong generating set (BSGS)
Definition bsgs_core.h:42