33 #ifndef MATRIXREFINEMENT2_H_ 34 #define MATRIXREFINEMENT2_H_ 36 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 37 #include <permlib/search/partition/refinement.h> 48 template<
class PERM,
class MATRIX>
59 const MATRIX& m_matrix;
64 Fingerprint(
unsigned long k) : m_fingerprint(k) {}
67 bool operator<(
const Fingerprint& f)
const {
68 BOOST_ASSERT(f.m_fingerprint.size() == m_fingerprint.size());
69 for (
unsigned int i=0; i<m_fingerprint.size(); ++i) {
70 if (m_fingerprint[i] < f.m_fingerprint[i])
72 if (m_fingerprint[i] > f.m_fingerprint[i])
77 bool operator==(
const Fingerprint& f)
const {
78 BOOST_ASSERT(f.m_fingerprint.size() == m_fingerprint.size());
79 for (
unsigned int i=0; i<m_fingerprint.size(); ++i) {
80 if (m_fingerprint[i] != f.m_fingerprint[i])
85 unsigned long& operator[](
unsigned long i) {
86 BOOST_ASSERT(i < m_fingerprint.size());
87 return m_fingerprint[i];
89 const unsigned long& operator[](
unsigned long i)
const {
90 BOOST_ASSERT(i < m_fingerprint.size());
91 return m_fingerprint[i];
94 std::vector<unsigned long> m_fingerprint;
97 unsigned int splitCell(
Partition& pi,
unsigned long i)
const;
98 void computeFingerprint(
const Partition& pi,
unsigned long i,
unsigned long j, std::map<Fingerprint,std::list<unsigned long> >& map)
const;
101 template<
class PERM,
class MATRIX>
103 :
Refinement<PERM>(n, Default), m_matrix(matrix)
107 template<
class PERM,
class MATRIX>
109 BOOST_ASSERT( this->initialized() );
111 unsigned int ret = 0;
114 unsigned long i = *cellPairIt++;
115 ret += splitCell(pi, static_cast<unsigned long>(i));
121 template<
class PERM,
class MATRIX>
123 for (
unsigned long i = 0; i < pi.
cells(); ++i) {
124 if (splitCell(pi, i))
136 template<
class PERM,
class MATRIX>
138 unsigned long ret = 0;
141 for (
unsigned long j = 0; j < pi.
cells(); ++j) {
142 std::map<Fingerprint,std::list<unsigned long> > map;
143 computeFingerprint(pi, i, j, map);
144 if (map.size() > 1) {
145 PERMLIB_DEBUG(std::cout <<
"split " << i <<
" because of " << j <<
" in " << pi << std::endl;)
146 typename std::map<Fingerprint,std::list<unsigned long> >::const_iterator fit;
147 for (fit = map.begin(); fit != map.end(); ++fit) {
148 std::pair<Fingerprint, std::list<unsigned long> > splitCellPair = *fit;
159 if (pi.
intersect(splitCellPair.second.begin(), splitCellPair.second.end(), i)) {
169 template<
class PERM,
class MATRIX>
170 void MatrixRefinement2<PERM,MATRIX>::computeFingerprint(
const Partition& pi,
unsigned long i,
unsigned long j, std::map<Fingerprint,std::list<unsigned long> >& map)
const {
171 for (Partition::CellIt cellI = pi.cellBegin(i); cellI != pi.cellEnd(i); ++cellI) {
172 Fingerprint f(m_matrix.k());
173 for (Partition::CellIt cellJ = pi.cellBegin(j); cellJ != pi.cellEnd(j); ++cellJ) {
174 ++f[m_matrix.at(*cellI, *cellJ)];
176 std::pair<typename std::map<Fingerprint,std::list<unsigned long> >::iterator,
bool> p =
177 map.insert(std::pair<Fingerprint, std::list<unsigned long> >(f, std::list<unsigned long>()));
178 std::list<unsigned long>& l = p.first->second;
186 #endif // -- MATRIXREFINEMENT2_H_ virtual bool init(Partition &pi)
initializes refinement
Definition: matrix_refinement2.h:122
base class for a -refinement which is used in an R-base and bound to an initial partition ...
Definition: refinement.h:53
partition
Definition: partition.h:48
unsigned long cells() const
number of cells in this partition
Definition: partition.h:157
bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j)
intersects the j-th cell of this partition with a given set
Definition: partition.h:186
MatrixRefinement2(unsigned long n, const MATRIX &matrix)
constructor
Definition: matrix_refinement2.h:102
virtual unsigned int apply(Partition &pi) const
applies (left-)refinement to pi which is the original partition this refinement was initialized to ...
Definition: matrix_refinement2.h:108
concrete -refinement for symmetric matrix automorphisms
Definition: matrix_refinement2.h:49
Definition: abstract_bsgs.h:49
unsigned long cellSize(unsigned int c) const
size of the c-th cell
Definition: partition.h:170