00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include "ColPackHeaders.h"
00022
00023 using namespace std;
00024
00025 namespace ColPack
00026 {
00027
00028 int GraphOrdering::OrderVertices(string s_OrderingVariant)
00029 {
00030 s_OrderingVariant = toUpper(s_OrderingVariant);
00031
00032 if((s_OrderingVariant.compare("NATURAL") == 0))
00033 {
00034 return(NaturalOrdering());
00035 }
00036 else
00037 if((s_OrderingVariant.compare("LARGEST_FIRST") == 0))
00038 {
00039 return(LargestFirstOrdering());
00040 }
00041 else
00042 if((s_OrderingVariant.compare("DYNAMIC_LARGEST_FIRST") == 0))
00043 {
00044 return(DynamicLargestFirstOrdering());
00045 }
00046 else
00047 if((s_OrderingVariant.compare("DISTANCE_TWO_LARGEST_FIRST") == 0))
00048 {
00049 return(DistanceTwoLargestFirstOrdering());
00050 }
00051 else
00052 if((s_OrderingVariant.compare("SMALLEST_LAST") == 0))
00053 {
00054 return(SmallestLastOrdering());
00055 }
00056 else
00057 if((s_OrderingVariant.compare("DISTANCE_TWO_SMALLEST_LAST") == 0))
00058 {
00059 return(DistanceTwoSmallestLastOrdering());
00060 }
00061 else
00062 if((s_OrderingVariant.compare("INCIDENCE_DEGREE") == 0))
00063 {
00064 return(IncidenceDegreeOrdering());
00065 }
00066 else
00067 if((s_OrderingVariant.compare("DISTANCE_TWO_INCIDENCE_DEGREE") == 0))
00068 {
00069 return(DistanceTwoIncidenceDegreeOrdering());
00070 }
00071 else
00072 if((s_OrderingVariant.compare("RANDOM") == 0))
00073 {
00074 return(RandomOrdering());
00075 }
00076 else
00077 {
00078 cerr<<endl;
00079 cerr<<"Unknown Ordering Method: "<<s_OrderingVariant;
00080 cerr<<endl;
00081 }
00082
00083 return(_TRUE);
00084 }
00085
00086
00087 int GraphOrdering::CheckVertexOrdering(string s_VertexOrderingVariant)
00088 {
00089 if(m_s_VertexOrderingVariant.compare(s_VertexOrderingVariant) == 0)
00090 {
00091 return(_TRUE);
00092 }
00093
00094 if(m_s_VertexOrderingVariant.compare("ALL") != 0)
00095 {
00096 m_s_VertexOrderingVariant = s_VertexOrderingVariant;
00097 }
00098
00099 return(_FALSE);
00100 }
00101
00102
00103 GraphOrdering::GraphOrdering() :GraphInputOutput()
00104 {
00105 Clear();
00106 }
00107
00108
00109
00110 GraphOrdering::~GraphOrdering()
00111 {
00112 Clear();
00113 }
00114
00115
00116
00117 void GraphOrdering::Clear()
00118 {
00119 m_d_OrderingTime = _UNKNOWN;
00120
00121 m_s_VertexOrderingVariant.clear();
00122 m_vi_OrderedVertices.clear();
00123
00124 GraphCore::Clear();
00125
00126 return;
00127 }
00128
00129
00130
00131 int GraphOrdering::NaturalOrdering()
00132 {
00133 if(CheckVertexOrdering("NATURAL") == _TRUE)
00134 {
00135 return(_TRUE);
00136 }
00137
00138 int i;
00139
00140 int i_VertexCount;
00141
00142 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00143
00144 m_vi_OrderedVertices.clear();
00145
00146 m_vi_OrderedVertices.resize((unsigned) i_VertexCount);
00147
00148 for(i=0; i<i_VertexCount; i++)
00149 {
00150 m_vi_OrderedVertices[i] = i;
00151 }
00152
00153 return(_TRUE);
00154 }
00155
00156 int GraphOrdering::RandomOrdering()
00157 {
00158 if(CheckVertexOrdering("RANDOM") == _TRUE)
00159 {
00160 return(_TRUE);
00161 }
00162
00163 m_s_VertexOrderingVariant = "RANDOM";
00164
00165 int i;
00166
00167 int i_VertexCount;
00168
00169 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00170
00171 m_vi_OrderedVertices.clear();
00172
00173 m_vi_OrderedVertices.resize((unsigned) i_VertexCount);
00174
00175
00176 for(unsigned int i = 0; i<i_VertexCount; i++) {
00177 m_vi_OrderedVertices[i] = i;
00178 }
00179
00180 randomOrdering(m_vi_OrderedVertices);
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204 return(_TRUE);
00205 }
00206
00207 int GraphOrdering::ColoringBasedOrdering(vector<int> &vi_VertexColors)
00208 {
00209
00210 m_s_VertexOrderingVariant = "COLORING_BASED";
00211
00212 int i, j;
00213
00214 int i_VertexCount;
00215
00216 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00217
00218 m_vi_OrderedVertices.clear();
00219
00220 m_vi_OrderedVertices.resize((unsigned) i_VertexCount);
00221
00222 vector< vector <int> > vvi_ColorGroups;
00223
00224 vvi_ColorGroups.clear();
00225 vvi_ColorGroups.resize((unsigned) i_VertexCount);
00226
00227 int i_HighestColor = _FALSE;
00228
00229
00230 for(int i=0; i < vi_VertexColors.size(); i++)
00231 {
00232 vvi_ColorGroups[vi_VertexColors[i]].push_back(i);
00233
00234 if(i_HighestColor < vi_VertexColors[i])
00235 i_HighestColor = vi_VertexColors[i];
00236 }
00237
00238
00239 int count = i_VertexCount;
00240
00241 for(i = 0; i< STEP_UP(i_HighestColor); i++)
00242 {
00243 if(vvi_ColorGroups[i].size() > 0)
00244 {
00245 for(j = vvi_ColorGroups[i].size() - 1; j >= 0; j--)
00246 {
00247 m_vi_OrderedVertices[count - 1] = vvi_ColorGroups[i][j];
00248 count--;
00249 }
00250
00251 vvi_ColorGroups[i].clear();
00252 }
00253 }
00254
00255 if(count!=0)
00256 {
00257 cout << "TROUBLE!!!"<<endl;
00258 Pause();
00259 }
00260
00261 vvi_ColorGroups.clear();
00262 return(_TRUE);
00263 }
00264
00265
00266
00267 int GraphOrdering::LargestFirstOrdering()
00268 {
00269 if(CheckVertexOrdering("LARGEST FIRST") == _TRUE)
00270 {
00271 return(_TRUE);
00272 }
00273
00274 int i, j;
00275
00276 int i_VertexCount;
00277
00278 int i_VertexDegree, i_VertexDegreeCount;
00279
00280 vector< vector<int> > vvi_GroupedVertexDegree;
00281
00282 m_i_MaximumVertexDegree = _FALSE;
00283
00284 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00285
00286 vvi_GroupedVertexDegree.resize((unsigned) i_VertexCount);
00287
00288 for(i=0; i<i_VertexCount; i++)
00289 {
00290 i_VertexDegree = m_vi_Vertices[STEP_UP(i)] - m_vi_Vertices[i];
00291
00292 vvi_GroupedVertexDegree[i_VertexDegree].push_back(i);
00293
00294 if(m_i_MaximumVertexDegree < i_VertexDegree)
00295 {
00296 m_i_MaximumVertexDegree = i_VertexDegree;
00297 }
00298 }
00299
00300
00301 m_vi_OrderedVertices.clear();
00302 m_vi_OrderedVertices.reserve((unsigned) i_VertexCount);
00303
00304 for(i=m_i_MaximumVertexDegree; i>=0; i--)
00305 {
00306 i_VertexDegreeCount = (signed) vvi_GroupedVertexDegree[i].size();
00307
00308 for(j=0; j<i_VertexDegreeCount; j++)
00309 {
00310 m_vi_OrderedVertices.push_back(vvi_GroupedVertexDegree[i][j]);
00311 }
00312 }
00313
00314
00315 vvi_GroupedVertexDegree.clear();
00316 return(_TRUE);
00317 }
00318
00319 int GraphOrdering::printVertexEdgeMap(vector< vector< pair< int, int> > > &vvpii_VertexEdgeMap) {
00320 ostringstream oout;
00321 string tempS;
00322 cout<<"vvpii_VertexEdgeMap.size() = "<<vvpii_VertexEdgeMap.size()<<endl;
00323
00324 for(int i=0; i<vvpii_VertexEdgeMap.size(); i++) {
00325 cout<<'['<<setw(4)<<i<<']';
00326 for(int j=0; j< vvpii_VertexEdgeMap[i].size(); j++) {
00327 oout.str("");
00328 oout << '(' << vvpii_VertexEdgeMap[i][j].first << ", " << vvpii_VertexEdgeMap[i][j].second << ')';
00329 tempS = oout.str();
00330 cout<<setw(10)<<tempS;
00331 if(j%5 == 4 && j != vvpii_VertexEdgeMap[i].size() - 1) cout<<endl<<setw(6)<<' ';
00332 }
00333 cout<<endl;
00334 }
00335
00336 cout<<"*****************"<<endl;
00337
00338 return _TRUE;
00339 }
00340
00341 struct less_degree_than {
00342 bool operator()(const pair< int, int> *a, const pair< int, int> *b) const {
00343
00344 if(a->second < b->second) return true;
00345 if(a->second > b->second) return false;
00346
00347
00348 return (a->first > b->first);
00349 }
00350 };
00351
00352
00353 int GraphOrdering::DynamicLargestFirstOrdering() {
00354 if(CheckVertexOrdering("DYNAMIC LARGEST FIRST") == _TRUE)
00355 {
00356 return(_TRUE);
00357 }
00358
00359 int i, u, l;
00360
00361 int i_HighestInducedVertexDegree;
00362
00363 int i_VertexCount, i_InducedVertexDegree;
00364
00365 int i_InducedVertexDegreeCount;
00366
00367 int i_SelectedVertex, i_SelectedVertexCount;
00368
00369 vector<int> vi_InducedVertexDegree;
00370
00371 vector< vector <int> > vvi_GroupedInducedVertexDegree;
00372
00373 vector< int > vi_VertexLocation;
00374
00375 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00376
00377 vi_InducedVertexDegree.clear();
00378 vi_InducedVertexDegree.reserve((unsigned) i_VertexCount);
00379
00380 vvi_GroupedInducedVertexDegree.clear();
00381 vvi_GroupedInducedVertexDegree.resize((unsigned) i_VertexCount);
00382
00383 vi_VertexLocation.clear();
00384 vi_VertexLocation.reserve((unsigned) i_VertexCount);
00385
00386 i_SelectedVertex = _UNKNOWN;
00387
00388 i_HighestInducedVertexDegree = _FALSE;
00389
00390 for(i=0; i<i_VertexCount; i++)
00391 {
00392
00393 i_InducedVertexDegree = m_vi_Vertices[STEP_UP(i)] - m_vi_Vertices[i];
00394
00395
00396 vi_InducedVertexDegree.push_back(i_InducedVertexDegree);
00397
00398
00399
00400 vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].push_back(i);
00401
00402
00403 vi_VertexLocation.push_back(vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].size() - 1);
00404
00405
00406 if(i_HighestInducedVertexDegree < i_InducedVertexDegree)
00407 {
00408 i_HighestInducedVertexDegree = i_InducedVertexDegree;
00409 }
00410 }
00411
00412 m_vi_OrderedVertices.clear();
00413 m_vi_OrderedVertices.reserve((unsigned) i_VertexCount);
00414
00415 i_SelectedVertexCount = _FALSE;
00416
00417
00418
00419 while(i_SelectedVertexCount < i_VertexCount)
00420 {
00421
00422 for(i = i_HighestInducedVertexDegree; i >= 0; i--)
00423 {
00424 i_InducedVertexDegreeCount = (signed) vvi_GroupedInducedVertexDegree[i].size();
00425
00426 if(i_InducedVertexDegreeCount != _FALSE)
00427 {
00428 i_SelectedVertex = vvi_GroupedInducedVertexDegree[i].back();
00429
00430 vvi_GroupedInducedVertexDegree[i].pop_back();
00431 break;
00432 }
00433 else
00434 i_HighestInducedVertexDegree--;
00435 }
00436
00437
00438
00439 for(i=m_vi_Vertices[i_SelectedVertex]; i<m_vi_Vertices[STEP_UP(i_SelectedVertex)]; i++)
00440 {
00441 u = m_vi_Edges[i];
00442
00443 if(vi_InducedVertexDegree[u] == _UNKNOWN)
00444 {
00445 continue;
00446 }
00447
00448
00449 if(vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].size() > 1)
00450 {
00451 l = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].back();
00452
00453 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]][vi_VertexLocation[u]] = l;
00454
00455
00456 vi_VertexLocation[l] = vi_VertexLocation[u];
00457 }
00458
00459
00460 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].pop_back();
00461
00462
00463 vi_InducedVertexDegree[u]--;
00464
00465
00466 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].push_back(u);
00467
00468
00469 vi_VertexLocation[u] = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].size() - 1;
00470 }
00471
00472
00473 vi_InducedVertexDegree[i_SelectedVertex] = _UNKNOWN;
00474
00475
00476 m_vi_OrderedVertices.push_back(i_SelectedVertex);
00477
00478
00479 i_SelectedVertexCount = STEP_UP(i_SelectedVertexCount);
00480 }
00481
00482
00483 vi_InducedVertexDegree.clear();
00484 vi_VertexLocation.clear();
00485 vvi_GroupedInducedVertexDegree.clear();
00486
00487 return(_TRUE);
00488 }
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534
00535
00536
00537
00538
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570 int GraphOrdering::DistanceTwoLargestFirstOrdering()
00571 {
00572 if(CheckVertexOrdering("DISTANCE TWO LARGEST FIRST") == _TRUE)
00573 {
00574 return(_TRUE);
00575 }
00576
00577 int i, j, k;
00578
00579 int i_VertexCount;
00580
00581 int i_HighestDistanceTwoVertexDegree;
00582
00583 int i_DistanceTwoVertexDegree, i_DistanceTwoVertexDegreeCount;
00584
00585 vector<int> vi_IncludedVertices;
00586
00587 vector< vector<int> > v2i_GroupedDistanceTwoVertexDegree;
00588
00589 i_HighestDistanceTwoVertexDegree = _FALSE;
00590
00591 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00592
00593 v2i_GroupedDistanceTwoVertexDegree.clear();
00594 v2i_GroupedDistanceTwoVertexDegree.resize((unsigned) i_VertexCount);
00595
00596 vi_IncludedVertices.clear();
00597 vi_IncludedVertices.resize((unsigned) i_VertexCount, _UNKNOWN);
00598
00599 for(i=0; i<i_VertexCount; i++)
00600 {
00601 vi_IncludedVertices[i] = i;
00602
00603 i_DistanceTwoVertexDegree = _FALSE;
00604
00605 for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
00606 {
00607 if(vi_IncludedVertices[m_vi_Edges[j]] != i)
00608 {
00609 i_DistanceTwoVertexDegree++;
00610
00611 vi_IncludedVertices[m_vi_Edges[j]] = i;
00612 }
00613
00614 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
00615 {
00616 if(vi_IncludedVertices[m_vi_Edges[k]] != i)
00617 {
00618 i_DistanceTwoVertexDegree++;
00619
00620 vi_IncludedVertices[m_vi_Edges[k]] = i;
00621 }
00622 }
00623 }
00624
00625 v2i_GroupedDistanceTwoVertexDegree[i_DistanceTwoVertexDegree].push_back(i);
00626
00627 if(i_HighestDistanceTwoVertexDegree < i_DistanceTwoVertexDegree)
00628 {
00629 i_HighestDistanceTwoVertexDegree = i_DistanceTwoVertexDegree;
00630 }
00631 }
00632
00633 m_vi_OrderedVertices.clear();
00634 m_vi_OrderedVertices.reserve((unsigned) i_VertexCount);
00635
00636 for(i=i_HighestDistanceTwoVertexDegree; i>=0; i--)
00637 {
00638 i_DistanceTwoVertexDegreeCount = (signed) v2i_GroupedDistanceTwoVertexDegree[i].size();
00639
00640 for(j=0; j<i_DistanceTwoVertexDegreeCount; j++)
00641 {
00642 m_vi_OrderedVertices.push_back(v2i_GroupedDistanceTwoVertexDegree[i][j]);
00643 }
00644 }
00645
00646 vi_IncludedVertices.clear();
00647 v2i_GroupedDistanceTwoVertexDegree.clear();
00648
00649 return(_TRUE);
00650 }
00651
00652
00653
00654 int GraphOrdering::SmallestLastOrdering()
00655 {
00656 if(CheckVertexOrdering("SMALLEST LAST") == _TRUE)
00657 {
00658 return(_TRUE);
00659 }
00660
00661 int i, u, l;
00662
00663 int i_HighestInducedVertexDegree;
00664
00665 int i_VertexCount, i_InducedVertexDegree;
00666
00667 int i_VertexCountMinus1;
00668
00669 int i_InducedVertexDegreeCount;
00670
00671 int i_SelectedVertex, i_SelectedVertexCount;
00672
00673 vector < int > vi_InducedVertexDegree;
00674
00675 vector< vector< int > > vvi_GroupedInducedVertexDegree;
00676
00677 vector< int > vi_VertexLocation;
00678
00679 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00680
00681 i_VertexCountMinus1 = i_VertexCount - 1;
00682
00683 vi_InducedVertexDegree.clear();
00684 vi_InducedVertexDegree.reserve((unsigned) i_VertexCount);
00685
00686 vvi_GroupedInducedVertexDegree.clear();
00687 vvi_GroupedInducedVertexDegree.resize((unsigned) i_VertexCount);
00688
00689 vi_VertexLocation.clear();
00690 vi_VertexLocation.reserve((unsigned) i_VertexCount);
00691
00692 i_SelectedVertex = _UNKNOWN;
00693
00694 i_HighestInducedVertexDegree = _FALSE;
00695
00696
00697 for(i=0; i<i_VertexCount; i++)
00698 {
00699
00700 i_InducedVertexDegree = m_vi_Vertices[STEP_UP(i)] - m_vi_Vertices[i];
00701
00702
00703 vi_InducedVertexDegree.push_back(i_InducedVertexDegree);
00704
00705
00706
00707 vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].push_back(i);
00708
00709
00710 vi_VertexLocation.push_back(vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].size() - 1);
00711
00712
00713 if(i_HighestInducedVertexDegree < i_InducedVertexDegree)
00714 {
00715 i_HighestInducedVertexDegree = i_InducedVertexDegree;
00716 }
00717 }
00718
00719 m_vi_OrderedVertices.clear();
00720 m_vi_OrderedVertices.resize((unsigned) i_VertexCount, _UNKNOWN);
00721
00722 i_SelectedVertexCount = _FALSE;
00723 int iMin = 1;
00724
00725
00726
00727 while(i_SelectedVertexCount < i_VertexCount)
00728 {
00729 if(iMin != 0 && vvi_GroupedInducedVertexDegree[iMin - 1].size() != _FALSE)
00730 iMin--;
00731
00732
00733 for(i=iMin; i<STEP_UP(i_HighestInducedVertexDegree); i++)
00734 {
00735 i_InducedVertexDegreeCount = (signed) vvi_GroupedInducedVertexDegree[i].size();
00736
00737 if(i_InducedVertexDegreeCount != _FALSE)
00738 {
00739 i_SelectedVertex = vvi_GroupedInducedVertexDegree[i].back();
00740
00741 vvi_GroupedInducedVertexDegree[i].pop_back();
00742 break;
00743 }
00744 else
00745 iMin++;
00746 }
00747
00748 for(i=m_vi_Vertices[i_SelectedVertex]; i<m_vi_Vertices[STEP_UP(i_SelectedVertex)]; i++)
00749 {
00750 u = m_vi_Edges[i];
00751
00752 if(vi_InducedVertexDegree[u] == _UNKNOWN)
00753 {
00754 continue;
00755 }
00756
00757
00758 if(vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].size() > 1)
00759 {
00760 l = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].back();
00761
00762 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]][vi_VertexLocation[u]] = l;
00763
00764
00765 vi_VertexLocation[l] = vi_VertexLocation[u];
00766 }
00767
00768 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].pop_back();
00769
00770
00771 vi_InducedVertexDegree[u]--;
00772
00773
00774 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].push_back(u);
00775
00776
00777 vi_VertexLocation[u] = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegree[u]].size() - 1;
00778 }
00779
00780
00781 vi_InducedVertexDegree[i_SelectedVertex] = _UNKNOWN;
00782
00783 m_vi_OrderedVertices[i_VertexCountMinus1 - i_SelectedVertexCount] = i_SelectedVertex;
00784
00785 i_SelectedVertexCount = STEP_UP(i_SelectedVertexCount);
00786 }
00787
00788
00789 vi_InducedVertexDegree.clear();
00790 vi_VertexLocation.clear();
00791 vvi_GroupedInducedVertexDegree.clear();
00792
00793 return(_TRUE);
00794 }
00795
00796 int GraphOrdering::DistanceTwoDynamicLargestFirstOrdering()
00797 {
00798 if(CheckVertexOrdering("DISTANCE TWO DYNAMIC LARGEST FIRST") == _TRUE)
00799 {
00800 return(_TRUE);
00801 }
00802
00803 int i, j, k, l, u, v;
00804
00805 int i_HighestInducedVertexDegree;
00806
00807 int i_VertexCount, i_InducedVertexDegree;
00808
00809 int i_InducedVertexDegreeCount;
00810
00811 int i_SelectedVertex, i_SelectedVertexCount;
00812
00813 vector < int > vi_IncludedVertices;
00814
00815 vector < int > vi_InducedVertexDegrees;
00816
00817 vector < vector < int > > vvi_GroupedInducedVertexDegree;
00818
00819 vector < int > vi_VertexLocations;
00820
00821 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00822
00823 vi_IncludedVertices.clear();
00824 vi_IncludedVertices.resize((unsigned) i_VertexCount, _UNKNOWN);
00825
00826 vi_InducedVertexDegrees.clear();
00827 vi_InducedVertexDegrees.reserve((unsigned) i_VertexCount);
00828
00829 vvi_GroupedInducedVertexDegree.clear();
00830 vvi_GroupedInducedVertexDegree.resize((unsigned) i_VertexCount);
00831
00832 vi_VertexLocations.clear();
00833 vi_VertexLocations.reserve((unsigned) i_VertexCount);
00834
00835
00836 i_SelectedVertex = _UNKNOWN;
00837
00838 i_HighestInducedVertexDegree = _FALSE;
00839
00840 for(i=0; i<i_VertexCount; i++)
00841 {
00842 vi_IncludedVertices[i] = i;
00843
00844 i_InducedVertexDegree = _FALSE;
00845
00846 for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
00847 {
00848 if(vi_IncludedVertices[m_vi_Edges[j]] != i)
00849 {
00850 i_InducedVertexDegree++;
00851
00852 vi_IncludedVertices[m_vi_Edges[j]] = i;
00853 }
00854
00855 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
00856 {
00857 if(vi_IncludedVertices[m_vi_Edges[k]] != i)
00858 {
00859 i_InducedVertexDegree++;
00860
00861 vi_IncludedVertices[m_vi_Edges[k]] = i;
00862 }
00863 }
00864 }
00865
00866 vi_InducedVertexDegrees.push_back(i_InducedVertexDegree);
00867
00868 vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].push_back(i);
00869
00870 vi_VertexLocations.push_back(vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].size() - 1);
00871
00872 if(i_HighestInducedVertexDegree < i_InducedVertexDegree)
00873 {
00874 i_HighestInducedVertexDegree = i_InducedVertexDegree;
00875 }
00876 }
00877
00878 m_vi_OrderedVertices.clear();
00879 m_vi_OrderedVertices.reserve((unsigned) i_VertexCount);
00880
00881 vi_IncludedVertices.assign((unsigned) i_VertexCount, _UNKNOWN);
00882
00883 i_SelectedVertexCount = _FALSE;
00884
00885 while(i_SelectedVertexCount < i_VertexCount)
00886 {
00887 for(i=i_HighestInducedVertexDegree; i >= 0; i--)
00888 {
00889 i_InducedVertexDegreeCount = (signed) vvi_GroupedInducedVertexDegree[i].size();
00890
00891 if(i_InducedVertexDegreeCount != _FALSE)
00892 {
00893 i_SelectedVertex = vvi_GroupedInducedVertexDegree[i].back();
00894 vvi_GroupedInducedVertexDegree[i].pop_back();
00895 break;
00896 }
00897 else
00898 i_HighestInducedVertexDegree--;
00899
00900 }
00901
00902 vi_IncludedVertices[i_SelectedVertex] = i_SelectedVertex;
00903
00904 for(i=m_vi_Vertices[i_SelectedVertex]; i<m_vi_Vertices[STEP_UP(i_SelectedVertex)]; i++)
00905 {
00906 u = m_vi_Edges[i];
00907
00908 if(vi_InducedVertexDegrees[u] == _UNKNOWN)
00909 {
00910 continue;
00911 }
00912
00913 if(vi_IncludedVertices[u] != i_SelectedVertex)
00914 {
00915
00916 if(vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].size() > 1)
00917 {
00918 l = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].back();
00919 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]][vi_VertexLocations[u]] = l;
00920 vi_VertexLocations[l] = vi_VertexLocations[u];
00921 }
00922
00923
00924 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].pop_back();
00925
00926
00927 vi_InducedVertexDegrees[u]--;
00928
00929
00930 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].push_back(u);
00931
00932
00933 vi_VertexLocations[u] = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].size() - 1;
00934
00935
00936 vi_IncludedVertices[u] = i_SelectedVertex;
00937 }
00938
00939 for(j=m_vi_Vertices[m_vi_Edges[i]]; j<m_vi_Vertices[STEP_UP(m_vi_Edges[i])]; j++)
00940 {
00941 v = m_vi_Edges[j];
00942
00943 if(vi_InducedVertexDegrees[v] == _UNKNOWN)
00944 {
00945 continue;
00946 }
00947
00948 if(vi_IncludedVertices[v] != i_SelectedVertex)
00949 {
00950
00951 if(vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].size() > 1)
00952 {
00953 l = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].back();
00954 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]][vi_VertexLocations[v]] = l;
00955 vi_VertexLocations[l] = vi_VertexLocations[v];
00956 }
00957
00958
00959 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].pop_back();
00960
00961
00962 vi_InducedVertexDegrees[v]--;
00963
00964
00965 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].push_back(v);
00966
00967
00968 vi_VertexLocations[v] = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].size() - 1;
00969
00970
00971 vi_IncludedVertices[v] = i_SelectedVertex;
00972 }
00973 }
00974 }
00975
00976 vi_InducedVertexDegrees[i_SelectedVertex] = _UNKNOWN;
00977 m_vi_OrderedVertices.push_back(i_SelectedVertex);
00978 i_SelectedVertexCount = STEP_UP(i_SelectedVertexCount);
00979 }
00980
00981 vi_IncludedVertices.clear();
00982 vi_InducedVertexDegrees.clear();
00983 vvi_GroupedInducedVertexDegree.clear();
00984 vi_VertexLocations.clear();
00985
00986 return(_TRUE);
00987 }
00988
00989
00990
00991 int GraphOrdering::DistanceTwoSmallestLastOrdering()
00992 {
00993 if(CheckVertexOrdering("DISTANCE TWO SMALLEST LAST") == _TRUE)
00994 {
00995 return(_TRUE);
00996 }
00997
00998 int i, j, k, l, u, v;
00999
01000 int i_HighestInducedVertexDegree;
01001
01002 int i_VertexCount, i_InducedVertexDegree;
01003
01004 int i_VertexCountMinus1;
01005
01006 int i_InducedVertexDegreeCount;
01007
01008 int i_SelectedVertex, i_SelectedVertexCount;
01009
01010 vector < int > vi_IncludedVertices;
01011
01012 vector < int > vi_InducedVertexDegrees;
01013
01014 vector < vector < int > > vvi_GroupedInducedVertexDegree;
01015
01016 vector < int > vi_VertexLocations;
01017
01018 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
01019 i_VertexCountMinus1 = i_VertexCount - 1;
01020
01021 vi_IncludedVertices.clear();
01022 vi_IncludedVertices.resize((unsigned) i_VertexCount, _UNKNOWN);
01023
01024 vi_InducedVertexDegrees.clear();
01025 vi_InducedVertexDegrees.reserve((unsigned) i_VertexCount);
01026
01027 vvi_GroupedInducedVertexDegree.clear();
01028 vvi_GroupedInducedVertexDegree.resize((unsigned) i_VertexCount);
01029
01030 vi_VertexLocations.clear();
01031 vi_VertexLocations.reserve((unsigned) i_VertexCount);
01032
01033
01034 i_SelectedVertex = _UNKNOWN;
01035
01036 i_HighestInducedVertexDegree = _FALSE;
01037
01038 for(i=0; i<i_VertexCount; i++)
01039 {
01040 vi_IncludedVertices[i] = i;
01041
01042 i_InducedVertexDegree = _FALSE;
01043
01044 for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
01045 {
01046 if(vi_IncludedVertices[m_vi_Edges[j]] != i)
01047 {
01048 i_InducedVertexDegree++;
01049
01050 vi_IncludedVertices[m_vi_Edges[j]] = i;
01051 }
01052
01053 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
01054 {
01055 if(vi_IncludedVertices[m_vi_Edges[k]] != i)
01056 {
01057 i_InducedVertexDegree++;
01058
01059 vi_IncludedVertices[m_vi_Edges[k]] = i;
01060 }
01061 }
01062 }
01063
01064 vi_InducedVertexDegrees.push_back(i_InducedVertexDegree);
01065
01066 vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].push_back(i);
01067
01068 vi_VertexLocations.push_back(vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].size() - 1);
01069
01070 if(i_HighestInducedVertexDegree < i_InducedVertexDegree)
01071 {
01072 i_HighestInducedVertexDegree = i_InducedVertexDegree;
01073 }
01074 }
01075
01076 m_vi_OrderedVertices.clear();
01077 m_vi_OrderedVertices.resize((unsigned) i_VertexCount, _UNKNOWN);
01078
01079 vi_IncludedVertices.assign((unsigned) i_VertexCount, _UNKNOWN);
01080
01081 i_SelectedVertexCount = _FALSE;
01082
01083 int iMin = 1;
01084
01085 while(i_SelectedVertexCount < i_VertexCount)
01086 {
01087 if(iMin != 0 && vvi_GroupedInducedVertexDegree[iMin -1].size() != _FALSE)
01088 iMin--;
01089
01090 for(i= iMin; i < STEP_UP(i_HighestInducedVertexDegree); i++)
01091 {
01092 i_InducedVertexDegreeCount = (signed) vvi_GroupedInducedVertexDegree[i].size();
01093
01094 if(i_InducedVertexDegreeCount != _FALSE)
01095 {
01096 i_SelectedVertex = vvi_GroupedInducedVertexDegree[i].back();
01097 vvi_GroupedInducedVertexDegree[i].pop_back();
01098 break;
01099 }
01100 else
01101 iMin++;
01102 }
01103
01104 vi_IncludedVertices[i_SelectedVertex] = i_SelectedVertex;
01105
01106 for(i=m_vi_Vertices[i_SelectedVertex]; i<m_vi_Vertices[STEP_UP(i_SelectedVertex)]; i++)
01107 {
01108 u = m_vi_Edges[i];
01109
01110 if(vi_InducedVertexDegrees[u] == _UNKNOWN)
01111 {
01112 continue;
01113 }
01114
01115 if(vi_IncludedVertices[u] != i_SelectedVertex)
01116 {
01117
01118 if(vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].size() > 1)
01119 {
01120 l = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].back();
01121 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]][vi_VertexLocations[u]] = l;
01122 vi_VertexLocations[l] = vi_VertexLocations[u];
01123 }
01124
01125
01126 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].pop_back();
01127
01128
01129 vi_InducedVertexDegrees[u]--;
01130
01131
01132 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].push_back(u);
01133
01134
01135 vi_VertexLocations[u] = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].size() - 1;
01136
01137
01138 vi_IncludedVertices[u] = i_SelectedVertex;
01139 }
01140
01141 for(j=m_vi_Vertices[m_vi_Edges[i]]; j<m_vi_Vertices[STEP_UP(m_vi_Edges[i])]; j++)
01142 {
01143 v = m_vi_Edges[j];
01144
01145 if(vi_InducedVertexDegrees[v] == _UNKNOWN)
01146 {
01147 continue;
01148 }
01149
01150 if(vi_IncludedVertices[v] != i_SelectedVertex)
01151 {
01152
01153 if(vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].size() > 1)
01154 {
01155 l = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].back();
01156 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]][vi_VertexLocations[v]] = l;
01157 vi_VertexLocations[l] = vi_VertexLocations[v];
01158 }
01159
01160
01161 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].pop_back();
01162
01163
01164 vi_InducedVertexDegrees[v]--;
01165
01166
01167 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].push_back(v);
01168
01169
01170 vi_VertexLocations[v] = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].size() - 1;
01171
01172
01173 vi_IncludedVertices[v] = i_SelectedVertex;
01174 }
01175 }
01176 }
01177
01178 vi_InducedVertexDegrees[i_SelectedVertex] = _UNKNOWN;
01179
01180 m_vi_OrderedVertices[i_VertexCountMinus1 - i_SelectedVertexCount] = i_SelectedVertex;
01181 i_SelectedVertexCount = STEP_UP(i_SelectedVertexCount);
01182 }
01183
01184 vi_IncludedVertices.clear();
01185 vi_InducedVertexDegrees.clear();
01186 vvi_GroupedInducedVertexDegree.clear();
01187 vi_VertexLocations.clear();
01188
01189 return(_TRUE);
01190 }
01191
01192
01193
01194 int GraphOrdering::IncidenceDegreeOrdering()
01195 {
01196 if(CheckVertexOrdering("INCIDENCE DEGREE") == _TRUE)
01197 {
01198 return(_TRUE);
01199 }
01200
01201 int i, u, v, l;
01202
01203 int i_HighestDegreeVertex, i_MaximumVertexDegree;
01204
01205 int i_VertexCount, i_VertexDegree;
01206
01207 int i_IncidenceVertexDegree, i_IncidenceVertexDegreeCount;
01208
01209 int i_SelectedVertex, i_SelectedVertexCount;
01210
01211 vector< int > vi_IncidenceVertexDegree;
01212
01213 vector< vector< int > > vvi_GroupedIncidenceVertexDegree;
01214
01215 vector< int > vi_VertexLocation;
01216
01217 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
01218
01219 vi_IncidenceVertexDegree.clear();
01220 vi_IncidenceVertexDegree.reserve((unsigned) i_VertexCount);
01221
01222 vvi_GroupedIncidenceVertexDegree.clear();
01223 vvi_GroupedIncidenceVertexDegree.resize((unsigned) i_VertexCount);
01224
01225 vi_VertexLocation.clear();
01226 vi_VertexLocation.reserve((unsigned) i_VertexCount);
01227
01228 i_HighestDegreeVertex = i_MaximumVertexDegree = _UNKNOWN;
01229
01230 i_SelectedVertex = _UNKNOWN;
01231
01232 i_IncidenceVertexDegree = _FALSE;
01233
01234
01235
01236 vvi_GroupedIncidenceVertexDegree[i_IncidenceVertexDegree].reserve((unsigned) i_VertexCount);
01237
01238
01239 for(i=0; i<i_VertexCount; i++)
01240 {
01241
01242 vi_IncidenceVertexDegree.push_back(i_IncidenceVertexDegree);
01243
01244
01245 vvi_GroupedIncidenceVertexDegree[i_IncidenceVertexDegree].push_back(i);
01246
01247
01248 vi_VertexLocation.push_back(vvi_GroupedIncidenceVertexDegree[i_IncidenceVertexDegree].size() - 1);
01249
01250
01251 i_VertexDegree = m_vi_Vertices[STEP_UP(i)] - m_vi_Vertices[i];
01252
01253
01254 if(i_MaximumVertexDegree < i_VertexDegree)
01255 {
01256 i_MaximumVertexDegree = i_VertexDegree;
01257
01258 i_HighestDegreeVertex = i;
01259 }
01260 }
01261
01262
01263 m_vi_OrderedVertices.clear();
01264 m_vi_OrderedVertices.reserve((unsigned) i_VertexCount);
01265
01266 i_SelectedVertexCount = _FALSE;
01267
01268
01269 l = vvi_GroupedIncidenceVertexDegree[i_IncidenceVertexDegree].size() - 1;
01270 v = vvi_GroupedIncidenceVertexDegree[i_IncidenceVertexDegree][l];
01271
01272 u = vvi_GroupedIncidenceVertexDegree[i_IncidenceVertexDegree][vi_VertexLocation[i_HighestDegreeVertex]];
01273
01274 swap(vvi_GroupedIncidenceVertexDegree[i_IncidenceVertexDegree][vi_VertexLocation[i_HighestDegreeVertex]], vvi_GroupedIncidenceVertexDegree[i_IncidenceVertexDegree][l]);
01275 swap(vi_VertexLocation[v], vi_VertexLocation[u]);
01276
01277 int iMax = i_MaximumVertexDegree - 1;
01278
01279
01280 while(i_SelectedVertexCount < i_VertexCount)
01281 {
01282
01283 if(iMax != i_MaximumVertexDegree && vvi_GroupedIncidenceVertexDegree[iMax + 1].size() != _FALSE)
01284 iMax++;
01285
01286
01287 for(i=iMax; i>=0; i--)
01288 {
01289 i_IncidenceVertexDegreeCount = (signed) vvi_GroupedIncidenceVertexDegree[i].size();
01290
01291 if(i_IncidenceVertexDegreeCount != _FALSE)
01292 {
01293 i_SelectedVertex = vvi_GroupedIncidenceVertexDegree[i].back();
01294
01295 vvi_GroupedIncidenceVertexDegree[i].pop_back();
01296 break;
01297 }
01298 else
01299 iMax--;
01300 }
01301
01302
01303
01304 for(i=m_vi_Vertices[i_SelectedVertex]; i<m_vi_Vertices[STEP_UP(i_SelectedVertex)]; i++)
01305 {
01306 u = m_vi_Edges[i];
01307
01308 if(vi_IncidenceVertexDegree[u] == _UNKNOWN)
01309 {
01310 continue;
01311 }
01312
01313
01314 if(vvi_GroupedIncidenceVertexDegree[vi_IncidenceVertexDegree[u]].size() > 1)
01315 {
01316 l = vvi_GroupedIncidenceVertexDegree[vi_IncidenceVertexDegree[u]].back();
01317
01318 vvi_GroupedIncidenceVertexDegree[vi_IncidenceVertexDegree[u]][vi_VertexLocation[u]] = l;
01319
01320 vi_VertexLocation[l] = vi_VertexLocation[u];
01321 }
01322
01323
01324 vvi_GroupedIncidenceVertexDegree[vi_IncidenceVertexDegree[u]].pop_back();
01325
01326
01327 vi_IncidenceVertexDegree[u]++;
01328
01329
01330 vvi_GroupedIncidenceVertexDegree[vi_IncidenceVertexDegree[u]].push_back(u);
01331
01332
01333 vi_VertexLocation[u] = vvi_GroupedIncidenceVertexDegree[vi_IncidenceVertexDegree[u]].size() - 1;
01334 }
01335
01336
01337 vi_IncidenceVertexDegree[i_SelectedVertex] = _UNKNOWN;
01338
01339 m_vi_OrderedVertices.push_back(i_SelectedVertex);
01340
01341 i_SelectedVertexCount = STEP_UP(i_SelectedVertexCount);
01342 }
01343
01344
01345 vi_IncidenceVertexDegree.clear();
01346 vi_VertexLocation.clear();
01347 vvi_GroupedIncidenceVertexDegree.clear();
01348
01349 return(_TRUE);
01350 }
01351
01352
01353
01354 int GraphOrdering::DistanceTwoIncidenceDegreeOrdering()
01355 {
01356 if(CheckVertexOrdering("DISTANCE TWO INCIDENCE DEGREE") == _TRUE)
01357 {
01358 return(_TRUE);
01359 }
01360
01361 int i, j, k, l, u, v;
01362
01363
01364 int i_DistanceTwoVertexDegree;
01365
01366 int i_HighestDistanceTwoDegreeVertex, i_HighestDistanceTwoVertexDegree;
01367
01368 int i_VertexCount, i_InducedVertexDegree;
01369
01370 int i_InducedVertexDegreeCount;
01371
01372 int i_SelectedVertex, i_SelectedVertexCount;
01373
01374 vector < int > vi_IncludedVertices;
01375
01376 vector < int > vi_InducedVertexDegrees;
01377
01378 vector < vector < int > > vvi_GroupedInducedVertexDegree;
01379
01380 vector < int > vi_VertexLocations;
01381
01382 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
01383
01384 vi_IncludedVertices.clear();
01385 vi_IncludedVertices.resize((unsigned) i_VertexCount, _UNKNOWN);
01386
01387 vi_InducedVertexDegrees.clear();
01388 vi_InducedVertexDegrees.reserve((unsigned) i_VertexCount);
01389
01390 vvi_GroupedInducedVertexDegree.clear();
01391 vvi_GroupedInducedVertexDegree.resize((unsigned) i_VertexCount);
01392
01393 vi_VertexLocations.clear();
01394 vi_VertexLocations.reserve((unsigned) i_VertexCount);
01395
01396 i_SelectedVertex = _UNKNOWN;
01397
01398 i_HighestDistanceTwoDegreeVertex = i_HighestDistanceTwoVertexDegree = _UNKNOWN;
01399 i_InducedVertexDegree = _FALSE;
01400
01401
01402 vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].reserve((unsigned) i_VertexCount);
01403
01404 for(i=0; i<i_VertexCount; i++)
01405 {
01406 vi_InducedVertexDegrees.push_back(i_InducedVertexDegree);
01407
01408 vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].push_back(i);
01409
01410 vi_VertexLocations.push_back(vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].size() - 1);
01411
01412 vi_IncludedVertices[i] = i;
01413
01414 i_DistanceTwoVertexDegree = _FALSE;
01415
01416 for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
01417 {
01418 if(vi_IncludedVertices[m_vi_Edges[j]] != i)
01419 {
01420 i_DistanceTwoVertexDegree++;
01421
01422 vi_IncludedVertices[m_vi_Edges[j]] = i;
01423 }
01424
01425 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
01426 {
01427 if(vi_IncludedVertices[m_vi_Edges[k]] != i)
01428 {
01429 i_DistanceTwoVertexDegree++;
01430
01431 vi_IncludedVertices[m_vi_Edges[k]] = i;
01432 }
01433 }
01434 }
01435
01436 if(i_HighestDistanceTwoVertexDegree < i_DistanceTwoVertexDegree)
01437 {
01438 i_HighestDistanceTwoVertexDegree = i_DistanceTwoVertexDegree;
01439 i_HighestDistanceTwoDegreeVertex = i;
01440 }
01441 }
01442
01443 m_vi_OrderedVertices.clear();
01444 m_vi_OrderedVertices.reserve((unsigned) i_VertexCount);
01445
01446 vi_IncludedVertices.assign((unsigned) i_VertexCount, _UNKNOWN);
01447
01448
01449
01450 l = vvi_GroupedInducedVertexDegree[i_InducedVertexDegree].size() - 1;
01451 v = vvi_GroupedInducedVertexDegree[i_InducedVertexDegree][l];
01452 u = vvi_GroupedInducedVertexDegree[i_InducedVertexDegree][vi_VertexLocations[i_HighestDistanceTwoDegreeVertex]];
01453 swap(vvi_GroupedInducedVertexDegree[i_InducedVertexDegree][vi_VertexLocations[i_HighestDistanceTwoDegreeVertex]], vvi_GroupedInducedVertexDegree[i_InducedVertexDegree][l]);
01454 swap(vi_VertexLocations[v], vi_VertexLocations[u]);
01455
01456 i_SelectedVertexCount = _FALSE;
01457
01458 int iMax = i_HighestDistanceTwoVertexDegree - 1;
01459
01460 while(i_SelectedVertexCount < i_VertexCount)
01461 {
01462 if(iMax != i_HighestDistanceTwoVertexDegree && vvi_GroupedInducedVertexDegree[iMax + 1].size() != _FALSE)
01463 iMax++;
01464
01465 for(i= iMax; i>= 0; i--)
01466 {
01467 i_InducedVertexDegreeCount = (signed) vvi_GroupedInducedVertexDegree[i].size();
01468
01469 if(i_InducedVertexDegreeCount != _FALSE)
01470 {
01471 i_SelectedVertex = vvi_GroupedInducedVertexDegree[i].back();
01472 vvi_GroupedInducedVertexDegree[i].pop_back();
01473 break;
01474 }
01475 else
01476 iMax--;
01477 }
01478
01479 vi_IncludedVertices[i_SelectedVertex] = i_SelectedVertex;
01480
01481 for(i=m_vi_Vertices[i_SelectedVertex]; i<m_vi_Vertices[STEP_UP(i_SelectedVertex)]; i++)
01482 {
01483 u = m_vi_Edges[i];
01484
01485 if(vi_InducedVertexDegrees[u] == _UNKNOWN)
01486 {
01487 continue;
01488 }
01489
01490 if(vi_IncludedVertices[u] != i_SelectedVertex)
01491 {
01492
01493 if(vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].size() > 1)
01494 {
01495 l = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].back();
01496 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]][vi_VertexLocations[u]] = l;
01497 vi_VertexLocations[l] = vi_VertexLocations[u];
01498 }
01499
01500
01501 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].pop_back();
01502
01503
01504 vi_InducedVertexDegrees[u]++;
01505
01506
01507 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].push_back(u);
01508
01509
01510 vi_VertexLocations[u] = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[u]].size() - 1;
01511
01512
01513 vi_IncludedVertices[u] = i_SelectedVertex;
01514 }
01515
01516 for(j=m_vi_Vertices[m_vi_Edges[i]]; j<m_vi_Vertices[STEP_UP(m_vi_Edges[i])]; j++)
01517 {
01518 v = m_vi_Edges[j];
01519
01520 if(vi_InducedVertexDegrees[v] == _UNKNOWN)
01521 {
01522 continue;
01523 }
01524
01525 if(vi_IncludedVertices[v] != i_SelectedVertex)
01526 {
01527
01528 if(vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].size() > 1)
01529 {
01530 l = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].back();
01531 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]][vi_VertexLocations[v]] = l;
01532 vi_VertexLocations[l] = vi_VertexLocations[v];
01533 }
01534
01535
01536 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].pop_back();
01537
01538
01539 vi_InducedVertexDegrees[v]++;
01540
01541
01542 vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].push_back(v);
01543
01544
01545 vi_VertexLocations[v] = vvi_GroupedInducedVertexDegree[vi_InducedVertexDegrees[v]].size() - 1;
01546
01547
01548 vi_IncludedVertices[v] = i_SelectedVertex;
01549 }
01550 }
01551 }
01552
01553 vi_InducedVertexDegrees[i_SelectedVertex] = _UNKNOWN;
01554 m_vi_OrderedVertices.push_back(i_SelectedVertex);
01555 i_SelectedVertexCount = STEP_UP(i_SelectedVertexCount);
01556 }
01557
01558 vi_IncludedVertices.clear();
01559 vi_InducedVertexDegrees.clear();
01560 vvi_GroupedInducedVertexDegree.clear();
01561 vi_VertexLocations.clear();
01562
01563 return(_TRUE);
01564 }
01565
01566
01567 string GraphOrdering::GetVertexOrderingVariant()
01568 {
01569 return(m_s_VertexOrderingVariant);
01570 }
01571
01572
01573 void GraphOrdering::GetOrderedVertices(vector<int> &output)
01574 {
01575 output = (m_vi_OrderedVertices);
01576 }
01577
01578
01579
01580 double GraphOrdering::GetVertexOrderingTime()
01581 {
01582 return(m_d_OrderingTime);
01583 }
01584
01585 int GraphOrdering::GetMaxBackDegree() {
01586
01587
01588 vector<int> vectorID2orderingID;
01589 vectorID2orderingID.resize(m_vi_OrderedVertices.size(),-1);
01590 for( unsigned int i=0; i < m_vi_OrderedVertices.size(); i++) {
01591 vectorID2orderingID[m_vi_OrderedVertices[i]] = i;
01592 }
01593
01594
01595 for( unsigned int i=0; i < vectorID2orderingID.size(); i++) {
01596 if(vectorID2orderingID[i]==-1) {
01597 cerr<<"What the hell? There is a vertex missing"<<endl;
01598 }
01599 }
01600
01601
01602 int i_MaxBackDegree = -1;
01603 int i_CurrentVertexBackDegre = -1;
01604 int currentOrderingID = -1;
01605 for( unsigned int i=0; i < m_vi_Vertices.size() - 1; i++) {
01606 currentOrderingID = vectorID2orderingID[i];
01607 i_CurrentVertexBackDegre = 0;
01608
01609 for( unsigned int j = m_vi_Vertices[i]; j < m_vi_Vertices[i + 1]; j++) {
01610 if(vectorID2orderingID[m_vi_Edges[j]] < currentOrderingID) i_CurrentVertexBackDegre++;
01611 }
01612 if( i_MaxBackDegree < i_CurrentVertexBackDegre) i_MaxBackDegree = i_CurrentVertexBackDegre;
01613 }
01614
01615 return i_MaxBackDegree;
01616 }
01617
01618
01619 void GraphOrdering::PrintVertexOrdering() {
01620 cout<<"PrintVertexOrdering() "<<m_s_VertexOrderingVariant<<endl;
01621 for(unsigned int i=0; i<m_vi_OrderedVertices.size();i++) {
01622
01623 cout<<"\t["<<setw(5)<<i<<"] "<<setw(5)<<m_vi_OrderedVertices[i]<<endl;
01624 }
01625 cout<<endl;
01626 }
01627 }