permlib  0.2.9
Library for permutation computations
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_
dom_int n
degree of group
Definition: bsgs_core.h:61
BSGS< Permutation, SchreierTreeTransversal< Permutation > > BSGSSchreier
a BSGS which uses Permutation and SchreierTreeTransversal
Definition: bsgs_schreier_export.h:94
BSGSSchreierData * exportData(const BSGSSchreier &bsgs) const
Definition: bsgs_schreier_export.h:104
BSGSSchreier * importData(const BSGSSchreierData *data) const
Definition: bsgs_schreier_export.h:151
dom_int * base
base
Definition: bsgs_schreier_export.h:56
dom_int n
degree of the group
Definition: bsgs_schreier_export.h:48
import of a BSGS based on SchreierTreeTransversal
Definition: bsgs_schreier_export.h:146
dom_int ** sgs
strong generating set
Definition: bsgs_schreier_export.h:64
Transversal class that stores transversal elements in a Schreier tree.
Definition: schreier_tree_transversal.h:44
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
export of a BSGS based on SchreierTreeTransversal
Definition: bsgs_schreier_export.h:99
dom_int baseSize
size of the base
Definition: bsgs_schreier_export.h:51
dom_int sgsSize
size of the strong generating set
Definition: bsgs_schreier_export.h:59
data structure with elementary data types to represent a BSGS based on SchreierTreeTransversal ...
Definition: bsgs_schreier_export.h:46
boost::shared_ptr< Permutation > ptr
boost shared_ptr of this class
Definition: permutation.h:64
base class for import/export of a BSGS based on SchreierTreeTransversal
Definition: bsgs_schreier_export.h:92
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
int ** transversals
transversals
Definition: bsgs_schreier_export.h:77
Permutation class storing all values explicitly.
Definition: permutation.h:58
std::list< unsigned long > m_orbit
orbit elements
Definition: transversal.h:157
PERMlist S
strong generating set
Definition: bsgs_core.h:57
std::vector< boost::shared_ptr< PERM > > m_transversal
transversal elements
Definition: transversal.h:154
Definition: abstract_bsgs.h:49