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 Backtrack search test - matrix automorphism
35 #include <boost/test/unit_test.hpp>
36
37 #include <iostream>
38 #include <fstream>
39
40 #include <permlib/permutation.h>
41 #include <permlib/bsgs.h>
42 #include <permlib/symmetric_group.h>
43 #include <permlib/construct/schreier_sims_construction.h>
44
45 #include <permlib/transversal/schreier_tree_transversal.h>
46 #include <permlib/change/conjugating_base_change.h>
47 #include <permlib/search/partition/matrix_automorphism_search.h>
48
49 #include "test-common.h"
50
51 #include <boost/foreach.hpp>
52
53 using namespace permlib;
54 using namespace permlib::test;
55
56 template<class T>
57 class Matrix {
58 public:
Matrix(unsigned long dimension)59 Matrix(unsigned long dimension) : m_dimension(dimension), m_matrix(dimension*dimension) {}
60
dimension() const61 unsigned long dimension() const { return m_dimension; }
at(unsigned long i,unsigned long j) const62 inline const T& at(unsigned long i, unsigned long j) const { return m_matrix[j * m_dimension + i]; }
at(unsigned long i,unsigned long j)63 inline T& at(unsigned long i, unsigned long j) { return m_matrix[j * m_dimension + i]; }
64
65 private:
66 const unsigned long m_dimension;
67 std::vector<T> m_matrix;
68 };
69
70 class ZMatrix : public Matrix<unsigned long> {
71 public:
ZMatrix(unsigned long dimension,unsigned long k=0)72 ZMatrix(unsigned long dimension, unsigned long k = 0) : Matrix<unsigned long>(dimension), m_k(k) {}
73
k() const74 unsigned long k() const { return m_k; }
k()75 unsigned long& k() { return m_k; }
76 private:
77 unsigned long m_k;
78 };
79
80
BOOST_AUTO_TEST_CASE(matrix_auto)81 BOOST_AUTO_TEST_CASE( matrix_auto )
82 {
83 // we use elementary permutations
84 typedef Permutation PERM;
85 // and Schreier tree transversals
86 typedef SchreierTreeTransversal<PERM> TRANSVERSAL;
87
88 // our group will have degree 4
89 const unsigned long n = 4;
90
91 ZMatrix matrix(4,3);
92 matrix.at(0,0) = 1;
93 matrix.at(0,1) = 0;
94 matrix.at(0,2) = 0;
95 matrix.at(0,3) = 2;
96
97 matrix.at(1,1) = 1;
98 matrix.at(1,2) = 0;
99 matrix.at(1,3) = 2;
100
101 matrix.at(2,2) = 2;
102 matrix.at(2,3) = 2;
103
104 matrix.at(3,3) = 1;
105
106 for(unsigned int i=0; i<n; ++i) {
107 for(unsigned int j=i+1; j<n; ++j) {
108 matrix.at(j,i) = matrix.at(i,j);
109 }
110 }
111
112 SymmetricGroup<PERM> s_n(n);
113 partition::MatrixAutomorphismSearch<SymmetricGroup<PERM>, TRANSVERSAL> mas(s_n, false);
114 mas.construct(matrix);
115
116 BSGS<PERM,TRANSVERSAL> K(n);
117 mas.search(K);
118
119 BOOST_CHECK(K.order() == 2);
120 }
121