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 MATRIXREFINEMENT2_H_ 00034 #define MATRIXREFINEMENT2_H_ 00035 00036 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 00037 #include <permlib/search/partition/refinement.h> 00038 00039 #include <map> 00040 00041 namespace permlib { 00042 namespace partition { 00043 00045 00048 template<class PERM,class MATRIX> 00049 class MatrixRefinement2 : public Refinement<PERM> { 00050 public: 00052 explicit MatrixRefinement2(unsigned long n, const MATRIX& matrix); 00053 00054 virtual unsigned int apply(Partition& pi) const; 00055 00056 virtual bool init(Partition& pi); 00057 00058 private: 00059 const MATRIX& m_matrix; 00060 00062 class Fingerprint { 00063 public: 00064 Fingerprint(unsigned long k) : m_fingerprint(k) {} 00065 00067 bool operator<(const Fingerprint& f) const { 00068 BOOST_ASSERT(f.m_fingerprint.size() == m_fingerprint.size()); 00069 for (unsigned int i=0; i<m_fingerprint.size(); ++i) { 00070 if (m_fingerprint[i] < f.m_fingerprint[i]) 00071 return true; 00072 if (m_fingerprint[i] > f.m_fingerprint[i]) 00073 return false; 00074 } 00075 return false; 00076 } 00077 bool operator==(const Fingerprint& f) const { 00078 BOOST_ASSERT(f.m_fingerprint.size() == m_fingerprint.size()); 00079 for (unsigned int i=0; i<m_fingerprint.size(); ++i) { 00080 if (m_fingerprint[i] != f.m_fingerprint[i]) 00081 return false; 00082 } 00083 return true; 00084 } 00085 unsigned long& operator[](unsigned long i) { 00086 BOOST_ASSERT(i < m_fingerprint.size()); 00087 return m_fingerprint[i]; 00088 } 00089 const unsigned long& operator[](unsigned long i) const { 00090 BOOST_ASSERT(i < m_fingerprint.size()); 00091 return m_fingerprint[i]; 00092 } 00093 private: 00094 std::vector<unsigned long> m_fingerprint; 00095 }; 00096 00097 unsigned int splitCell(Partition& pi, unsigned long i) const; 00098 void computeFingerprint(const Partition& pi, unsigned long i, unsigned long j, std::map<Fingerprint,std::list<unsigned long> >& map) const; 00099 }; 00100 00101 template<class PERM,class MATRIX> 00102 MatrixRefinement2<PERM,MATRIX>::MatrixRefinement2(unsigned long n, const MATRIX& matrix) 00103 : Refinement<PERM>(n, Default), m_matrix(matrix) 00104 { 00105 } 00106 00107 template<class PERM,class MATRIX> 00108 unsigned int MatrixRefinement2<PERM,MATRIX>::apply(Partition& pi) const { 00109 BOOST_ASSERT( this->initialized() ); 00110 00111 unsigned int ret = 0; 00112 std::list<int>::const_iterator cellPairIt = Refinement<PERM>::m_cellPairs.begin(); 00113 while (cellPairIt != Refinement<PERM>::m_cellPairs.end()) { 00114 unsigned long i = *cellPairIt++; 00115 ret += splitCell(pi, static_cast<unsigned long>(i)); 00116 } 00117 return ret; 00118 } 00119 00120 00121 template<class PERM,class MATRIX> 00122 bool MatrixRefinement2<PERM,MATRIX>::init(Partition& pi) { 00123 for (unsigned long i = 0; i < pi.cells(); ++i) { 00124 if (splitCell(pi, i)) 00125 Refinement<PERM>::m_cellPairs.push_back(i); 00126 } 00127 00128 if (!Refinement<PERM>::m_cellPairs.empty()) { 00129 typename Refinement<PERM>::RefinementPtr ref(new MatrixRefinement2<PERM,MATRIX>(*this)); 00130 Refinement<PERM>::m_backtrackRefinements.push_back(ref); 00131 return true; 00132 } 00133 return false; 00134 } 00135 00136 template<class PERM,class MATRIX> 00137 unsigned int MatrixRefinement2<PERM,MATRIX>::splitCell(Partition& pi, unsigned long i) const { 00138 unsigned long ret = 0; 00139 if (pi.cellSize(i) < 2) 00140 return ret; 00141 for (unsigned long j = 0; j < pi.cells(); ++j) { 00142 std::map<Fingerprint,std::list<unsigned long> > map; 00143 computeFingerprint(pi, i, j, map); 00144 if (map.size() > 1) { 00145 PERMLIB_DEBUG(std::cout << "split " << i << " because of " << j << " in " << pi << std::endl;) 00146 typename std::map<Fingerprint,std::list<unsigned long> >::const_iterator fit; 00147 for (fit = map.begin(); fit != map.end(); ++fit) { 00148 std::pair<Fingerprint, std::list<unsigned long> > splitCellPair = *fit; 00149 /*std::cout << "FOO "; 00150 BOOST_FOREACH(unsigned long a, splitCellPair.second) { 00151 std::cout << (a+1) << " "; 00152 } 00153 std::cout << std::endl; 00154 std::cout << "GOO "; 00155 BOOST_FOREACH(unsigned long a, splitCellPair.first.m_fingerprint) { 00156 std::cout << (a) << " "; 00157 } 00158 std::cout << std::endl;*/ 00159 if (pi.intersect(splitCellPair.second.begin(), splitCellPair.second.end(), i)) { 00160 ++ret; 00161 } 00162 } 00163 break; 00164 } 00165 } 00166 return ret; 00167 } 00168 00169 template<class PERM,class MATRIX> 00170 void MatrixRefinement2<PERM,MATRIX>::computeFingerprint(const Partition& pi, unsigned long i, unsigned long j, std::map<Fingerprint,std::list<unsigned long> >& map) const { 00171 for (Partition::CellIt cellI = pi.cellBegin(i); cellI != pi.cellEnd(i); ++cellI) { 00172 Fingerprint f(m_matrix.k()); 00173 for (Partition::CellIt cellJ = pi.cellBegin(j); cellJ != pi.cellEnd(j); ++cellJ) { 00174 ++f[m_matrix.at(*cellI, *cellJ)]; 00175 } 00176 std::pair<typename std::map<Fingerprint,std::list<unsigned long> >::iterator, bool> p = 00177 map.insert(std::pair<Fingerprint, std::list<unsigned long> >(f, std::list<unsigned long>())); 00178 std::list<unsigned long>& l = p.first->second; 00179 l.push_back(*cellI); 00180 } 00181 } 00182 00183 } 00184 } 00185 00186 #endif // -- MATRIXREFINEMENT2_H_