1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2012 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 #include <boost/shared_ptr.hpp>
33 #include <boost/scoped_ptr.hpp>
34 #include <boost/iterator/counting_iterator.hpp>
35
36 #include <algorithm>
37
38 #include <permlib/abstract_permutation_group.h>
39 #include <permlib/abstract_bsgs_helpers.h>
40
41 #include <permlib/change/random_base_transpose.h>
42 #include <permlib/change/conjugating_base_change.h>
43 #include <permlib/search/classic/set_stabilizer_search.h>
44 #include <permlib/search/orbit_lex_min_search.h>
45
46 #ifndef ABSTRACT_BSGS_H_
47 #define ABSTRACT_BSGS_H_
48
49 namespace permlib {
50
51 /// A high level interface implementing a group represented by a BSGS data structure
52 template<typename TRANS>
53 class AbstractBSGS : public AbstractPermutationGroup {
54 public:
55 /// typedef for the BSGS type associated with this group
56 typedef BSGS<typename TRANS::PERMtype, TRANS> PermutationGroup;
57 /// constructor
58 /**
59 * @param bsgs_ the BSGS data structure that represents this group
60 * @param computeSupport if true, the support of the group is computed to accelerate stabilizer and lexMin computations
61 */
62 AbstractBSGS(const boost::shared_ptr<PermutationGroup>& bsgs_, bool computeSupport = true);
63
64 virtual AbstractPermutationGroup* setStabilizer(const std::vector<dom_int>& s) const;
65 virtual OrbitList* orbits() const;
66 virtual OrbitList* orbits(const std::vector<dom_int>& s) const;
67 virtual bool isLexMinSet(const std::vector<dom_int>& setIndices, const std::vector<dom_int>& rankIndices) const;
type()68 virtual AbstractGroupType type() const { return AGT_BSGS; }
69
70 /// strong generating set of this permutation group
71 std::list<typename TRANS::PERMtype::ptr> generators() const;
72
73 /// BSGS data structure for this permutation group
bsgs()74 const boost::shared_ptr<PermutationGroup> bsgs() const { return m_bsgs; }
75 protected:
76 virtual void transversalSizes(std::vector<unsigned long>& sizes) const;
77
78 template<typename Iterator>
79 OrbitList* orbits(Iterator begin, Iterator end) const;
80
81 /// returns a strategy to decide whether the action of this group is trivial on /s/
82 helpers::BaseSupportRestriction* supportRestriction(const std::vector<dom_int>& s) const;
83 private:
84 const boost::shared_ptr<PermutationGroup> m_bsgs;
85 boost::shared_ptr<std::set<dom_int> > m_support;
86 };
87
88
89 template<typename TRANS>
AbstractBSGS(const boost::shared_ptr<PermutationGroup> & bsgs_,bool computeSupport)90 AbstractBSGS<TRANS>::AbstractBSGS(const boost::shared_ptr<PermutationGroup>& bsgs_, bool computeSupport)
91 : m_bsgs(bsgs_)
92 {
93 if ( ! computeSupport )
94 return;
95
96 m_support.reset( new std::set<dom_int>() );
97 BOOST_FOREACH(const typename TRANS::PERMtype::ptr& p, m_bsgs->S) {
98 for (dom_int i = 0; i < m_bsgs->n; ++i) {
99 if (p->at(i) != i)
100 m_support->insert(i);
101 }
102 }
103 }
104
105 template <class TRANS>
transversalSizes(std::vector<unsigned long> & sizes)106 void AbstractBSGS<TRANS>::transversalSizes(std::vector<unsigned long>& sizes) const {
107 sizes.clear();
108 sizes.reserve(m_bsgs->U.size());
109 BOOST_FOREACH(const TRANS &Ui, m_bsgs->U) {
110 sizes.push_back(Ui.size());
111 }
112 }
113
114 template <class TRANS>
setStabilizer(const std::vector<dom_int> & s)115 AbstractPermutationGroup* AbstractBSGS<TRANS>::setStabilizer(const std::vector<dom_int>& s) const {
116 if (s.empty())
117 return new AbstractBSGS<TRANS>(*this);
118
119 boost::scoped_ptr<helpers::BaseSupportRestriction> supRestriction( supportRestriction(s) );
120 if ( supRestriction->canBeIgnored() )
121 return new AbstractBSGS<TRANS>(*this);
122 const std::vector<dom_int>* setToStabilize = supRestriction->set();
123 BOOST_ASSERT( setToStabilize );
124
125 typedef typename TRANS::PERMtype PERM;
126 PermutationGroup copy(*m_bsgs);
127 // change the base so that is prefixed by the set
128 ConjugatingBaseChange<PERM, TRANS,
129 RandomBaseTranspose<PERM, TRANS> > baseChange(copy);
130 baseChange.change(copy, setToStabilize->begin(), setToStabilize->end());
131
132 // prepare search without DCM pruning
133 classic::SetStabilizerSearch<BSGS<PERM, TRANS>, TRANS> backtrackSearch(copy, 0);
134 backtrackSearch.construct(setToStabilize->begin(), setToStabilize->end());
135
136 // start the search
137 boost::shared_ptr<PermutationGroup> stabilizer(new PermutationGroup(copy.n));
138 backtrackSearch.search(*stabilizer);
139 return new AbstractBSGS<TRANS>(stabilizer, bool(m_support));
140 }
141
142 template <class TRANS>
orbits()143 AbstractPermutationGroup::OrbitList* AbstractBSGS<TRANS>::orbits() const {
144 return this->orbits(boost::counting_iterator<dom_int>(0), boost::counting_iterator<dom_int>(m_bsgs->n));
145 }
146
147 template <class TRANS>
orbits(const std::vector<dom_int> & s)148 AbstractPermutationGroup::OrbitList* AbstractBSGS<TRANS>::orbits(const std::vector<dom_int>& s) const {
149 return this->orbits(s.begin(), s.end());
150 }
151
152 template <class TRANS>
153 template<typename Iterator>
orbits(Iterator begin,Iterator end)154 AbstractPermutationGroup::OrbitList* AbstractBSGS<TRANS>::orbits(Iterator begin, Iterator end) const {
155 OrbitList* retList = new OrbitList();
156
157 for (Iterator it = begin; it != end; ++it) {
158 const dom_int& alpha = *it;
159 bool knownElement = false;
160 BOOST_FOREACH(const std::set<dom_int>& orb, *retList) {
161 if (orb.find(alpha) != orb.end()) {
162 knownElement = true;
163 break;
164 }
165 }
166
167 if (knownElement)
168 continue;
169
170 typedef typename TRANS::PERMtype PERM;
171 OrbitSet<PERM,dom_int> orbit;
172 orbit.orbit(alpha, m_bsgs->S, typename Transversal<PERM>::TrivialAction());
173 retList->push_back(std::set<dom_int>(orbit.begin(), orbit.end()));
174 }
175
176 return retList;
177 }
178
179 template <class TRANS>
isLexMinSet(const std::vector<dom_int> & setIndices,const std::vector<dom_int> & rankIndices)180 bool AbstractBSGS<TRANS>::isLexMinSet(const std::vector<dom_int>& setIndices, const std::vector<dom_int>& rankIndices) const {
181 if (setIndices.empty())
182 return true;
183
184 boost::scoped_ptr<helpers::BaseSupportRestriction> supRestriction( supportRestriction(setIndices) );
185 if ( supRestriction->canBeIgnored() )
186 return true;
187 const std::vector<dom_int>* setToLexMin = supRestriction->set();
188 BOOST_ASSERT( setToLexMin );
189
190 typedef typename TRANS::PERMtype PERM;
191 const unsigned int n = m_bsgs->n;
192
193 // compute a permutation that we can use for conjugation
194 typename PERM::perm conjugatingPerm(n);
195
196 // rank indices shall be mapped to 1,2,3,4,5,...
197 unsigned int i = 0;
198 dset rankSet(n);
199 for (std::vector<dom_int>::const_iterator it = rankIndices.begin(); it != rankIndices.end(); ++it)
200 {
201 conjugatingPerm[*it] = i;
202 rankSet[*it] = 1;
203 ++i;
204 }
205
206 // fill up the rest arbitrarily so that we get a proper permutation
207 unsigned int v = 0;
208 for ( ; i < n; ++i )
209 {
210 while (rankSet[v])
211 ++v;
212 conjugatingPerm[v] = i;
213 ++v;
214 }
215
216 PERM c(conjugatingPerm);
217 PermutationGroup conjugatedBSGS(*m_bsgs);
218 conjugatedBSGS.conjugate(c);
219
220 dset rankedTestSet(n);
221 for (std::vector<dom_int>::const_iterator it = setToLexMin->begin(); it != setToLexMin->end(); ++it)
222 {
223 rankedTestSet[c / *it] = 1;
224 }
225
226 OrbitLexMinSearch<PermutationGroup> orbLexMin(conjugatedBSGS, true);
227 const bool t = ( orbLexMin.lexMin(rankedTestSet) == rankedTestSet );
228 return t;
229 }
230
231 template <class TRANS>
generators()232 std::list<typename TRANS::PERMtype::ptr> AbstractBSGS<TRANS>::generators() const {
233 return m_bsgs->S;
234 }
235
236 template <class TRANS>
supportRestriction(const std::vector<dom_int> & s)237 helpers::BaseSupportRestriction* AbstractBSGS<TRANS>::supportRestriction(const std::vector<dom_int>& s) const {
238 BOOST_ASSERT( m_bsgs );
239 if ( ! m_support )
240 return new helpers::BaseSupportRestriction(m_support, s);
241
242 // don't use full support restriction if the group base is small
243 if (m_bsgs->B.size() <= 10 )
244 return new helpers::ReducedSupportRestriction(m_support, s);
245
246 return new helpers::FullSupportRestriction(m_support, s);
247 }
248
249 } // end NS permlib
250
251 #endif
252