permlib
0.2.6
Library for permutation computations
|
00001 // --------------------------------------------------------------------------- 00002 // 00003 // This file is part of PermLib. 00004 // 00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de> 00006 // All rights reserved. 00007 // 00008 // Redistribution and use in source and binary forms, with or without 00009 // modification, are permitted provided that the following conditions 00010 // are met: 00011 // 1. Redistributions of source code must retain the above copyright 00012 // notice, this list of conditions and the following disclaimer. 00013 // 2. Redistributions in binary form must reproduce the above copyright 00014 // notice, this list of conditions and the following disclaimer in the 00015 // documentation and/or other materials provided with the distribution. 00016 // 3. The name of the author may not be used to endorse or promote products 00017 // derived from this software without specific prior written permission. 00018 // 00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 // 00030 // --------------------------------------------------------------------------- 00031 00032 00033 #ifndef REFIMENET_FAMILY_H 00034 #define REFIMENET_FAMILY_H 00035 00036 #include <permlib/search/partition/group_refinement.h> 00037 #include <permlib/search/partition/set_stabilize_refinement.h> 00038 #include <permlib/search/partition/set_image_refinement.h> 00039 #include <permlib/search/partition/matrix_refinement2.h> 00040 00041 namespace permlib { 00042 namespace partition { 00043 00045 00048 template<class PERM> 00049 class RefinementFamily { 00050 public: 00051 typedef typename Refinement<PERM>::RefinementPtr RefinementPtr; 00052 typedef boost::shared_ptr<Partition> PartitionPtr; 00053 00055 virtual ~RefinementFamily() {} 00056 00058 00062 virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const = 0; 00063 }; 00064 00066 template<class PERM,class TRANS> 00067 class GroupRefinementFamily : public RefinementFamily<PERM> { 00068 public: 00069 typedef typename RefinementFamily<PERM>::RefinementPtr RefinementPtr; 00070 typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr; 00071 00073 explicit GroupRefinementFamily(const BSGSCore<PERM,TRANS>& bsgs) : m_bsgs(bsgs) {} 00074 00075 virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const { 00076 RefinementPtr ref(new GroupRefinement<PERM,TRANS>(m_bsgs)); 00077 GroupRefinement<PERM,TRANS> *gref = static_cast<GroupRefinement<PERM,TRANS>*>(ref.get()); 00078 bool strictRefinement = gref->initializeAndApply(pi); 00079 if (strictRefinement) 00080 return std::make_pair(PartitionPtr(new Partition(pi)), ref); 00081 else 00082 return std::make_pair(PartitionPtr(), RefinementPtr()); 00083 } 00084 private: 00085 const BSGSCore<PERM,TRANS>& m_bsgs; 00086 }; 00087 00089 template<class PERM> 00090 class SetStabilizeRefinementFamily : public RefinementFamily<PERM> { 00091 public: 00092 typedef typename RefinementFamily<PERM>::RefinementPtr RefinementPtr; 00093 typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr; 00094 00096 00101 template<class InputIterator> 00102 SetStabilizeRefinementFamily(unsigned long n, InputIterator begin, InputIterator end) : m_n(n), toStab(begin, end) 00103 {} 00104 00105 virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const { 00106 RefinementPtr ref(new SetStabilizeRefinement<PERM>(m_n, toStab.begin(), toStab.end())); 00107 SetStabilizeRefinement<PERM> *gref = static_cast<SetStabilizeRefinement<PERM>*>(ref.get()); 00108 bool strictRefinement = gref->initializeAndApply(pi); 00109 if (strictRefinement) 00110 return std::make_pair(PartitionPtr(new Partition(pi)), ref); 00111 else 00112 return std::make_pair(PartitionPtr(), RefinementPtr()); 00113 } 00114 private: 00115 unsigned long m_n; 00116 std::vector<unsigned long> toStab; 00117 }; 00118 00120 template<class PERM> 00121 class SetImageRefinementFamily : public RefinementFamily<PERM> { 00122 public: 00123 typedef typename RefinementFamily<PERM>::RefinementPtr RefinementPtr; 00124 typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr; 00125 00127 00134 template<class InputIterator> 00135 SetImageRefinementFamily(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg) 00136 : m_n(n), delta(begin, end), phi(beginImg, endImg) 00137 {} 00138 00139 virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const { 00140 RefinementPtr ref(new SetImageRefinement<PERM>(m_n, delta.begin(), delta.end(), phi.begin(), phi.end())); 00141 SetImageRefinement<PERM> *gref = static_cast<SetImageRefinement<PERM>*>(ref.get()); 00142 bool strictRefinement = gref->initializeAndApply(pi); 00143 if (strictRefinement) 00144 return std::make_pair(PartitionPtr(new Partition(pi)), ref); 00145 else 00146 return std::make_pair(PartitionPtr(), RefinementPtr()); 00147 } 00148 private: 00149 unsigned long m_n; 00150 std::vector<unsigned long> delta; 00151 std::vector<unsigned long> phi; 00152 }; 00153 00155 template<class PERM,class MATRIX> 00156 class MatrixAutomorphismRefinementFamily : public RefinementFamily<PERM> { 00157 public: 00158 typedef typename RefinementFamily<PERM>::RefinementPtr RefinementPtr; 00159 typedef typename RefinementFamily<PERM>::PartitionPtr PartitionPtr; 00160 00162 00166 MatrixAutomorphismRefinementFamily(unsigned long n, const MATRIX& matrix) : m_n(n), m_matrix(matrix) 00167 {} 00168 00169 virtual std::pair<PartitionPtr,RefinementPtr> apply(Partition& pi) const { 00170 RefinementPtr ref(new MatrixRefinement2<PERM,MATRIX>(m_n, m_matrix)); 00171 MatrixRefinement2<PERM,MATRIX> *gref = static_cast<MatrixRefinement2<PERM,MATRIX>*>(ref.get()); 00172 bool strictRefinement = gref->initializeAndApply(pi); 00173 if (strictRefinement) 00174 return std::make_pair(PartitionPtr(new Partition(pi)), ref); 00175 else 00176 return std::make_pair(PartitionPtr(), RefinementPtr()); 00177 } 00178 private: 00179 unsigned long m_n; 00180 const MATRIX& m_matrix; 00181 }; 00182 00183 } 00184 } 00185 00186 #endif // -- REFIMENET_FAMILY_H