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