permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/search/partition/refinement_family.h
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