permlib  0.2.9
Library for permutation computations
set_image_refinement.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31 
32 
33 #ifndef SETIMAGEREFINEMENT_H_
34 #define SETIMAGEREFINEMENT_H_
35 
36 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
37 
38 #include <permlib/search/partition/partition.h>
39 #include <permlib/search/partition/refinement.h>
40 
41 #include <algorithm>
42 #include <boost/dynamic_bitset.hpp>
43 #include <boost/foreach.hpp>
44 
45 namespace permlib {
46 namespace partition {
47 
50 template<class PERM>
51 class SetImageRefinement : public Refinement<PERM> {
52 public:
54 
61  template<class InputIterator>
62  SetImageRefinement(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg);
63 
64  virtual unsigned int apply(Partition& pi) const;
65  virtual unsigned int apply2(Partition& pi, const PERM& t) const;
66 
67  virtual bool init(Partition& pi);
68 private:
69  std::vector<unsigned long> delta;
70  std::vector<unsigned long> gamma;
71 };
72 
73 template<class PERM>
74 template<class InputIterator>
75 SetImageRefinement<PERM>::SetImageRefinement(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg)
76  : Refinement<PERM>(n, Default), delta(begin, end), gamma(beginImg, endImg)
77 {
78  std::sort(delta.begin(), delta.end());
79  std::sort(gamma.begin(), gamma.end());
80 }
81 
82 template<class PERM>
83 unsigned int SetImageRefinement<PERM>::apply(Partition& pi) const {
84  BOOST_ASSERT( this->initialized() );
85  unsigned int ret = 0;
86  BOOST_FOREACH(unsigned int cell, Refinement<PERM>::m_cellPairs) {
87  PERMLIB_DEBUG(std::cout << "apply set image1 " << cell << std::endl;)
88  if (pi.intersect(delta.begin(), delta.end(), cell))
89  ++ret;
90  }
91  return ret;
92 }
93 
94 template<class PERM>
95 unsigned int SetImageRefinement<PERM>::apply2(Partition& pi, const PERM& t) const {
96  BOOST_ASSERT( this->initialized() );
97  unsigned int ret = 0;
98  BOOST_FOREACH(unsigned int cell, Refinement<PERM>::m_cellPairs) {
99  PERMLIB_DEBUG(std::cout << "apply set image2 " << cell << std::endl;)
100  if (pi.intersect(gamma.begin(), gamma.end(), cell))
101  ++ret;
102  }
103  return ret;
104 }
105 
106 template<class PERM>
108  for (unsigned int c = 0; c < pi.cells(); ++c) {
109  if (pi.intersect(delta.begin(), delta.end(), c))
110  Refinement<PERM>::m_cellPairs.push_back(c);
111  }
112  if (!Refinement<PERM>::m_cellPairs.empty()) {
113  typename Refinement<PERM>::RefinementPtr ref(new SetImageRefinement<PERM>(*this));
115  return true;
116  }
117  return false;
118 }
119 
120 }
121 }
122 
123 #endif // -- SETIMAGEREFINEMENT_H_
Definition: set_image_refinement.h:51
virtual unsigned int apply2(Partition &pi, const PERM &t) const
applies (right-)refinement to pi which is the image of the original partition this refinement was ini...
Definition: set_image_refinement.h:95
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
virtual unsigned int apply(Partition &pi) const
applies (left-)refinement to pi which is the original partition this refinement was initialized to ...
Definition: set_image_refinement.h:83
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
SetImageRefinement(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg)
constructor
Definition: set_image_refinement.h:75
virtual bool init(Partition &pi)
initializes refinement
Definition: set_image_refinement.h:107
Definition: abstract_bsgs.h:49