permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/export/bsgs_schreier_export.h
00001 // ---------------------------------------------------------------------------
00002 //
00003 //  This file is part of PermLib.
00004 //
00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
00006 // All rights reserved.
00007 // 
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions
00010 // are met:
00011 // 1. Redistributions of source code must retain the above copyright
00012 //    notice, this list of conditions and the following disclaimer.
00013 // 2. Redistributions in binary form must reproduce the above copyright
00014 //    notice, this list of conditions and the following disclaimer in the
00015 //    documentation and/or other materials provided with the distribution.
00016 // 3. The name of the author may not be used to endorse or promote products
00017 //    derived from this software without specific prior written permission.
00018 // 
00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029 //
00030 // ---------------------------------------------------------------------------
00031 
00032 
00033 #ifndef BSGS_EXPORT_H_
00034 #define BSGS_EXPORT_H_
00035 
00036 #include <map>
00037 
00038 #include <permlib/permutation.h>
00039 #include <permlib/transversal/schreier_tree_transversal.h>
00040 
00041 #include <boost/foreach.hpp>
00042 
00043 namespace permlib { namespace exports { 
00044 
00046 struct BSGSSchreierData {
00048         dom_int n;
00049         
00051         dom_int baseSize;
00053 
00056         dom_int* base;
00057         
00059         dom_int sgsSize;
00061 
00064         dom_int** sgs;
00065         
00067 
00077         int** transversals;
00078         
00079         ~BSGSSchreierData() {
00080                 delete[] base;
00081                 for (unsigned int i = 0; i < sgsSize; ++i)
00082                         delete[] sgs[i];
00083                 delete[] sgs;
00084                 for (unsigned int i = 0; i < baseSize; ++i)
00085                         delete[] transversals[i];
00086                 delete[] transversals;
00087         }
00088 };
00089 
00090 
00092 struct BSGSSchreierBase {
00094         typedef BSGS<Permutation, SchreierTreeTransversal<Permutation> > BSGSSchreier;
00095 };
00096 
00097 
00099 struct BSGSSchreierExport : public BSGSSchreierBase {
00104         BSGSSchreierData* exportData(const BSGSSchreier& bsgs) const {
00105                 std::map<Permutation::ptr, int> generatorMap;
00106                 BSGSSchreierData* data = new BSGSSchreierData();
00107                 
00108                 data->n = bsgs.n;
00109                 data->baseSize = bsgs.B.size();
00110                 data->base = new dom_int[data->baseSize];
00111                 std::copy(bsgs.B.begin(), bsgs.B.end(), data->base);
00112                 
00113                 data->sgsSize = bsgs.S.size();
00114                 data->sgs = new dom_int*[data->sgsSize];
00115                 int idx = 0;
00116                 BOOST_FOREACH(const Permutation::ptr& p, bsgs.S) {
00117                         data->sgs[idx] = new dom_int[bsgs.n];
00118                         std::copy(p->m_perm.begin(), p->m_perm.end(), data->sgs[idx]);
00119                         generatorMap[p] = idx;
00120                         ++idx;
00121                 }
00122                 
00123                 data->transversals = new int*[data->baseSize];
00124                 idx = 0;
00125                 BOOST_FOREACH(const SchreierTreeTransversal<Permutation>& trans, bsgs.U) {
00126                         data->transversals[idx] = new int[bsgs.n];
00127                         std::vector<int> transversalData(bsgs.n);
00128                         for (unsigned int i = 0; i < bsgs.n; ++i) {
00129                                 if (i == bsgs.B[idx]) {
00130                                         data->transversals[idx][i] = -1;
00131                                 } else if (trans.m_transversal[i]) {
00132                                         data->transversals[idx][i] = generatorMap[trans.m_transversal[i]];
00133                                 } else {
00134                                         data->transversals[idx][i] = -2;
00135                                 }
00136                         }
00137                         ++idx;
00138                 }
00139                 
00140                 return data;
00141         }
00142 };
00143 
00144 
00146 struct BSGSSchreierImport : public BSGSSchreierBase {
00151         BSGSSchreier* importData(const BSGSSchreierData* data) const {
00152                 std::map<int, Permutation::ptr> generatorMap;
00153                 BSGSSchreier* bsgs = new BSGSSchreier(data->n);
00154                 
00155                 bsgs->B.resize(data->baseSize);
00156                 std::copy(data->base, data->base + data->baseSize, bsgs->B.begin());
00157                 
00158                 for (unsigned int idx = 0; idx < data->sgsSize; ++idx) {
00159                         Permutation::ptr perm(new Permutation(data->sgs[idx], data->sgs[idx] + data->n));
00160                         bsgs->S.push_back(perm);
00161                         generatorMap[idx] = perm;
00162                 }
00163                 
00164                 Permutation::ptr identity(new Permutation(data->n));
00165                 
00166                 bsgs->U.resize(data->baseSize, SchreierTreeTransversal<Permutation>(data->n));
00167                 for (unsigned int idx = 0; idx < data->baseSize; ++idx) {
00168                         SchreierTreeTransversal<Permutation> U(data->n);
00169                         for (unsigned int i = 0; i < data->n; ++i) {
00170                                 if (data->transversals[idx][i] >= 0) {
00171                                         U.m_transversal[i] = generatorMap[data->transversals[idx][i]];
00172                                         U.m_orbit.push_back(i);
00173                                 } else if (i == bsgs->B[idx]) {
00174                                         BOOST_ASSERT( data->transversals[idx][i] == -1 );
00175                                         U.m_transversal[i] = identity;
00176                                         U.m_orbit.push_back(i);
00177                                 }
00178                         }
00179                         bsgs->U[idx] = U;
00180                 }
00181                 
00182                 return bsgs;
00183         }
00184 };
00185 
00186 } } // end NS
00187 
00188 #endif // -- BSGS_EXPORT_H_