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 MATRIXREFINEMENT1_H_ 00034 #define MATRIXREFINEMENT1_H_ 00035 00036 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 00037 #include <permlib/search/partition/refinement.h> 00038 00039 namespace permlib { 00040 namespace partition { 00041 00043 00047 template<class PERM,class MATRIX> 00048 class MatrixRefinement1 : public Refinement<PERM> { 00049 public: 00051 explicit MatrixRefinement1(unsigned long n, const MATRIX& matrix); 00052 00053 virtual unsigned int apply(Partition& pi) const; 00054 00055 virtual bool init(Partition& pi); 00056 00057 private: 00058 const MATRIX& m_matrix; 00059 std::vector<std::list<unsigned long> > m_diagonalPartition; 00060 }; 00061 00062 template<class PERM,class MATRIX> 00063 MatrixRefinement1<PERM,MATRIX>::MatrixRefinement1(unsigned long n, const MATRIX& matrix) 00064 : Refinement<PERM>(n, Default), m_matrix(matrix) 00065 { 00066 } 00067 00068 template<class PERM,class MATRIX> 00069 unsigned int MatrixRefinement1<PERM,MATRIX>::apply(Partition& pi) const { 00070 BOOST_ASSERT( this->initialized() ); 00071 00072 unsigned int ret = 0; 00073 std::list<int>::const_iterator cellPairIt = Refinement<PERM>::m_cellPairs.begin(); 00074 while (cellPairIt != Refinement<PERM>::m_cellPairs.end()) { 00075 unsigned long cell = *cellPairIt; 00076 ++cellPairIt; 00077 while (cellPairIt != Refinement<PERM>::m_cellPairs.end() && *cellPairIt != -1) { 00078 unsigned long diagIndex = *cellPairIt; 00079 if (pi.intersect(m_diagonalPartition[diagIndex].begin(), m_diagonalPartition[diagIndex].end(), cell)) 00080 ++ret; 00081 ++cellPairIt; 00082 } 00083 ++cellPairIt; 00084 } 00085 return ret; 00086 } 00087 00088 00089 template<class PERM,class MATRIX> 00090 bool MatrixRefinement1<PERM,MATRIX>::init(Partition& pi) { 00091 m_diagonalPartition.resize(m_matrix.k()); 00092 for (unsigned long i = 0; i < m_matrix.dimension(); ++i) { 00093 m_diagonalPartition[m_matrix.at(i,i)].push_back(i); 00094 } 00095 00096 bool foundIntersection = false; 00097 for (unsigned int c = 0; c < pi.cells(); ++c) { 00098 Refinement<PERM>::m_cellPairs.push_back(c); 00099 for (unsigned long i = 0; i < m_diagonalPartition.size(); ++i) { 00100 if (pi.intersect(m_diagonalPartition[i].begin(), m_diagonalPartition[i].end(), c)) { 00101 Refinement<PERM>::m_cellPairs.push_back(i); 00102 foundIntersection = true; 00103 } 00104 } 00105 Refinement<PERM>::m_cellPairs.push_back(-1); 00106 } 00107 if (foundIntersection) { 00108 typename Refinement<PERM>::RefinementPtr ref(new MatrixRefinement1<PERM,MATRIX>(*this)); 00109 Refinement<PERM>::m_backtrackRefinements.push_back(ref); 00110 return true; 00111 } 00112 return false; 00113 } 00114 00115 00116 } 00117 } 00118 00119 #endif // -- MATRIXREFINEMENT1_H_