00001
00011 #ifndef __graphgen_util_hpp
00012 #define __graphgen_util_hpp
00013
00014
00015 #include<vector>
00016 #include<iostream>
00017
00018 #include<algorithm>
00019
00020 #include<cmath>
00021
00022
00023 namespace graphgen{
00025 typedef unsigned int qint;
00026
00027 namespace graphtype{
00028 const unsigned int SIMPLE=2 ;
00029 const unsigned int TREE=4 ;
00030 const unsigned int CONNECTED=8 ;
00031
00032 const unsigned int NSIMPLE=~SIMPLE ;
00033 const unsigned int NTREE=~TREE ;
00034 const unsigned int NCONNECTED=~CONNECTED ;
00035 }
00036
00037
00046 template<class Ch,class Tr >
00047 std::basic_ostream<Ch,Tr>& tab(std::basic_ostream<Ch,Tr>& s){
00048 return s<<"\t";
00049 }
00050
00051 void err( const char* msg );
00052
00059 class RNG_DRAND48{
00060 unsigned short int x0;
00061 unsigned short int x1;
00062 unsigned short int x2;
00063
00064 double drand48()
00065 {
00066
00067 unsigned short int x10, x11, x12;
00068 unsigned int w;
00069
00070 w = (long) 0xe66d*x0;
00071 x10 = w;
00072 w = w/65536;
00073 w += (long) 0xdeec*x0;
00074 x11 = w;
00075 w = w/65536;
00076 x12 = w + (long) 0x0005*x0;
00077 w = (long) 0xe66d*x1 ;
00078 w += x11;
00079 x11 = w;
00080 w = w/65536 ;
00081 x12 += w + (long)0xdeec*x1 +(long)0xe66d*x2 ;
00082 x0=x10; x1=x11; x2=x12;
00083 w=(long) x0+0xb ; x0=w ;
00084 if (w>=65536)
00085 {
00086 w=(long) x1+1;
00087 x1=w;
00088 if (w>=65536)
00089 x2++;
00090 }
00091 return ((x2*4294967296.0+x1*65536.0+x0*1.0)/281474976710656.0);
00092 }
00093
00094
00095 double rng()
00096 {
00097 return drand48();
00098 }
00099 unsigned long rng( long unsigned int N ){
00100 return static_cast<unsigned long>(drand48()*N);
00101 }
00102
00103 public:
00104 RNG_DRAND48(): x0(1),x1(1),x2(1){};
00105
00112 double operator()(){
00113
00114
00115
00116 return drand48();
00117 }
00118
00124 unsigned long operator()( unsigned long N ){
00125
00126
00127
00128 return static_cast<unsigned long>(N*drand48());
00129 }
00130 };
00131
00132
00133
00134 typedef RNG_DRAND48 RNG;
00135
00139 static RNG rng;
00140
00141
00150 inline
00151 unsigned int ltm_index( unsigned int i, unsigned int j )
00152 {
00153 unsigned int q = std::max(i,j);
00154 unsigned int k = std::min(i,j);
00155
00156 return (q*(q+1))/2 + k;
00157 };
00158
00159
00160
00171 template<class I>
00172 class integer_pool {
00173 private:
00178 I max_;
00180 I n_;
00182 std::vector<I> ind_;
00184 std::vector<I> item_;
00185
00186 public:
00188 integer_pool() : max_(0), n_(0) {}
00189
00191 integer_pool(int m) : max_(m), n_(0), ind_(m), item_(m) {
00192 for(I i=0;i<max_;i++) {
00193 item_[i]=i;
00194 }
00195 }
00196
00201 integer_pool(int m, int taken)
00202 : max_(m), n_(taken), ind_(m), item_(m)
00203 {
00204 I i = 0;
00205 for( ; i<taken; i++ ){
00206 item_[i]=i;
00207 ind_[i]=i;
00208 }
00209 for( ; i<max_; i++ ) item_[i]=i;
00210 }
00211
00213 ~integer_pool(){};
00214
00216 I n() const {
00217 return n_;
00218 }
00219
00221 I max() const {
00222 return max_;
00223 }
00224
00226 void reset() {
00227 for(I i=0;i<max_;i++) item_[i]=i;
00228
00229 n_=0;
00230 }
00231
00236 void reset( I taken ){
00237 for( I i=0; i<taken; i++ ){
00238 item_[i]=i;
00239 ind_[i]=i;
00240 }
00241
00242 n_=taken;
00243 for( I i=taken; i<max_; i++ ) item_[i]=i;
00244 }
00245
00246
00248 I take() {
00249 I i=item_[n_];
00250
00251 ind_[i]=n_;
00252 n_++;
00253 return i;
00254 }
00255
00263 I put(I i) {
00264 I ind=ind_[i];
00265 I last=item_[n_-1];
00266
00267 item_[n_-1]=i;
00268 item_[ind]=last;
00269 ind_[last]=ind;
00270 n_--;
00271 return last;
00272 }
00273
00278 I operator[](I i) const {return item_[i];};
00279
00283 void resize(I m) {
00284 ind_.resize(m);
00285 item_.resize(m);
00286 for(I i=max_;i<m;i++)
00287 item_[i]=i;
00288
00289 max_=m;
00290 }
00291
00293 size_t size() {
00294 return ind_.size()+item_.size();
00295 }
00296
00301 size_t capacity() {
00302 return ind_.size()+item_.capacity();
00303 }
00304 };
00305
00322 template<class T> class symmetric_matrix{
00323 std::vector<T> values;
00324 unsigned int index( unsigned int i, unsigned int j ) const {
00325 return (std::max(i,j)*(std::max(i,j)+1))/2 + std::min(i,j);
00326 }
00327
00328 unsigned int inverse( unsigned int i ) const {
00329 return static_cast<unsigned int>((std::sqrt(9+8*i)-3)/2 + 0.5);
00330 }
00331
00332 public:
00333 symmetric_matrix()
00334 : values(1) {}
00335
00336 symmetric_matrix( unsigned int size )
00337 : values(index(size-1,size-1)+1) {}
00338
00339 symmetric_matrix( unsigned int size, T val )
00340 : values(index(size-1,size-1)+1,val) {}
00341
00343 T& operator()( unsigned int i, unsigned int j ){ return values[index(i,j)]; }
00344
00346 const T& operator()( unsigned int i, unsigned int j ) const { return values[index(i,j)]; }
00347
00353 T& at( unsigned int i, unsigned int j ){
00354 if(index(i,j)>=values.size()) resize(std::max(i,j));
00355 return values.at(index(i,j));
00356 }
00357
00364 const T& at( unsigned int i, unsigned int j ) const {
00365 if(index(i,j)>=values.size()) resize(std::max(i,j));
00366 return values.at(index(i,j));
00367 }
00368
00372 size_t size() const{
00373 return inverse(values.size())+1;
00374 }
00375
00377 void resize( unsigned int n ){
00378 values.resize( index(n-1,n-1)+1 );
00379 }
00380
00381 };
00382
00384 }
00385
00386 #endif