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