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