00001
00007 #include "TreeGenerator.hpp"
00008 #include <cstring>
00009 #include <climits>
00010
00011 #include <iostream>
00012 #include <vector>
00013 using namespace std;
00014
00015 TreeGenerator::TreeGenerator( unsigned int numVertices ) :
00016 mNumVertices( numVertices ),
00017 firstTime( true )
00018 {
00019
00020 L = new int[mNumVertices];
00021 currentLevelSequence = new int[numVertices];
00022 }
00023
00024 TreeGenerator::~TreeGenerator()
00025 {
00026 delete [] L;
00027 delete [] currentLevelSequence;
00028 }
00029
00030 bool TreeGenerator::nextTree( Tree & t )
00031 {
00032
00033
00034 if( !firstTime && this->q == 0 )
00035 {
00036 return false;
00037 }
00038
00039 if( firstTime )
00040 {
00041 generateFirstLevelSequence();
00042 firstTime = false;
00043 }
00044 else
00045 {
00046 generateNextLevelSequence();
00047 }
00048
00049
00050 Tree tree( mNumVertices, currentLevelSequence );
00051
00052 t = tree;
00053 return true;
00054 }
00055
00056
00057
00058 void TreeGenerator::generateFirstLevelSequence()
00059 {
00060 int k = ( mNumVertices / 2 ) + 1;
00061
00062 if( mNumVertices == 4 )
00063 {
00064 this->p = 3;
00065 }
00066 else
00067 {
00068 this->p = mNumVertices;
00069 }
00070
00071 this->q = mNumVertices - 1;
00072 this->h1 = k;
00073 this->h2 = mNumVertices;
00074
00075 if( mNumVertices % 2 == 0 )
00076 {
00077 this->c = mNumVertices + 1;
00078 }
00079 else
00080 {
00081 this->c = INT_MAX;
00082 }
00083
00084 this->r = k;
00085
00086 for( int i = 1; i <= k; i++ )
00087 {
00088 L[i - 1] = i;
00089 }
00090 for( unsigned int i = k + 1; i <= mNumVertices; i++ )
00091 {
00092 L[i - 1] = i - k + 1;
00093 }
00094 for( unsigned int i = 0; i < mNumVertices; i++ )
00095 {
00096 currentLevelSequence[i] = i;
00097 }
00098
00099 if( mNumVertices > 2 )
00100 {
00101 currentLevelSequence[k] = 1;
00102 }
00103 if( mNumVertices <= 3 )
00104 {
00105 this->q = 0;
00106 }
00107 }
00108
00109
00110 void TreeGenerator::generateNextLevelSequence()
00111 {
00112 int fixit = 0;
00113
00114 int needr = 0;
00115 int needc = 0;
00116 int needh2 = 0;
00117
00118 int n = mNumVertices;
00119
00120 if( c == n + 1 ||
00121 ( p == h2 &&
00122 ( ( L[h1 - 1] == L[h2 - 1] + 1 &&
00123 n - h2 > r - h1 ) ||
00124 ( L[h1 - 1] == L[h2 - 1] &&
00125 n - h2 + 1 < r - h1 ) ) ) )
00126 {
00127 if( L[r - 1] > 3 )
00128 {
00129 p = r;
00130 q = currentLevelSequence[r - 1];
00131 if( h1 == r )
00132 {
00133 h1--;
00134 }
00135 fixit = 1;
00136 }
00137 else
00138 {
00139 p = r;
00140 r--;
00141 q = 2;
00142 }
00143 }
00144
00145 if( p <= h1 )
00146 {
00147 h1 = p - 1;
00148 }
00149 if( p <= r )
00150 {
00151 needr = 1;
00152 }
00153 else if( p <= h2 )
00154 {
00155 needh2 = 1;
00156 }
00157 else if( L[h2 - 1] == L[h1 - 1] - 1 && n - h2 == r - h1 )
00158 {
00159 if( p <= c )
00160 {
00161 needc = 1;
00162 }
00163 }
00164 else
00165 {
00166 c = INT_MAX;
00167 }
00168
00169 int oldp = p;
00170 int delta = q - p;
00171 int oldlq = L[q - 1];
00172 int oldwq = currentLevelSequence[q - 1];
00173 p = INT_MAX;
00174
00175 for( int i = oldp; i <= n; i++ )
00176 {
00177 L[i - 1] = L[i - 1 + delta];
00178 if( L[i - 1] == 2 )
00179 {
00180 currentLevelSequence[i - 1] = 1;
00181 }
00182 else
00183 {
00184 p = i;
00185 if( L[i - 1] == oldlq )
00186 {
00187 q = oldwq;
00188 }
00189 else
00190 {
00191 q = currentLevelSequence[i - 1 + delta] - delta;
00192 }
00193 currentLevelSequence[i - 1] = q;
00194 }
00195 if( needr == 1 && L[i - 1] == 2 )
00196 {
00197 needr = 0;
00198 needh2 = 1;
00199 r = i - 1;
00200 }
00201 if( needh2 == 1 && L[i - 1] <= L[i - 2] && i > r + 1 )
00202 {
00203 needh2 = 0;
00204 h2 = i - 1;
00205 if( L[h2 - 1] == L[h1 - 1] - 1 && n - h2 == r - h1 )
00206 {
00207 needc = 1;
00208 }
00209 else
00210 {
00211 c = INT_MAX;
00212 }
00213 }
00214 if( needc == 1 )
00215 {
00216 if( L[i - 1] != L[h1 - h2 + i - 1] - 1 )
00217 {
00218 needc = 0;
00219 c = i;
00220 }
00221 else
00222 {
00223 c = i + 1;
00224 }
00225 }
00226 }
00227
00228 if( fixit == 1 )
00229 {
00230 r = n - h1 + 1;
00231 for( int i = r + 1; i <= n; i++ )
00232 {
00233 L[i - 1] = i - r + 1;
00234 currentLevelSequence[i - 1] = i - 1;
00235 }
00236 currentLevelSequence[r] = 1;
00237 h2 = n;
00238 p = n;
00239 q = p - 1;
00240 c = INT_MAX;
00241 }
00242 else
00243 {
00244 if( p == INT_MAX )
00245 {
00246 if( L[oldp - 2] != 2 )
00247 {
00248 p = oldp - 1;
00249 }
00250 else
00251 {
00252 p = oldp - 2;
00253 }
00254 q = currentLevelSequence[p - 1];
00255 }
00256 if( needh2 == 1 )
00257 {
00258 h2 = n;
00259 if( L[h2 - 1] == L[h1 - 1] - 1 && h1 == r )
00260 {
00261 c = n + 1;
00262 }
00263 else
00264 {
00265 c = INT_MAX;
00266 }
00267 }
00268 }
00269 }
00270