permlib  0.2.8
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
bsgs_schreier_export.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 BSGS_EXPORT_H_
34 #define BSGS_EXPORT_H_
35 
36 #include <map>
37 
38 #include <permlib/permutation.h>
39 #include <permlib/transversal/schreier_tree_transversal.h>
40 
41 #include <boost/foreach.hpp>
42 
43 namespace permlib { namespace exports {
44 
48  dom_int n;
49 
51  dom_int baseSize;
53 
56  dom_int* base;
57 
59  dom_int sgsSize;
61 
64  dom_int** sgs;
65 
67 
77  int** transversals;
78 
79  ~BSGSSchreierData() {
80  delete[] base;
81  for (unsigned int i = 0; i < sgsSize; ++i)
82  delete[] sgs[i];
83  delete[] sgs;
84  for (unsigned int i = 0; i < baseSize; ++i)
85  delete[] transversals[i];
86  delete[] transversals;
87  }
88 };
89 
90 
95 };
96 
97 
105  std::map<Permutation::ptr, int> generatorMap;
106  BSGSSchreierData* data = new BSGSSchreierData();
107 
108  data->n = bsgs.n;
109  data->baseSize = bsgs.B.size();
110  data->base = new dom_int[data->baseSize];
111  std::copy(bsgs.B.begin(), bsgs.B.end(), data->base);
112 
113  data->sgsSize = bsgs.S.size();
114  data->sgs = new dom_int*[data->sgsSize];
115  int idx = 0;
116  BOOST_FOREACH(const Permutation::ptr& p, bsgs.S) {
117  data->sgs[idx] = new dom_int[bsgs.n];
118  std::copy(p->m_perm.begin(), p->m_perm.end(), data->sgs[idx]);
119  generatorMap[p] = idx;
120  ++idx;
121  }
122 
123  data->transversals = new int*[data->baseSize];
124  idx = 0;
125  BOOST_FOREACH(const SchreierTreeTransversal<Permutation>& trans, bsgs.U) {
126  data->transversals[idx] = new int[bsgs.n];
127  std::vector<int> transversalData(bsgs.n);
128  for (unsigned int i = 0; i < bsgs.n; ++i) {
129  if (i == bsgs.B[idx]) {
130  data->transversals[idx][i] = -1;
131  } else if (trans.m_transversal[i]) {
132  data->transversals[idx][i] = generatorMap[trans.m_transversal[i]];
133  } else {
134  data->transversals[idx][i] = -2;
135  }
136  }
137  ++idx;
138  }
139 
140  return data;
141  }
142 };
143 
144 
152  std::map<int, Permutation::ptr> generatorMap;
153  BSGSSchreier* bsgs = new BSGSSchreier(data->n);
154 
155  bsgs->B.resize(data->baseSize);
156  std::copy(data->base, data->base + data->baseSize, bsgs->B.begin());
157 
158  for (unsigned int idx = 0; idx < data->sgsSize; ++idx) {
159  Permutation::ptr perm(new Permutation(data->sgs[idx], data->sgs[idx] + data->n));
160  bsgs->S.push_back(perm);
161  generatorMap[idx] = perm;
162  }
163 
164  Permutation::ptr identity(new Permutation(data->n));
165 
166  bsgs->U.resize(data->baseSize, SchreierTreeTransversal<Permutation>(data->n));
167  for (unsigned int idx = 0; idx < data->baseSize; ++idx) {
169  for (unsigned int i = 0; i < data->n; ++i) {
170  if (data->transversals[idx][i] >= 0) {
171  U.m_transversal[i] = generatorMap[data->transversals[idx][i]];
172  U.m_orbit.push_back(i);
173  } else if (i == bsgs->B[idx]) {
174  BOOST_ASSERT( data->transversals[idx][i] == -1 );
175  U.m_transversal[i] = identity;
176  U.m_orbit.push_back(i);
177  }
178  }
179  bsgs->U[idx] = U;
180  }
181 
182  return bsgs;
183  }
184 };
185 
186 } } // end NS
187 
188 #endif // -- BSGS_EXPORT_H_