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