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 API test
35 #include <boost/test/unit_test.hpp>
36
37 #include <iostream>
38 #include <fstream>
39 #include <vector>
40
41 #include <permlib/permlib_api.h>
42
43 #include "test-common.h"
44
45 using namespace permlib;
46 using namespace permlib::test;
47
BOOST_AUTO_TEST_CASE(orbit_ulong_trivial)48 BOOST_AUTO_TEST_CASE( orbit_ulong_trivial )
49 {
50 const PermutationGroup group = construct<PERMUTATION,TRANSVERSAL>(info_trivial);
51 std::list<boost::shared_ptr<OrbitAsSet> > o = orbits(group);
52
53 BOOST_CHECK_EQUAL( o.size(), info_trivial.n );
54 }
55
56
BOOST_AUTO_TEST_CASE(orbit_stabilizer_ulong_test1997)57 BOOST_AUTO_TEST_CASE( orbit_stabilizer_ulong_test1997 )
58 {
59 const PermutationGroup group = construct<PERMUTATION,TRANSVERSAL>(info_1997);
60 std::list<boost::shared_ptr<OrbitAsSet> > o = orbits(group);
61
62 BOOST_CHECK_EQUAL( o.size(), 1 );
63
64 const unsigned long DeltaSize = 3;
65 unsigned long Delta[DeltaSize] = {0,1,4};
66 boost::shared_ptr<PermutationGroup> stab1 = setStabilizer(group, Delta, Delta+DeltaSize);
67 BOOST_REQUIRE( stab1 );
68 o = orbits(*stab1);
69
70 BOOST_FOREACH(const boost::shared_ptr<OrbitAsSet>& orb, o) {
71 if (orb->contains(Delta[0])) {
72 BOOST_REQUIRE_EQUAL( orb->size(), DeltaSize );
73 for (unsigned int i = 1; i < DeltaSize; ++i) {
74 BOOST_CHECK( orb->contains(Delta[i]) );
75 }
76 }
77 }
78
79 BOOST_CHECK_EQUAL(o.size(), 3);
80 }
81
82 typedef std::vector<unsigned long> Vector;
83 template<class PERM>
84 struct VectorAction {
operator ()VectorAction85 Vector operator()(const PERM& p, const Vector& v) {
86 Vector ret(v);
87 for (unsigned int i = 0; i < v.size(); ++i) {
88 ret[i] = v[p / i];
89 }
90 return ret;
91 }
92 };
93
BOOST_AUTO_TEST_CASE(orbit_stabilizer_vector_test1997)94 BOOST_AUTO_TEST_CASE( orbit_stabilizer_vector_test1997 )
95 {
96 const PermutationGroup group = construct<PERMUTATION,TRANSVERSAL>(info_1997);
97
98 Vector v(group.n);
99 for (unsigned int i = 0; i < v.size(); ++i)
100 v[i] = i;
101
102 std::list<Vector> vectors;
103 vectors.push_back(v);
104
105 std::list<boost::shared_ptr<OrbitSet<PERMUTATION,Vector> > > o = orbits<Vector, VectorAction<PERMUTATION> >(group, vectors.begin(), vectors.end());
106
107 BOOST_REQUIRE_EQUAL( o.size(), 1 );
108 BOOST_CHECK_EQUAL( o.front()->size(), group.order() );
109 BOOST_CHECK( o.front()->contains(v) );
110
111 boost::shared_ptr<PermutationGroup> stab1 = setStabilizer(group, v.begin(), v.end());
112 BOOST_REQUIRE( stab1 );
113 o = orbits<Vector, VectorAction<PERMUTATION> >(*stab1, vectors.begin(), vectors.end());
114
115 BOOST_REQUIRE_EQUAL( o.size(), 1 );
116 BOOST_CHECK_EQUAL( o.front()->size(), stab1->order() );
117 BOOST_CHECK( o.front()->contains(v) );
118
119 OrbitSet<PERMUTATION,Vector>::const_iterator orbIt = o.front()->begin();
120 const unsigned int magicNumber = 4267;
121 BOOST_REQUIRE_GT(o.front()->size(), magicNumber);
122 // #magicNumber is a number between 0 and 5616-1
123 // the hope is that v != w
124 std::advance(orbIt, magicNumber);
125 Vector w = *orbIt;
126 vectors.push_back(w);
127
128 o = orbits<Vector, VectorAction<PERMUTATION> >(group, vectors.begin(), vectors.end());
129
130 BOOST_REQUIRE_EQUAL( o.size(), 1 );
131 BOOST_CHECK( o.front()->contains(v) );
132 BOOST_CHECK( o.front()->contains(w) );
133 }
134
BOOST_AUTO_TEST_CASE(vector_stabilizer_test1997)135 BOOST_AUTO_TEST_CASE( vector_stabilizer_test1997 )
136 {
137 const PermutationGroup group = construct<PERMUTATION,TRANSVERSAL>(info_1997);
138
139 Vector v(group.n);
140 for (unsigned int i = 0; i < v.size(); ++i)
141 v[i] = i%3;
142
143 boost::shared_ptr<PermutationGroup> stab = vectorStabilizer(group, v.begin(), v.end());
144 BOOST_REQUIRE( stab );
145 // correct order computed with GAP
146 BOOST_CHECK_EQUAL( stab->order(), 2 );
147 }
148
BOOST_AUTO_TEST_CASE(notlexmin_test1997)149 BOOST_AUTO_TEST_CASE( notlexmin_test1997 )
150 {
151 const PermutationGroup group = construct<PERMUTATION,TRANSVERSAL>(info_1997);
152
153 const unsigned int base[] = {3,5,6,8,9};
154 const unsigned int zeros[] = {0,5,6};
155 const unsigned int ones[] = {3,8,9,11};
156
157 // [4,6,7,9,10] is not lex-min in orbit because e.g. [ 1, 12, 3, 11, 13 ] is lex-smaller
158 BOOST_CHECK( isNotLexMinSet(group, base, base+5, zeros, zeros+3, ones, ones+4) );
159 }
160