permlib
0.2.6
Library for permutation computations
|
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_