00001
00002
00003
00004
00005
00006
00007 #include <iostream>
00008 #include <fstream>
00009 #include <cstdio>
00010 #include <cstdlib>
00011 #include <set>
00012 #include <vector>
00013 #include <map>
00014 #include <queue>
00015 #include <algorithm>
00016
00017 using namespace std;
00018
00019
00020 #define ABS(_x) ((_x) < 0 ? -(_x) : (_x))
00021 #define NODEBUG 0
00022 #if NODEBUG
00023 #define MYASSERT( _v, _c, _s ) (void)0
00024 #else
00025 int alvl = 0;
00026 #define MYASSERT( _v, _c, _s ) if((_v) <= alvl && !(_c)){cout<< \
00027 "Assertion failed at "<<__FILE__<<"@"<<__LINE__<<": "<<_s<<endl;exit(1);}else
00028 #endif
00029
00030 #if NODEBUG
00031 #define MYDBG( _v, _s ) (void)0
00032 #else
00033 int dlvl = 0;
00034 #define MYDBG( _v, _s ) if((_v) <= dlvl){cout<< \
00035 __FILE__<<"@"<<__LINE__<<": "<<_s<<endl;}else
00036 #endif
00037
00038
00039
00040 typedef vector<int> Labels;
00041
00042
00043
00044
00045 void initlabels( Labels &labels, int n, bool identity )
00046 {
00047 MYASSERT( 0, labels.size() == 0, "Must be empty to begin with" );
00048 for( int i = 0; i < n; i++ ) { labels.push_back(identity ? i : -1); }
00049 MYASSERT( 0, (int)labels.size() == n, "Must have " << n << " elements" );
00050 }
00051
00052
00053
00054
00055 void randpermutation( Labels &labels, int n )
00056 {
00057 initlabels( labels, n, true );
00058 srand48(1234);
00059 for( int j = 0; j < n; j++ )
00060 {
00061 int k1 = drand48()*n;
00062 int k2 = drand48()*n;
00063 #define SWAP(_x,_y,_t) do{ _t _temp = _x; _x = _y; _y = _temp; }while(0)
00064 SWAP( labels[k1], labels[k2], int );
00065 }
00066 }
00067
00068
00069
00070
00071 bool ispermutation( const Labels &labels, int n )
00072 {
00073 MYASSERT( 0, (int)labels.size() == n, "Must have " << n << " elements" );
00074 vector<bool> seen;
00075 bool allseen = true;
00076 for( int i = 0; i < n; i++ )
00077 { seen.push_back(false); }
00078 for( int i = 0; i < n; i++ )
00079 { int vi = labels[i]; if( 0 <= vi && vi < n ) seen[vi] = true; }
00080 for( int i = 0; i < n; i++ )
00081 { allseen = allseen && seen[i]; }
00082 return allseen;
00083 }
00084
00085
00086
00087
00088 void invertpermutation( const Labels &perm, Labels &invperm, int n )
00089 {
00090 MYASSERT( 0, ispermutation( perm, n ), "" );
00091 initlabels( invperm, n, true );
00092 for( int i = 0; i < n; i++ )
00093 { invperm[perm[i]] = i; }
00094 }
00095
00096
00097
00098
00099 void printpermutation( ostream &out, const Labels &labels )
00100 {
00101 for( int i = 0, n = labels.size(); i < n; i++ )
00102 { out << "PERM " << i << " " << labels[i] << endl; }
00103 }
00104
00105
00106 class BWGraph
00107 {
00108
00109 protected: typedef set<int> EdgeSet;
00110
00111 protected: typedef map<int,EdgeSet> AdjMap;
00112
00113 public: BWGraph() : adjmap(), nedges(0) {}
00114 public: BWGraph(const BWGraph &bwg ) :
00115 adjmap(bwg.adjmap), nedges(bwg.nedges) {}
00116
00117 protected: AdjMap adjmap;
00118 protected: int nedges;
00119
00120 public: void addnode( int i );
00121 public: void addedge( int i, int j, bool duplex );
00122 public: void readfile( const char *fname );
00123 public: int getnumnodes( void ) const { return adjmap.size(); }
00124 public: int getnumedges( void ) const { return nedges; }
00125 public: int getnumleaves( void );
00126 public: int bandwidth( const Labels &labels ) const;
00127 public: void printdiffs( const Labels &labels ) const;
00128 public: void relabel( Labels &labels ) const;
00129 public: void printdegreedistribution( ostream &out ) const;
00130
00131 public: static bool isleaf( AdjMap &m, int n, int i );
00132
00133 protected: void relabel_phase1( int n, int &nextlabel, Labels &labels,
00134 AdjMap &scratchmap, int &scratchnedges ) const;
00135 protected: void relabel_phase2( int n, int &nextlabel, Labels &labels,
00136 AdjMap &scratchmap, int &scratchnedges ) const;
00137 protected: void relabel_phase3( int n, int &nextlabel, Labels &labels,
00138 AdjMap &scratchmap, int &scratchnedges ) const;
00139 };
00140
00141
00142
00143
00144 bool BWGraph::isleaf( AdjMap &m, int n, int i )
00145 {
00146 return ( (0 <= i && i < n) && (m[i].size() == 1) );
00147 }
00148
00149
00150
00151
00152 int BWGraph::bandwidth( const Labels &labels ) const
00153 {
00154 int n = getnumnodes();
00155 MYASSERT( 0, (int)labels.size() == n, "" );
00156 MYASSERT( 0, ispermutation( labels, n ), "" );
00157 int maxdiff = 0;
00158 for( AdjMap::const_iterator it = adjmap.begin(); it != adjmap.end(); it++ )
00159 {
00160 int i = it->first;
00161 MYASSERT( 0, 0 <= i && i < n, "" );
00162 int lbli = labels[i];
00163 MYASSERT( 0, 0 <= lbli && lbli < n, "" );
00164 const EdgeSet &edgeset = it->second;
00165 for( EdgeSet::iterator et = edgeset.begin(); et != edgeset.end(); et++ )
00166 {
00167 int j = *et;
00168 MYASSERT( 0, 0 <= j && j < n, j );
00169 int lblj = labels[j];
00170 MYASSERT( 0, 0 <= lblj && lblj < n, "" );
00171 int diff = ABS(lbli-lblj);
00172 if( diff > maxdiff )
00173 {
00174 maxdiff = diff;
00175 }
00176 }
00177 }
00178 return maxdiff;
00179 }
00180
00181
00182 struct DI
00183 {
00184 int i, j;
00185 int diff;
00186 DI( int _i, int _j, int _d ) : i(_i), j(_j), diff(_d) {}
00187 bool operator<(const DI&a) const { return diff < a.diff; }
00188 };
00189
00190
00191
00192
00193 void BWGraph::printdiffs( const Labels &labels ) const
00194 {
00195 int n = getnumnodes();
00196 MYASSERT( 0, (int)labels.size() == n, "" );
00197 MYASSERT( 0, ispermutation( labels, n ), "" );
00198 vector<DI> diffs;
00199 for( AdjMap::const_iterator it = adjmap.begin(); it != adjmap.end(); it++ )
00200 {
00201 int i = it->first;
00202 MYASSERT( 0, 0 <= i && i < n, "" );
00203 int lbli = labels[i];
00204 MYASSERT( 0, 0 <= lbli && lbli < n, "" );
00205 const EdgeSet &edgeset = it->second;
00206 for( EdgeSet::iterator et = edgeset.begin(); et != edgeset.end(); et++ )
00207 {
00208 int j = *et;
00209 MYASSERT( 0, 0 <= j && j < n, j );
00210 int lblj = labels[j];
00211 MYASSERT( 0, 0 <= lblj && lblj < n, "" );
00212 int diff = ABS(lbli-lblj);
00213 diffs.push_back( DI(i,j,diff) );
00214 }
00215 }
00216
00217 sort( diffs.begin(), diffs.end() );
00218
00219 MYDBG( 0, "-------------------------------------------------------------" );
00220 MYDBG( 0, "Edge#\t(\tnodei\t,\tnodej\t)\t=\tdiff");
00221 MYDBG( 0, "-------------------------------------------------------------" );
00222 for( int v = 0; v < (int)diffs.size(); v++ )
00223 {
00224 const DI &di = diffs[v];
00225 MYDBG( 0, v << "\t" <<
00226 "(\t" << di.i << "\t,\t" << di.j << "\t)\t=\t" << di.diff );
00227 }
00228 MYDBG( 0, "-------------------------------------------------------------" );
00229 }
00230
00231
00232
00233
00234 void BWGraph::relabel_phase1( int n, int &nextlabel, Labels &labels,
00235 AdjMap &scratchmap, int &scratchnedges ) const
00236 {
00237 MYDBG( 0, "-------------------------" );
00238 MYDBG( 0, "Phase 1: begin nextlabel "<<nextlabel );
00239 MYDBG( 0, "-------------------------" );
00240
00241 typedef set<int> LeafSet;
00242 LeafSet leaves;
00243
00244
00245 for( AdjMap::const_iterator it = scratchmap.begin();
00246 it != scratchmap.end(); it++ )
00247 {
00248 int nodei = it->first;
00249 if( isleaf( scratchmap, n, nodei ) )
00250 {
00251 leaves.insert( nodei );
00252 }
00253 }
00254
00255
00256 int leafi = -1;
00257 while( leaves.size() > 0 )
00258 {
00259
00260 if( leafi >= 0 )
00261 {
00262 MYDBG( 0, "\tContinuing with prev parent (now leaf) "<<leafi );
00263 }
00264 else
00265 {
00266 LeafSet::const_iterator leafit = leaves.begin();
00267 MYASSERT( 0, leafit != leaves.end(), "" );
00268 leafi = *leafit;
00269 MYDBG( 0, "\tSelected new leaf "<<leafi );
00270 }
00271
00272 MYASSERT( 0, 0 <= leafi && leafi < n, "" );
00273 MYASSERT( 0, isleaf( scratchmap, n, leafi ), "must be leaf" );
00274
00275 const EdgeSet &leafedges = scratchmap[leafi];
00276 int parenti = *(leafedges.begin());
00277 MYASSERT( 0, 0 <= parenti && parenti < n, "" );
00278
00279
00280 vector<int> unlabeledkids;
00281 const EdgeSet &cparentedges = scratchmap[parenti];
00282 for( EdgeSet::iterator et = cparentedges.begin();
00283 et != cparentedges.end(); et++ )
00284 {
00285 int kidi = *et;
00286 MYASSERT( 0, 0 <= kidi && kidi < n, "" );
00287 if( isleaf( scratchmap, n, kidi ) )
00288 {
00289 MYASSERT( 0, *(scratchmap[kidi].begin()) == parenti, "Sanity");
00290 int kidlbl = labels[kidi];
00291 if( kidlbl < 0 )
00292 {
00293 unlabeledkids.push_back( kidi );
00294 }
00295 }
00296 }
00297
00298 int d = unlabeledkids.size();
00299 int halfd = ( (d <= 0) ? 0 : (1+(d-1)/2) );
00300
00301
00302 bool parentlabeled = false;
00303 if( labels[parenti] < 0 )
00304 {
00305 labels[parenti] = nextlabel + halfd;
00306 parentlabeled = true;
00307 MYDBG( 0, "\t\tLabeled parent "<<parenti<<" with "<<labels[parenti]);
00308 }
00309
00310
00311 for( int i = 0; i < halfd; i++ )
00312 {
00313 int kidi = unlabeledkids[i];
00314 MYASSERT( 0, 0 <= kidi && kidi < n, "" );
00315 MYASSERT( 0, labels[kidi] < 0, "" );
00316 labels[kidi] = nextlabel+i;
00317 MYDBG(0,"\t\t\tLabeled 1-half leaf "<<kidi<<" with "<<labels[kidi]);
00318 }
00319
00320
00321 for( int i = halfd; i < d; i++ )
00322 {
00323 int kidi = unlabeledkids[i];
00324 MYASSERT( 0, 0 <= kidi && kidi < n, "" );
00325 MYASSERT( 0, labels[kidi] < 0, "" );
00326 labels[kidi] = nextlabel+i+1;
00327 MYDBG(0,"\t\t\tLabeled 2-half leaf "<<kidi<<" with "<<labels[kidi]);
00328 }
00329
00330
00331 nextlabel += d;
00332 if( parentlabeled ) nextlabel++;
00333
00334
00335 EdgeSet &parentedges = scratchmap[parenti];
00336 for( int i = 0, nk = unlabeledkids.size(); i < nk; i++ )
00337 {
00338 int kidi = unlabeledkids[i];
00339 parentedges.erase( kidi );
00340 scratchmap.erase( kidi );
00341 leaves.erase( kidi );
00342 scratchnedges -= 2;
00343 }
00344
00345 leafi = -1;
00346
00347
00348 if( isleaf( scratchmap, n, parenti ) )
00349 {
00350 leafi = parenti;
00351 }
00352 }
00353
00354 MYDBG( 0, "Phase 1: end nextlabel "<<nextlabel<<endl );
00355 }
00356
00357
00358 struct SLElem { SLElem(int l=-1,int i=-1):label(l),nodei(i){}
00359 int label; int nodei; };
00360 struct SLCompare{ bool operator()( const SLElem&lhs, const SLElem &rhs ) const
00361 { return lhs.label>rhs.label;} };
00362 typedef priority_queue<SLElem, vector<SLElem>, SLCompare> LabelPQ;
00363
00364
00365
00366
00367 void BWGraph::relabel_phase2( int n, int &nextlabel, Labels &labels,
00368 AdjMap &scratchmap, int &scratchnedges ) const
00369 {
00370 MYDBG( 0, "-------------------------" );
00371 MYDBG( 0, "Phase 2: begin nextlabel "<<nextlabel );
00372 MYDBG( 0, "-------------------------" );
00373
00374 LabelPQ scratchlabels;
00375
00376 for( AdjMap::const_iterator cit = scratchmap.begin();
00377 cit != scratchmap.end(); cit++ )
00378 {
00379 int nodei = cit->first;
00380 int lbli = labels[nodei];
00381 if( lbli >= 0 )
00382 {
00383 scratchlabels.push( SLElem(lbli, nodei) );
00384 }
00385 }
00386
00387 while( scratchnedges > 0 )
00388 {
00389 int nodei = -1;
00390
00391 while( scratchlabels.size() > 0 )
00392 {
00393 int tempi = scratchlabels.top().nodei;
00394 scratchlabels.pop();
00395 MYASSERT( 0, 0 <= tempi && tempi < n, "" );
00396 int lbli = labels[tempi];
00397 MYASSERT( 0, 0 <= lbli && lbli < n, "Must be labeled" );
00398
00399 if( scratchmap.find(tempi) != scratchmap.end() )
00400 {
00401 nodei = tempi;
00402 MYDBG( 0,"\tPicked least label "<<lbli<<" node "<<nodei );
00403 break;
00404 }
00405 }
00406
00407 if( nodei < 0 )
00408 {
00409
00410 for( AdjMap::const_iterator it = scratchmap.begin();
00411 it != scratchmap.end(); it++ )
00412 {
00413 int li = it->first;
00414 if( isleaf( scratchmap, n, li ) )
00415 {
00416 nodei = li;
00417 break;
00418 }
00419 }
00420
00421 if( nodei < 0 )
00422 {
00423 MYDBG( 0, "\tCouldn't find any leaves" );
00424 }
00425 else
00426 {
00427 MYASSERT( 0, 0 <= nodei && nodei < n, "" );
00428 MYDBG( 0, "\tPicked a leaf node "<<nodei );
00429 int lbli = labels[nodei];
00430 MYASSERT( 0, lbli < 0, nodei<<" labeled "<<lbli);
00431
00432 lbli = labels[nodei] = nextlabel++;
00433 MYDBG( 0, "\tLabeled leaf node "<<nodei<<" with "<<lbli);
00434 }
00435 }
00436
00437 if( nodei < 0 )
00438 {
00439
00440 AdjMap::iterator nodeit=scratchmap.begin();
00441 MYASSERT( 0, nodeit != scratchmap.end(), "A node must exist" );
00442 nodei = nodeit->first;
00443 MYASSERT( 0, 0 <= nodei && nodei < n, "" );
00444 MYDBG( 0, "\tPicked random node "<<nodei );
00445 int lbli = labels[nodei];
00446 MYASSERT( 0, lbli < 0, nodei<<" labeled "<<lbli);
00447
00448 lbli = labels[nodei] = nextlabel++;
00449 MYDBG( 0, "\tLabeled random node "<<nodei<<" with "<<lbli);
00450 }
00451
00452 MYASSERT( 0, 0 <= nodei && nodei < n, "" );
00453 int lbli = labels[nodei];
00454 MYASSERT( 0, 0 <= lbli && lbli < n, lbli );
00455
00456 AdjMap::iterator nodeit = scratchmap.find(nodei);
00457 MYASSERT( 0, nodeit != scratchmap.end(), "Must be there" );
00458 const EdgeSet &edgeset = nodeit->second;
00459
00460
00461 for( EdgeSet::iterator et = edgeset.begin(); et != edgeset.end(); et++ )
00462 {
00463 int nodej = *et;
00464 MYASSERT( 0, 0 <= nodej && nodej < n, "" );
00465 AdjMap::iterator nbrit = scratchmap.find(nodej);
00466 MYASSERT( 0, nbrit != scratchmap.end(), "Must be there" );
00467 int lblj = labels[nodej];
00468 if( lblj >= 0 )
00469 {
00470
00471 MYASSERT( 0, 0 <= lblj && lblj < n, "" );
00472 MYDBG( 0, "\t\t\tNbr "<<nodej<<" already labeled "<<lblj );
00473 }
00474 else
00475 {
00476
00477 MYASSERT( 0, lblj < 0, "Must be unlabeled" );
00478 lblj = labels[nodej] = nextlabel++;
00479 MYDBG( 0, "\t\tLabeled nbr "<<nodej<<" with "<<lblj );
00480 scratchlabels.push( SLElem(lblj, nodej) );
00481 }
00482 }
00483
00484
00485 for( EdgeSet::iterator et = edgeset.begin(); et != edgeset.end(); et++ )
00486 {
00487 int nodej = *et;
00488 MYASSERT( 0, 0 <= nodej && nodej < n, "" );
00489 int lblj = labels[nodej];
00490 MYASSERT( 0, 0 <= lblj && lblj < n, "Must be labeled by now" );
00491
00492 AdjMap::iterator nbrit = scratchmap.find(nodej);
00493 MYASSERT( 0, nbrit != scratchmap.end(), "Must be there" );
00494
00495 EdgeSet &edgeset = nbrit->second;
00496 const EdgeSet::iterator &seti = edgeset.find(nodei);
00497 MYASSERT(0, seti !=edgeset.end(), nodei<<" must be nbr of "<<nodej);
00498
00499 edgeset.erase(seti);
00500
00501 scratchnedges -= 2;
00502 }
00503
00504
00505 scratchmap.erase( nodeit );
00506 }
00507
00508 MYDBG( 0, "Phase 2: end nextlabel "<<nextlabel<<endl );
00509 }
00510
00511
00512
00513
00514 void BWGraph::relabel_phase3( int n, int &nextlabel, Labels &labels,
00515 AdjMap &scratchmap, int &scratchnedges ) const
00516 {
00517 MYDBG( 0, "-------------------------" );
00518 MYDBG( 0, "Phase 3: begin nextlabel "<<nextlabel );
00519 MYDBG( 0, "-------------------------" );
00520 for( int i = 0; i < n; i++ )
00521 {
00522 int lbli = labels[i];
00523 if( lbli < 0 )
00524 {
00525 MYASSERT( 0, scratchmap[i].size() == 0, "" );
00526 lbli = labels[i] = nextlabel++;
00527 scratchmap.erase( i );
00528 MYDBG( 0, "\t\t\tLabeled island "<<i<<" with "<<lbli );
00529 }
00530 }
00531 MYDBG( 0, "Phase 3: end nextlabel "<<nextlabel<<endl );
00532 }
00533
00534
00535
00536
00537 void BWGraph::relabel( Labels &labels ) const
00538 {
00539 int n = getnumnodes();
00540 initlabels( labels, n, false );
00541
00542 AdjMap scratchmap(adjmap);
00543 int scratchnedges = getnumedges();
00544
00545 int nextlabel = 0;
00546
00547 bool dophase1 = getenv("DOPHASE1")&&(atoi(getenv("DOPHASE1"))>0);
00548 if( !dophase1 ) MYDBG(0,"Skipping phase 1");
00549 else relabel_phase1( n, nextlabel, labels, scratchmap, scratchnedges );
00550
00551 relabel_phase2( n, nextlabel, labels, scratchmap, scratchnedges );
00552
00553 relabel_phase3( n, nextlabel, labels, scratchmap, scratchnedges );
00554
00555 MYASSERT( 0, ispermutation( labels, n ), "" );
00556 MYASSERT( 0, nextlabel == n, "" );
00557 MYASSERT( 0, scratchnedges == 0, "" );
00558
00559
00560
00561 }
00562
00563
00564
00565
00566 void BWGraph::addnode( int i )
00567 {
00568 adjmap[i].clear();
00569 }
00570
00571
00572
00573
00574 void BWGraph::addedge( int i, int j, bool duplex )
00575 {
00576 if( i != j )
00577 {
00578 adjmap[i].insert(j); nedges++;
00579 if( duplex ) { adjmap[j].insert(i); nedges++; }
00580 }
00581 }
00582
00583
00584
00585
00586 int BWGraph::getnumleaves( void )
00587 {
00588 int nleaves = 0;
00589 int n = getnumnodes();
00590 for( AdjMap::const_iterator it = adjmap.begin();
00591 it != adjmap.end(); it++ )
00592 {
00593 int li = it->first;
00594 if( isleaf( adjmap, n, li ) )
00595 {
00596 nleaves++;
00597 }
00598 }
00599 return nleaves;
00600 }
00601
00602
00603
00604
00605 void BWGraph::printdegreedistribution( ostream &out ) const
00606 {
00607 map<int,int> degrees;
00608 for( AdjMap::const_iterator it = adjmap.begin();
00609 it != adjmap.end(); it++ )
00610 {
00611 const EdgeSet &edgeset = it->second;
00612 int degree = edgeset.size();
00613
00614 if( degrees.find(degree) == degrees.end() )
00615 {
00616 degrees[degree] = 1;
00617 }
00618 else
00619 {
00620 degrees[degree]++;
00621 }
00622 }
00623 for( map<int,int>::const_iterator dit = degrees.begin();
00624 dit != degrees.end(); dit++ )
00625 {
00626 int degree = dit->first;
00627 int count = dit->second;
00628 out << "DEGREEDIST:"
00629 << " " << degree << " " << count
00630 << " " << (count*1.0/getnumnodes())
00631 << endl;
00632 }
00633 }
00634
00635
00636
00637
00638
00639 void BWGraph::readfile( const char *fname )
00640 {
00641 int nnodes = -1;
00642 int nedges = -1;
00643 FILE *fp = fopen( fname, "r" );
00644 char aline[1000];
00645 MYASSERT( 0, fp, "Need \""<<fname<<"\" to read graph" );
00646 Labels inputperm;
00647 while( fgets( aline, sizeof(aline), fp ) )
00648 {
00649 int in1 = 0, in2 = 0;
00650 int nscanned = sscanf( aline, "%d %d", &in1, &in2 );
00651 MYASSERT( 0, nscanned == 2, "Expected 2 integers" );
00652 MYASSERT( 0, 0 <= in1 && 0 <= in2, "Expected +ve integers" );
00653 if( nnodes < 0 )
00654 {
00655 nnodes = in1;
00656 nedges = in2;
00657
00658 bool randomizeinput=getenv("INPUTRAND")&&atoi(getenv("INPUTRAND"))>0;
00659 if( randomizeinput ) randpermutation( inputperm, in1 );
00660 else initlabels( inputperm, in1, true );
00661
00662 for( int i = 0; i < nnodes; i++ )
00663 {
00664 addnode( i );
00665 }
00666 }
00667 else
00668 {
00669 MYASSERT( 0, 0 <= in1 && in1 < nnodes, "" );
00670 MYASSERT( 0, 0 <= in2 && in2 < nnodes, "" );
00671 MYASSERT( 0, in1 != in2, "" );
00672 in1 = inputperm[in1];
00673 in2 = inputperm[in2];
00674 addedge( in1, in2, true );
00675 }
00676 }
00677 fclose(fp);
00678 }
00679
00680
00681 #ifndef TESTMAIN
00682 #define TESTMAIN main
00683 #endif
00684 int TESTMAIN( int ac, char *av[] )
00685 {
00686 MYASSERT( 0, ac >= 2, "Supply graph file name as the only argument" );
00687 const char *fname = av[1];
00688
00689 BWGraph bwg;
00690
00691 bwg.readfile( fname );
00692 cout << "GRAPHINFO:"
00693 << " #nodes= " << bwg.getnumnodes()
00694 << " #edges= " << bwg.getnumedges()
00695 << " #leaves= " << bwg.getnumleaves()
00696 << endl;
00697 bwg.printdegreedistribution( cout );
00698
00699 Labels identityperm;
00700 initlabels( identityperm, bwg.getnumnodes(), true );
00701 int idbw = bwg.bandwidth(identityperm);
00702 cout << "InputBW= "<< idbw << endl;
00703
00704 Labels finalperm;
00705 bwg.relabel( finalperm );
00706 bwg.printdiffs( finalperm );
00707 printpermutation( cout, finalperm );
00708 int minbw = bwg.bandwidth(finalperm);
00709 cout << "FinalBW= "<< minbw << endl;
00710 return 0;
00711 }
00712
00713