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 #define BOOST_TEST_DYN_LINK
34 #define BOOST_TEST_MODULE BSGS construction and change test
35 #include <boost/test/unit_test.hpp>
36
37 #include <iostream>
38 #include <fstream>
39 #include <cmath>
40
41 #include <permlib/permutation.h>
42 #include <permlib/permutationword.h>
43 #include <permlib/bsgs.h>
44
45 #include <permlib/transversal/schreier_tree_transversal.h>
46 #include <permlib/transversal/explicit_transversal.h>
47 #include <permlib/construct/schreier_sims_construction.h>
48
49 #include <permlib/construct/cyclic_group_construction.h>
50
51 #include <permlib/change/simple_base_change.h>
52 #include <permlib/change/conjugating_base_change.h>
53 #include <permlib/change/deterministic_base_transpose.h>
54 #include <permlib/change/random_base_transpose.h>
55
56 #include "test-common.h"
57 #include <permlib/generator/bsgs_random_generator.h>
58
59 using namespace permlib;
60 using namespace permlib::test;
61
62 template<class CONSTRUCTOR>
checkGroup(const GroupInformation & info)63 void checkGroup(const GroupInformation &info) {
64 typedef typename CONSTRUCTOR::PERMtype PERM;
65 typedef typename CONSTRUCTOR::TRANStype TRANS;
66
67 BSGS<PERM,TRANS> bsgs = CONSTRUCTOR()(info);
68 BOOST_CHECK_EQUAL( bsgs.n, info.n );
69 BOOST_CHECK_EQUAL( bsgs.order(), info.order );
70
71 unsigned int transversalProduct = 1;
72 BOOST_FOREACH(const TRANS &U, bsgs.U) {
73 transversalProduct *= U.size();
74 }
75 BOOST_CHECK_EQUAL( transversalProduct, bsgs.order() );
76
77 for (unsigned int i = 0; i < bsgs.n; ++i) {
78 BSGS<PERM,TRANS> bsgs2(bsgs);
79 bsgs2.insertRedundantBasePoint(i);
80
81 transversalProduct = 1;
82 BOOST_FOREACH(const TRANS &U, bsgs2.U) {
83 transversalProduct *= U.size();
84 }
85 BOOST_CHECK_EQUAL( transversalProduct, bsgs2.order() );
86 BOOST_CHECK_EQUAL( bsgs.order(), bsgs2.order() );
87 }
88 }
89
checkGroup(const GroupInformation & info)90 void checkGroup(const GroupInformation &info) {
91 checkGroup<ConstructDeterministic1<Permutation, ExplicitTransversal<Permutation> > >(info);
92 checkGroup<ConstructDeterministic1<Permutation, SchreierTreeTransversal<Permutation> > >(info);
93 checkGroup<ConstructDeterministic1<PermutationWord, SchreierTreeTransversal<PermutationWord> > >(info);
94
95 checkGroup<ConstructDeterministic2<Permutation, ExplicitTransversal<Permutation> > >(info);
96 checkGroup<ConstructDeterministic2<Permutation, SchreierTreeTransversal<Permutation> > >(info);
97
98 checkGroup<ConstructRandomized<Permutation, ExplicitTransversal<Permutation> > >(info);
99 checkGroup<ConstructRandomized<Permutation, SchreierTreeTransversal<Permutation> > >(info);
100 }
101
102
103 template<class PERM,class TRANS,class TRANSPOSE>
checkTranspose(const GroupInformation & info,const BSGS<PERM,TRANS> & bsgs)104 void checkTranspose(const GroupInformation &info, const BSGS<PERM,TRANS> &bsgs) {
105 const unsigned int m = bsgs.B.size();
106 for (unsigned int i=0; i<m-1; ++i) {
107 BSGS<PERM,TRANS> bsgs_copy(bsgs);
108 TRANSPOSE bt;
109 bt.transpose(bsgs_copy, i);
110
111 BOOST_REQUIRE_EQUAL( bsgs_copy.B.size(), bsgs.B.size() );
112 BOOST_CHECK_EQUAL( bsgs_copy.order(), bsgs.order() );
113 unsigned int transversalProduct = 1;
114 BOOST_FOREACH(const TRANS &U, bsgs_copy.U) {
115 transversalProduct *= U.size();
116 }
117 BOOST_CHECK_EQUAL( transversalProduct, bsgs.order() );
118
119 BOOST_CHECK_EQUAL( bsgs_copy.B[i], bsgs.B[i+1] );
120 BOOST_CHECK_EQUAL( bsgs_copy.B[i+1], bsgs.B[i] );
121 for (unsigned int j=0; j<m; ++j) {
122 if (j == i || j == i+1)
123 continue;
124 BOOST_CHECK_EQUAL( bsgs_copy.B[j], bsgs.B[j] );
125 }
126 }
127 }
128
129 template<class PERM,class TRANS>
checkTranspose(const GroupInformation & info)130 void checkTranspose(const GroupInformation &info) {
131 BSGS<PERM,TRANS> bsgs = construct<PERM,TRANS>(info);
132
133 checkTranspose<PERM,TRANS,DeterministicBaseTranspose<PERM,TRANS> >(info, bsgs);
134 checkTranspose<PERM,TRANS,RandomBaseTranspose<PERM,TRANS> >(info, bsgs);
135 }
136
137 template<class PERM,class TRANS,class BASECHANGE>
checkChange(const GroupInformation & info)138 void checkChange(const GroupInformation &info) {
139 BSGS<PERM,TRANS> bsgs = construct<PERM,TRANS>(info);
140 BSGS<PERM,TRANS> bsgs_copy(bsgs);
141
142 BASECHANGE bc(bsgs);
143 std::vector<unsigned long> newBase(5);
144 newBase[0] = 0;
145 newBase[1] = 2;
146 newBase[2] = 4;
147 newBase[3] = 6;
148 newBase[4] = 8;
149 bc.change(bsgs_copy, newBase.begin(), newBase.end());
150
151 BOOST_REQUIRE_GE( bsgs_copy.B.size(), newBase.size() );
152 BOOST_CHECK_EQUAL( bsgs_copy.order(), bsgs.order() );
153 unsigned int transversalProduct = 1;
154 BOOST_FOREACH(const TRANS &U, bsgs_copy.U) {
155 transversalProduct *= U.size();
156 }
157 BOOST_CHECK_EQUAL( transversalProduct, bsgs.order() );
158
159 for (unsigned int i=0; i<newBase.size(); ++i)
160 BOOST_CHECK_EQUAL( newBase[i], bsgs_copy.B[i] );
161 }
162
BOOST_AUTO_TEST_CASE(construction_test33)163 BOOST_AUTO_TEST_CASE( construction_test33 )
164 {
165 checkGroup(info_test33);
166 }
167
BOOST_AUTO_TEST_CASE(construction_trivial)168 BOOST_AUTO_TEST_CASE( construction_trivial )
169 {
170 checkGroup(info_trivial);
171 }
172
BOOST_AUTO_TEST_CASE(construction_test1997)173 BOOST_AUTO_TEST_CASE( construction_test1997 )
174 {
175 checkGroup(info_1997);
176 }
177
BOOST_AUTO_TEST_CASE(construction_psu4_3)178 BOOST_AUTO_TEST_CASE( construction_psu4_3 )
179 {
180 checkGroup(info_psu4_3);
181 }
182
BOOST_AUTO_TEST_CASE(construction_S6)183 BOOST_AUTO_TEST_CASE( construction_S6 )
184 {
185 checkGroup(info_S6);
186 }
187
BOOST_AUTO_TEST_CASE(transpose_test1997)188 BOOST_AUTO_TEST_CASE( transpose_test1997 )
189 {
190 typedef Permutation PERM;
191 typedef ExplicitTransversal<PERM> TRANS;
192 checkTranspose<PERM,TRANS>(info_1997);
193 }
194
BOOST_AUTO_TEST_CASE(transpose_psu4_3)195 BOOST_AUTO_TEST_CASE( transpose_psu4_3 )
196 {
197 typedef PermutationWord PERM;
198 typedef SchreierTreeTransversal<PERM> TRANS;
199 checkTranspose<PERM,TRANS>(info_psu4_3);
200 }
201
202
BOOST_AUTO_TEST_CASE(change_test1997_simple)203 BOOST_AUTO_TEST_CASE( change_test1997_simple )
204 {
205 typedef Permutation PERM;
206 typedef ExplicitTransversal<PERM> TRANS;
207 checkChange<PERM,TRANS,SimpleBaseChange<PERM,TRANS,DeterministicBaseTranspose<PERM,TRANS> > >(info_1997);
208 checkChange<PERM,TRANS,SimpleBaseChange<PERM,TRANS,RandomBaseTranspose<PERM,TRANS> > >(info_1997);
209 }
210
BOOST_AUTO_TEST_CASE(change_test1997_conjugating)211 BOOST_AUTO_TEST_CASE( change_test1997_conjugating )
212 {
213 typedef Permutation PERM;
214 typedef ExplicitTransversal<PERM> TRANS;
215 checkChange<PERM,TRANS,ConjugatingBaseChange<PERM,TRANS,DeterministicBaseTranspose<PERM,TRANS> > >(info_1997);
216 checkChange<PERM,TRANS,ConjugatingBaseChange<PERM,TRANS,RandomBaseTranspose<PERM,TRANS> > >(info_1997);
217 }
218
BOOST_AUTO_TEST_CASE(change_trivial_conjugating)219 BOOST_AUTO_TEST_CASE( change_trivial_conjugating )
220 {
221 typedef Permutation PERM;
222 typedef ExplicitTransversal<PERM> TRANS;
223 checkChange<PERM,TRANS,ConjugatingBaseChange<PERM,TRANS,DeterministicBaseTranspose<PERM,TRANS> > >(info_trivial);
224 checkChange<PERM,TRANS,ConjugatingBaseChange<PERM,TRANS,RandomBaseTranspose<PERM,TRANS> > >(info_trivial);
225 }
226
BOOST_AUTO_TEST_CASE(cyclic_construction)227 BOOST_AUTO_TEST_CASE( cyclic_construction )
228 {
229 typedef Permutation PERM;
230 typedef SchreierTreeTransversal<PERM> TRANS;
231 for (unsigned int n = 2; n < 13; ++n) {
232 BSGS<PERM, TRANS> cyclicBSGS = constructCyclicGroup<PERM, TRANS>(n);
233 BOOST_CHECK_EQUAL( cyclicBSGS.n, n );
234 BOOST_CHECK_EQUAL( cyclicBSGS.order<unsigned int>(), n );
235 // a base of one point suffices with a cyclic group
236 BOOST_CHECK_EQUAL( cyclicBSGS.B.size(), 1 );
237 BOOST_CHECK_EQUAL( cyclicBSGS.U.size(), 1 );
238 }
239 }
240
241
242 template<class PERM,class TRANS>
checkRedundantStrongGenerators(const GroupInformation & info)243 void checkRedundantStrongGenerators(const GroupInformation& info) {
244 BSGS<PERM,TRANS> bsgs = ConstructDeterministic1<PERM, TRANS>()(info);
245 BSGS<PERM,TRANS> bsgsCopy(bsgs);
246 BSGSRandomGenerator<PERM,TRANS> randGen(bsgs);
247
248 for (unsigned int i = 0; i < info.n; ++i) {
249 typename PERM::ptr p(new PERM(randGen.next()));
250 bsgsCopy.S.push_front(p);
251 }
252
253 bsgsCopy.stripRedundantStrongGenerators();
254
255 SchreierSimsConstruction<PERM,TRANS> ssc(bsgsCopy.n);
256 BSGS<PERM,TRANS> bsgsStripped = ssc.construct(bsgsCopy.S.begin(), bsgsCopy.S.end(), bsgs.B.begin(), bsgs.B.end());
257
258 BOOST_CHECK_EQUAL(bsgs.order(), bsgsStripped.order());
259 BOOST_CHECK_GE(bsgsCopy.S.size(), bsgsStripped.S.size());
260 BOOST_CHECK_LE(bsgsCopy.S.size(), std::log(bsgs.order()) / std::log(2));
261
262 // stripRedundantStrongGenerators has to be idempotent
263 const unsigned int oldGeneratorNumber = bsgsCopy.S.size();
264 bsgsCopy.stripRedundantStrongGenerators();
265 BOOST_CHECK_EQUAL(oldGeneratorNumber, bsgsCopy.S.size());
266 }
267
BOOST_AUTO_TEST_CASE(strip_redundant_generators)268 BOOST_AUTO_TEST_CASE( strip_redundant_generators )
269 {
270 typedef Permutation PERM;
271 typedef SchreierTreeTransversal<PERM> TRANS;
272
273 checkRedundantStrongGenerators<PERM,TRANS>(info_1997);
274 checkRedundantStrongGenerators<PERM,TRANS>(info_S6);
275 checkRedundantStrongGenerators<PERM,TRANS>(info_A9);
276 checkRedundantStrongGenerators<PERM,TRANS>(info_S3wrS5);
277 checkRedundantStrongGenerators<PERM,TRANS>(info_testThesis);
278 checkRedundantStrongGenerators<PERM,TRANS>(info_test33);
279 checkRedundantStrongGenerators<PERM,TRANS>(info_cyclic37_2);
280 checkRedundantStrongGenerators<PERM,TRANS>(info_e6);
281 checkRedundantStrongGenerators<PERM,TRANS>(info_myciel3);
282 checkRedundantStrongGenerators<PERM,TRANS>(info_cov1075);
283 checkRedundantStrongGenerators<PERM,TRANS>(info_metric5);
284 }
285