ColPack
GraphColoring/GraphColoring.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.GraphColoring::GraphColoring()
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 1401
00028         int GraphColoring::FindCycle(int i_Vertex, int i_AdjacentVertex, int i_DistanceOneVertex, int i_SetID, vector<int> & vi_CandidateColors, vector<int> & vi_FirstVisitedOne, vector<int> & vi_FirstVisitedTwo)
00029         {
00030                 int i_VertexOne, i_VertexTwo;
00031 
00032                 if(i_SetID != _UNKNOWN)
00033                 {
00034                         i_VertexOne = vi_FirstVisitedOne[i_SetID];
00035                         i_VertexTwo = vi_FirstVisitedTwo[i_SetID];
00036 
00037                         if(i_VertexOne != i_Vertex)
00038                         {
00039                                 vi_FirstVisitedOne[i_SetID] = i_Vertex;
00040                                 vi_FirstVisitedTwo[i_SetID] = i_AdjacentVertex;
00041                         }
00042                         else
00043                         if((i_VertexOne == i_Vertex) && (i_VertexTwo != i_AdjacentVertex))
00044                         {
00045                                 vi_CandidateColors[m_vi_VertexColors[i_DistanceOneVertex]] = i_Vertex;
00046 
00047 #if DEBUG == 1401
00048 
00049                                 cout<<"DEBUG 1401 | Acyclic Coloring | Found Cycle | Vertex "<<STEP_UP(i_Vertex)<<endl;
00050 #endif
00051 
00052                         }
00053                 }
00054 
00055                 return(_TRUE);
00056         }
00057 
00058 
00059         //Private Function 1402
00060         //mimi2_VertexEdgeMap is used as input only
00061         int GraphColoring::UpdateSet(int i_Vertex, int i_AdjacentVertex, int i_DistanceOneVertex, map< int, map<int, int> > & mimi2_VertexEdgeMap, vector<int> & vi_FirstSeenOne, vector<int> & vi_FirstSeenTwo, vector<int> & vi_FirstSeenThree)
00062         {
00063                 int i_ColorID;
00064 
00065                 int i_VertexOne, i_VertexTwo, i_VertexThree;
00066 
00067                 i_ColorID = m_vi_VertexColors[i_AdjacentVertex];
00068 
00069                 i_VertexOne = vi_FirstSeenOne[i_ColorID];
00070                 i_VertexTwo = vi_FirstSeenTwo[i_ColorID];
00071                 i_VertexThree = vi_FirstSeenThree[i_ColorID];
00072 
00073                 if(i_VertexOne != i_Vertex)
00074                 {
00075                         vi_FirstSeenOne[i_ColorID] = i_Vertex;
00076                         vi_FirstSeenTwo[i_ColorID] = i_AdjacentVertex;
00077                         vi_FirstSeenThree[i_ColorID] = i_DistanceOneVertex;
00078                 }
00079                 else
00080                 {
00081                         if(i_VertexTwo < i_VertexThree)
00082                         {
00083                                 return(mimi2_VertexEdgeMap[i_VertexTwo][i_VertexThree]);
00084                         }
00085                         else
00086                         {
00087                                 return(mimi2_VertexEdgeMap[i_VertexThree][i_VertexTwo]);
00088                         }
00089                 }
00090 
00091                 return(_UNKNOWN);
00092         }
00093 
00094 
00095         //Private Function 1403
00096         int GraphColoring::SearchDepthFirst(int i_RootVertex, int i_ParentVertex, int i_Vertex, vector<int> & vi_TouchedVertices)
00097         {
00098                 int i;
00099 
00100                 int i_VertexCount;
00101 
00102                 int i_ViolationCount;
00103 
00104                 i_ViolationCount = _FALSE;
00105 
00106                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00107 
00108                 for(i=m_vi_Vertices[i_Vertex]; i<m_vi_Vertices[STEP_UP(i_Vertex)]; i++)
00109                 {
00110                         if(m_vi_Edges[i] == i_ParentVertex)
00111                         {
00112                                 continue;
00113                         }
00114 
00115                         if(m_vi_Edges[i] == i_RootVertex)
00116                         {
00117                                 i_ViolationCount++;
00118 
00119                                 if(i_ViolationCount == _TRUE)
00120                                 {
00121                                         cout<<endl;
00122                                         cout<<"Acyclic Coloring | Violation Check | "<<m_s_InputFile<<endl;
00123                                         cout<<endl;
00124                                 }
00125 
00126                                 cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(i_RootVertex)<<" ["<<STEP_UP(m_vi_VertexColors[i_RootVertex])<<"] ... "<<STEP_UP(i_ParentVertex)<<" ["<<STEP_UP(m_vi_VertexColors[i_ParentVertex])<<"] - "<<STEP_UP(i_Vertex)<<" ["<<STEP_UP(m_vi_VertexColors[i_Vertex])<<"] - "<<STEP_UP(m_vi_Edges[i])<<" ["<<STEP_UP(m_vi_VertexColors[m_vi_Edges[i]])<<"]"<<endl;
00127                         }
00128 
00129                         if(m_vi_VertexColors[m_vi_Edges[i]] == m_vi_VertexColors[i_Vertex])
00130                         {
00131                                 i_ViolationCount++;
00132 
00133                                 if(i_ViolationCount == _TRUE)
00134                                 {
00135                                         cout<<endl;
00136                                         cout<<"Acyclic Coloring | Violation Check | "<<m_s_InputFile<<endl;
00137                                         cout<<endl;
00138                                 }
00139 
00140                                 cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(i_Vertex)<<" ["<<STEP_UP(m_vi_VertexColors[i_Vertex])<<"] - "<<STEP_UP(m_vi_Edges[i])<<" ["<<STEP_UP(m_vi_VertexColors[m_vi_Edges[i]])<<"]"<<endl;
00141 
00142                         }
00143 
00144                         if(vi_TouchedVertices[m_vi_Edges[i]] == _TRUE)
00145                         {
00146                                 continue;
00147                         }
00148 
00149                         if(m_vi_VertexColors[m_vi_Edges[i]] != m_vi_VertexColors[i_ParentVertex])
00150                         {
00151                                 continue;;
00152                         }
00153 
00154                         vi_TouchedVertices[m_vi_Edges[i]] = _TRUE;
00155 
00156                         i_ViolationCount = SearchDepthFirst(i_RootVertex, i_Vertex, m_vi_Edges[i], vi_TouchedVertices);
00157 
00158                 }
00159 
00160                 return(i_ViolationCount);
00161 
00162         }
00163 
00164 
00165         //Private Function 1404
00166         int GraphColoring::CheckVertexColoring(string s_GraphColoringVariant)
00167         {
00168                 if(m_s_VertexColoringVariant.compare(s_GraphColoringVariant) == 0)
00169                 {
00170                         return(_TRUE);
00171                 }
00172 
00173                 if(m_s_VertexColoringVariant.compare("ALL") != 0)
00174                 {
00175                         m_s_VertexColoringVariant = s_GraphColoringVariant;
00176                 }
00177 
00178                 if(m_s_VertexOrderingVariant.empty())
00179                 {
00180                         NaturalOrdering();
00181                 }
00182 
00183                 return(_FALSE);
00184         }
00185 
00186 
00187         //Private Function 1405
00188         int GraphColoring::CalculateVertexColorClasses()
00189         {
00190                 if(m_s_VertexColoringVariant.empty())
00191                 {
00192                         return(_FALSE);
00193                 }
00194 
00195                 int i_TotalVertexColors = STEP_UP(m_i_VertexColorCount);
00196 
00197                 m_vi_VertexColorFrequency.clear();
00198                 m_vi_VertexColorFrequency.resize((unsigned) i_TotalVertexColors, _FALSE);
00199 
00200                 int i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00201 
00202                 for(int i = 0; i < i_VertexCount; i++)
00203                 {
00204                         m_vi_VertexColorFrequency[m_vi_VertexColors[i]]++;
00205                 }
00206 
00207                 for(int i = 0; i < i_TotalVertexColors; i++)
00208                 {
00209                         if(m_i_LargestColorClassSize < m_vi_VertexColorFrequency[i])
00210                         {
00211                                 m_i_LargestColorClass = i;
00212 
00213                                 m_i_LargestColorClassSize = m_vi_VertexColorFrequency[i];
00214 
00215                         }
00216 
00217                         if(m_i_SmallestColorClassSize == _UNKNOWN)
00218                         {
00219                                 m_i_SmallestColorClass = i;
00220 
00221                                 m_i_SmallestColorClassSize = m_vi_VertexColorFrequency[i];
00222                         }
00223                         else
00224                         if(m_i_SmallestColorClassSize > m_vi_VertexColorFrequency[i])
00225                         {
00226                                 m_i_SmallestColorClass = i;
00227 
00228                                 m_i_SmallestColorClassSize = m_vi_VertexColorFrequency[i];
00229                         }
00230                 }
00231 
00232                 m_d_AverageColorClassSize = i_TotalVertexColors / i_VertexCount;
00233 
00234                 return(_TRUE);
00235         }
00236 
00237 
00238         //Public Constructor 1451
00239         GraphColoring::GraphColoring() : GraphOrdering()
00240         {
00241                 Clear();
00242 
00243                 Seed_init();
00244         }
00245 
00246 
00247         //Public Destructor 1452
00248         GraphColoring::~GraphColoring()
00249         {
00250                 Clear();
00251 
00252                 Seed_reset();
00253         }
00254 
00255         //Virtual Function 1453
00256         void GraphColoring::Clear()
00257         {
00258                 GraphOrdering::Clear();
00259 
00260                 m_i_VertexColorCount = _UNKNOWN;
00261 
00262                 m_i_LargestColorClass = _UNKNOWN;
00263                 m_i_SmallestColorClass = _UNKNOWN;
00264 
00265                 m_i_LargestColorClassSize = _UNKNOWN;
00266                 m_i_SmallestColorClassSize = _UNKNOWN;
00267 
00268                 m_d_AverageColorClassSize = _UNKNOWN;
00269 
00270                 m_i_ColoringUnits = _UNKNOWN;
00271 
00272                 m_d_ColoringTime = _UNKNOWN;
00273                 m_d_CheckingTime = _UNKNOWN;
00274 
00275                 m_s_VertexColoringVariant.clear();
00276 
00277                 m_vi_VertexColors.clear();
00278 
00279                 m_vi_VertexColorFrequency.clear();
00280 
00281 
00282                 return;
00283         }
00284 
00285         void GraphColoring::ClearColoringONLY()
00286         {
00287                 m_i_VertexColorCount = _UNKNOWN;
00288 
00289                 m_i_LargestColorClass = _UNKNOWN;
00290                 m_i_SmallestColorClass = _UNKNOWN;
00291 
00292                 m_i_LargestColorClassSize = _UNKNOWN;
00293                 m_i_SmallestColorClassSize = _UNKNOWN;
00294 
00295                 m_d_AverageColorClassSize = _UNKNOWN;
00296 
00297                 m_i_ColoringUnits = _UNKNOWN;
00298 
00299                 m_d_ColoringTime = _UNKNOWN;
00300                 m_d_CheckingTime = _UNKNOWN;
00301 
00302                 m_s_VertexColoringVariant.clear();
00303 
00304                 m_vi_VertexColors.clear();
00305 
00306                 m_vi_VertexColorFrequency.clear();
00307 
00308                 return;
00309         }
00310 
00311         //Public Function 1454
00312         int GraphColoring::DistanceOneColoring()
00313         {
00314                 //*
00315                 if(CheckVertexColoring("DISTANCE ONE"))
00316                 {
00317                         return(_TRUE);
00318                 }
00319                 //*/
00320 
00321                 int i, j;
00322 
00323                 int i_PresentVertex;
00324 
00325                 int i_VertexCount;
00326 
00327                 vector<int> vi_CandidateColors;
00328 
00329                 m_i_VertexColorCount = _UNKNOWN;
00330 
00331                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00332 
00333                 m_vi_VertexColors.clear();
00334                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
00335 
00336                 vi_CandidateColors.clear();
00337                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
00338 
00339                 for(i=0; i<i_VertexCount; i++)
00340                 {
00341                         i_PresentVertex = m_vi_OrderedVertices[i];
00342 
00343 #if VERBOSE == _TRUE
00344 
00345                         cout<<"DEBUG 1454 | Distance One Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
00346 
00347 #endif
00348 
00349                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
00350                         {
00351                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
00352                                 {
00353                                         continue;
00354                                 }
00355 
00356                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
00357 
00358                         }
00359 
00360                         for(j=0; j<i_VertexCount; j++)
00361                         {
00362                                 if(vi_CandidateColors[j] != i_PresentVertex)
00363                                 {
00364                                         m_vi_VertexColors[i_PresentVertex] = j;
00365 
00366                                         if(m_i_VertexColorCount < j)
00367                                         {
00368                                                 m_i_VertexColorCount = j;
00369                                         }
00370 
00371                                         break;
00372                                 }
00373                         }
00374                 }
00375 
00376                 return(_TRUE);
00377 
00378         }
00379 
00380 
00381         //Public Function 1455
00382         int GraphColoring::DistanceTwoColoring()
00383         {
00384                 if(CheckVertexColoring("DISTANCE TWO"))
00385                 {
00386                         return(_TRUE);
00387                 }
00388 
00389                 int i, j, k;
00390 
00391                 int i_PresentVertex;
00392 
00393                 int i_VertexCount;
00394 
00395                 vector<int> vi_CandidateColors;
00396 
00397                 m_i_VertexColorCount = _UNKNOWN;
00398 
00399                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00400 
00401                 m_vi_VertexColors.clear();
00402                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
00403 
00404                 vi_CandidateColors.clear();
00405                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
00406 
00407                 for(i=0; i<i_VertexCount; i++)
00408                 {
00409                         i_PresentVertex = m_vi_OrderedVertices[i];
00410 
00411 #if VERBOSE == _TRUE
00412 
00413                         cout<<"DEBUG 1455 | Distance Two Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
00414 
00415 #endif
00416                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
00417                         {
00418 /*
00419                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
00420                                 {
00421                                         continue;
00422                                 }
00423                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
00424 //*/
00425                                 if(m_vi_VertexColors[m_vi_Edges[j]] != _UNKNOWN) vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
00426 
00427                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
00428                                 {
00429                                         //is this "if" statement really necessary? because the i_PresentVertex is not colored anyway
00430                                         // say it another way, the second if statement will take care of the i_PresentVertex
00431 /*
00432                                         if(m_vi_Edges[k] == i_PresentVertex)
00433                                         {
00434                                                 continue;
00435                                         }
00436 //*/
00437 
00438                                         if(m_vi_VertexColors[m_vi_Edges[k]] != _UNKNOWN)
00439                                         {
00440                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
00441                                         }
00442                                 }
00443                         }
00444 
00445                         for(j=0; j<i_VertexCount; j++)
00446                         {
00447                                 if(vi_CandidateColors[j] != i_PresentVertex)
00448                                 {
00449                                         m_vi_VertexColors[i_PresentVertex] = j;
00450 
00451                                         if(m_i_VertexColorCount < j)
00452                                         {
00453                                                 m_i_VertexColorCount = j;
00454                                         }
00455 
00456                                         break;
00457                                 }
00458                         }
00459                 }
00460 
00461                 return(_TRUE);
00462         }
00463 
00464 
00465         //Public Function 1456
00466         int GraphColoring::NaiveStarColoring()
00467         {
00468                 if(CheckVertexColoring("NAIVE STAR"))
00469                 {
00470                         return(_TRUE);
00471                 }
00472 
00473                 int i, j, k, l;
00474 
00475                 int i_PresentVertex;
00476 
00477                 int i_VertexCount;
00478 
00479                 vector<int> vi_CandidateColors;
00480 
00481                 m_i_VertexColorCount = _UNKNOWN;
00482 
00483                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00484 
00485                 m_vi_VertexColors.clear();
00486                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
00487 
00488                 vi_CandidateColors.clear();
00489                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
00490 
00491                 for(i=0; i<i_VertexCount; i++)
00492                 {
00493                         i_PresentVertex = m_vi_OrderedVertices[i];
00494 
00495 #if VERBOSE == _TRUE
00496 
00497                 cout<<"DEBUG 1456 | Naive Star Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
00498 
00499 #endif
00500 
00501                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
00502                         {
00503                                 if(m_vi_VertexColors[m_vi_Edges[j]] != _UNKNOWN)
00504                                 {
00505                                         vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
00506                                 }
00507 
00508                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
00509                                 {
00510                                         if(m_vi_Edges[k] == i_PresentVertex)
00511                                         {
00512                                                 continue;
00513                                         }
00514 
00515                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
00516                                         {
00517                                                 continue;
00518                                         }
00519 
00520                                         if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
00521                                         {
00522                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
00523                                         }
00524                                         else
00525                                         {
00526                                                 for(l=m_vi_Vertices[m_vi_Edges[k]]; l<m_vi_Vertices[STEP_UP(m_vi_Edges[k])]; l++)
00527                                                 {
00528                                                         if(m_vi_Edges[l] == m_vi_Edges[j])
00529                                                         {
00530                                                                 continue;
00531                                                         }
00532 
00533                                                         if(m_vi_VertexColors[m_vi_Edges[l]] == _UNKNOWN)
00534                                                         {
00535                                                                 continue;
00536                                                         }
00537 
00538                                                         if(m_vi_VertexColors[m_vi_Edges[l]] == m_vi_VertexColors[m_vi_Edges[j]])
00539                                                         {
00540                                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
00541 
00542                                                                 break;
00543                                                         }
00544                                                 }
00545                                         }
00546                                 }
00547                         }
00548 
00549                         for(j=0; j<i_VertexCount; j++)
00550                         {
00551                                 if(vi_CandidateColors[j] != i_PresentVertex)
00552                                 {
00553                                         m_vi_VertexColors[i_PresentVertex] = j;
00554 
00555                                         if(m_i_VertexColorCount < j)
00556                                         {
00557                                                 m_i_VertexColorCount = j;
00558                                         }
00559 
00560                                         break;
00561                                 }
00562                         }
00563                 }
00564 
00565                 return(_TRUE);
00566 
00567         }
00568 
00569         //Public Function 1457
00570         int GraphColoring::RestrictedStarColoring()
00571         {
00572                 if(CheckVertexColoring("RESTRICTED STAR"))
00573                 {
00574                         return(_TRUE);
00575                 }
00576 
00577                 int i, j, k;
00578 
00579                 int i_PresentVertex;
00580 
00581                 int i_VertexCount;
00582 
00583                 vector<int> vi_CandidateColors;
00584 
00585                 m_i_VertexColorCount = _UNKNOWN;
00586 
00587                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00588 
00589                 m_vi_VertexColors.clear();
00590                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
00591 
00592                 vi_CandidateColors.clear();
00593                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
00594 
00595                 for(i=0; i<i_VertexCount; i++)
00596                 {
00597 
00598                         i_PresentVertex = m_vi_OrderedVertices[i];
00599 
00600 #if VERBOSE == _TRUE
00601 
00602                         cout<<"DEBUG 1457 | Restricted Star Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
00603 
00604 #endif
00605 
00606                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
00607                         {
00608                                 if(m_vi_VertexColors[m_vi_Edges[j]] != _UNKNOWN)
00609                                 {
00610                                         vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
00611                                 }
00612 
00613                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
00614                                 {
00615                                         if(m_vi_Edges[k] == i_PresentVertex)
00616                                         {
00617                                                 continue;
00618                                         }
00619 
00620                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
00621                                         {
00622                                                 continue;
00623                                         }
00624 
00625                                         if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
00626                                         {
00627                                                 //mark as forbidden
00628                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
00629                                         }
00630                                         else
00631                                         if(m_vi_VertexColors[m_vi_Edges[k]] < m_vi_VertexColors[m_vi_Edges[j]])
00632                                         {
00633                                                 //mark as forbidden
00634                                                  vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
00635                                         }
00636                                 }
00637                         }
00638 
00639                         for(j=0; j<i_VertexCount; j++)
00640                         {
00641                                 if(vi_CandidateColors[j] != i_PresentVertex)
00642                                 {
00643                                         m_vi_VertexColors[i_PresentVertex] = j;
00644 
00645                                         if(m_i_VertexColorCount < j)
00646                                         {
00647                                                 m_i_VertexColorCount = j;
00648                                         }
00649 
00650                                         break;
00651                                 }
00652                         }
00653                 }
00654 
00655                 return(_TRUE);
00656 
00657         }
00658         
00659         int GraphColoring::PrintVertexColorCombination(map <int, int >* VertexColorCombination) {
00660                 cout<<"PrintVertexColorCombination"<<endl;
00661                 map< int, int>::iterator mii_iter;
00662                 mii_iter = (*VertexColorCombination).begin();
00663                 for(;mii_iter != (*VertexColorCombination).end(); mii_iter++) {
00664                         cout<<"\t c "<<mii_iter->first<<": ";
00665                         
00666                         if( mii_iter->second > -1) {
00667                                 cout<<" NO hub, connect to v "<<mii_iter->second<<" c "<<m_vi_VertexColors[mii_iter->second];
00668                         }
00669                         else if ( mii_iter->second == -1) {
00670                                 cout<<" HUB";
00671                         }
00672                         else { // (*itr)[iii].second < -1
00673                                 cout<<" LEAF of hub v "<<-(mii_iter->second+2) <<" c "<<m_vi_VertexColors[-(mii_iter->second+2)];
00674                         }
00675                         cout<<endl;
00676                                                 
00677                 }
00678         }
00679         
00680         int GraphColoring::PrintPotentialHub(map< int, int> *PotentialHub_Private, int i_thread_num, pair<int, int> pii_ColorCombination) {
00681                 cout<<"PrintPotentialHub - Star collection of combination "<< pii_ColorCombination.first << " "<< pii_ColorCombination.second <<endl;
00682                 map< int, int>::iterator mii_iter;
00683                 mii_iter = PotentialHub_Private[i_thread_num].begin();
00684                 for(;mii_iter != PotentialHub_Private[i_thread_num].end(); mii_iter++) {
00685                         cout<<"\t v "<<mii_iter->first<<" c "<<m_vi_VertexColors[mii_iter->first]<<":";
00686                         
00687                         if( mii_iter->second > -1) {
00688                                 cout<<" NO hub, connect to v "<<mii_iter->second<<" c "<<m_vi_VertexColors[mii_iter->second];
00689                         }
00690                         else if ( mii_iter->second == -1) {
00691                                 cout<<" HUB";
00692                         }
00693                         else { // (*itr)[iii].second < -1
00694                                 cout<<" LEAF of hub v "<<-(mii_iter->second+2) <<" c "<<m_vi_VertexColors[-(mii_iter->second+2)];
00695                         }
00696                         cout<<endl;
00697                                                 
00698                 }
00699         }
00700         
00701                 
00702         // !!! later on, remove the codes that check for conflicts (because we assume no conflict) => make this function run faster)
00703         int GraphColoring::BuildStarFromColorCombination_forChecking(int i_Mode, int i_MaxNumThreads, int i_thread_num, pair<int, int> pii_ColorCombination, map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private,
00704                                                           map< int, int> * PotentialHub_Private) {
00705                 map< pair<int, int>, Colors2Edge_Value, lt_pii >::iterator mpii_iter;
00706                 map< int, int>::iterator mii_iter;
00707                 int i_PotentialHub=0;
00708                 int i_ConflictVertex=-1;
00709                 bool b_isConflict=false;
00710                 // reset PotentialHub_Private;
00711                 PotentialHub_Private[i_thread_num].clear();
00712                 for(int i= 0; i<i_MaxNumThreads; i++) {
00713                         mpii_iter = Colors2Edge_Private[i].find(pii_ColorCombination);
00714                         if(mpii_iter != Colors2Edge_Private[i].end()) { //Colors2Edge_Private[i] contains the color combination
00715                                 vector<int> vi_ConflictedEdgeIndices;
00716                                 vector< pair<int, int> >* vpii_EdgesPtr = &(mpii_iter->second.value);
00717                                 pair<int, int> pii_Edge;
00718                                 // now start counting the appearance of vertices and detect conflict
00719                                 for(int j=0; j< vpii_EdgesPtr->size(); j++  ) {
00720                                         pii_Edge = (*vpii_EdgesPtr)[j];
00721 #ifdef COLPACK_DEBUG            
00722                                         cout<<"\t Looking at "<<pii_Edge.first<<"-"<<pii_Edge.second;
00723 #endif
00724                                         i_PotentialHub=0;
00725                                         b_isConflict=false;
00726                                         //check and see if either end of the edge could be a potential hub
00727                                         mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.first);
00728                                         if(mii_iter != PotentialHub_Private[i_thread_num].end()) {
00729                                                 if( mii_iter->second >=-1) {
00730                                                         //pii_Edge.first is a potential hub
00731                                                         i_PotentialHub += 1;
00732                                                 }
00733                                                 else {
00734                                                         b_isConflict=true;
00735                                                         i_ConflictVertex=pii_Edge.second;
00736                                                 }
00737                                         }
00738                                         mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.second);
00739                                         if(mii_iter != PotentialHub_Private[i_thread_num].end()) {
00740                                                 if( mii_iter->second >=-1) {
00741                                                 //pii_Edge.second is a potential hub
00742                                                         i_PotentialHub += 2;
00743                                                 }
00744                                                 else {
00745                                                         b_isConflict=true;
00746                                                         i_ConflictVertex=pii_Edge.first;
00747                                                 }
00748                                         }
00749                                         
00750                                         if(i_PotentialHub == 3 || b_isConflict) { // pii_Edge.first and pii_Edge.second are both potential hubs || conflict has been detected 
00751                                                 CoutLock::set(); 
00752                                                 {
00753                                                         //Detect conflict
00754                                                         cerr<<endl<<" !!! conflict detected in BuildStarFromColorCombination_forChecking()"<<endl;
00755                                                         cout<<"\t i_PotentialHub="<<i_PotentialHub<<endl;
00756                                                         cout<<"\t b_isConflict="<<b_isConflict<<endl;
00757                                                         if(!b_isConflict) i_ConflictVertex=-2; // signal that both ends are Potential Hubs
00758                                                         cout<<"Color combination "<<pii_ColorCombination.first<<" "<<pii_ColorCombination.second<<endl;
00759                                                         cout<<"\t Looking at "<<pii_Edge.first<<"(color "<< m_vi_VertexColors[pii_Edge.first]<<")-"<<pii_Edge.second<<"(color "<< m_vi_VertexColors[pii_Edge.second]<<") "<<endl;
00760                                                         //PrintColorCombination(Colors2Edge_Private, i_MaxNumThreads, pii_ColorCombination, 100);
00761                                                         PrintColorCombination(Colors2Edge_Private, i_MaxNumThreads, pii_ColorCombination);
00762                                                         PrintPotentialHub(PotentialHub_Private, i_thread_num, pii_ColorCombination);
00763                                                         
00764                                                         map< int, map<int,bool> > *graph = new map< int, map<int,bool> >;
00765                                                         map<int, bool> *mib_FilterByColors = new map<int, bool>;
00766                                                         {
00767                                                                 (*mib_FilterByColors)[m_vi_VertexColors[pii_Edge.first]] = true;
00768                                                                 (*mib_FilterByColors)[m_vi_VertexColors[pii_Edge.second]] = true;
00769                                                                 
00770                                                         }
00771                                                         //BuildSubGraph(graph, pii_Edge.first, 4, mib_FilterByColors);
00772                                                         BuildColorsSubGraph(graph,mib_FilterByColors);
00773                                                         vector<int> vi_VertexColors; 
00774                                                         GetVertexColors(vi_VertexColors);
00775                                                         displayGraph(graph, &vi_VertexColors, true, FDP);
00776                                                         delete graph;
00777                                                         delete mib_FilterByColors;
00778                                                         //Pause();
00779 
00780 #if COLPACK_DEBUG_LEVEL > 100
00781                                                         cout<<" FAILED"<<endl;
00782                                                         //fout.close();
00783 #endif
00784                                                         if(i_Mode==1) {
00785                                                                 CoutLock::unset(); 
00786                                                                 //cout<<"IN BuildStarFromColorCombination_forChecking i_ConflictVertex="<<i_ConflictVertex<<endl;
00787                                                                 //Pause();
00788                                                                 return i_ConflictVertex;
00789                                                         }
00790                                                         else if(i_Mode==0) {
00791                                                                 Pause();
00792                                                         }
00793                                                 }
00794                                                 CoutLock::unset(); 
00795                                                 continue;
00796                                         }
00797                                         else if(i_PotentialHub == 1) { //only pii_Edge.first is a potential hub
00798                                                 mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.first);
00799                                                 if(mii_iter->second >=0) { // This is a single edge hub => mark the pii_Edge.first vertex as hub and (the other connected vertex + pii_Edge.second) as a leaf
00800                                                         PotentialHub_Private[i_thread_num][PotentialHub_Private[i_thread_num][pii_Edge.first] ] = -(pii_Edge.first+2);
00801                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -(pii_Edge.first+2);
00802                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -1;
00803                                                 }
00804                                                 else { // mii_iter->second = -1 : This is a hub with more than one edge => mark pii_Edge.second as a leaf
00805                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -(pii_Edge.first+2);
00806                                                 }
00807                                         }
00808                                         else if(i_PotentialHub == 2) { //only pii_Edge.second is a potential hub
00809                                                 mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.second);
00810                                                 if(mii_iter->second >=0) { // This is a single edge hub => mark the pii_Edge.second vertex as hub and (the other connected vertex + pii_Edge.first) as a leaf
00811                                                         PotentialHub_Private[i_thread_num][ PotentialHub_Private[i_thread_num][pii_Edge.second] ] = -(pii_Edge.second+2);
00812                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -(pii_Edge.second+2);
00813                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -1;
00814                                                 }
00815                                                 else { // mii_iter->second = -1 : This is a hub with more than one edge => mark pii_Edge.first as a leaf
00816                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -(pii_Edge.second+2);
00817                                                 }
00818                                         }
00819                                         else { // Both end of the vertices are seen for the first time => make them potential hubs
00820                                                 PotentialHub_Private[i_thread_num][pii_Edge.second] = pii_Edge.first;
00821                                                 PotentialHub_Private[i_thread_num][pii_Edge.first] = pii_Edge.second;
00822                                         }
00823 #ifdef COLPACK_DEBUG            
00824                                         cout<<" PASSED"<<endl;
00825 #endif
00826                                         
00827                                 }
00828                         }
00829                 }
00830                 
00831                 //cout<<"IN BuildStarFromColorCombination_forChecking i_ConflictVertex="<<-1<<endl;
00832                 return -1;
00833         }
00834         
00835         int GraphColoring::CheckStarColoring_OMP(int i_Mode, pair<int,int> *pii_ConflictColorCombination) {
00836                 
00837                 int i_MaxNumThreads;
00838 #ifdef _OPENMP
00839                 i_MaxNumThreads = omp_get_max_threads();
00840 #else
00841                 i_MaxNumThreads = 1;
00842 #endif
00843                 int i_VertexCount = m_vi_Vertices.size() - 1;
00844                 int* i_ConflictVertex= new int[i_MaxNumThreads];
00845                 for(int i=0; i<i_MaxNumThreads;i++) i_ConflictVertex[i] = -1;
00846                 map< int, int> * PotentialHub_Private = new map< int, int> [i_MaxNumThreads];
00847                 
00848 #ifdef COLPACK_DEBUG            
00849                 cout<<"Color combination "<<pii_ColorCombination.first<<" "<<pii_ColorCombination.second<<endl;
00850 #endif
00851                 
00852                 // Threads go through all edges and put each edge into a 2-color group
00853                 i_ProcessedEdgeCount=0;
00854                 map< pair<int, int>, Colors2Edge_Value, lt_pii> *Colors2Edge_Private = new map< pair<int, int>, Colors2Edge_Value, lt_pii> [i_MaxNumThreads]; // map 2-color combination to edges that have those 2 colors
00855                 
00856                 bool b_Stop = false;
00857 #ifdef _OPENMP
00858                 #pragma omp parallel for default(none) shared(i_ConflictVertex, i_VertexCount, Colors2Edge_Private, cout , i_MaxNumThreads, i_Mode, b_Stop) 
00859 #endif
00860                 for(int i=0; i<i_VertexCount; i++) {
00861                         if(b_Stop) continue;
00862                         if( m_vi_VertexColors[i] == _UNKNOWN) continue;
00863                         int i_thread_num;
00864 #ifdef _OPENMP
00865                         i_thread_num = omp_get_thread_num();
00866 #else
00867                         i_thread_num = 0;
00868 #endif
00869                         pair<int, int> pii_ColorCombination;
00870                         pair<int, int> pii_Edge;
00871                         for(int j=m_vi_Vertices[i]; j<m_vi_Vertices[i+1]; j++) {
00872                                 if(b_Stop) break;
00873                                 if(i < m_vi_Edges[j]) {
00874                                         if(m_vi_VertexColors[ m_vi_Edges[j] ] == _UNKNOWN ) continue;
00875                                         pii_Edge.first = i;
00876                                         pii_Edge.second = m_vi_Edges[j];
00877                                         //#pragma omp critical
00878                                         //{i_ProcessedEdgeCount++;}
00879                                          
00880                                         if(m_vi_VertexColors[i] < m_vi_VertexColors[ m_vi_Edges[j] ]) {
00881                                                 pii_ColorCombination.first = m_vi_VertexColors[i];
00882                                                 pii_ColorCombination.second = m_vi_VertexColors[m_vi_Edges[j]];
00883                                                 
00884                                                 Colors2Edge_Private[i_thread_num][pii_ColorCombination].value.push_back(pii_Edge);
00885                                         }
00886                                         else if ( m_vi_VertexColors[i] > m_vi_VertexColors[ m_vi_Edges[j] ] ) {
00887                                                 pii_ColorCombination.second = m_vi_VertexColors[i];
00888                                                 pii_ColorCombination.first = m_vi_VertexColors[m_vi_Edges[j]];
00889                                                 
00890                                                 Colors2Edge_Private[i_thread_num][pii_ColorCombination].value.push_back(pii_Edge);
00891                                         }
00892                                         else { //m_vi_VertexColors[i] == m_vi_VertexColors[ m_vi_Edges[j] ]
00893                                                 // conflict found! 
00894                                                 CoutLock::set(); 
00895                                                 {
00896                                                         //Detect conflict
00897                                                         cout<<endl<<" !!! conflict detected in CheckStarColoring_OMP()"<<endl;
00898                                                         i_ConflictVertex[i_thread_num] = i;
00899                                                         cout<<"m_vi_VertexColors[i] == m_vi_VertexColors[ m_vi_Edges[j] ]"<<endl;
00900                                                         cout<<"\t m_vi_VertexColors["<<i<<"]="<<m_vi_VertexColors[i]<<endl;
00901                                                         cout<<"\t m_vi_VertexColors["<< m_vi_Edges[j]<<"]="<<m_vi_VertexColors[ m_vi_Edges[j]]<<endl;
00902                                                         cout<<"Color combination "<<pii_ColorCombination.first<<" "<<pii_ColorCombination.second<<endl;
00903                                                         cout<<"\t Looking at "<<pii_Edge.first<<"(color "<< m_vi_VertexColors[pii_Edge.first]<<")-"<<pii_Edge.second<<"(color "<< m_vi_VertexColors[pii_Edge.second]<<") "<<endl;
00904                                                         //PrintColorCombination(Colors2Edge_Private, i_MaxNumThreads, pii_ColorCombination, 100);
00905                                                         PrintColorCombination(Colors2Edge_Private, i_MaxNumThreads, pii_ColorCombination);
00906 
00907 #if COLPACK_DEBUG_LEVEL > 100
00908                                                         cout<<" FAILED"<<endl;
00909                                                         //fout.close();
00910 #endif
00911                                                         if(i_Mode==1) {
00912                                                                 CoutLock::unset(); 
00913                                                                 b_Stop = true;
00914                                                         }
00915                                                         else if(i_Mode==0) {
00916                                                                 Pause();
00917                                                         }
00918                                                 }
00919                                                 CoutLock::unset(); 
00920                                         }
00921                                 }
00922                         }
00923                 }
00924                 if(b_Stop) {
00925                         for(int i=0; i<i_MaxNumThreads;i++) {
00926                                 if( i_ConflictVertex[i]!=-1) {
00927                                         int i_tmp = i_ConflictVertex[i];
00928                                         delete[] Colors2Edge_Private;
00929                                         delete[] i_ConflictVertex;
00930                                         return i_tmp;
00931                                 }
00932                         }
00933                         delete[] Colors2Edge_Private;
00934                         delete[] i_ConflictVertex;
00935                         return -1;
00936                 }
00937                 
00938                 /* Each thread will goes through 2-color combination, attemp to build stars (assume that there is no conflict edges)
00939                 */
00940                 for(int i=0; i<i_MaxNumThreads; i++) {
00941                         if(b_Stop) break;
00942                 
00943 #ifdef _OPENMP
00944                         #pragma omp parallel default(none) firstprivate(i) shared(pii_ConflictColorCombination, i_ConflictVertex, cout, i_VertexCount, Colors2Edge_Private, PotentialHub_Private, i_MaxNumThreads, b_Stop, i_Mode) 
00945 #endif
00946                         for(map< pair<int, int>, Colors2Edge_Value, lt_pii >::iterator iter = Colors2Edge_Private[i].begin(); iter != Colors2Edge_Private[i].end() ; iter++) {
00947                                 #pragma omp single nowait
00948                                 {
00949                                         if(iter->second.visited == false && !b_Stop) {
00950                                                 iter->second.visited=true;
00951                                                 // mark the same color combination in other Colors2Edge_Private[] as visited so that a thread can freely work on this color combination in all Colors2Edge_Private[]
00952                                                 for(int ii = i; ii<i_MaxNumThreads;ii++) {
00953                                                         //see if the same combination exists in Colors2Edge_Private[ii]
00954                                                         map< pair<int, int>, Colors2Edge_Value, lt_pii >::iterator iter2 = Colors2Edge_Private[ii].find(iter->first);
00955                                                         if(iter2!=Colors2Edge_Private[ii].end()) { // if the combination exists, we mark it as visited
00956                                                                 iter2->second.visited = true;
00957                                                         }
00958                                                 }
00959                                                 
00960                                                 int i_thread_num;
00961 #ifdef _OPENMP
00962                                                 i_thread_num = omp_get_thread_num();
00963 #else
00964                                                 i_thread_num = 0;
00965 #endif
00966                                                 
00967                                                 // now, let a thread works on this combination:
00968                                                 //    build stars and identify conflict edges
00969                                                 i_ConflictVertex[i_thread_num] = BuildStarFromColorCombination_forChecking(i_Mode, i_MaxNumThreads, i_thread_num, iter->first, Colors2Edge_Private, PotentialHub_Private);
00970                                                 
00971                                                 if(i_ConflictVertex[i_thread_num]  != -1) {
00972                                                         #pragma omp critial
00973                                                         {
00974                                                                 if(pii_ConflictColorCombination!=NULL) {
00975                                                                         (*pii_ConflictColorCombination).first = iter->first.first;
00976                                                                         (*pii_ConflictColorCombination).second = iter->first.second;
00977                                                                 }
00978                                                         }
00979                                                         b_Stop = true;
00980                                                         cout<<"IN CheckStarColoring_OMP i_ConflictVertex["<< i_thread_num<<"]="<< i_ConflictVertex[i_thread_num] <<endl;
00981                                                         //Pause();
00982                                                 }
00983 /*
00984 #ifdef COLPACK_DEBUG            
00985                                                 #pragma omp critical
00986                                                 {
00987                                                         cout<<flush<<"Color combination "<<(iter->first).first<<" "<<(iter->first).second<<endl;
00988                                                         PrintVertex2ColorCombination(i_MaxNumThreads, Vertex2ColorCombination_Private);
00989                                                         cout<<"\n\n\n\n\n\n\n"<<flush;
00990                                                 }
00991 #endif
00992 //*/
00993                                         }
00994                                 }
00995                         }
00996                 }
00997                 delete[] Colors2Edge_Private;
00998                 delete[] PotentialHub_Private;
00999                 
01000                 if(b_Stop) {
01001                         for(int i=0; i<i_MaxNumThreads;i++) {
01002                                 if( i_ConflictVertex[i]!=-1) {
01003                                         int i_tmp = i_ConflictVertex[i];
01004                                         delete[] i_ConflictVertex;
01005                                         return i_tmp;
01006                                 }
01007                         }
01008                 }
01009                 
01010                 
01011                 delete[] i_ConflictVertex;
01012                 return -1;
01013         }
01014         
01015         // !!! later on, remove the codes that check for conflicts (because we assume no conflict) => make this function run faster)
01016         int GraphColoring::BuildStarFromColorCombination(int i_MaxNumThreads, int i_thread_num, pair<int, int> pii_ColorCombination, map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private,
01017                                                          map< int, vector< pair<int, int> > > *Vertex2ColorCombination_Private, map< int, int> * PotentialHub_Private) {
01018                 int i_VertexCount = m_vi_Vertices.size() - 1;
01019                 map< pair<int, int>, Colors2Edge_Value, lt_pii >::iterator mpii_iter;
01020                 map< int, int>::iterator mii_iter;
01021                 int i_PotentialHub=0;
01022                 bool b_isConflict=false;
01023                 // reset PotentialHub_Private;
01024                 PotentialHub_Private[i_thread_num].clear();
01025                 
01026 #ifdef COLPACK_DEBUG            
01027                 cout<<"Color combination "<<pii_ColorCombination.first<<" "<<pii_ColorCombination.second<<endl;
01028 #endif
01029                 
01030                 for(int i= 0; i<i_MaxNumThreads; i++) {
01031                         mpii_iter = Colors2Edge_Private[i].find(pii_ColorCombination);
01032                         if(mpii_iter != Colors2Edge_Private[i].end()) { //Colors2Edge_Private[i] contains the color combination
01033                                 vector<int> vi_ConflictedEdgeIndices;
01034                                 vector< pair<int, int> >* vpii_EdgesPtr = &(mpii_iter->second.value);
01035                                 pair<int, int> pii_Edge;
01036                                 // now start counting the appearance of vertices and detect conflict
01037                                 for(int j=0; j< vpii_EdgesPtr->size(); j++  ) {
01038                                         pii_Edge = (*vpii_EdgesPtr)[j];
01039 #ifdef COLPACK_DEBUG            
01040                                         cout<<"\t Looking at "<<pii_Edge.first<<"-"<<pii_Edge.second;
01041 #endif
01042                                         i_PotentialHub=0;
01043                                         b_isConflict=false;
01044                                         //check and see if either end of the edge could be a potential hub
01045                                         mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.first);
01046                                         if(mii_iter != PotentialHub_Private[i_thread_num].end()) {
01047                                                 if( mii_iter->second >=-1) {
01048                                                         //pii_Edge.first is a potential hub
01049                                                         i_PotentialHub += 1;
01050                                                 }
01051                                                 else {
01052                                                         b_isConflict=true;
01053                                                 }
01054                                         }
01055                                         mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.second);
01056                                         if(mii_iter != PotentialHub_Private[i_thread_num].end()) {
01057                                                 if( mii_iter->second >=-1) {
01058                                                 //pii_Edge.second is a potential hub
01059                                                         i_PotentialHub += 2;
01060                                                 }
01061                                                 else {
01062                                                         b_isConflict=true;
01063                                                 }
01064                                         }
01065                                         
01066                                         if(i_PotentialHub == 3 || b_isConflict) { // pii_Edge.first and pii_Edge.second are both potential hubs || conflict has been detected => add this edge into ConflictedEdges_Private
01067                                                 CoutLock::set(); 
01068                                                 {
01069                                                         //Detect conflict
01070                                                         cerr<<endl<<" !!! conflict detected in BuildStarFromColorCombination()"<<endl;
01071                                                         cout<<"\t i_PotentialHub="<<i_PotentialHub<<endl;
01072                                                         cout<<"\t b_isConflict="<<b_isConflict<<endl;
01073                                                         cout<<"Color combination "<<pii_ColorCombination.first<<" "<<pii_ColorCombination.second<<endl;
01074                                                         cout<<"\t Looking at "<<pii_Edge.first<<"(color "<< m_vi_VertexColors[pii_Edge.first]<<")-"<<pii_Edge.second<<"(color "<< m_vi_VertexColors[pii_Edge.second]<<") "<<endl;
01075                                                         PrintColorCombination(Colors2Edge_Private, i_MaxNumThreads, pii_ColorCombination, 100);
01076                                                         PrintPotentialHub(PotentialHub_Private, i_thread_num, pii_ColorCombination);
01077 
01078 #if COLPACK_DEBUG_LEVEL > 100
01079                                                         cout<<" FAILED"<<endl;
01080                                                         //fout.close();
01081 #endif
01082                                                         Pause();
01083                                                 }
01084                                                 CoutLock::unset(); 
01085                                                 continue;
01086                                         }
01087                                         else if(i_PotentialHub == 1) { //only pii_Edge.first is a potential hub
01088                                                 mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.first);
01089                                                 if(mii_iter->second >=0) { // This is a single edge hub => mark the pii_Edge.first vertex as hub and (the other connected vertex + pii_Edge.second) as a leaf
01090                                                         PotentialHub_Private[i_thread_num][PotentialHub_Private[i_thread_num][pii_Edge.first] ] = -(pii_Edge.first+2);
01091                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -(pii_Edge.first+2);
01092                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -1;
01093                                                 }
01094                                                 else { // mii_iter->second = -1 : This is a hub with more than one edge => mark pii_Edge.second as a leaf
01095                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -(pii_Edge.first+2);
01096                                                 }
01097                                         }
01098                                         else if(i_PotentialHub == 2) { //only pii_Edge.second is a potential hub
01099                                                 mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.second);
01100                                                 if(mii_iter->second >=0) { // This is a single edge hub => mark the pii_Edge.second vertex as hub and (the other connected vertex + pii_Edge.first) as a leaf
01101                                                         PotentialHub_Private[i_thread_num][ PotentialHub_Private[i_thread_num][pii_Edge.second] ] = -(pii_Edge.second+2);
01102                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -(pii_Edge.second+2);
01103                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -1;
01104                                                 }
01105                                                 else { // mii_iter->second = -1 : This is a hub with more than one edge => mark pii_Edge.first as a leaf
01106                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -(pii_Edge.second+2);
01107                                                 }
01108                                         }
01109                                         else { // Both end of the vertices are seen for the first time => make them potential hubs
01110                                                 PotentialHub_Private[i_thread_num][pii_Edge.second] = pii_Edge.first;
01111                                                 PotentialHub_Private[i_thread_num][pii_Edge.first] = pii_Edge.second;
01112                                         }
01113 #ifdef COLPACK_DEBUG            
01114                                         cout<<" PASSED"<<endl;
01115 #endif
01116                                         
01117                                 }
01118                         }
01119                 }
01120                                 
01121                 //Make each vertex remember this combination and whether or not it is a leaf in this combination
01122                 int i_TheOtherColor = 0;
01123                 pair<int, int> pii_pair;
01124                 mii_iter = PotentialHub_Private[i_thread_num].begin();
01125                 for(;mii_iter != PotentialHub_Private[i_thread_num].end(); mii_iter++) {
01126                         if(m_vi_VertexColors[mii_iter->first] == pii_ColorCombination.first) i_TheOtherColor = pii_ColorCombination.second;
01127                         else i_TheOtherColor = pii_ColorCombination.first;
01128                         pii_pair.first = i_TheOtherColor;
01129                         pii_pair.second = mii_iter->second; // if pii_pair.second < -1, then mii_iter->first is a leaf and its hub can be calculated as [-(pii_pair.second+2)]
01130                         Vertex2ColorCombination_Private[i_thread_num][ mii_iter->first ].push_back(pii_pair);
01131                 }
01132         }
01133 
01134         
01138         int GraphColoring::DetectConflictInColorCombination(int i_MaxNumThreads, int i_thread_num, pair<int, int> pii_ColorCombination, map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private, 
01139                                              map< int, vector< pair<int, int> > > *Vertex2ColorCombination_Private, map< int, int> * PotentialHub_Private, vector< pair<int, int> >* ConflictedEdges_Private, vector<int>* ConflictCount_Private) {
01140                 int i_VertexCount = m_vi_Vertices.size() - 1;
01141                 map< pair<int, int>, Colors2Edge_Value, lt_pii >::iterator mpii_iter;
01142                 map< int, int>::iterator mii_iter;
01143                 int i_PotentialHub=0;
01144                 bool b_isConflict=false;
01145                 // reset PotentialHub_Private;
01146                 PotentialHub_Private[i_thread_num].clear();
01147                 
01148                 // !!! consider remove AppearanceCount_Private (if not used)
01149                 //reset AppearanceCount_Private[i_thread_num]
01150                 //for(int i=0; i<i_VertexCount;i++) AppearanceCount_Private[i_thread_num][i] = 0;
01151                 
01152 #ifdef COLPACK_DEBUG            
01153                 cout<<"Color combination "<<pii_ColorCombination.first<<" "<<pii_ColorCombination.second<<endl;
01154                 //cout<<"i_StartingIndex="<<i_StartingIndex<<endl;
01155 #endif
01156                 
01157                 // Now count the appearance of each vertex in the star collection
01158                 // Because we suppose to have a collection of stars, with any edge, only one vertex can have the count > 1. This property is used to detect conflict
01159                 for(int i= 0; i<i_MaxNumThreads; i++) {
01160                         mpii_iter = Colors2Edge_Private[i].find(pii_ColorCombination);
01161                         if(mpii_iter != Colors2Edge_Private[i].end()) { //Colors2Edge_Private[i] contains the color combination
01162                                 //vector<int> vi_ConflictedEdgeIndices;
01163                                 vector< pair<int, int> >* vpii_EdgesPtr = &(mpii_iter->second.value);
01164                                 
01165                                 pair<int, int> pii_Edge;
01166                                 // now start counting the appearance of vertices and detect conflict
01167                                 for(int j=0; j< vpii_EdgesPtr->size(); j++  ) {
01168                                         pii_Edge = (*vpii_EdgesPtr)[j];
01169                                         //#pragma omp critical
01170                                         //{i_ProcessedEdgeCount++;}
01171 #ifdef COLPACK_DEBUG            
01172                                         //if(pii_ColorCombination.first==1 && pii_ColorCombination.second==2 && pii_Edge.first==1 && pii_Edge.second==3) cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;
01173                                         cout<<"\t Looking at "<<pii_Edge.first<<"-"<<pii_Edge.second<<endl<<flush;
01174 #endif
01175                                         i_PotentialHub=0;
01176                                         b_isConflict=false;
01177                                         //check and see if either end of the edge could be a potential hub
01178                                         mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.first);
01179                                         if(mii_iter != PotentialHub_Private[i_thread_num].end()) {
01180                                                 if( mii_iter->second >=-1) {
01181                                                         //pii_Edge.first is a potential hub
01182                                                         i_PotentialHub += 1;
01183                                                 }
01184                                                 else {
01185                                                         b_isConflict=true;
01186                                                 }
01187                                         }
01188                                         mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.second);
01189                                         if(mii_iter != PotentialHub_Private[i_thread_num].end()) {
01190                                                 if( mii_iter->second >=-1) {
01191                                                 //pii_Edge.second is a potential hub
01192                                                         i_PotentialHub += 2;
01193                                                 }
01194                                                 else {
01195                                                         b_isConflict=true;
01196                                                 }
01197                                         }
01198                                         
01199                                         if(i_PotentialHub == 3 || b_isConflict) { // pii_Edge.first and pii_Edge.second are both potential hubs || conflict has been detected => add this edge into ConflictedEdges_Private
01200                                                 //Detect conflict
01201                                                 ConflictedEdges_Private[i_thread_num].push_back(pii_Edge);
01202                                                 //vi_ConflictedEdgeIndices.push_back(j);
01203                                                 ConflictCount_Private[i_thread_num][pii_Edge.first]++;
01204                                                 ConflictCount_Private[i_thread_num][pii_Edge.second]++;
01205 #if COLPACK_DEBUG_LEVEL > 100
01206                                                 cout<<"\t\t"<<pii_Edge.first<<"-"<<pii_Edge.second<<" FAILED"<<endl<<flush;
01207                                                 #pragma omp critical
01208                                                 {
01209                                                         fout<<"\t\t"<<pii_Edge.first<<"-"<<pii_Edge.second<<" FAILED"<<endl;
01210                                                 }
01211 #endif
01212                                                 continue;
01213                                         }
01214                                         else if(i_PotentialHub == 1) { //only pii_Edge.first is a potential hub
01215                                                 mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.first);
01216                                                 if(mii_iter->second >=0) { // This is a single edge hub => mark the pii_Edge.first vertex as hub and (the other connected vertex + pii_Edge.second) as a leaf
01217                                                         PotentialHub_Private[i_thread_num][PotentialHub_Private[i_thread_num][pii_Edge.first] ] = -(pii_Edge.first+2);
01218                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -(pii_Edge.first+2);
01219                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -1;
01220                                                 }
01221                                                 else { // mii_iter->second = -1 : This is a hub with more than one edge => mark pii_Edge.second as a leaf
01222                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -(pii_Edge.first+2);
01223                                                 }
01224                                         }
01225                                         else if(i_PotentialHub == 2) { //only pii_Edge.second is a potential hub
01226                                                 mii_iter = PotentialHub_Private[i_thread_num].find(pii_Edge.second);
01227                                                 if(mii_iter->second >=0) { // This is a single edge hub => mark the pii_Edge.second vertex as hub and (the other connected vertex + pii_Edge.first) as a leaf
01228                                                         PotentialHub_Private[i_thread_num][ PotentialHub_Private[i_thread_num][pii_Edge.second] ] = -(pii_Edge.second+2);
01229                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -(pii_Edge.second+2);
01230                                                         PotentialHub_Private[i_thread_num][pii_Edge.second] = -1;
01231                                                 }
01232                                                 else { // mii_iter->second = -1 : This is a hub with more than one edge => mark pii_Edge.first as a leaf
01233                                                         PotentialHub_Private[i_thread_num][pii_Edge.first] = -(pii_Edge.second+2);
01234                                                 }
01235                                         }
01236                                         else { // Both end of the vertices are seen for the first time => make them potential hubs
01237                                                 PotentialHub_Private[i_thread_num][pii_Edge.second] = pii_Edge.first;
01238                                                 PotentialHub_Private[i_thread_num][pii_Edge.first] = pii_Edge.second;
01239                                         }
01240 #if COLPACK_DEBUG_LEVEL > 100
01241                                         cout<<"\t\t"<<pii_Edge.first<<"-"<<pii_Edge.second<<" PASSED"<<endl;
01242                                         #pragma omp critical
01243                                         {
01244                                                 fout<<"\t\t"<<pii_Edge.first<<"-"<<pii_Edge.second<<" PASSED"<<endl;
01245                                         }
01246 #endif
01247                                         
01248                                         /*
01249                                         if( (pii_Edge.first==18310 && pii_Edge.second==18342) || (pii_Edge.first==11413 && pii_Edge.second==11506) 
01250                                             || (pii_Edge.first==117989 && pii_Edge.second==118105) || (pii_Edge.first==46761 && pii_Edge.second==46798)) {
01251                                                 #pragma omp critical
01252                                                 {
01253                                                         cout<<"\t\t"<<pii_Edge.first<<"-"<<pii_Edge.second<<" PASSED"<<endl;
01254                                                         PrintColorCombination(Colors2Edge_Private, i_MaxNumThreads, pii_ColorCombination, 100);
01255                                                         PrintPotentialHub(PotentialHub_Private, i_thread_num, pii_ColorCombination);
01256                                                         Pause();
01257                                                 }
01258                                         }
01259                                         //*/
01260                                         
01261                                         /* !!! consider remove
01262                                         if(AppearanceCount_Private[i_thread_num][pii_Edge.first]>0 && AppearanceCount_Private[i_thread_num][pii_Edge.second]>0) {
01263                                                 //Detect conflict
01264                                                 ConflictedEdges_Private[i_thread_num].push_back(pii_Edge);
01265                                                 ConflictCount_Private[i_thread_num][pii_Edge.first]++;
01266                                                 ConflictCount_Private[i_thread_num][pii_Edge.second]++; 
01267                                                 continue;
01268                                         }
01269                                         AppearanceCount_Private[i_thread_num][pii_Edge.first]++;
01270                                         AppearanceCount_Private[i_thread_num][pii_Edge.second]++;
01271                                         //*/
01272                                 }
01273                                 
01274                                 /*
01275                                 
01276                                 //Remove conflict edges out of this ColorCombination
01277                                 for(int j=vi_ConflictedEdgeIndices.size()-1; j>=0;j--) {
01278                                         if(vi_ConflictedEdgeIndices[j] != (vpii_EdgesPtr->size()-1)) {
01279                                                 (*vpii_EdgesPtr)[ vi_ConflictedEdgeIndices[j] ] = (*vpii_EdgesPtr)[ vpii_EdgesPtr->size()-1 ];                                          
01280                                         }
01281                                         vpii_EdgesPtr->pop_back();
01282                                 }
01283                                 
01284                                 //Make each vertex remember this combination and whether or not it is a leaf in this combination
01285                                 int i_TheOtherColor = 0;
01286                                 pair<int, int> pii_pair;
01287                                 mii_iter = PotentialHub_Private[i_thread_num].begin();
01288                                 for(;mii_iter != PotentialHub_Private[i_thread_num].end(); mii_iter++) {
01289                                         if(m_vi_VertexColors[mii_iter->first] == pii_ColorCombination.first) i_TheOtherColor = pii_ColorCombination.second;
01290                                         else i_TheOtherColor = pii_ColorCombination.first;
01291                                         pii_pair.first = i_TheOtherColor;
01292                                         pii_pair.second = mii_iter->second; // if pii_pair.second < -1, then mii_iter->first is a leaf and its hub can be calculated as [-(pii_pair.second+2)]
01293                                         Vertex2ColorCombination_Private[i_thread_num][ mii_iter->first ].push_back(pii_pair);
01294                                 }
01295                                 //*/
01296                         }
01297                 }
01298                 
01299                 return(_TRUE);
01300         }
01301         
01302         int GraphColoring::PrintColorCombination(map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private, int i_MaxNumThreads, pair<int, int> pii_ColorCombination, int i_MaxElementsOfCombination) {
01303                 cout<<"PrintColorCombination "<<pii_ColorCombination.first<<"-"<<pii_ColorCombination.second<<": "<<endl;
01304                 int i_ElementCount = 0, i_TotalElementsOfCombination=0;
01305                 for(int i=0; i< i_MaxNumThreads; i++) {
01306                         map< pair<int, int>, Colors2Edge_Value , lt_pii>::iterator itr = Colors2Edge_Private[i].find(pii_ColorCombination);
01307                         if(itr != Colors2Edge_Private[i].end()) {
01308                                 i_TotalElementsOfCombination += (itr->second.value).size();
01309                         }
01310                 }
01311                 for(int i=0; i< i_MaxNumThreads; i++) {
01312                         map< pair<int, int>, Colors2Edge_Value , lt_pii>::iterator itr = Colors2Edge_Private[i].find(pii_ColorCombination);
01313                         if(itr != Colors2Edge_Private[i].end()) {
01314                                 cout<<"(thread "<<i<<") ";
01315                                 vector< pair<int, int> > *Edges = &(itr->second.value);
01316                                 for(int ii=0; ii< (*Edges).size(); ii++) {
01317                                         cout<<(*Edges)[ii].first<<"-"<<(*Edges)[ii].second<<"; ";
01318                                         i_ElementCount++;
01319                                         if( i_ElementCount >= i_MaxElementsOfCombination) {
01320                                                 cout<<" MAX #="<<i_MaxElementsOfCombination <<" REACHED. Total elements="<<i_TotalElementsOfCombination;
01321                                                 break;
01322                                         }
01323                                 }
01324                                 cout<<endl;
01325                                 if( i_ElementCount >= i_MaxElementsOfCombination) break;
01326                         }
01327                 }
01328         }
01329         
01330         int GraphColoring::PrintAllColorCombination(map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private, int i_MaxNumThreads, int i_MaxNumOfCombination, int i_MaxElementsOfCombination) {
01331                 cout<<"PrintAllColorCombination"<<endl;
01332                 map< pair<int, int>, bool, lt_pii > mpiib_VisitedColorCombination;
01333                 for(int i=0; i< i_MaxNumThreads; i++) {
01334                         map< pair<int, int>, Colors2Edge_Value , lt_pii>::iterator itr = Colors2Edge_Private[i].begin();
01335                         
01336                         for(; itr != Colors2Edge_Private[i].end(); itr++) {
01337                                 if(mpiib_VisitedColorCombination.find(itr->first) == mpiib_VisitedColorCombination.end()) {
01338                                         mpiib_VisitedColorCombination[itr->first] = true;
01339                                         cout<<"Combination "<<itr->first.first<<"-"<<itr->first.second<<": "<<endl;
01340                                         int i_ElementCount = 0;
01341                                         for(int ii=i; ii<i_MaxNumThreads; ii++) {
01342                                                 map< pair<int, int>, Colors2Edge_Value , lt_pii>::iterator itr2 = Colors2Edge_Private[ii].find(itr->first);
01343                                                 if(itr2 != Colors2Edge_Private[ii].end()) {
01344                                                         cout<<"(thread "<<ii<<") ";
01345                                                         vector< pair<int, int> > *Edges = &(itr2->second.value);
01346                                                         for(int iii=0; iii< (*Edges).size(); iii++) {
01347                                                                 cout<<(*Edges)[iii].first<<"-"<<(*Edges)[iii].second<<"; ";
01348                                                                 i_ElementCount++;
01349                                                                 if( i_ElementCount >= i_MaxElementsOfCombination) break;
01350                                                         }
01351                                                         if( i_ElementCount >= i_MaxElementsOfCombination) break;
01352                                                 }
01353                                         }
01354                                         cout<<endl;
01355                                 }
01356                                 if(mpiib_VisitedColorCombination.size() >= i_MaxNumOfCombination) break;
01357                         }
01358                         if(mpiib_VisitedColorCombination.size() >= i_MaxNumOfCombination) break;
01359                 }
01360                 cout<<endl;
01361                 
01362                 return(_TRUE);
01363         }
01364         
01365         int GraphColoring::PrintVertex2ColorCombination(int i_MaxNumThreads, map< int, vector< pair<int, int> > > *Vertex2ColorCombination_Private) {
01366                 int i_VertexCount = m_vi_Vertices.size() - 1;
01367                 map< int, vector< pair<int, int> > >::iterator itr;
01368                 cout<<"PrintVertex2ColorCombination"<<endl;
01369                 
01370                 for(int i=0; i<i_VertexCount;i++) {
01371                         cout<<"\t Vertex "<<i;
01372                         if(m_vi_VertexColors[i]==_UNKNOWN) {
01373                                 cout<<" color UNKNOWN"<<endl;
01374                                 continue;
01375                         }
01376                         else {
01377                                 cout<<" color "<< m_vi_VertexColors[i] <<endl;
01378                         }
01379                         for(int ii=0; ii<i_MaxNumThreads;ii++) {
01380                                 
01381                                 itr = Vertex2ColorCombination_Private[ii].find(i) ;
01382                                 if(itr !=Vertex2ColorCombination_Private[ii].end()) {
01383                                         cout<<"\t   Thread "<<ii<<" size()="<<itr->second.size()<<endl;
01384                                         for(int iii=0; iii<itr->second.size();iii++) {
01385                                                 cout<<"\t\t( Color "<<(itr->second)[iii].first<< ";";
01386                                                 if( (itr->second)[iii].second > -1) {
01387                                                         cout<<" NO hub, connect to "<<(itr->second)[iii].second;
01388                                                 }
01389                                                 else if ( (itr->second)[iii].second == -1) {
01390                                                         cout<<" HUB";
01391                                                 }
01392                                                 else { // (*itr)[iii].second < -1
01393                                                         cout<<" LEAF of hub "<<-((itr->second)[iii].second+2);
01394                                                 }
01395                                                 cout<<")"<<endl;
01396                                         }
01397                                 }
01398                         }
01399                 }
01400                 cout<<"DONE PrintVertex2ColorCombination"<<endl;
01401                 
01402                 
01403                 return(_TRUE);
01404         }
01405         
01406         int GraphColoring::PrintConflictEdges(vector< pair<int, int> > *ConflictedEdges_Private, int i_MaxNumThreads) {
01407                 cout<<"PrintConflictEdges"<<endl;
01408                 for(int i=0; i<i_MaxNumThreads;i++) {
01409                         for(int ii=0; ii<ConflictedEdges_Private[i].size();ii++) {
01410                                 cout<<ConflictedEdges_Private[i][ii].first<<"-"<< ConflictedEdges_Private[i][ii].second <<endl;
01411                         }
01412                 }
01413                 cout<<endl;
01414                 
01415                 return(_TRUE);
01416         }
01417         
01418         int GraphColoring::PrintConflictCount(vector<int> &ConflictCount) {
01419                 cout<<"PrintConflictCount"<<endl;
01420                 for(int i=0; i<ConflictCount.size(); i++) {
01421                         cout<<"Vertex "<<i<<": "<<ConflictCount[i]<<endl;
01422                 }
01423                 cout<<endl;
01424                 
01425                 return(_TRUE);
01426         }
01427         
01428         int GraphColoring::PickVerticesToBeRecolored(int i_MaxNumThreads, vector< pair<int, int> > *ConflictedEdges_Private, vector<int> &ConflictCount) {
01429 #if COLPACK_DEBUG_LEVEL > 100
01430                 fout<<"PickVerticesToBeRecolored ..."<<endl;
01431 #endif
01432 #ifdef _OPENMP
01433                 #pragma omp parallel for schedule(static,1) default(none) shared(cout, ConflictedEdges_Private, ConflictCount, i_MaxNumThreads) 
01434 #endif
01435                 for(int i=0; i<i_MaxNumThreads; i++) {
01436                         for(int j=0; j< ConflictedEdges_Private[i].size(); j++) {
01437                                 pair<int, int> pii_Edge = ConflictedEdges_Private[i][j];
01438                                 //before decide which end, remember to check if one end's color is already removed. If this is the case, just skip to the next conflicted edge.
01439                                 if(m_vi_VertexColors[pii_Edge.first] == _UNKNOWN || m_vi_VertexColors[pii_Edge.second] == _UNKNOWN ) continue;
01440                                 
01441                                 if(ConflictCount[pii_Edge.first] > ConflictCount[pii_Edge.second]) {
01442                                         m_vi_VertexColors[pii_Edge.first] = _UNKNOWN;
01443 #if COLPACK_DEBUG_LEVEL > 100
01444                                         cout<<"\t Pick "<< pii_Edge.first <<endl;
01445                                         #pragma omp critical
01446                                         {
01447                                                 fout<<"\t Pick "<<pii_Edge.first<<endl;
01448                                         }
01449 #endif
01450                                 }
01451                                 else if (ConflictCount[pii_Edge.first] < ConflictCount[pii_Edge.second]) {
01452                                         m_vi_VertexColors[pii_Edge.second] = _UNKNOWN;
01453 #if COLPACK_DEBUG_LEVEL > 100
01454                                         cout<<"\t Pick "<< pii_Edge.second <<endl;
01455                                         #pragma omp critical
01456                                         {
01457                                                 fout<<"\t Pick "<<pii_Edge.second<<endl;
01458                                         }
01459 #endif
01460                                 }
01461                                 else { //ConflictCount[pii_Edge.first] == ConflictCount[pii_Edge.second]
01462                                         if(pii_Edge.first < pii_Edge.second) {
01463                                                 m_vi_VertexColors[pii_Edge.first] = _UNKNOWN;
01464 #if COLPACK_DEBUG_LEVEL > 100
01465                                                 cout<<"\t Pick "<< pii_Edge.first <<endl;
01466                                                 #pragma omp critical
01467                                                 {
01468                                                         fout<<"\t Pick "<<pii_Edge.first<<endl;
01469                                                 }
01470 #endif
01471                                         }
01472                                         else {
01473                                                 m_vi_VertexColors[pii_Edge.second] = _UNKNOWN;
01474 #if COLPACK_DEBUG_LEVEL > 100
01475                                                 cout<<"\t Pick "<< pii_Edge.second <<endl;
01476                                                 #pragma omp critical
01477                                                 {
01478                                                         fout<<"\t Pick "<<pii_Edge.second<<endl;
01479                                                 }
01480 #endif
01481                                         }
01482                                 }
01483                         }
01484                 }
01485                 /*
01486                 bool* ip_VerticesToBeRecolored = new bool[i_VertexCount];
01487 #ifdef _OPENMP
01488                 #pragma omp parallel for schedule(static,50) default(none) shared(i_VertexCount, ip_VerticesToBeRecolored) 
01489 #endif
01490                 for(int i=0; i<i_VertexCount; i++) {
01491                         ip_VerticesToBeRecolored[i] = false;
01492                 }
01493 #ifdef _OPENMP
01494                 #pragma omp parallel for schedule(static,1) default(none) shared(i_VertexCount, ConflictedEdges_Private, ip_VerticesToBeRecolored, ConflictCount, i_MaxNumThreads) 
01495 #endif
01496                 for(int i=0; i<i_MaxNumThreads; i++) {
01497                         for(int j=0; j< ConflictedEdges_Private[i].size(); j++) {
01498                                 pair<int, int> pii_Edge = ConflictedEdges_Private[i][j];
01499                                 if(ConflictCount[pii_Edge.first] > ConflictCount[pii_Edge.second]) {
01500                                         ip_VerticesToBeRecolored[pii_Edge.first] = true;
01501                                 }
01502                                 else if (ConflictCount[pii_Edge.first] < ConflictCount[pii_Edge.second]) {
01503                                         ip_VerticesToBeRecolored[pii_Edge.second] = true;
01504                                 }
01505                                 else { //ConflictCount[pii_Edge.first] == ConflictCount[pii_Edge.second]
01506                                         if(pii_Edge.first < pii_Edge.second) {
01507                                                 ip_VerticesToBeRecolored[pii_Edge.first] = true;
01508                                         }
01509                                         else {
01510                                                 ip_VerticesToBeRecolored[pii_Edge.second] = true;
01511                                         }
01512                                 }
01513                         }
01514                 }
01515                 int i_TotalVertexToBeRecolored=0;
01516 #ifdef _OPENMP
01517                 #pragma omp parallel for schedule(static,50) default(none) shared(i_VertexCount, ip_VerticesToBeRecolored) reduction(+:i_TotalVertexToBeRecolored)
01518 #endif
01519                 for(int i=0; i<i_VertexCount; i++) {
01520                         if(ip_VerticesToBeRecolored[i] == true) i_TotalVertexToBeRecolored = i_TotalVertexToBeRecolored+1;
01521                 }
01522                 //*/
01523                 return (_TRUE);
01524         }
01525         
01526         int GraphColoring::BuildVertex2ColorCombination(int i_MaxNumThreads, map< int, vector< pair<int, int> > > *Vertex2ColorCombination_Private, vector< map <int, int > > *Vertex2ColorCombination) {
01527                 int i_VertexCount = m_vi_Vertices.size() - 1;
01528                 (*Vertex2ColorCombination).resize(i_VertexCount);
01529                 
01530                 // Build Vertex2ColorCombination
01531 #ifdef _OPENMP
01532                 #pragma omp parallel for default(none) shared(i_VertexCount, Vertex2ColorCombination_Private, Vertex2ColorCombination, i_MaxNumThreads) 
01533 #endif
01534                 for(int i=0; i<i_VertexCount;i++) {
01535                         int i_thread_num;
01536 #ifdef _OPENMP
01537                         i_thread_num = omp_get_thread_num();
01538 #else
01539                         i_thread_num = 0;
01540 #endif
01541                         map< int, vector< pair<int, int> > >::iterator iter;
01542                         for(int ii=0; ii<i_MaxNumThreads;ii++) {
01543                                 iter = Vertex2ColorCombination_Private[ii].find(i);
01544                                 if(iter != Vertex2ColorCombination_Private[ii].end()) {
01545                                         vector< pair<int, int> >* vpii_Ptr = & (iter->second);
01546                                         for(int iii=0; iii< vpii_Ptr->size(); iii++) {
01547                                                 (*Vertex2ColorCombination)[i][(*vpii_Ptr)[iii].first] = (*vpii_Ptr)[iii].second;
01548                                         }
01549                                         
01550                                 }
01551                         }
01552                 }
01553                 
01554                 // Deallocate memory for Vertex2ColorCombination_Private
01555                 for(int i=0; i<i_MaxNumThreads;i++) {
01556                         Vertex2ColorCombination_Private[i].clear();
01557                 }
01558                 delete[] Vertex2ColorCombination_Private;
01559                 return (_TRUE);
01560         }
01561         
01562         int GraphColoring::PrintD1Colors(map<int, int>* D1Colors, int i_thread_num) {
01563                 cout<<"PrintD1Colors"<<endl;
01564                 map<int, int>::iterator mib_itr = D1Colors[i_thread_num].begin();
01565                 // Note: Theoratically, the locks should have been released in the reverse order.Hope this won't cause any problem
01566                 for(;mib_itr != D1Colors[i_thread_num].end(); mib_itr++) {
01567                         cout<<flush<<"\t color "<<mib_itr->first<<"; count "<<mib_itr->second<<endl;
01568                 }                                                               
01569         }
01570         
01571         int GraphColoring::PrintForbiddenColors(map<int, bool>* mip_ForbiddenColors,int i_thread_num) {
01572                 map< int, bool >::iterator itr = mip_ForbiddenColors[i_thread_num].begin();
01573                 cout<<"PrintForbiddenColors for thread "<<i_thread_num<<": ";
01574                 for(; itr!= mip_ForbiddenColors[i_thread_num].end(); itr++) {
01575                         cout<< itr->first<<", ";
01576                 }
01577                 cout<<endl;
01578         }
01579         
01580         int GraphColoring::PrintSubGraph(map< int, map<int,bool> > *graph) {
01581                 cout<<"PrintSubGraph (0-based indexing)"<<endl;
01582                 map< int, map<int,bool> >::iterator itr = graph->begin();
01583                 for(; itr != graph->end(); itr++) {
01584                         cout<<"\t v "<<itr->first<<": ";
01585                         map<int,bool>::iterator itr2 = (itr->second).begin();
01586                         for(; itr2 != (itr->second).end(); itr2++) {
01587                                 cout<<" v "<<itr2->first<<";";
01588                         }
01589                         cout<<endl;
01590                 }
01591 
01592         }
01593         
01594         int GraphColoring::PrintVertexD1NeighborAndColor(int VertexIndex, int excludedVertex) {
01595                 if(VertexIndex > (int)m_vi_Vertices.size() - 2) {
01596                         cout<<"Illegal request. VertexIndex is too large. VertexIndex > m_vi_Vertices.size() - 2"<<endl;
01597                         return _FALSE;
01598                 }
01599                 if(VertexIndex < 0) {
01600                         cout<<"Illegal request. VertexIndex is too small. VertexIndex < 0"<<endl;
01601                         return _FALSE;
01602                 }
01603                 cout<<"Distance-1 neighbors of "<<VertexIndex<<" are (0-based): ";
01604                 for(int i=m_vi_Vertices[VertexIndex]; i<m_vi_Vertices[STEP_UP(VertexIndex)]; i++) {
01605                         if( excludedVertex == m_vi_Edges[i]) continue;
01606                         cout<<"v "<<m_vi_Edges[i]<<" (c "<<m_vi_VertexColors[m_vi_Edges[i]]<<" ); ";
01607                 }
01608                 cout<<"( # of edges = "<<m_vi_Vertices[STEP_UP(VertexIndex)] - m_vi_Vertices[VertexIndex]<<")"<<endl;
01609                 
01610                 return _TRUE;
01611         }
01612         
01613         int GraphColoring::FindDistance(int v1, int v2) {
01614                 cout<<"FindDistance between v "<<v1<<" and v "<<v2<<endl;
01615                 int i_Distance=0;
01616                 pair<int,int> pii_tmp; 
01617                 pii_tmp.first = v1; //.first is the vertexID
01618                 pii_tmp.second = -1; // .second is the parent
01619                 map<int, int> mib_IncludedVertices;
01620                 
01621                 // Step *: Run a BFS to get all vertices within  distance-<distance> of i_CenterVertex
01622                 queue<pair<int,int> > Q;
01623                 //cout<<"Push in v "<< pii_tmp.first<< " l "<<pii_tmp.second<<endl;
01624                 Q.push(pii_tmp);
01625                 mib_IncludedVertices[pii_tmp.first] = pii_tmp.second;
01626                 //cout<<"Q.size()="<<Q.size()<<endl;
01627                 while(Q.size() > 0 ) {
01628                         //cout<<"Q.size()="<<Q.size()<<endl;
01629                         pair<int,int> pii_CurrentVertex;
01630                         pii_CurrentVertex.first = Q.front().first; //pii_CurrentVertex
01631                         pii_CurrentVertex.second = Q.front().second; //pii_CurrentVertex
01632                         //cout<<"CurrentVertex "<< pii_CurrentVertex.first<< " from "<<pii_CurrentVertex.second<<endl;
01633                         
01634                         for(int i=m_vi_Vertices[pii_CurrentVertex.first]; i < m_vi_Vertices[pii_CurrentVertex.first+1]; i++) {
01635                                 int i_D1Neighbor = m_vi_Edges[i];
01636                                 //cout<<"i_D1Neighbor="<<i_D1Neighbor<<endl;
01637                                 
01638                                 if( mib_IncludedVertices.find(i_D1Neighbor) == mib_IncludedVertices.end() //make sure that i_D1Neighbor is not already included
01639                                 ) {
01640                                         pii_tmp.first = i_D1Neighbor;
01641                                         pii_tmp.second = pii_CurrentVertex.first;
01642                                         if(i_D1Neighbor == v2) {
01643                                                 cout<<"\t"<<pii_tmp.first;
01644                                                 while(pii_tmp.second != -1) {
01645                                                         pii_tmp.first = pii_tmp.second;
01646                                                         cout<<" <= "<<pii_tmp.first;
01647                                                         pii_tmp.second = mib_IncludedVertices[pii_tmp.first];
01648                                                         i_Distance++;
01649                                                 }
01650                                                 cout<<endl;
01651                                                 cout<< "\tDistance = "<<i_Distance<<endl;
01652                                                 return _TRUE;
01653                                         }
01654                                         //cout<<"Push in v "<< pii_tmp.first<< " l "<<pii_tmp.second<<endl;
01655                                         Q.push(pii_tmp);
01656                                         mib_IncludedVertices[pii_tmp.first] = pii_tmp.second;
01657                                 }
01658                         }
01659                           
01660                         Q.pop();                        
01661                 }
01662                 cout<<"\tDISCONNECTED"<<endl;
01663                 
01664                 return _FALSE;
01665         }
01666         
01667         int GraphColoring::BuildColorsSubGraph(map< int, map<int,bool> > *graph, map<int,bool> *mib_Colors) {
01668                 cout<<"BuildColorsSubGraph for colors: "<<endl;
01669                 map<int,bool>::iterator itr= (*mib_Colors).begin();
01670                 for(;itr != (*mib_Colors).end(); itr++) {
01671                         cout<<"\t c "<<itr->first<<endl;
01672                 }
01673 
01674                 if(  mib_Colors==NULL) {
01675                         cout<<"ERR: mib_Colors==NULL"<<endl;
01676                         return _FALSE;
01677                 }
01678                 if(  (*mib_Colors).size()==0) {
01679                         cout<<"ERR: (*mib_Colors).size()==0"<<endl;
01680                         return _FALSE;
01681                 }
01682                 // Step *: now build a subgraph with my own structure
01683                 for(int i=0; i<m_vi_Vertices.size()-1;i++) {
01684                         if((*mib_Colors).find(m_vi_VertexColors[i]) == (*mib_Colors).end()) continue;
01685                         
01686                         for(int ii=m_vi_Vertices[i]; ii<m_vi_Vertices[i+1];ii++) {
01687                                 int i_D1Neighbor = m_vi_Edges[ii];
01688                                 if(i<=i_D1Neighbor) continue;
01689                                 
01690                                 if((*mib_Colors).find(m_vi_VertexColors[i_D1Neighbor]) != (*mib_Colors).end()){
01691                                         (*graph)[i][i_D1Neighbor] = true;
01692                                         (*graph)[i_D1Neighbor][i] = true;
01693                                 }
01694                                 
01695                         }
01696                         
01697                 }
01698                 
01699                 return _TRUE;
01700         }
01701         
01702         int GraphColoring::BuildSubGraph(map< int, map<int,bool> > *graph, int i_CenterVertex, int distance, map<int, bool> *mib_FilterByColors) {
01703                 cout<<"BuildSubGraph centered at v "<<i_CenterVertex<<" distance="<<distance<<"... "<<endl;
01704                 map<int, bool> mib_IncludedVertices;
01705                 pair<int,int> pii_tmp; 
01706                 pii_tmp.first = i_CenterVertex; //.first is the vertexID
01707                 pii_tmp.second = 0; // .second is the level/distance
01708                 
01709                 // Step *: Run a BFS to get all vertices within  distance-<distance> of i_CenterVertex
01710                 queue<pair<int,int> > Q;
01711                 //cout<<"Push in v "<< pii_tmp.first<< " l "<<pii_tmp.second<<endl;
01712                 Q.push(pii_tmp);
01713                 mib_IncludedVertices[pii_tmp.first] = true;
01714                 //cout<<"Q.size()="<<Q.size()<<endl;
01715                 while(Q.size() > 0) {
01716                         pair<int,int> pii_CurrentVertex;
01717                         pii_CurrentVertex.first = Q.front().first; //pii_CurrentVertex
01718                         pii_CurrentVertex.second = Q.front().second; //pii_CurrentVertex
01719                         //cout<<"CurrentVertex "<< pii_CurrentVertex.first<< " l "<<pii_CurrentVertex.second<<endl;
01720                         
01721                         int i_NexLevel = pii_CurrentVertex.second+1;
01722                         if(i_NexLevel<=distance) {
01723                                 //cout<<"i_NexLevel<=distance"<<endl;
01724                                 for(int i=m_vi_Vertices[pii_CurrentVertex.first]; i < m_vi_Vertices[pii_CurrentVertex.first+1]; i++) {
01725                                         int i_D1Neighbor = m_vi_Edges[i];
01726                                         //cout<<"i_D1Neighbor="<<i_D1Neighbor<<endl;
01727                                         
01728                                         if( mib_IncludedVertices.find(i_D1Neighbor) == mib_IncludedVertices.end() //make sure that i_D1Neighbor is not already included
01729                                         ) {
01730                                                 pii_tmp.first = i_D1Neighbor;
01731                                                 pii_tmp.second = i_NexLevel;
01732                                                 //cout<<"Push in v "<< pii_tmp.first<< " l "<<pii_tmp.second<<endl;
01733                                                 Q.push(pii_tmp);
01734                                                 mib_IncludedVertices[pii_tmp.first] = true;
01735                                         }
01736                                 }
01737                         }
01738                           
01739                         Q.pop();                        
01740                 }
01741                 
01742                 cout<<" ... "<<endl;
01743                 
01744                 // Step *: now build a subgraph with my own structure
01745                 map<int,bool> mib_tmp;
01746                 for(int i=0; i<m_vi_Vertices.size()-1;i++) {
01747                         if(mib_IncludedVertices.find(i) == mib_IncludedVertices.end()) continue;
01748                         (*graph)[i] = mib_tmp; // just to make sure that my graphs will have all vertices (even when the vertex has no edge)
01749                         if(  mib_FilterByColors==NULL //NOT filter by colors
01750                                 || ((*mib_FilterByColors).size()>0 && (*mib_FilterByColors).find(m_vi_VertexColors[i])!=(*mib_FilterByColors).end() ) // filter by colors
01751                           ) {
01752 
01753                                 for(int ii=m_vi_Vertices[i]; ii<m_vi_Vertices[i+1];ii++) {
01754                                         int i_D1Neighbor = m_vi_Edges[ii];
01755                                         if(  mib_FilterByColors==NULL //NOT filter by colors
01756                                               || ((*mib_FilterByColors).size()>0 && (*mib_FilterByColors).find(m_vi_VertexColors[i_D1Neighbor])!=(*mib_FilterByColors).end() ) // filter by colors
01757                                         ){
01758                                                 if(mib_IncludedVertices.find(i_D1Neighbor) != mib_IncludedVertices.end()){
01759                                                         (*graph)[i][i_D1Neighbor] = true;
01760                                                 }
01761                                         }
01762                                 }
01763                         }
01764                 }
01765                 
01766                 //PrintSubGraph(graph);
01767                 //vector<int> vi_VertexColors; 
01768                 //GetVertexColors(vi_VertexColors);
01769                 //displayGraph(graph, &vi_VertexColors);
01770                 //Pause();
01771                 
01772                 cout<<"DONE"<<endl;
01773                 
01774                 return _TRUE;
01775         }
01776         
01777         int GraphColoring::BuildConnectedSubGraph(map< int, map<int,bool> > *graph, int i_CenterVertex, int distance, map<int, bool> *mib_FilterByColors) {
01778                 cout<<"BuildConnectedSubGraph i_CenterVertex="<<i_CenterVertex<<" distance="<<distance<<"... "<<endl;
01779                 map<int, bool> mib_IncludedVertices;
01780                 pair<int,int> pii_tmp; 
01781                 pii_tmp.first = i_CenterVertex; //.first is the vertexID
01782                 pii_tmp.second = 0; // .second is the level/distance
01783                 
01784                 // Step *: Run a BFS to get all vertices within  distance-<distance> of i_CenterVertex
01785                 queue<pair<int,int> > Q;
01786                 //cout<<"Push in v "<< pii_tmp.first<< " l "<<pii_tmp.second<<endl;
01787                 Q.push(pii_tmp);
01788                 mib_IncludedVertices[pii_tmp.first] = true;
01789                 //cout<<"Q.size()="<<Q.size()<<endl;
01790                 while(Q.size() > 0) {
01791                         pair<int,int> pii_CurrentVertex;
01792                         pii_CurrentVertex.first = Q.front().first; //pii_CurrentVertex
01793                         pii_CurrentVertex.second = Q.front().second; //pii_CurrentVertex
01794                         //cout<<"CurrentVertex "<< pii_CurrentVertex.first<< " l "<<pii_CurrentVertex.second<<endl;
01795                         
01796                         int i_NexLevel = pii_CurrentVertex.second+1;
01797                         if(i_NexLevel<=distance) {
01798                                 //cout<<"i_NexLevel<=distance # of D1 neighbors = "<< m_vi_Vertices[pii_CurrentVertex.first+1] - m_vi_Vertices[pii_CurrentVertex.first] <<endl;
01799                                 for(int i=m_vi_Vertices[pii_CurrentVertex.first]; i < m_vi_Vertices[pii_CurrentVertex.first+1]; i++) {
01800                                         int i_D1Neighbor = m_vi_Edges[i];
01801                                         //cout<<"i_D1Neighbor="<<i_D1Neighbor<<endl;
01802                                         
01803                                         if( mib_IncludedVertices.find(i_D1Neighbor) == mib_IncludedVertices.end() //make sure that i_D1Neighbor is not already included
01804                                               && (  mib_FilterByColors==NULL //NOT filter by colors
01805                                                     || ((*mib_FilterByColors).size()>0 && (*mib_FilterByColors).find(m_vi_VertexColors[i_D1Neighbor])!=(*mib_FilterByColors).end() ) // filter by colors
01806                                                  )
01807                                         ) {
01808                                                 pii_tmp.first = i_D1Neighbor;
01809                                                 pii_tmp.second = i_NexLevel;
01810                                                 //cout<<"Push in v "<< pii_tmp.first<< " l "<<pii_tmp.second<<endl;
01811                                                 Q.push(pii_tmp);
01812                                                 mib_IncludedVertices[pii_tmp.first] = true;
01813                                         }
01814                                 }
01815                         }
01816                           
01817                         Q.pop();                        
01818                 }
01819                 
01820                 cout<<" ... "<<endl;
01821                 
01822                 // Step *: now build a subgraph with my own structure
01823                 map<int,bool> mib_tmp;
01824                 for(int i=0; i<m_vi_Vertices.size()-1;i++) {
01825                         if(mib_IncludedVertices.find(i) == mib_IncludedVertices.end()) continue;
01826                         (*graph)[i] = mib_tmp; // just to make sure that my graphs will have all vertices (even when the vertex has no edge)
01827                         for(int ii=m_vi_Vertices[i]; ii<m_vi_Vertices[i+1];ii++) {
01828                                 int i_D1Neighbor = m_vi_Edges[ii];
01829                                 if(mib_IncludedVertices.find(i_D1Neighbor) != mib_IncludedVertices.end()){
01830                                         (*graph)[i][i_D1Neighbor] = true;
01831                                 }
01832                         }
01833                 }
01834                 
01835                 //PrintSubGraph(graph);
01836                 //vector<int> vi_VertexColors; 
01837                 //GetVertexColors(vi_VertexColors);
01838                 //displayGraph(graph, &vi_VertexColors);
01839                 //Pause();
01840                 
01841                 cout<<"DONE"<<endl;
01842                 
01843                 return _TRUE;
01844         }
01845         
01846         int GraphColoring::PrintVertexAndColorAdded(int i_MaxNumThreads, vector< pair<int, int> > *vi_VertexAndColorAdded, int i_LastNEntries) {
01847                 int i_MaxSize = vi_VertexAndColorAdded[0].size();
01848                 for(int i=1; i<i_MaxNumThreads;i++) {
01849                         if(vi_VertexAndColorAdded[i].size()>i_MaxSize) i_MaxSize=vi_VertexAndColorAdded[i].size();
01850                 }
01851                 
01852                 if(i_LastNEntries>i_MaxSize) i_LastNEntries=i_MaxSize;
01853                 cout<<"PrintVertexAndColorAdded the last "<< i_LastNEntries<<" entries"<<endl;
01854                 for(int i=i_MaxSize-i_LastNEntries; i<i_MaxSize;i++) {
01855                         cout<<"\t "<<setw(7)<<i<<": ";
01856                         for(int ii=0; ii<i_MaxNumThreads; ii++) {
01857                                 //if( ii< vi_VertexAndColorAdded[i].size() ) {
01858                                         cout<<"(v "<<setw(11)<<vi_VertexAndColorAdded[ii][i].first<<",c "<<setw(11)<<vi_VertexAndColorAdded[ii][i].second<<" )  ";
01859                                 //}
01860                                 //else cout<<setw(32)<<" ";
01861                         }
01862                         cout<<endl;
01863                 }
01864         }
01865         
01866         int GraphColoring::BuildForbiddenColors(int i_MaxNumThreads, int i_thread_num, int i_CurrentVertex, map<int, bool>* mip_ForbiddenColors, map<int, int>* D1Colors, vector<  map <int, int > > *Vertex2ColorCombination) {
01867                         mip_ForbiddenColors[i_thread_num].clear();
01868                         D1Colors[i_thread_num].clear();
01869                         
01870 #if COLPACK_DEBUG_LEVEL > 10            
01871                         //cout<<flush<<endl<<"degree of i_CurrentVertex "<<m_vi_Vertices[i_CurrentVertex+1]-m_vi_Vertices[i_CurrentVertex]<<endl;
01872 #endif
01873                         // count how many D1 colors are there and mark all of them as forbidden
01874                         for(int ii=m_vi_Vertices[i_CurrentVertex]; ii<m_vi_Vertices[i_CurrentVertex+1];ii++) {
01875                                 if(m_vi_VertexColors[m_vi_Edges[ii]] != _UNKNOWN) {
01876                                   int i_Color = m_vi_VertexColors[m_vi_Edges[ii]];
01877                                   if(D1Colors[i_thread_num].find(i_Color)==D1Colors[i_thread_num].end()) {
01878                                             D1Colors[i_thread_num][i_Color]=1;
01879                                             //mark forbidden color
01880                                             mip_ForbiddenColors[i_thread_num][i_Color] = true;
01881 #if COLPACK_DEBUG_LEVEL > 10            
01882                                             cout<<flush<<endl<<"Thread "<<i_thread_num<<": "<< "D1 color="<<i_Color<<"; SET count="<< D1Colors[i_thread_num][ i_Color]<<endl;
01883 #endif
01884                                   }
01885                                   else {
01886                                             D1Colors[i_thread_num][ i_Color]++;
01887 #if COLPACK_DEBUG_LEVEL > 10            
01888                                             cout<<flush<<endl<<"Thread "<<i_thread_num<<": "<< "D1 color="<<i_Color<<"; INCREASE count="<< D1Colors[i_thread_num][ i_Color]<<endl;
01889 #endif
01890                                   }
01891                                 }
01892                         }
01893 #if COLPACK_DEBUG_LEVEL > 10            
01894                         cout<<"after D1Colors is polulated"<<endl;
01895                         PrintD1Colors(D1Colors, i_thread_num);
01896 #endif
01897                         
01898                         /* mark forbidden color using these 2 rules:
01899                           * - if vertex with color appear more than once or _UNKOWN, forbid all colors that its D1 neighbors have
01900                           *    (its D1 neighbors have) => make a function for this so I can improve latter
01901                           * - if vertex with color appear once and is NOT a hub, forbid all of its hubs color
01902                           */
01903                         // !!! could to be improved ???
01904                         for(int ii=m_vi_Vertices[i_CurrentVertex]; ii<m_vi_Vertices[i_CurrentVertex+1];ii++) {
01905                                 int D1Neighbor = m_vi_Edges[ii];
01906                                 
01907                                 map <int, int >::iterator mii_iter = (*Vertex2ColorCombination)[D1Neighbor].begin();
01908                                 // !!! could this read from the hash table cause problem if we don't lock it?
01909                                 if( m_vi_VertexColors[D1Neighbor] == _UNKNOWN ) {
01910                                         // Note: the part (m_vi_VertexColors[D1Neighbor] == _UNKNOWN) here is conservative because I assume that if another thread is working on this vertex, it could pick the color D1Colors[i_thread_num][m_vi_VertexColors[D1Neighbor]] and make the whole thing bad
01911                                         // !!! might be able to improve by checking and ?communitation with other threads and see if they works on the vertices around me
01912                                         for(int iii=m_vi_Vertices[D1Neighbor]; iii<m_vi_Vertices[D1Neighbor+1]; iii++) {
01913                                                 int D2Neighbor = m_vi_Edges[iii];
01914                                                 if(D2Neighbor == i_CurrentVertex) {
01915                                                         continue;
01916                                                 }
01917                                                 if(m_vi_VertexColors[D2Neighbor] != _UNKNOWN) {
01918                                                         mip_ForbiddenColors[i_thread_num][m_vi_VertexColors[D2Neighbor]] = true;
01919                                                 }
01920                                         }
01921                                 }
01922                                 else if (D1Colors[i_thread_num][m_vi_VertexColors[D1Neighbor]] > 1 ) { 
01923                                         //forbid all colors that its D1 neighbors have                                          
01924                                         for(; mii_iter != (*Vertex2ColorCombination)[D1Neighbor].end(); mii_iter++) {
01925                                                 //mark mii_iter->first as forbidden
01926                                                 mip_ForbiddenColors[i_thread_num][mii_iter->first] = true;
01927                                         }
01928                                 }
01929                                 else {
01930                                         // For any color combinations that D1Neighbor is NOT a hub (i.e. a leaf or a non-HUB), forbid the color of the hub (in this color combination)                                          
01931                                         for(; mii_iter != (*Vertex2ColorCombination)[D1Neighbor].end(); mii_iter++) {
01932                                                 if(mii_iter->second != -1) { // D1Neighbor is NOT a hub in the combination (m_vi_VertexColors[D1Neighbor], mii_iter->first)
01933                                                         //mark mii_iter->first as forbidden
01934                                                         mip_ForbiddenColors[i_thread_num][mii_iter->first] = true;
01935                                                 }
01936                                         }
01937                                 }
01938                                 
01939                         }
01940         }
01941         
01942         int GraphColoring::StarColoring_serial2() {
01943                 if(CheckVertexColoring("STAR"))
01944                 {
01945                         return(_TRUE);
01946                 }
01947                 
01948                 int i_MaxNumThreads = 1;
01949                 int i_MaxColor;
01950                 if(m_i_VertexColorCount>0) i_MaxColor = m_i_VertexColorCount;
01951                 else i_MaxColor = 3;
01952                 int i_VertexCount = m_vi_Vertices.size() - 1;
01953                 m_vi_VertexColors.clear();
01954                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
01955                 
01956                 /*
01957                 for(int i=0; i<=i_MaxColor;i++) {
01958                         if(!omp_test_lock( vl_ColorLock[i] )) {
01959                                 cout<<"Fail to lock color "<<i<<endl;
01960                         }
01961                 }
01962                 //*/
01963                 
01964                 vector<int> vi_VerticesToBeColored;
01965                 vector<int>* vip_VerticesToBeRecolored_Private = new vector<int>[i_MaxNumThreads];
01966                 map<int, bool>* mip_ForbiddenColors = new map<int,bool>[i_MaxNumThreads];
01967                 map<int, int>* D1Colors = new map<int, int>[i_MaxNumThreads];
01968                 
01969                 vector<  map <int, int > > *Vertex2ColorCombination = new vector<  map <int, int > >;
01970                 (*Vertex2ColorCombination).resize(i_VertexCount);
01971                 
01972                 //Populate (vi_VerticesToBeColored)
01973                 for(int i=0 ; i< i_VertexCount; i++) {
01974                         int i_thread_num;
01975                         i_thread_num = 0;
01976                         vip_VerticesToBeRecolored_Private[i_thread_num].push_back(m_vi_OrderedVertices[i]);
01977                 }
01978                 
01979                 int* i_StartingIndex = new int[i_MaxNumThreads];
01980                 i_StartingIndex[0] = 0;
01981                 for(int i=1; i < i_MaxNumThreads; i++) {
01982                         i_StartingIndex[i] =  i_StartingIndex[i-1]+vip_VerticesToBeRecolored_Private[i-1].size();
01983                 }
01984                 vi_VerticesToBeColored.resize(i_StartingIndex[i_MaxNumThreads-1]+vip_VerticesToBeRecolored_Private[i_MaxNumThreads-1].size(),_UNKNOWN);
01985                 for(int i=0 ; i< i_MaxNumThreads; i++) {
01986                         for(int j=0; j<vip_VerticesToBeRecolored_Private[i].size();j++) {
01987                                 vi_VerticesToBeColored[i_StartingIndex[i]+j] = vip_VerticesToBeRecolored_Private[i][j];
01988                         }
01989                 }
01990                 
01991 #if COLPACK_DEBUG_LEVEL == 0            
01992                 int i_LoopCount = 0;
01993 #endif
01994                 while(vi_VerticesToBeColored.size()>0) {
01995 #if COLPACK_DEBUG_LEVEL == 0            
01996                         i_LoopCount++;
01997                         //cout<<"(loop "<<i_LoopCount<<") vi_VerticesToBeColored.size()="<<vi_VerticesToBeColored.size()<<"/"<<i_VertexCount<<endl;
01998                         //cout<<"(loop "<<i_LoopCount<<") i_MaxColor="<<i_MaxColor<<endl;
01999                         //Pause();
02000 #endif
02001                         // reinitialize vip_VerticesToBeRecolored_Private
02002                         for(int i=0; i < i_MaxNumThreads; i++) {
02003                                 vip_VerticesToBeRecolored_Private[i].clear();
02004                         }
02005                         
02006                         int i_RecolorCount = vi_VerticesToBeColored.size();
02007                         for(int i=0; i<i_RecolorCount;i++) {
02008                                 
02009                                 int i_thread_num = 0;
02010                                 int i_CurrentVertex = vi_VerticesToBeColored[i];
02011 //                              cout<<"v"<<i_CurrentVertex<<endl<<flush;
02012 //                              if(i_CurrentVertex==20 || i_CurrentVertex==21) {
02013 //                                      PrintVertex2ColorCombination(Vertex2ColorCombination);
02014 //                                      Pause();
02015 //                              }
02016 #if COLPACK_DEBUG_LEVEL > 10            
02017                                 cout<<flush<<endl<<"Thread "<<i_thread_num<<": "<<"works on v"<<i_CurrentVertex<<endl<<flush;
02018 #endif
02019                                 mip_ForbiddenColors[i_thread_num].clear();
02020                                 D1Colors[i_thread_num].clear();
02021                                 
02022 #if COLPACK_DEBUG_LEVEL > 10            
02023                                 cout<<flush<<endl<<"degree of i_CurrentVertex "<<m_vi_Vertices[i_CurrentVertex+1]-m_vi_Vertices[i_CurrentVertex]<<endl;
02024 #endif
02025                                 // DONE Step *: count how many D1 colors are there and mark all of them as forbidden
02026                                 for(int ii=m_vi_Vertices[i_CurrentVertex]; ii<m_vi_Vertices[i_CurrentVertex+1];ii++) {
02027                                         if(m_vi_VertexColors[m_vi_Edges[ii]] != _UNKNOWN) {
02028                                           int i_Color = m_vi_VertexColors[m_vi_Edges[ii]];
02029                                           if(D1Colors[i_thread_num].find(i_Color)==D1Colors[i_thread_num].end()) {
02030                                                     D1Colors[i_thread_num][i_Color]=1;
02031                                                     //mark forbidden color
02032                                                     mip_ForbiddenColors[i_thread_num][i_Color] = true;
02033 #if COLPACK_DEBUG_LEVEL > 10            
02034                                                     cout<<flush<<endl<<"Thread "<<i_thread_num<<": "<< "D1 color="<<i_Color<<"; SET count="<< D1Colors[i_thread_num][ i_Color]<<endl;
02035 #endif
02036                                           }
02037                                           else {
02038                                                     D1Colors[i_thread_num][ i_Color]++;
02039 #if COLPACK_DEBUG_LEVEL > 10            
02040                                                     cout<<flush<<endl<<"Thread "<<i_thread_num<<": "<< "D1 color="<<i_Color<<"; INCREASE count="<< D1Colors[i_thread_num][ i_Color]<<endl;
02041 #endif
02042                                           }
02043                                         }
02044                                 }
02045 #if COLPACK_DEBUG_LEVEL > 10            
02046                                 cout<<"after D1Colors is polulated"<<endl;
02047                                 PrintD1Colors(D1Colors, i_thread_num);
02048 #endif
02049 
02050 /*
02051                                 map<int, int>::iterator mib_itr2 = D1Colors[i_thread_num].begin();
02052                                 for(;mib_itr2 != D1Colors[i_thread_num].end(); mib_itr2++) {
02053                                         cout<<flush<<endl<<"Thread "<<i_thread_num<<": "<< "D1 color="<<mib_itr2->first<<"; count="<< mib_itr2->second<<endl;
02054                                 }
02055 //*/
02056 #if COLPACK_DEBUG_LEVEL > 10            
02057                                 PrintD1Colors(D1Colors, i_thread_num);
02058                                 cout<<"*Start marking forbidden color"<<endl;
02059 #endif
02060                                 
02061                                 /* DONE Step *: mark forbidden color using these 2 rules:
02062                                  * - if vertex with color appear more than once, forbid all colors that its D1 neighbors have
02063                                  *    (its D1 neighbors have) => make a function for this so I can improve latter
02064                                  * - if vertex with color appear once and is a LEAF, forbid all of its HUBs color.
02065                                  */
02066                                 // !!! could to be improved ???
02067                                 for(int ii=m_vi_Vertices[i_CurrentVertex]; ii<m_vi_Vertices[i_CurrentVertex+1];ii++) {
02068                                         int D1Neighbor = m_vi_Edges[ii];
02069 //                                      if(i_CurrentVertex==31) {
02070 //                                              cout<<"D1Neighbor="<<D1Neighbor<<" color="<< m_vi_VertexColors[D1Neighbor] <<endl;
02071 //                                              if(D1Neighbor==20) {
02072 //                                                      for(int iii=m_vi_Vertices[D1Neighbor]; iii<m_vi_Vertices[D1Neighbor+1];iii++) {
02073 //                                                              cout<<"\t D2Neighbor="<< m_vi_Edges[iii] <<" color="<< m_vi_VertexColors[m_vi_Edges[iii]]  <<endl;
02074 //                                                      }
02075 //                                                      
02076 //                                              }
02077 //                                      }
02078                                         if(m_vi_VertexColors[D1Neighbor] != _UNKNOWN) {
02079                                                 map <int, int >::iterator mii_iter = (*Vertex2ColorCombination)[D1Neighbor].begin();
02080                                                 if( D1Colors[i_thread_num][m_vi_VertexColors[D1Neighbor]] > 1 ) {
02081                                                         //forbid all colors that its D1 neighbors have                                          
02082                                                         for(; mii_iter != (*Vertex2ColorCombination)[D1Neighbor].end(); mii_iter++) {
02083                                                                 //mark mii_iter->first as forbidden
02084                                                                 mip_ForbiddenColors[i_thread_num][mii_iter->first] = true;
02085 //                                                              if(i_CurrentVertex==31) {
02086 //                                                                      cout<<"\t Forbid color "<<mii_iter->first<<" around v "<<D1Neighbor<<endl;
02087 //                                                              }
02088                                                         }
02089                                                 }
02090                                                 else {
02091                                                         // For any color combinations that this vertex is a LEAF, forbid the color of the hub (in this color combination)                                               
02092                                                         for(; mii_iter != (*Vertex2ColorCombination)[D1Neighbor].end(); mii_iter++) {
02093 //                                                              if(i_CurrentVertex==31 && D1Neighbor==20) {
02094 //                                                                      cout<<"\t mii_iter->first="<<mii_iter->first<<" mii_iter->second="<< mii_iter->second <<endl;
02095 //                                                              }
02096                                                                 if(mii_iter->second < -1) { // D1Neighbor is a leaf in the combination (m_vi_VertexColors[D1Neighbor], mii_iter->first)
02097                                                                         //mark mii_iter->first as forbidden
02098                                                                         mip_ForbiddenColors[i_thread_num][mii_iter->first] = true;
02099 //                                                                      if(i_CurrentVertex==31) {
02100 //                                                                              cout<<"\t Forbid color "<<mii_iter->first<<" of v "<<-(mii_iter->second+2)<<endl;
02101 //                                                                      }
02102                                                                 }
02103                                                         }
02104                                                 }
02105                                         }
02106                                 }
02107 #if COLPACK_DEBUG_LEVEL > 10    
02108                                 cout<<"*After finish marking forbidden color"<<endl;
02109                                 PrintD1Colors(D1Colors, i_thread_num);
02110 #endif
02111                                 
02112                                 /* Step *: Pick a color for the current vertex:
02113                                  * Among the available color, test the lock of that color and see if I can lock it
02114                                  *      if I'm able to lock one
02115                                  *      if all current color are locked, allocate a new color & its lock (push into vl_ColorLock)
02116                                  *              update i_MaxColor
02117                                  */
02118                                 int i_PotentialColor = 0;
02119                                 for(; i_PotentialColor<=i_MaxColor;i_PotentialColor++) {
02120                                         if(mip_ForbiddenColors[i_thread_num].find(i_PotentialColor) == mip_ForbiddenColors[i_thread_num].end()) { // if this color is not forbidden
02121                                                 // see if we could get the lock for this color
02122                                                 break;
02123                                         }
02124                                 }
02125                                 if(i_PotentialColor > i_MaxColor) { //we will need a new color
02126                                         i_MaxColor = i_PotentialColor;
02127                                 }
02128                                 // Now we have a color, i.e. i_PotentialColor
02129                                 m_vi_VertexColors[i_CurrentVertex] = i_PotentialColor;
02130                                 //cout<<"c "<<i_PotentialColor<<" for v "<<i_CurrentVertex<<endl;
02131                                 if(false){
02132                                 //#pragma omp critical
02133                                         {
02134                                                 pair<int,int> *pii_ConflictColorCombination = new pair<int,int>;
02135                                                 int i_ConflictVertex = CheckStarColoring_OMP(1, pii_ConflictColorCombination);
02136                                                 //PrintVertexAndColorAdded(i_MaxNumThreads ,vi_VertexAndColorAdded);
02137                                                 //Pause();
02138 
02139                                                 // !! find the 2 vertices and find the distance between them
02140                                                 if (i_ConflictVertex!=-1) {
02141                                                         //PrintVertexAndColorAdded(i_MaxNumThreads ,vi_VertexAndColorAdded);
02142                                                         cout<<"t"<<i_thread_num<<": After assign color "<<i_PotentialColor<<" to v "<<i_CurrentVertex<<endl;
02143                                                         PrintForbiddenColors(mip_ForbiddenColors, i_thread_num);
02144                                                         
02145                                                         //map< int, map<int,bool> > *graph = new map< int, map<int,bool> >;
02146                                                         //BuildConnectedSubGraph(graph , i_CurrentVertex, 1);
02147                                                         //vector<int> vi_VertexColors; 
02148                                                         //GetVertexColors(vi_VertexColors);
02149                                                         //displayGraph(graph, &vi_VertexColors, true, FDP);
02150                                                         //delete graph;
02151                                                         
02152                                                         //graph = new map< int, map<int,bool> >;
02153                                                         //BuildSubGraph(graph , i_CurrentVertex, 0);
02154                                                         //displayGraph(graph, &vi_VertexColors, true, FDP);
02155                                                         //delete graph;
02156                                                         
02157                                                         cout<<"i_ConflictVertex="<<i_ConflictVertex;
02158                                                         if(i_ConflictVertex>=0)cout<<" with color "<< m_vi_VertexColors[i_ConflictVertex];
02159                                                         cout<<endl;
02160                                                         //cout<<"i="<<i<<"/vi_VerticesToBeColored.size()="<<vi_VerticesToBeColored.size() <<"/i_VertexCount="<<i_VertexCount <<endl;
02161                                                         //displayVector(i_PotentialColor_Private,i_MaxNumThreads);
02162                                                         //displayVector(i_CurrentVertex_Private,i_MaxNumThreads);
02163                                                         cout<<"CheckStarColoring_OMP() FAILED"<<endl;
02164                                                         cout<<"conflict colors "<<(*pii_ConflictColorCombination).first<<" "<<(*pii_ConflictColorCombination).second<<endl;
02165                                                         /*
02166                                                         map<int, bool> VerticiesWithConflictColors;
02167                                                         for(int i=0; i<i_MaxNumThreads; i++) {
02168                                                                 if(i_PotentialColor_Private[i]==(*pii_ConflictColorCombination).first || i_PotentialColor_Private[i]==(*pii_ConflictColorCombination).second) {
02169                                                                         VerticiesWithConflictColors[ i_CurrentVertex_Private[i] ]=true;
02170                                                                         PrintForbiddenColors(mip_ForbiddenColors,i);
02171                                                                 }
02172                                                         }
02173                                                         cout<<"VerticiesWithConflictColors.size()="<< VerticiesWithConflictColors.size() <<endl;
02174                                                         for(map<int, bool>::iterator itr=VerticiesWithConflictColors.begin(); itr != VerticiesWithConflictColors.end(); itr++) {
02175                                                                 map<int, bool>::iterator itr2 = itr;itr2++;
02176                                                                 for(;  itr2 != VerticiesWithConflictColors.end(); itr2++) {
02177                                                                         FindDistance(itr->first, itr2->first);
02178                                                                 }                                                       
02179                                                         }
02180                                                         //*/
02181                                                         
02182                                                         cout<<"-----------------------------------"<<endl;
02183                                                         Pause();
02184                                                 }
02185                                                 delete pii_ConflictColorCombination;
02186                                         }
02187                                 }
02188 #if COLPACK_DEBUG_LEVEL > 10            
02189                                 cout<<flush<<endl<<"Thread "<<i_thread_num<<": "<<"Pick color "<< i_PotentialColor <<" for vertex "<<i_CurrentVertex<<endl<<flush;
02190 #endif
02191                                 
02192                                 /* Step *: update Vertex2ColorCombination
02193                                  */
02194                                 for(int ii=m_vi_Vertices[i_CurrentVertex]; ii<m_vi_Vertices[i_CurrentVertex+1];ii++) {
02195                                         int D1Neighbor = m_vi_Edges[ii];
02196                                         if(m_vi_VertexColors[D1Neighbor] != _UNKNOWN) {
02197                                                 if(D1Colors[i_thread_num][ m_vi_VertexColors[D1Neighbor] ] >1) {
02198                                                         //i_CurrentVertex should be a hub
02199                                                         (*Vertex2ColorCombination)[i_CurrentVertex][ m_vi_VertexColors[D1Neighbor] ] = -1; // mark i_CurrentVertex a hub of ( m_vi_VertexColors[i_CurrentVertex] , m_vi_VertexColors[D1Neighbor] ) combination
02200                                                         (*Vertex2ColorCombination)[D1Neighbor][m_vi_VertexColors[i_CurrentVertex]] = -(i_CurrentVertex+2); // mark D1Neighbor a leaf of ( m_vi_VertexColors[i_CurrentVertex] , m_vi_VertexColors[D1Neighbor] ) combination
02201                                                 }
02202                                                 // D1Colors[i_thread_num][ m_vi_VertexColors[D1Neighbor] ] == 1
02203                                                 else if ((*Vertex2ColorCombination)[D1Neighbor].find(m_vi_VertexColors[i_CurrentVertex]) != (*Vertex2ColorCombination)[D1Neighbor].end() ) {
02204                                                         int v2 = (*Vertex2ColorCombination)[D1Neighbor][m_vi_VertexColors[i_CurrentVertex]];
02205                                                         if(v2 != -1) {
02206                                                                 // D1Neighbor is currently connected to a vertice v2 with the same color as i_CurrentVertex (i.e. D1Neighbor and v2 formed a non-HUB)
02207                                                                 //cout<<"\t v2 "<<v2<<endl;
02208                                                                 (*Vertex2ColorCombination)[v2][m_vi_VertexColors[D1Neighbor]] = -(D1Neighbor+2);
02209                                                                 // D1Neighbor will become a hub now
02210                                                                 (*Vertex2ColorCombination)[D1Neighbor][m_vi_VertexColors[i_CurrentVertex]] = -1;
02211                                                         } // else D1Neighbor is already a HUB of this color combination
02212                                                         (*Vertex2ColorCombination)[i_CurrentVertex][m_vi_VertexColors[D1Neighbor]] = -(D1Neighbor+2);
02213                                                 }
02214                                                 else {
02215                                                         // D1Neighbor does not connect to any other vertex with the same color as i_CurrentVertex
02216                                                         //this edge is not a part of any hub (D1Neighbor canNOT be a LEAF)
02217                                                         (*Vertex2ColorCombination)[D1Neighbor][m_vi_VertexColors[i_CurrentVertex]] = i_CurrentVertex;
02218                                                         (*Vertex2ColorCombination)[i_CurrentVertex][m_vi_VertexColors[D1Neighbor]] = D1Neighbor;
02219                                                 }
02220                                         }
02221                                 }
02222                                 
02223                         }
02224                   
02225                         //Populate (vi_VerticesToBeColored)
02226                         vi_VerticesToBeColored.clear();
02227                         for(int i=1; i < i_MaxNumThreads; i++) {
02228                                 i_StartingIndex[i] =  i_StartingIndex[i-1]+vip_VerticesToBeRecolored_Private[i-1].size();
02229                                 //cout<<"i_StartingIndex["<< i <<"]="<<i_StartingIndex[i]<<endl;
02230                         }
02231                         vi_VerticesToBeColored.resize(i_StartingIndex[i_MaxNumThreads-1]+vip_VerticesToBeRecolored_Private[i_MaxNumThreads-1].size(),_UNKNOWN);
02232 #if COLPACK_DEBUG_LEVEL > 10            
02233                         cout<<"vi_VerticesToBeColored.size()="<<vi_VerticesToBeColored.size()<<endl;
02234 #endif
02235                         for(int i=0 ; i< i_MaxNumThreads; i++) {
02236                                 for(int j=0; j<vip_VerticesToBeRecolored_Private[i].size();j++) {
02237                                         vi_VerticesToBeColored[i_StartingIndex[i]+j] = vip_VerticesToBeRecolored_Private[i][j];
02238                                 }
02239                         }
02240                 }
02241                 
02242                 //
02243                 
02244                 delete Vertex2ColorCombination;
02245                 Vertex2ColorCombination=NULL;
02246                 delete[] vip_VerticesToBeRecolored_Private;
02247                 vip_VerticesToBeRecolored_Private = NULL;
02248                 delete[] mip_ForbiddenColors;
02249                 mip_ForbiddenColors = NULL;
02250                 delete[] D1Colors;
02251                 D1Colors=NULL;
02252                 
02253                 delete[] i_StartingIndex;
02254                 i_StartingIndex=NULL;
02255                 
02256                 m_i_VertexColorCount=i_MaxColor;
02257                 
02258                 return(_TRUE);
02259         }
02260         
02261         int GraphColoring::PrintVertex2ColorCombination (vector<  map <int, int > > *Vertex2ColorCombination) {
02262                 cout<<"PrintVertex2ColorCombination()"<<endl;
02263                 for(int i=0; i< (*Vertex2ColorCombination).size(); i++) {
02264                         cout<<"v "<<i<<" c "<<m_vi_VertexColors[i]<<endl;
02265                         map<int, int>::iterator mii_iter = (*Vertex2ColorCombination)[i].begin();
02266                         for(; mii_iter != (*Vertex2ColorCombination)[i].end(); mii_iter++) {
02267                                 if(mii_iter->second < -1) { // LEAF
02268                                         cout<<"\t is a LEAF of v "<<-(mii_iter->second+2)<<" c "<<mii_iter->first<<endl;
02269                                 }
02270                                 else if (mii_iter->second == -1) { // HUB
02271                                         cout<<"\t is a HUB with c "<<mii_iter->first<<endl;
02272                                 }
02273                                 else { // non-HUB
02274                                         cout<<"\t just connect with v "<<mii_iter->second<<" c "<<mii_iter->first<<" (non-HUB)"<<endl;
02275                                 }
02276                         }
02277                 }
02278         }
02279         
02280         int GraphColoring::PrintVertex2ColorCombination_raw (vector<  map <int, int > > *Vertex2ColorCombination) {
02281                 cout<<"PrintVertex2ColorCombination_raw()"<<endl;
02282                 for(int i=0; i< (*Vertex2ColorCombination).size(); i++) {
02283                         cout<<"v "<<i<<" c "<<m_vi_VertexColors[i]<<endl;
02284                         map<int, int>::iterator mii_iter = (*Vertex2ColorCombination)[i].begin();
02285                         for(; mii_iter != (*Vertex2ColorCombination)[i].end(); mii_iter++) {
02286                                 cout<<"\t Vertex2ColorCombination["<< i <<"][] "<<mii_iter->second<<" c "<<mii_iter->first<<endl;
02287                         }
02288                 }
02289         }
02290         
02291 
02292         int GraphColoring::StarColoring() {
02293                 return GraphColoring::StarColoring_serial2();
02294         }
02295                 
02296         
02297 
02298         // !!! if not use, remove this function.
02299         /* ?Possible improvement: A dedicate thread will be used to push the result into vi_VerticesToBeRecolored
02300          * NOTE: this routine will not work correctly if there are conflicts
02301          */
02302         int GraphColoring::BuildStarCollection(vector<int> & vi_VerticesToBeRecolored) {
02303           
02304                 int i, j, k;
02305                 int i_StarID, i_VertexOne, i_VertexTwo;
02306                 int i_VertexCount = m_vi_Vertices.size() - 1;
02307                 int i_EdgeCount = (signed) m_vi_Edges.size();
02308 
02309                 vector<int> vi_EdgeStarMap; // map an edge to a star. For example vi_EdgeStarMap[edge#1] = star#5
02310                 vector<int> vi_StarHubMap; // map a star to its hub (the center of 2-color star. For example vi_StarHubMap[star#5] = edge#7
02311                 map< int, map<int, int> > mimi2_VertexEdgeMap; // map 2 vertices to its edge ID. Note that for mimi2_VertexEdgeMap[vertex#1][vertex#2]= edge#1, the id of vertex#1 must always less than vertex#2
02312                 vector<int> vi_FirstSeenOne, vi_FirstSeenTwo;
02313                 
02314                 vi_FirstSeenOne.clear();
02315                 vi_FirstSeenOne.resize((unsigned) i_VertexCount, _UNKNOWN);
02316 
02317                 vi_FirstSeenTwo.clear();
02318                 vi_FirstSeenTwo.resize((unsigned) i_VertexCount, _UNKNOWN);
02319 
02320                 vi_EdgeStarMap.clear();
02321                 vi_EdgeStarMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
02322 
02323                 vi_StarHubMap.clear();
02324                 vi_StarHubMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
02325 
02326                 // label each edge
02327                 //populate mimi2_VertexEdgeMap[][] and vi_EdgeStarMap[]
02328                 k=0;
02329                 for(i=0; i<i_VertexCount; i++)
02330                 {
02331                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
02332                         {
02333                                 if(i < m_vi_Edges[j])
02334                                 {
02335                                         mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k;
02336 
02337                                         vi_EdgeStarMap[k] = k; // initilized vi_EdgeStarMap, just let each edge belongs to its own star
02338 
02339                                         k++;
02340                                 }
02341                         }
02342                 }
02343                 
02344                 // This function is similar to Algorithm 4.3: procedure updateStars(v)
02345                 //              in paper: A. Gebremedhin, A. Tarafdar, F. Manne and A. Pothen, New Acyclic and Star Coloring Algorithms with Applications to Hessian Computation, SIAM Journal on Scientific Computing, Vol 29, No 3, pp 1042--1072, 2007.
02346                 //  updating the collection of two-colored stars incident on the colored vertex v
02347                 // i.e. update vi_EdgeStarMap[][] and vi_StarHubMap[]
02348                 for(i=0; i<m_vi_Vertices.size()-1;i++) {
02349                         if(m_vi_VertexColors[i] == _UNKNOWN) {
02350                                 vi_VerticesToBeRecolored.push_back(i);
02351                                 continue;
02352                         }
02353                         int i_PresentVertex = i;
02354                                         
02355                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
02356                         {
02357                                 int _FOUND = _FALSE;
02358 
02359                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
02360                                 {
02361                                         continue;
02362                                 }
02363 
02364                                 // for each colored vertex, find the star that has colors of i_PresentVertex and m_vi_Edges[j]
02365                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
02366                                 {
02367                                         // skip of m_vi_Edges[k] is the i_PresentVertex
02368                                         if(m_vi_Edges[k] == i_PresentVertex)
02369                                         {
02370                                                 continue;
02371                                         }
02372 
02373                                         // skip of the color of m_vi_Edges[k] (D2 neighbor of v (the i_PresentVertex)
02374                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
02375                                         {
02376                                                 continue;
02377                                         }
02378 
02379                                         // Line 3-5, Algorithm 4.3
02380                                         // if D2 neighbor of v and v has the same color
02381                                         if(m_vi_VertexColors[m_vi_Edges[k]] == m_vi_VertexColors[i_PresentVertex])
02382                                         {
02383                                                 _FOUND = _TRUE;
02384 
02385                                                 if(m_vi_Edges[j] < m_vi_Edges[k])
02386                                                 {
02387                                                         //find the ID of the star that includes m_vi_Edges[j] and m_vi_Edges[k]
02388                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]];
02389 
02390                                                         // m_vi_Edges[j] (D1 neighbor of v) will be the hub of the star that include i_PresentVertex, m_vi_Edges[j], m_vi_Edges[k]
02391                                                         vi_StarHubMap[i_StarID] = m_vi_Edges[j]; 
02392 
02393                                                         // add edge (i_PresentVertex, m_vi_Edges[j]) in to the star i_StarID
02394                                                         if(i_PresentVertex < m_vi_Edges[j])
02395                                                         {
02396                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
02397                                                         }
02398                                                         else
02399                                                         {
02400                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
02401                                                         }
02402                                                 }
02403                                                 else
02404                                                 {
02405                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]];
02406 
02407                                                         vi_StarHubMap[i_StarID] = m_vi_Edges[j];
02408 
02409                                                         if(i_PresentVertex < m_vi_Edges[j])
02410                                                         {
02411                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
02412                                                         }
02413                                                         else
02414                                                         {
02415                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
02416                                                         }
02417                                                 }
02418 
02419                                                 break;
02420                                         }
02421                                 }
02422 
02423                                 // Line 6-13, Algorithm 4.3
02424                                 // If we cannot find the star that has colors of i_PresentVertex and m_vi_Edges[j]
02425                                 // do ???
02426                                 if (!_FOUND)
02427                                 {
02428                                         i_VertexOne = vi_FirstSeenOne[m_vi_VertexColors[m_vi_Edges[j]]];
02429                                         i_VertexTwo = vi_FirstSeenTwo[m_vi_VertexColors[m_vi_Edges[j]]];
02430 
02431                                         if((i_VertexOne == i_PresentVertex) && (i_VertexTwo != m_vi_Edges[j])) {
02432                                                 if(i_PresentVertex < i_VertexTwo) {
02433                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][i_VertexTwo]];
02434                                                 }
02435                                                 else {
02436                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[i_VertexTwo][i_PresentVertex]];
02437                                                 }
02438 
02439                                                 vi_StarHubMap[i_StarID] = i_PresentVertex;
02440 
02441                                                 if(i_PresentVertex < m_vi_Edges[j]) {
02442                                                         vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
02443                                                 }
02444                                                 else {
02445                                                         vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
02446                                                 }
02447                                                 
02448                                         }
02449                                 }
02450                         }
02451                 }
02452                 
02453                 PrintVertexColors();
02454                 PrintStarCollection(vi_EdgeStarMap, vi_StarHubMap, mimi2_VertexEdgeMap);
02455                 return(_TRUE);
02456         }
02457         
02458         int GraphColoring::PrintStarCollection(vector<int>& vi_EdgeStarMap, vector<int>& vi_StarHubMap, map< int, map<int, int> >& mimi2_VertexEdgeMap) {
02459                 int i, j;
02460                 int i_VertexCount = m_vi_Vertices.size() - 1;
02461                 for(i=0; i<i_VertexCount; i++)
02462                 {
02463                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
02464                         {
02465                                 if(i < m_vi_Edges[j])
02466                                 {
02467                                   cout<<"Vertex "<< i <<" - vertex "<< m_vi_Edges[j] <<" : ";
02468                                   int i_Hub = vi_StarHubMap[ vi_EdgeStarMap[mimi2_VertexEdgeMap[i][ m_vi_Edges[j] ] ] ];
02469                                   if(i_Hub<0) {
02470                                     cout<<" NO HUB"<<endl;
02471                                   }
02472                                   else cout<<"starhub "<< i_Hub <<endl;
02473                                 }
02474                         }
02475                 }
02476                 
02477                 return (_TRUE);
02478         }
02479 
02480         //Public Function 1458
02481         int GraphColoring::StarColoring_serial()
02482         {
02483           // Line 2: Initialize data structures
02484                 if(CheckVertexColoring("STAR"))
02485                 {
02486                         return(_TRUE);
02487                 }
02488 
02489                 int i, j, k;
02490 
02491                 int _FOUND;
02492 
02493                 int i_ColorID, i_StarID;
02494 
02495                 int i_PresentVertex;
02496 
02497                 int i_VertexCount, i_EdgeCount;
02498 
02499                 int i_VertexOne, i_VertexTwo;
02500 
02501                 vector<int> vi_MemberEdges;
02502 
02503                 vector<int> vi_CandidateColors;
02504 
02505                 vector<int> vi_EdgeStarMap; // map an edge to a star. For example vi_EdgeStarMap[edge#1] = star#5
02506                 vector<int> vi_StarHubMap; // map a star to its hub (the center of 2-color star. For example vi_StarHubMap[star#5] = edge#7
02507 
02508                 vector<int> vi_FirstTreated; // ??? what these structures are for?
02509 
02510                 /* The two vectors vi_FirstSeenOne, vi_FirstSeenTwo are indexed by the color ID
02511                  * vi_FirstSeenOne[color a] = vertex 1 : means that color a is first seen when we are processing vertex 1 (as colored vertex w)
02512                  * vi_FirstSeenTwo[color a] = vertex 2 : means that vertex 2 (connected to vertex 1) has color a and this is first seen when we were processing vertex 1
02513                  * */
02514                 vector<int> vi_FirstSeenOne, vi_FirstSeenTwo; // ??? what these structures are for?
02515 
02516                 map< int, map<int, int> > mimi2_VertexEdgeMap; // map 2 vertices to its edge ID. Note that for mimi2_VertexEdgeMap[vertex#1][vertex#2]= edge#1, the id of vertex#1 must always less than vertex#2
02517 
02518                 m_i_VertexColorCount = _UNKNOWN;
02519 
02520                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
02521 
02522                 i_EdgeCount = (signed) m_vi_Edges.size();
02523 
02524                 vi_EdgeStarMap.clear();
02525                 vi_EdgeStarMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
02526 
02527                 vi_StarHubMap.clear();
02528                 vi_StarHubMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
02529 
02530                 m_vi_VertexColors.clear();
02531                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
02532 
02533                 vi_CandidateColors.clear();
02534                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
02535 
02536                 vi_FirstSeenOne.clear();
02537                 vi_FirstSeenOne.resize((unsigned) i_VertexCount, _UNKNOWN);
02538 
02539                 vi_FirstSeenTwo.clear();
02540                 vi_FirstSeenTwo.resize((unsigned) i_VertexCount, _UNKNOWN);
02541 
02542         //    vi_FirstTreated.clear();
02543         //    vi_FirstTreated.resize((unsigned) i_EdgeCount, _UNKNOWN);
02544 
02545                 vi_FirstTreated.clear();
02546                 vi_FirstTreated.resize((unsigned) i_VertexCount, _UNKNOWN);
02547 
02548                 k = _FALSE;
02549 
02550                 // label each edge
02551                 //populate mimi2_VertexEdgeMap[][] and vi_EdgeStarMap[]
02552                 for(i=0; i<i_VertexCount; i++)
02553                 {
02554                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
02555                         {
02556                                 if(i < m_vi_Edges[j])
02557                                 {
02558                                         mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k;
02559 
02560                                         vi_EdgeStarMap[k] = k; // initilized vi_EdgeStarMap, just let each edge belongs to its own star
02561 
02562                                         k++;
02563                                 }
02564                         }
02565                 }
02566 
02567 #if VERBOSE == _TRUE
02568 
02569                 cout<<endl;
02570 
02571 #endif
02572 
02573                 // Line 3: for each v ∈ V do
02574                 for(i=0; i<i_VertexCount; i++)
02575                 {
02576                         i_PresentVertex = m_vi_OrderedVertices[i];
02577 
02578 #if VERBOSE == _TRUE
02579 
02580                         cout<<"DEBUG 1458 | Star Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
02581 
02582 #endif
02583                         // Line 4: for each colored vertex w ∈ N1 (v) do
02584                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
02585                         {
02586                                 i_ColorID = m_vi_VertexColors[m_vi_Edges[j]];
02587 
02588                                 if(i_ColorID == _UNKNOWN)
02589                                 {
02590                                   continue;
02591                                 }
02592 
02593                                 // Line 5: forbid vertex i_PresentVertex to use color i_ColorID
02594                                 vi_CandidateColors[i_ColorID] = i_PresentVertex; 
02595 
02596                                 // Line 6?
02597                                 i_VertexOne = vi_FirstSeenOne[i_ColorID];
02598                                 i_VertexTwo = vi_FirstSeenTwo[i_ColorID];
02599 
02600                                 // Line 7-10, Algorithm 4.1
02601                                 if(i_VertexOne == i_PresentVertex)
02602                                 {
02603                                         // Line 8-9, Algorithm 4.1
02604                                         if(vi_FirstTreated[i_VertexTwo] != i_PresentVertex)
02605                                         {
02606 
02607                                                 //forbid colors of neighbors of q
02608                                                 for(k=m_vi_Vertices[i_VertexTwo]; k<m_vi_Vertices[STEP_UP(i_VertexTwo)]; k++)
02609                                                 {
02610                                                         if(m_vi_Edges[k] == i_PresentVertex)
02611                                                         {
02612                                                                 continue;
02613                                                         }
02614 
02615                                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
02616                                                         {
02617                                                                 continue;
02618                                                         }
02619 
02620                                                         vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
02621 
02622                                                 }
02623 
02624                                                 vi_FirstTreated[i_VertexTwo] = i_PresentVertex;
02625                                         }
02626 
02627                                         // Line 10, Algorithm 4.1: forbid colors of neighbors of w
02628                                         for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
02629                                         {
02630                                                 if(m_vi_Edges[k] == i_PresentVertex)
02631                                                 {
02632                                                         continue;
02633                                                 }
02634 
02635                                                 if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
02636                                                 {
02637                                                         continue;
02638                                                 }
02639 
02640                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
02641 
02642                                         }
02643 
02644                                         vi_FirstTreated[m_vi_Edges[j]] = i_PresentVertex;
02645                                 }
02646                                 // Line 11-15, Algorithm 4.1
02647                                 else
02648                                 {
02649                                 vi_FirstSeenOne[i_ColorID] = i_PresentVertex;
02650                                         vi_FirstSeenTwo[i_ColorID] = m_vi_Edges[j];
02651 
02652                                         for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
02653                                         {
02654                                                 if(m_vi_Edges[k] == i_PresentVertex)
02655                                                 {
02656                                                         continue;
02657                                                 }
02658 
02659                                                 if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
02660                                                 {
02661                                                         continue;
02662                                                 }
02663 
02664                                                 if(m_vi_Edges[j] < m_vi_Edges[k])
02665                                                 {
02666                                                         if(vi_StarHubMap[vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]]] == m_vi_Edges[k])
02667                                                         {
02668                                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
02669                                                         }
02670                                                 }
02671                                                 else
02672                                                 {
02673                                                         if(vi_StarHubMap[vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]]] == m_vi_Edges[k])
02674                                                         {
02675                                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
02676                                                         }
02677                                                 }
02678                                         }
02679                                 }
02680                         }
02681 
02682                         // Line 16, Algorithm 4.1
02683                         // the smallest permissible color is chosen and assigned to the vertex v (i_PresentVertex)
02684                         for(j=0; j<i_VertexCount; j++)
02685                         {
02686                                 if(vi_CandidateColors[j] != i_PresentVertex)
02687                                 {
02688                                         m_vi_VertexColors[i_PresentVertex] = j;
02689                                         //cout<<"c "<<j<<" for v "<<i_PresentVertex<<endl;
02690 
02691                                         if(m_i_VertexColorCount < j)
02692                                         {
02693                                                 m_i_VertexColorCount = j;
02694                                         }
02695 
02696                                         break;
02697                                 }
02698                         }
02699 
02700                         // Line 17, Algorithm 4.1
02701                         // This for loop is also Algorithm 4.3: procedure updateStars(v)
02702                         //  updating the collection of two-colored stars incident on the colored vertex v
02703                         // i.e. update vi_EdgeStarMap[][] and vi_StarHubMap[]
02704                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
02705                         {
02706                                 _FOUND = _FALSE;
02707 
02708                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
02709                                 {
02710                                         continue;
02711                                 }
02712 
02713                                 // for each colored vertex, find the star that has colors of i_PresentVertex and m_vi_Edges[j]
02714                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
02715                                 {
02716                                         // skip of m_vi_Edges[k] is the i_PresentVertex
02717                                         if(m_vi_Edges[k] == i_PresentVertex)
02718                                         {
02719                                                 continue;
02720                                         }
02721 
02722                                         // skip of the color of m_vi_Edges[k] (D2 neighbor of v (the i_PresentVertex)
02723                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
02724                                         {
02725                                                 continue;
02726                                         }
02727 
02728                                         // Line 3-5, Algorithm 4.3
02729                                         // if D2 neighbor of v and v has the same color
02730                                         if(m_vi_VertexColors[m_vi_Edges[k]] == m_vi_VertexColors[i_PresentVertex])
02731                                         {
02732                                                 _FOUND = _TRUE;
02733 
02734                                                 if(m_vi_Edges[j] < m_vi_Edges[k])
02735                                                 {
02736                                                         //find the ID of the star that includes m_vi_Edges[j] and m_vi_Edges[k]
02737                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]];
02738 
02739                                                         // m_vi_Edges[j] (D1 neighbor of v) will be the hub of the star that include i_PresentVertex, m_vi_Edges[j], m_vi_Edges[k]
02740                                                         vi_StarHubMap[i_StarID] = m_vi_Edges[j]; 
02741 
02742                                                         // add edge (i_PresentVertex, m_vi_Edges[j]) in to the star i_StarID
02743                                                         if(i_PresentVertex < m_vi_Edges[j])
02744                                                         {
02745                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
02746                                                         }
02747                                                         else
02748                                                         {
02749                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
02750                                                         }
02751                                                 }
02752                                                 else
02753                                                 {
02754                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]];
02755 
02756                                                         vi_StarHubMap[i_StarID] = m_vi_Edges[j];
02757 
02758                                                         if(i_PresentVertex < m_vi_Edges[j])
02759                                                         {
02760                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
02761                                                         }
02762                                                         else
02763                                                         {
02764                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
02765                                                         }
02766                                                 }
02767 
02768                                                 break;
02769                                         }
02770                                 }
02771 
02772                                 // Line 6-13, Algorithm 4.3
02773                                 // If we cannot find the star that has colors of i_PresentVertex and m_vi_Edges[j]
02774                                 // do ???
02775                                 if (!_FOUND)
02776                                 {
02777                                         i_VertexOne = vi_FirstSeenOne[m_vi_VertexColors[m_vi_Edges[j]]];
02778                                         i_VertexTwo = vi_FirstSeenTwo[m_vi_VertexColors[m_vi_Edges[j]]];
02779 
02780                                         if((i_VertexOne == i_PresentVertex) && (i_VertexTwo != m_vi_Edges[j]))
02781                                         {
02782                                                 if(i_PresentVertex < i_VertexTwo)
02783                                                 {
02784                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][i_VertexTwo]];
02785 
02786                                                         vi_StarHubMap[i_StarID] = i_PresentVertex;
02787 
02788                                                         if(i_PresentVertex < m_vi_Edges[j])
02789                                                         {
02790                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
02791                                                         }
02792                                                         else
02793                                                         {
02794                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
02795                                                         }
02796                                                 }
02797                                                 else
02798                                                 {
02799                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[i_VertexTwo][i_PresentVertex]];
02800 
02801                                                         vi_StarHubMap[i_StarID] = i_PresentVertex;
02802 
02803                                                         if(i_PresentVertex < m_vi_Edges[j])
02804                                                         {
02805                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
02806                                                         }
02807                                                         else
02808                                                         {
02809                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
02810                                                         }
02811                                                 }
02812                                         }
02813                                 }
02814                         }
02815                 }
02816 
02817 #if VERBOSE == _TRUE
02818 
02819                 cout<<endl;
02820 
02821 #endif
02822 
02823 #if STATISTICS == _TRUE
02824 /* Commented out due to apparent Memory violation (see the checking code below)
02825                 vector<int> vi_Hubs;
02826 
02827                 vi_Hubs.resize((unsigned) i_EdgeCount/2, _FALSE);
02828 
02829                 m_i_ColoringUnits = _FALSE;
02830 
02831                 for(i=0; i<i_EdgeCount/2; i++)
02832                 {
02833                         if(vi_StarHubMap[i] == _UNKNOWN)
02834                         {
02835                                 m_i_ColoringUnits++;
02836 
02837                                 continue;
02838                         }
02839 
02840                         if(vi_StarHubMap[i] >= vi_Hubs.size() ) {
02841                           cout<<"Memory violation vi_StarHubMap[i] = "<<vi_StarHubMap[i]<<" ; vi_Hubs.size() = "<< vi_Hubs.size() <<endl;
02842                           Pause();
02843                         }
02844                         if(vi_Hubs[vi_StarHubMap[i]] == _FALSE)
02845                         {
02846                                 vi_Hubs[vi_StarHubMap[i]] = _TRUE;
02847 
02848                                 m_i_ColoringUnits++;
02849                         }
02850                 }
02851 //*/
02852 #endif
02853 
02854                 return(_TRUE);
02855 
02856         }
02857 
02858 
02859         //Public Function 1459
02860         int GraphColoring::StarColoring(vector<int> & vi_StarHubMap, vector<int> & vi_EdgeStarMap, map< int, map<int, int> > & mimi2_VertexEdgeMap)
02861         {
02862                 int i, j, k;
02863 
02864                 int _FOUND;
02865 
02866                 int i_ColorID, i_StarID;
02867 
02868                 int i_PresentVertex;
02869 
02870                 int i_VertexCount, i_EdgeCount;
02871 
02872                 int i_VertexOne, i_VertexTwo;
02873 
02874                 vector<int> vi_MemberEdges;
02875 
02876                 vector<int> vi_CandidateColors;
02877 
02878                 vector<int> vi_FirstTreated;
02879 
02880                 vector<int> vi_FirstSeenOne, vi_FirstSeenTwo;
02881 
02882                 m_i_VertexColorCount = _UNKNOWN;
02883 
02884                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
02885 
02886                 i_EdgeCount = (signed) m_vi_Edges.size();
02887 
02888                 vi_EdgeStarMap.clear();
02889                 vi_EdgeStarMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
02890 
02891                 vi_StarHubMap.clear();
02892                 vi_StarHubMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
02893 
02894                 m_vi_VertexColors.clear();
02895                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
02896 
02897                 vi_CandidateColors.clear();
02898                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
02899 
02900                 vi_FirstSeenOne.clear();
02901                 vi_FirstSeenOne.resize((unsigned) i_VertexCount, _UNKNOWN);
02902 
02903                 vi_FirstSeenTwo.clear();
02904                 vi_FirstSeenTwo.resize((unsigned) i_VertexCount, _UNKNOWN);
02905 
02906         //    vi_FirstTreated.clear();
02907         //    vi_FirstTreated.resize((unsigned) i_EdgeCount, _UNKNOWN);
02908 
02909                 vi_FirstTreated.clear();
02910                 vi_FirstTreated.resize((unsigned) i_VertexCount, _UNKNOWN);
02911 
02912                 k = _FALSE;
02913 
02914                 for(i=0; i<i_VertexCount; i++)
02915                 {
02916                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
02917                         {
02918                                 if(i < m_vi_Edges[j])
02919                                 {
02920                                         mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k;
02921 
02922                                         vi_EdgeStarMap[k] = k;
02923 
02924                                         k++;
02925                                 }
02926                         }
02927                 }
02928 
02929 #if VERBOSE == _TRUE
02930 
02931                 cout<<endl;
02932 
02933 #endif
02934 
02935                 for(i=0; i<i_VertexCount; i++)
02936                 {
02937                         i_PresentVertex = m_vi_OrderedVertices[i];
02938 
02939 #if VERBOSE == _TRUE
02940 
02941                         cout<<"DEBUG 305 | Star Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
02942 
02943 #endif
02944                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
02945                         {
02946                                 i_ColorID = m_vi_VertexColors[m_vi_Edges[j]];
02947 
02948                                 if(i_ColorID == _UNKNOWN)
02949                                 {
02950                                   continue;
02951                                 }
02952 
02953                                 vi_CandidateColors[i_ColorID] = i_PresentVertex;
02954 
02955                                 i_VertexOne = vi_FirstSeenOne[i_ColorID];
02956                                 i_VertexTwo = vi_FirstSeenTwo[i_ColorID];
02957 
02958                                 // Line 7-10, Algorithm 4.1
02959                                 if(i_VertexOne == i_PresentVertex)
02960                                 {
02961                                   
02962                                         // Line 8-9, Algorithm 4.1
02963                                         if(vi_FirstTreated[i_VertexTwo] != i_PresentVertex)
02964                                         {
02965 
02966                                                 for(k=m_vi_Vertices[i_VertexTwo]; k<m_vi_Vertices[STEP_UP(i_VertexTwo)]; k++)
02967                                                 {
02968                                                         if(m_vi_Edges[k] == i_PresentVertex)
02969                                                         {
02970                                                                 continue;
02971                                                         }
02972 
02973                                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
02974                                                         {
02975                                                                 continue;
02976                                                         }
02977 
02978                                                         vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
02979 
02980                                                 }
02981 
02982                                                 vi_FirstTreated[i_VertexTwo] = i_PresentVertex;
02983                                         }
02984 
02985                                         // Line 10, Algorithm 4.1
02986                                         for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
02987                                         {
02988                                                 if(m_vi_Edges[k] == i_PresentVertex)
02989                                                 {
02990                                                         continue;
02991                                                 }
02992 
02993                                                 if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
02994                                                 {
02995                                                         continue;
02996                                                 }
02997 
02998                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
02999 
03000                                         }
03001 
03002                                         vi_FirstTreated[m_vi_Edges[j]] = i_PresentVertex;
03003                                 }
03004                                 // Line 11-15, Algorithm 4.1
03005                                 else
03006                                 {
03007                                 vi_FirstSeenOne[i_ColorID] = i_PresentVertex;
03008                                         vi_FirstSeenTwo[i_ColorID] = m_vi_Edges[j];
03009 
03010                                         for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
03011                                         {
03012                                                 if(m_vi_Edges[k] == i_PresentVertex)
03013                                                 {
03014                                                         continue;
03015                                                 }
03016 
03017                                                 if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
03018                                                 {
03019                                                         continue;
03020                                                 }
03021 
03022                                                 if(m_vi_Edges[j] < m_vi_Edges[k])
03023                                                 {
03024                                                         if(vi_StarHubMap[vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]]] == m_vi_Edges[k])
03025                                                         {
03026                                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
03027                                                         }
03028                                                 }
03029                                                 else
03030                                                 {
03031                                                         if(vi_StarHubMap[vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]]] == m_vi_Edges[k])
03032                                                         {
03033                                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
03034                                                         }
03035                                                 }
03036                                         }
03037                                 }
03038                         }
03039 
03040                         for(j=0; j<i_VertexCount; j++)
03041                         {
03042                                 if(vi_CandidateColors[j] != i_PresentVertex)
03043                                 {
03044                                         m_vi_VertexColors[i_PresentVertex] = j;
03045 
03046                                         if(m_i_VertexColorCount < j)
03047                                         {
03048                                                 m_i_VertexColorCount = j;
03049                                         }
03050 
03051                                         break;
03052                                 }
03053                         }
03054 
03055                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
03056                         {
03057                                 _FOUND = _FALSE;
03058 
03059                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
03060                                 {
03061                                         continue;
03062                                 }
03063 
03064                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
03065                                 {
03066                                         if(m_vi_Edges[k] == i_PresentVertex)
03067                                         {
03068                                                 continue;
03069                                         }
03070 
03071                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
03072                                         {
03073                                                 continue;
03074                                         }
03075 
03076                                         if(m_vi_VertexColors[m_vi_Edges[k]] == m_vi_VertexColors[i_PresentVertex])
03077                                         {
03078                                                 _FOUND = _TRUE;
03079 
03080                                                 if(m_vi_Edges[j] < m_vi_Edges[k])
03081                                                 {
03082                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]];
03083 
03084                                                         vi_StarHubMap[i_StarID] = m_vi_Edges[j];
03085 
03086                                                         if(i_PresentVertex < m_vi_Edges[j])
03087                                                         {
03088                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
03089                                                         }
03090                                                         else
03091                                                         {
03092                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
03093                                                         }
03094                                                 }
03095                                                 else
03096                                                 {
03097                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]];
03098 
03099                                                         vi_StarHubMap[i_StarID] = m_vi_Edges[j];
03100 
03101                                                         if(i_PresentVertex < m_vi_Edges[j])
03102                                                         {
03103                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
03104                                                         }
03105                                                         else
03106                                                         {
03107                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
03108                                                         }
03109                                                 }
03110 
03111                                                 break;
03112                                         }
03113                                 }
03114 
03115                                 if (!_FOUND)
03116                                 {
03117                                         i_VertexOne = vi_FirstSeenOne[m_vi_VertexColors[m_vi_Edges[j]]];
03118                                         i_VertexTwo = vi_FirstSeenTwo[m_vi_VertexColors[m_vi_Edges[j]]];
03119 
03120                                         if((i_VertexOne == i_PresentVertex) && (i_VertexTwo != m_vi_Edges[j]))
03121                                         {
03122                                                 if(i_PresentVertex < i_VertexTwo)
03123                                                 {
03124                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][i_VertexTwo]];
03125 
03126                                                         vi_StarHubMap[i_StarID] = i_PresentVertex;
03127 
03128                                                         if(i_PresentVertex < m_vi_Edges[j])
03129                                                         {
03130                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
03131                                                         }
03132                                                         else
03133                                                         {
03134                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
03135                                                         }
03136                                                 }
03137                                                 else
03138                                                 {
03139                                                         i_StarID = vi_EdgeStarMap[mimi2_VertexEdgeMap[i_VertexTwo][i_PresentVertex]];
03140 
03141                                                         vi_StarHubMap[i_StarID] = i_PresentVertex;
03142 
03143                                                         if(i_PresentVertex < m_vi_Edges[j])
03144                                                         {
03145                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]] = i_StarID;
03146                                                         }
03147                                                         else
03148                                                         {
03149                                                                 vi_EdgeStarMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]] = i_StarID;
03150                                                         }
03151                                                 }
03152                                         }
03153                                 }
03154                         }
03155                 }
03156 
03157 #if VERBOSE == _TRUE
03158 
03159                 cout<<endl;
03160 
03161 #endif
03162 
03163 #if STATISTICS == _TRUE
03164 
03165                 vector<int> vi_Hubs;
03166 
03167                 vi_Hubs.resize((unsigned) i_EdgeCount/2, _FALSE);
03168 
03169                 m_i_ColoringUnits = _FALSE;
03170 
03171                 for(i=0; i<i_EdgeCount/2; i++)
03172                 {
03173                         if(vi_StarHubMap[i] == _UNKNOWN)
03174                         {
03175                                 m_i_ColoringUnits++;
03176 
03177                                 continue;
03178                         }
03179 
03180                         if(vi_Hubs[vi_StarHubMap[i]] == _FALSE)
03181                         {
03182                                 vi_Hubs[vi_StarHubMap[i]] = _TRUE;
03183 
03184                                 m_i_ColoringUnits++;
03185                         }
03186                 }
03187 
03188 #endif
03189 
03190                 return(_TRUE);
03191 
03192         }
03193 
03194 
03195 
03196         int GraphColoring::GetStarColoringConflicts(vector<vector<int> > &ListOfConflicts)
03197         {
03198                 int i, j, k, l;
03199 
03200                 int i_VertexCount, i_EdgeCount;
03201 
03202                 int i_FirstColor, i_SecondColor, i_ThirdColor, i_FourthColor;
03203 
03204                 int i_ViolationCount;
03205 
03206                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
03207 
03208                 i_EdgeCount = (signed) m_vi_Edges.size();
03209 
03210                 i_ViolationCount = _FALSE;
03211 
03212                 for(i=0; i<i_VertexCount; i++)
03213                 {
03214                         i_FirstColor = m_vi_VertexColors[i];
03215 
03216                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
03217                         {
03218                                 i_SecondColor = m_vi_VertexColors[m_vi_Edges[j]];
03219 
03220                                 if(i_SecondColor == i_FirstColor)
03221                                 {
03222                                         i_ViolationCount++;
03223 
03224                                         //cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(i)<<" ["<<STEP_UP(i_FirstColor)<<"] - "<<STEP_UP(m_vi_Edges[j])<<" ["<<STEP_UP(i_SecondColor)<<"]"<<endl;
03225                                         vector<int> violation;    violation.push_back(i);violation.push_back(m_vi_Edges[j]);    ListOfConflicts.push_back(violation);
03226 
03227                                         continue;
03228                                 }
03229 
03230                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
03231                                 {
03232                                         if(m_vi_Edges[k] == i)
03233                                         {
03234                                                 continue;
03235                                         }
03236 
03237                                         i_ThirdColor = m_vi_VertexColors[m_vi_Edges[k]];
03238 
03239                                         if(i_ThirdColor == i_SecondColor)
03240                                         {
03241                                                 i_ViolationCount++;
03242 
03243                                                 //cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(m_vi_Edges[j])<<" ["<<STEP_UP(i_SecondColor)<<"] - "<<STEP_UP(m_vi_Edges[k])<<" ["<<STEP_UP(i_ThirdColor)<<"]"<<endl;
03244                                                 vector<int> violation;    violation.push_back(m_vi_Edges[j]);violation.push_back(m_vi_Edges[k]);    ListOfConflicts.push_back(violation);
03245 
03246                                                 continue;
03247                                         }
03248 
03249                                         if(i_ThirdColor != i_FirstColor)
03250                                         {
03251                                                 continue;
03252                                         }
03253 
03254                                         if(i_ThirdColor == i_FirstColor)
03255                                         {
03256                                                 for(l=m_vi_Vertices[m_vi_Edges[k]]; l<m_vi_Vertices[STEP_UP(m_vi_Edges[k])]; l++)
03257                                                 {
03258                                                         if((m_vi_Edges[l] == m_vi_Edges[j]))
03259                                                         {
03260                                                                 continue;
03261                                                         }
03262 
03263                                                         i_FourthColor = m_vi_VertexColors[m_vi_Edges[l]];
03264 
03265                                                         if(i_FourthColor == i_ThirdColor)
03266                                                         {
03267                                                                 i_ViolationCount++;
03268 
03269                                                                 //cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(m_vi_Edges[k])<<" ["<<STEP_UP(i_ThirdColor)<<"] - "<<STEP_UP(m_vi_Edges[l])<<" ["<<STEP_UP(i_FourthColor)<<"]"<<endl;
03270                                                                 vector<int> violation;    violation.push_back(m_vi_Edges[k]);violation.push_back(m_vi_Edges[l]);    ListOfConflicts.push_back(violation);
03271 
03272                                                         }
03273 
03274                                                         if(i_FourthColor == i_SecondColor)
03275                                                         {
03276                                                                 i_ViolationCount++;
03277 
03278                                                                 //cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(i)<<" ["<<STEP_UP(i_FirstColor)<<"] - "<<STEP_UP(m_vi_Edges[j])<<" ["<<STEP_UP(i_SecondColor)<<"] - "<<STEP_UP(m_vi_Edges[k])<<" ["<<STEP_UP(i_ThirdColor)<<"] - "<<STEP_UP(m_vi_Edges[l])<<" ["<<STEP_UP(i_FourthColor)<<"]"<<endl;
03279                                                                 vector<int> violation;    violation.push_back(i);violation.push_back(m_vi_Edges[j]);violation.push_back(m_vi_Edges[k]);violation.push_back(m_vi_Edges[l]);    ListOfConflicts.push_back(violation);
03280 
03281                                                                 continue;
03282                                                         }
03283                                                 }
03284                                         }
03285                                 }
03286                         }
03287                 }
03288 /*
03289                 if(i_ViolationCount)
03290                 {
03291                         cout<<endl;
03292                         cout<<"[Total Violations = "<<i_ViolationCount<<"]"<<endl;
03293                         cout<<endl;
03294                 }
03295 //*/
03296                 return(i_ViolationCount);
03297         }
03298 
03299         //Public Function 1460
03300         int GraphColoring::CheckStarColoring()
03301         {
03302                 cout<<"Note: 1-based indexing is used"<<endl;
03303                 int i, j, k, l;
03304 
03305                 int i_VertexCount, i_EdgeCount;
03306 
03307                 int i_FirstColor, i_SecondColor, i_ThirdColor, i_FourthColor;
03308 
03309                 int i_ViolationCount;
03310 
03311                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
03312 
03313                 i_EdgeCount = (signed) m_vi_Edges.size();
03314 
03315                 i_ViolationCount = _FALSE;
03316 
03317                 for(i=0; i<i_VertexCount; i++)
03318                 {
03319                         i_FirstColor = m_vi_VertexColors[i];
03320 
03321                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
03322                         {
03323                                 i_SecondColor = m_vi_VertexColors[m_vi_Edges[j]];
03324 
03325                                 if(i_SecondColor == i_FirstColor)
03326                                 {
03327                                         i_ViolationCount++;
03328 
03329                                         if(i_ViolationCount == _TRUE)
03330                                         {
03331                                                 cout<<endl;
03332                                                 cout<<"Star Coloring | Violation Check | "<<m_s_InputFile<<endl;
03333                                                 cout<<endl;
03334                                         }
03335 
03336                                         cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(i)<<" ["<<STEP_UP(i_FirstColor)<<"] - "<<STEP_UP(m_vi_Edges[j])<<" ["<<STEP_UP(i_SecondColor)<<"]"<<endl;
03337 
03338                                         continue;
03339                                 }
03340 
03341                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
03342                                 {
03343                                         if(m_vi_Edges[k] == i)
03344                                         {
03345                                                 continue;
03346                                         }
03347 
03348                                         i_ThirdColor = m_vi_VertexColors[m_vi_Edges[k]];
03349 
03350                                         if(i_ThirdColor == i_SecondColor)
03351                                         {
03352                                                 i_ViolationCount++;
03353 
03354                                                 if(i_ViolationCount == _TRUE)
03355                                                 {
03356                                                         cout<<endl;
03357                                                         cout<<"Star Coloring | Violation Check | "<<m_s_InputFile<<endl;
03358                                                         cout<<endl;
03359                                                 }
03360 
03361                                                 cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(m_vi_Edges[j])<<" ["<<STEP_UP(i_SecondColor)<<"] - "<<STEP_UP(m_vi_Edges[k])<<" ["<<STEP_UP(i_ThirdColor)<<"]"<<endl;
03362 
03363                                                 continue;
03364                                         }
03365 
03366                                         if(i_ThirdColor != i_FirstColor)
03367                                         {
03368                                                 continue;
03369                                         }
03370 
03371                                         if(i_ThirdColor == i_FirstColor)
03372                                         {
03373                                                 for(l=m_vi_Vertices[m_vi_Edges[k]]; l<m_vi_Vertices[STEP_UP(m_vi_Edges[k])]; l++)
03374                                                 {
03375                                                         if((m_vi_Edges[l] == m_vi_Edges[j]))
03376                                                         {
03377                                                                 continue;
03378                                                         }
03379 
03380                                                         i_FourthColor = m_vi_VertexColors[m_vi_Edges[l]];
03381 
03382                                                         if(i_FourthColor == i_ThirdColor)
03383                                                         {
03384                                                                 i_ViolationCount++;
03385 
03386                                                                 if(i_ViolationCount == _TRUE)
03387                                                                 {
03388                                                                         cout<<endl;
03389                                                                         cout<<"Star Coloring | Violation Check | "<<m_s_InputFile<<endl;
03390                                                                         cout<<endl;
03391                                                                 }
03392 
03393                                                                 cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(m_vi_Edges[k])<<" ["<<STEP_UP(i_ThirdColor)<<"] - "<<STEP_UP(m_vi_Edges[l])<<" ["<<STEP_UP(i_FourthColor)<<"]"<<endl;
03394 
03395                                                         }
03396 
03397                                                         if(i_FourthColor == i_SecondColor)
03398                                                         {
03399                                                                 i_ViolationCount++;
03400 
03401                                                                 if(i_ViolationCount == _TRUE)
03402                                                                 {
03403                                                                         cout<<endl;
03404                                                                         cout<<"Star Coloring | Violation Check | "<<m_s_InputFile<<endl;
03405                                                                         cout<<endl;
03406                                                                 }
03407 
03408                                                                 cout<<"Violation "<<i_ViolationCount<<"\t : "<<STEP_UP(i)<<" ["<<STEP_UP(i_FirstColor)<<"] - "<<STEP_UP(m_vi_Edges[j])<<" ["<<STEP_UP(i_SecondColor)<<"] - "<<STEP_UP(m_vi_Edges[k])<<" ["<<STEP_UP(i_ThirdColor)<<"] - "<<STEP_UP(m_vi_Edges[l])<<" ["<<STEP_UP(i_FourthColor)<<"]"<<endl;
03409 
03410                                                                 continue;
03411                                                         }
03412                                                 }
03413                                         }
03414                                 }
03415                         }
03416                 }
03417 
03418                 if(i_ViolationCount)
03419                 {
03420                         cout<<endl;
03421                         cout<<"[Total Violations = "<<i_ViolationCount<<"]"<<endl;
03422                         cout<<endl;
03423                 }
03424 
03425                 return(i_ViolationCount);
03426         }
03427 
03428 
03429 
03430         //Public Function 1461
03431         int GraphColoring::AcyclicColoring()
03432         {
03433                 if(CheckVertexColoring("ACYCLIC"))
03434                 {
03435                         return(_TRUE);
03436                 }
03437 
03438                 int i, j, k;
03439 
03440                 int i_VertexCount, i_EdgeCount;
03441 
03442                 int i_AdjacentEdgeID, i_EdgeID, i_SetID;
03443 
03444                 int i_PresentVertex;
03445 
03446                 vector<int> vi_CandidateColors;
03447 
03448                 vector<int> vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree;
03449                 vector<int> vi_FirstVisitedOne, vi_FirstVisitedTwo;
03450 
03451 #if DISJOINT_SETS == _FALSE
03452 
03453                 int l;
03454 
03455                 int i_MemberCount;
03456 
03457                 int i_SmallerSetID, i_BiggerSetID;
03458 
03459                 vector<int> vi_DisjointSets;
03460                 vector<int> vi_MemberEdges;
03461                 vector<int> vi_EdgeSetMap;
03462 
03463                 vector< vector<int> > v2i_SetEdgeMap;
03464 
03465 #endif
03466 
03467 #if DISJOINT_SETS == _TRUE
03468 
03469                 int i_SetOneID, i_SetTwoID;
03470 
03471 #endif
03472 
03473                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
03474 
03475                 k = _FALSE;
03476 
03477                 m_mimi2_VertexEdgeMap.clear();
03478 
03479                 for(i=0; i<i_VertexCount; i++)
03480                 {
03481                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
03482                         {
03483                                 if(i < m_vi_Edges[j])
03484                                 {
03485                                         m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k;
03486 
03487                                         k++;
03488                                 }
03489                         }
03490                 }
03491 
03492 #if DEBUG == 1461
03493 
03494                 i_EdgeCount = (signed) v2i_EdgeVertexMap.size();
03495 
03496                 cout<<endl;
03497                 cout<<"DEBUG 1461 | Acyclic Coloring | Edge Vertex Map"<<endl;
03498                 cout<<endl;
03499 
03500                 for(i=0; i<i_EdgeCount; i++)
03501                 {
03502                         cout<<"Edge "<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(v2i_EdgeVertexMap[i][0])<<" - "<<STEP_UP(v2i_EdgeVertexMap[i][1])<<endl;
03503                 }
03504 
03505                 cout<<endl;
03506                 cout<<"DEBUG 1461 | Acyclic Coloring | Vertex Edge Map"<<endl;
03507                 cout<<endl;
03508 
03509                 for(i=0; i<i_EdgeCount; i++)
03510                 {
03511                         cout<<"Vertex "<<STEP_UP(v2i_EdgeVertexMap[i][0])<<" - Vertex "<<STEP_UP(v2i_EdgeVertexMap[i][1])<<"\t"<<" : "<<STEP_UP(m_mimi2_VertexEdgeMap[v2i_EdgeVertexMap[i][0]][v2i_EdgeVertexMap[i][1]])<<endl;
03512 
03513                 }
03514 
03515                 cout<<endl;
03516 
03517 #endif
03518 
03519                 i_EdgeCount = (signed) m_vi_Edges.size();
03520 
03521                 m_vi_VertexColors.clear();
03522                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
03523 
03524                 vi_CandidateColors.clear();
03525                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
03526 
03527                 vi_FirstSeenOne.clear();
03528                 vi_FirstSeenOne.resize((unsigned) i_VertexCount, _UNKNOWN);
03529 
03530                 vi_FirstSeenTwo.clear();
03531                 vi_FirstSeenTwo.resize((unsigned) i_VertexCount, _UNKNOWN);
03532 
03533                 vi_FirstSeenThree.clear();
03534                 vi_FirstSeenThree.resize((unsigned) i_VertexCount, _UNKNOWN);
03535 
03536                 vi_FirstVisitedOne.clear();
03537                 vi_FirstVisitedOne.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
03538 
03539                 vi_FirstVisitedTwo.clear();
03540                 vi_FirstVisitedTwo.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
03541 
03542 #if DISJOINT_SETS == _FALSE
03543 
03544                 vi_MemberEdges.clear();
03545 
03546                 vi_EdgeSetMap.clear();
03547                 vi_EdgeSetMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
03548 
03549                 v2i_SetEdgeMap.clear();
03550                 v2i_SetEdgeMap.resize((unsigned) i_EdgeCount/2);
03551 
03552                 vi_DisjointSets.clear();
03553 
03554 #endif
03555 
03556 #if DISJOINT_SETS == _TRUE
03557 
03558                 m_ds_DisjointSets.SetSize(i_EdgeCount/2);
03559 
03560 #endif
03561 
03562 #if VERBOSE == _TRUE
03563 
03564                 cout<<endl;
03565 
03566 #endif
03567 
03568                 m_i_VertexColorCount = _UNKNOWN;
03569 
03570                 for(i=0; i<i_VertexCount; i++)
03571                 {
03572                         i_PresentVertex = m_vi_OrderedVertices[i];
03573 
03574 #if VERBOSE == _TRUE
03575 
03576                         cout<<"DEBUG 1461 | Acyclic Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
03577 
03578 #endif
03579 
03580                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
03581                         {
03582                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
03583                                 {
03584                                         continue;
03585                                 }
03586 
03587                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
03588                         }
03589 
03590                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
03591                         {
03592                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
03593                                 {
03594                                         continue;
03595                                 }
03596 
03597                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
03598                                 {
03599                                         if(m_vi_Edges[k] == i_PresentVertex)
03600                                         {
03601                                                 continue;
03602                                         }
03603 
03604                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
03605                                         {
03606                                                 continue;
03607                                         }
03608 
03609                                         if(vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] == i_PresentVertex)
03610                                         {
03611                                                 continue;
03612                                         }
03613 
03614 #if DISJOINT_SETS == _TRUE
03615 
03616                                         if(m_vi_Edges[j] < m_vi_Edges[k])
03617                                         {
03618                                                 i_SetID = m_ds_DisjointSets.FindAndCompress(m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]);
03619                                         }
03620                                         else
03621                                         {
03622                                                 i_SetID = m_ds_DisjointSets.FindAndCompress(m_mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]);
03623                                         }
03624 #endif
03625 
03626 #if DISJOINT_SETS == _FALSE
03627 
03628                                         if(m_vi_Edges[j] < m_vi_Edges[k])
03629                                         {
03630                                                 i_SetID = vi_EdgeSetMap[m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]];
03631                                         }
03632                                         else
03633                                         {
03634                                                 i_SetID = vi_EdgeSetMap[m_mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]];
03635                                         }
03636 #endif
03637 
03638                                         FindCycle(i_PresentVertex, m_vi_Edges[j], m_vi_Edges[k], i_SetID, vi_CandidateColors, vi_FirstVisitedOne, vi_FirstVisitedTwo);
03639                                 }
03640                         }
03641 
03642                         for(j=0; j<i_VertexCount; j++)
03643                         {
03644                                 if(vi_CandidateColors[j] != i_PresentVertex)
03645                                 {
03646                                         m_vi_VertexColors[i_PresentVertex] = j;
03647 
03648                                         if(m_i_VertexColorCount < j)
03649                                         {
03650                                                 m_i_VertexColorCount = j;
03651                                         }
03652 
03653                                         break;
03654                                 }
03655                         }
03656 
03657                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
03658                         {
03659                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
03660                                 {
03661                                         continue;
03662                                 }
03663 
03664                                 if(i_PresentVertex < m_vi_Edges[j])
03665                                 {
03666                                         i_EdgeID = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]];
03667                                 }
03668                                 else
03669                                 {
03670                                         i_EdgeID = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex];
03671                                 }
03672 
03673 #if DISJOINT_SETS == _FALSE
03674 
03675                                 vi_DisjointSets.push_back(_TRUE);
03676 
03677                                 vi_EdgeSetMap[i_EdgeID] = STEP_DOWN((signed) vi_DisjointSets.size());
03678 
03679                                 v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].push_back(i_EdgeID);
03680 #endif
03681 
03682                                 i_AdjacentEdgeID = UpdateSet(i_PresentVertex, m_vi_Edges[j], i_PresentVertex, m_mimi2_VertexEdgeMap, vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree);
03683 
03684                                 if(i_AdjacentEdgeID != _UNKNOWN)
03685                                 {
03686 
03687 #if DISJOINT_SETS == _TRUE
03688 
03689                                         i_SetOneID = m_ds_DisjointSets.FindAndCompress(i_EdgeID);
03690                                         i_SetTwoID = m_ds_DisjointSets.FindAndCompress(i_AdjacentEdgeID);
03691 
03692 #if DEBUG == 1461
03693 
03694                                         cout<<endl;
03695                                         cout<<"DEBUG 1461 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(i_SetOneID)<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(i_SetTwoID)<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
03696                                         cout<<endl;
03697 
03698 #endif
03699 
03700                                         m_ds_DisjointSets.UnionBySize(i_SetOneID, i_SetTwoID);
03701 
03702 #endif
03703 
03704 #if DISJOINT_SETS == _FALSE
03705 
03706 #if DEBUG == 1461
03707 
03708                                         cout<<endl;
03709                                         cout<<"DEBUG 1461 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(vi_EdgeSetMap[i_EdgeID])<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(vi_EdgeSetMap[i_AdjacentEdgeID])<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
03710                                         cout<<endl;
03711 
03712 #endif
03713 
03714                                         if(v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].size() < v2i_SetEdgeMap[vi_EdgeSetMap[i_AdjacentEdgeID]].size())
03715                                         {
03716                                                 i_SmallerSetID = vi_EdgeSetMap[i_EdgeID];
03717                                                 i_BiggerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
03718                                         }
03719                                         else
03720                                         {
03721                                                 i_BiggerSetID = vi_EdgeSetMap[i_EdgeID];
03722                                                 i_SmallerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
03723                                         }
03724 
03725                                         vi_MemberEdges.clear();
03726                                         vi_MemberEdges.swap(v2i_SetEdgeMap[i_BiggerSetID]);
03727 
03728                                         vi_DisjointSets[i_BiggerSetID] = _FALSE;
03729 
03730                                         i_MemberCount = (signed) vi_MemberEdges.size();
03731 
03732                                         for(k=0; k<i_MemberCount; k++)
03733                                         {
03734                                                 vi_EdgeSetMap[vi_MemberEdges[k]] = i_SmallerSetID;
03735 
03736                                                 v2i_SetEdgeMap[i_SmallerSetID].push_back(vi_MemberEdges[k]);
03737                                         }
03738 #endif
03739                                 }
03740                         }
03741 
03742 
03743                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
03744                         {
03745                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
03746                                 {
03747                                         continue;
03748                                 }
03749 
03750                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
03751                                 {
03752                                         if(m_vi_Edges[k] == i_PresentVertex)
03753                                         {
03754                                                 continue;
03755                                         }
03756 
03757                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
03758                                         {
03759                                                 continue;
03760                                         }
03761 
03762                                         if(m_vi_VertexColors[m_vi_Edges[k]] == m_vi_VertexColors[i_PresentVertex])
03763                                         {
03764                                                 if(m_vi_Edges[j] <  m_vi_Edges[k])
03765                                                 {
03766                                                         i_AdjacentEdgeID = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]];
03767                                                 }
03768                                                 else
03769                                                 {
03770                                                         i_AdjacentEdgeID = m_mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]];
03771                                                 }
03772 
03773                                                 i_EdgeID = UpdateSet(i_PresentVertex, m_vi_Edges[j], m_vi_Edges[k], m_mimi2_VertexEdgeMap, vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree);
03774 
03775                                                 if(i_EdgeID != _UNKNOWN)
03776                                                 {
03777 
03778 #if DISJOINT_SETS == _TRUE
03779 
03780                                                         i_SetOneID = m_ds_DisjointSets.FindAndCompress(i_EdgeID);
03781                                                         i_SetTwoID = m_ds_DisjointSets.FindAndCompress(i_AdjacentEdgeID);
03782 
03783 #if DEBUG == 1461
03784                                                         cout<<endl;
03785                                                         cout<<"DEBUG 1461 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(i_SetOneID)<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(i_SetTwoID)<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
03786                                                         cout<<endl;
03787 
03788 #endif
03789 
03790                                                         m_ds_DisjointSets.UnionBySize(i_SetOneID, i_SetTwoID);
03791 
03792 #endif
03793 
03794 #if DISJOINT_SETS == _FALSE
03795 
03796 #if DEBUG == 1461
03797                                                         cout<<endl;
03798                                                         cout<<"DEBUG 1461 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(vi_EdgeSetMap[i_EdgeID])<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(vi_EdgeSetMap[i_AdjacentEdgeID])<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
03799                                                         cout<<endl;
03800 
03801 #endif
03802 
03803                                                         if(v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].size() < v2i_SetEdgeMap[vi_EdgeSetMap[i_AdjacentEdgeID]].size())
03804                                                         {
03805                                                                 i_SmallerSetID = vi_EdgeSetMap[i_EdgeID];
03806                                                                 i_BiggerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
03807                                                         }
03808                                                         else
03809                                                         {
03810                                                                 i_BiggerSetID = vi_EdgeSetMap[i_EdgeID];
03811                                                                 i_SmallerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
03812                                                         }
03813 
03814                                                         vi_MemberEdges.clear();
03815                                                         vi_MemberEdges.swap(v2i_SetEdgeMap[i_BiggerSetID]);
03816 
03817                                                         vi_DisjointSets[i_BiggerSetID] = _FALSE;
03818 
03819                                                         i_MemberCount = (signed) vi_MemberEdges.size();
03820 
03821                                                         for(l=0; l<i_MemberCount; l++)
03822                                                         {
03823                                                                 vi_EdgeSetMap[vi_MemberEdges[l]] = i_SmallerSetID;
03824 
03825                                                                 v2i_SetEdgeMap[i_SmallerSetID].push_back(vi_MemberEdges[l]);
03826                                                         }
03827 
03828 #endif
03829                                                 }
03830                                         }
03831                                 }
03832                         }
03833 
03834 #if DEBUG == 1461
03835 
03836                         cout<<endl;
03837                         cout<<"DEBUG 1461 | Acyclic Coloring | Vertex Colors | Upto Vertex "<<STEP_UP(i)<<endl;
03838                         cout<<endl;
03839 
03840                         for(j=0; j<i_VertexCount; j++)
03841                         {
03842                                 cout<<"Vertex "<<STEP_UP(j)<<" = "<<STEP_UP(m_vi_VertexColors[j])<<endl;
03843                         }
03844 #endif
03845 
03846                 }
03847 
03848 
03849 #if DEBUG == 1461
03850 
03851 #if DISJOINT_SETS == _FALSE
03852 
03853                 i_EdgeCount = (signed) v2i_EdgeVertexMap.size();
03854 
03855                 cout<<endl;
03856                 cout<<"DEBUG 1461 | Acyclic Coloring | Edge Set Map"<<endl;
03857                 cout<<endl;
03858 
03859                 for(i=0; i<i_EdgeCount; i++)
03860                 {
03861                         cout<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(vi_EdgeSetMap[i])<<endl;
03862                 }
03863 
03864                 cout<<endl;
03865                 cout<<"DEBUG 1461 | Acyclic Coloring | Set Edge Map"<<endl;
03866                 cout<<endl;
03867 
03868                 for(i=0; i<i_EdgeCount; i++)
03869                 {
03870                         i_MemberCount = (signed) v2i_SetEdgeMap[i].size();
03871 
03872                         if(i_MemberCount == _FALSE)
03873                         {
03874                                 continue;
03875                         }
03876 
03877                         cout<<"Set "<<STEP_UP(i)<<"\t"<<" : ";
03878 
03879                         for(j=0; j<i_MemberCount; j++)
03880                         {
03881                                 if(j == STEP_DOWN(i_MemberCount))
03882                                 {
03883                                         cout<<STEP_UP(v2i_SetEdgeMap[i][j])<<" ("<<i_MemberCount<<")"<<endl;
03884                                 }
03885                                 else
03886                                 {
03887                                         cout<<STEP_UP(v2i_SetEdgeMap[i][j])<<", ";
03888                                 }
03889                         }
03890                 }
03891 
03892                 cout<<endl;
03893 
03894 #endif
03895 
03896 #endif
03897 
03898 #if VERBOSE == _TRUE
03899 
03900                 cout<<endl;
03901 
03902 #endif
03903 
03904 #if STATISTICS == _TRUE
03905 
03906 #if DISJOINT_SETS == _TRUE
03907 
03908                 m_i_ColoringUnits = m_ds_DisjointSets.Count();
03909 
03910 
03911 #elif DISJOINT_SETS == _FALSE
03912 
03913                 int i_SetSize;
03914 
03915                 m_i_ColoringUnits = _FALSE;
03916 
03917                 i_SetSize = (unsigned) v2i_SetEdgeMap.size();
03918 
03919                 for(i=0; i<i_SetSize; i++)
03920                 {
03921                         if(v2i_SetEdgeMap[i].empty())
03922                         {
03923                                 continue;
03924                         }
03925 
03926                         m_i_ColoringUnits++;
03927                 }
03928 
03929 #endif
03930 
03931 #endif
03932 
03933 
03934         //cerr<<"START End Coloring ds_DisjointSets.Print()"<<endl;
03935         //m_ds_DisjointSets.Print();
03936         //cerr<<"END ds_DisjointSets.Print()"<<endl;
03937         //Pause();
03938                 return(_TRUE);
03939 
03940         }
03941 
03942         int GraphColoring::AcyclicColoring_ForIndirectRecovery() {
03943 //#define DEBUG 1462
03944                 if(CheckVertexColoring("ACYCLIC"))
03945                 {
03946                         return(_TRUE);
03947                 }
03948 
03949                 int i, j, k;
03950 
03951                 int i_VertexCount, i_EdgeCount;
03952 
03953                 int i_AdjacentEdgeID, i_EdgeID, i_SetID;
03954 
03955                 int i_PresentVertex;
03956 
03957                 vector<int> vi_CandidateColors;
03958 
03959                 vector<int> vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree;
03960                 vector<int> vi_FirstVisitedOne, vi_FirstVisitedTwo;
03961 
03962                 //m_mimi2_VertexEdgeMap is populated and used in this function;
03963 
03964 #if DISJOINT_SETS == _FALSE
03965 
03966                 int l;
03967 
03968                 int i_MemberCount;
03969 
03970                 int i_SmallerSetID, i_BiggerSetID;
03971 
03972                 vector<int> vi_DisjointSets;
03973                 vector<int> vi_MemberEdges;
03974                 vector<int> vi_EdgeSetMap;
03975 
03976                 vector< vector<int> > v2i_SetEdgeMap;
03977 
03978 #endif
03979 
03980 #if DISJOINT_SETS == _TRUE
03981 
03982                 int i_SetOneID, i_SetTwoID;
03983 
03984                 //DisjointSets ds_DisjointSets;
03985 
03986 #endif
03987 
03988                 if(m_s_VertexColoringVariant.compare("ALL") != 0)
03989                 {
03990                         m_s_VertexColoringVariant = "ACYCLIC";
03991                 }
03992 
03993                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
03994 
03995                 k=_FALSE;
03996 
03997                 //populate m_mimi2_VertexEdgeMap
03998                 //Basically assign a number (k = 1, 2, 3 ...) for each edge of the graph
03999                 m_mimi2_VertexEdgeMap.clear();
04000 
04001                 for(i=0; i<i_VertexCount; i++)
04002                 {
04003                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
04004                         {
04005                                 if(i < m_vi_Edges[j])
04006                                 {
04007                                         m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k;
04008 
04009                                         k++;
04010                                 }
04011                         }
04012                 }
04013 
04014 //GraphColoringInterface::PrintVertexEdgeMap(m_vi_Vertices, m_vi_Edges, m_mimi2_VertexEdgeMap);
04015 #if DEBUG == 1462
04016 
04017                 cout<<endl;
04018                 cout<<"DEBUG 1462 | Acyclic Coloring | Edge Vertex Map"<<endl;
04019                 cout<<endl;
04020 
04021                 for(i=0; i<i_VertexCount; i++)
04022                 {
04023                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
04024                         {
04025                                 if(i < m_vi_Edges[j])
04026                                 {
04027                                 cout<<"Edge "<<STEP_UP(m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]])<<"\t"<<" : "<<STEP_UP(i)<<" - "<<STEP_UP(m_vi_Edges[j])<<endl;
04028                                 }
04029                         }
04030                 }
04031 
04032                 cout<<endl;
04033 
04034 #endif
04035 
04036                 i_EdgeCount = (signed) m_vi_Edges.size();
04037 
04038                 m_vi_VertexColors.clear();
04039                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
04040 
04041                 vi_CandidateColors.clear();
04042                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
04043 
04044                 vi_FirstSeenOne.clear();
04045                 vi_FirstSeenOne.resize((unsigned) i_VertexCount, _UNKNOWN);
04046 
04047                 vi_FirstSeenTwo.clear();
04048                 vi_FirstSeenTwo.resize((unsigned) i_VertexCount, _UNKNOWN);
04049 
04050                 vi_FirstSeenThree.clear();
04051                 vi_FirstSeenThree.resize((unsigned) i_VertexCount, _UNKNOWN);
04052 
04053                 vi_FirstVisitedOne.clear();
04054                 vi_FirstVisitedOne.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
04055 
04056                 vi_FirstVisitedTwo.clear();
04057                 vi_FirstVisitedTwo.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
04058 
04059 //cout<<"*1"<<endl;
04060 #if DISJOINT_SETS == _FALSE
04061 
04062                 vi_MemberEdges.clear();
04063 
04064                 vi_EdgeSetMap.clear();
04065                 vi_EdgeSetMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
04066 
04067                 v2i_SetEdgeMap.clear();
04068                 v2i_SetEdgeMap.resize((unsigned) i_EdgeCount/2);
04069 
04070                 vi_DisjointSets.clear();
04071 
04072 #endif
04073 
04074 #if DISJOINT_SETS == _TRUE
04075 
04076                 m_ds_DisjointSets.SetSize(i_EdgeCount/2);
04077 
04078 #endif
04079 
04080 #if VERBOSE == _TRUE
04081 
04082                 cout<<endl;
04083 
04084 #endif
04085 
04086                 m_i_VertexColorCount = _UNKNOWN;
04087 
04088 //cout<<"*11 i_VertexCount="<<i_VertexCount<<endl;
04089                 for(i=0; i<i_VertexCount; i++)
04090                 {
04091 //cout<<"*12 m_vi_OrderedVertices="<<m_vi_OrderedVertices.size()<<endl;
04092                         i_PresentVertex = m_vi_OrderedVertices[i];
04093 //cout<<"*13 i_PresentVertex="<<i_PresentVertex<<endl;
04094 
04095 #if VERBOSE == _TRUE
04096 //#if DEBUG == 1462
04097 
04098                         cout<<"DEBUG 1462 | Acyclic Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
04099 
04100 #endif
04101 
04102                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
04103                         {
04104                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
04105                                 {
04106                                         continue;
04107                                 }
04108 
04109                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
04110                         }
04111 
04112                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
04113                         {
04114                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
04115                                 {
04116                                         continue;
04117                                 }
04118 
04119                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
04120                                 {
04121                                         if(m_vi_Edges[k] == i_PresentVertex)
04122                                         {
04123                                                 continue;
04124                                         }
04125 
04126                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
04127                                         {
04128                                                 continue;
04129                                         }
04130 
04131                                         if(vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] == i_PresentVertex)
04132                                         {
04133                                                 continue;
04134                                         }
04135 
04136 #if DISJOINT_SETS == _TRUE
04137 
04138                                         if(m_vi_Edges[j] < m_vi_Edges[k])
04139                                         {
04140                                                 i_SetID = m_ds_DisjointSets.FindAndCompress(m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]);
04141                                         }
04142                                         else
04143                                         {
04144                                                 i_SetID = m_ds_DisjointSets.FindAndCompress(m_mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]);
04145                                         }
04146 #endif
04147 
04148 #if DISJOINT_SETS == _FALSE
04149 
04150                                         if(m_vi_Edges[j] < m_vi_Edges[k])
04151                                         {
04152                                                 i_SetID = vi_EdgeSetMap[m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]];
04153                                         }
04154                                         else
04155                                         {
04156                                                 i_SetID = vi_EdgeSetMap[m_mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]];
04157                                         }
04158 #endif
04159 
04160                                         FindCycle(i_PresentVertex, m_vi_Edges[j], m_vi_Edges[k], i_SetID, vi_CandidateColors, vi_FirstVisitedOne, vi_FirstVisitedTwo);
04161                                 }
04162                         }
04163 
04164                         for(j=0; j<i_VertexCount; j++)
04165                         {
04166                                 if(vi_CandidateColors[j] != i_PresentVertex)
04167                                 {
04168                                         m_vi_VertexColors[i_PresentVertex] = j;
04169 
04170                                         if(m_i_VertexColorCount < j)
04171                                         {
04172                                                 m_i_VertexColorCount = j;
04173                                         }
04174 
04175                                         break;
04176                                 }
04177                         }
04178 
04179                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
04180                         {
04181                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
04182                                 {
04183                                         continue;
04184                                 }
04185 
04186                                 if(i_PresentVertex < m_vi_Edges[j])
04187                                 {
04188                                         i_EdgeID = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]];
04189                                 }
04190                                 else
04191                                 {
04192                                         i_EdgeID = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex];
04193                                 }
04194 
04195 #if DISJOINT_SETS == _FALSE
04196 
04197                                 vi_DisjointSets.push_back(_TRUE);
04198 
04199                                 vi_EdgeSetMap[i_EdgeID] = STEP_DOWN((signed) vi_DisjointSets.size());
04200 
04201                                 v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].push_back(i_EdgeID);
04202 #endif
04203 
04204 //cout<<"*2"<<endl;
04205                                 i_AdjacentEdgeID = UpdateSet(i_PresentVertex, m_vi_Edges[j], i_PresentVertex, m_mimi2_VertexEdgeMap, vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree);
04206 
04207                                 if(i_AdjacentEdgeID != _UNKNOWN)
04208                                 {
04209 
04210 #if DISJOINT_SETS == _TRUE
04211 
04212                                         i_SetOneID = m_ds_DisjointSets.FindAndCompress(i_EdgeID);
04213                                         i_SetTwoID = m_ds_DisjointSets.FindAndCompress(i_AdjacentEdgeID);
04214 
04215 #if DEBUG == 1462
04216 
04217                                         cout<<endl;
04218                                         cout<<"DEBUG 1462 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(i_SetOneID)<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(i_SetTwoID)<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
04219                                         cout<<endl;
04220 
04221 #endif
04222 
04223         //cerr<<"START In Coloring before Union ds_DisjointSets.Print()"<<endl;
04224         //m_ds_DisjointSets.Print();
04225         //cerr<<"END ds_DisjointSets.Print()"<<endl;
04226         //Pause();
04227                                         m_ds_DisjointSets.UnionBySize(i_SetOneID, i_SetTwoID);
04228         //cerr<<"START In Coloring after  Union ds_DisjointSets.Print()"<<endl;
04229         //m_ds_DisjointSets.Print();
04230         //cerr<<"END ds_DisjointSets.Print()"<<endl;
04231         //Pause();
04232 
04233 #endif
04234 
04235 #if DISJOINT_SETS == _FALSE
04236 
04237 #if DEBUG == 1462
04238 
04239                                         cout<<endl;
04240                                         cout<<"DEBUG 1462 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(vi_EdgeSetMap[i_EdgeID])<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(vi_EdgeSetMap[i_AdjacentEdgeID])<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
04241                                         cout<<endl;
04242 
04243 #endif
04244 
04245                                         if(v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].size() < v2i_SetEdgeMap[vi_EdgeSetMap[i_AdjacentEdgeID]].size())
04246                                         {
04247                                                 i_SmallerSetID = vi_EdgeSetMap[i_EdgeID];
04248                                                 i_BiggerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
04249                                         }
04250                                         else
04251                                         {
04252                                                 i_BiggerSetID = vi_EdgeSetMap[i_EdgeID];
04253                                                 i_SmallerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
04254                                         }
04255 
04256                                         vi_MemberEdges.clear();
04257                                         vi_MemberEdges.swap(v2i_SetEdgeMap[i_BiggerSetID]);
04258 
04259                                         vi_DisjointSets[i_BiggerSetID] = _FALSE;
04260 
04261                                         i_MemberCount = (signed) vi_MemberEdges.size();
04262 
04263                                         for(k=0; k<i_MemberCount; k++)
04264                                         {
04265                                                 vi_EdgeSetMap[vi_MemberEdges[k]] = i_SmallerSetID;
04266 
04267                                                 v2i_SetEdgeMap[i_SmallerSetID].push_back(vi_MemberEdges[k]);
04268                                         }
04269 #endif
04270                                 }
04271                         }
04272 
04273 
04274 //cout<<"*3"<<endl;
04275                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
04276                         {
04277                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
04278                                 {
04279                                         continue;
04280                                 }
04281 
04282                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
04283                                 {
04284                                         if(m_vi_Edges[k] == i_PresentVertex)
04285                                         {
04286                                                 continue;
04287                                         }
04288 
04289                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
04290                                         {
04291                                                 continue;
04292                                         }
04293 
04294                                         if(m_vi_VertexColors[m_vi_Edges[k]] == m_vi_VertexColors[i_PresentVertex])
04295                                         {
04296                                                 if(m_vi_Edges[j] <  m_vi_Edges[k])
04297                                                 {
04298                                                         i_AdjacentEdgeID = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]];
04299                                                 }
04300                                                 else
04301                                                 {
04302                                                         i_AdjacentEdgeID = m_mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]];
04303                                                 }
04304 
04305                                                 i_EdgeID = UpdateSet(i_PresentVertex, m_vi_Edges[j], m_vi_Edges[k], m_mimi2_VertexEdgeMap, vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree);
04306 
04307                                                 if(i_EdgeID != _UNKNOWN)
04308                                                 {
04309 
04310 #if DISJOINT_SETS == _TRUE
04311 
04312                                                         i_SetOneID = m_ds_DisjointSets.FindAndCompress(i_EdgeID);
04313                                                         i_SetTwoID = m_ds_DisjointSets.FindAndCompress(i_AdjacentEdgeID);
04314 
04315 #if DEBUG == 1462
04316                                                         cout<<endl;
04317                                                         cout<<"DEBUG 1462 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(i_SetOneID)<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(i_SetTwoID)<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
04318                                                         cout<<endl;
04319 
04320 #endif
04321 
04322         //cerr<<"START In Coloring before Union ds_DisjointSets.Print()"<<endl;
04323         //m_ds_DisjointSets.Print();
04324         //cerr<<"END ds_DisjointSets.Print()"<<endl;
04325         //Pause();
04326                                                         m_ds_DisjointSets.UnionBySize(i_SetOneID, i_SetTwoID);
04327         //cerr<<"START In Coloring after  Union ds_DisjointSets.Print()"<<endl;
04328         //m_ds_DisjointSets.Print();
04329         //cerr<<"END ds_DisjointSets.Print()"<<endl;
04330         //Pause();
04331 
04332 #endif
04333 
04334 #if DISJOINT_SETS == _FALSE
04335 
04336 #if DEBUG == 1462
04337 
04338                                                         cout<<endl;
04339                                                         cout<<"DEBUG 1462 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(vi_EdgeSetMap[i_EdgeID])<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(vi_EdgeSetMap[i_AdjacentEdgeID])<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
04340                                                         cout<<endl;
04341 
04342 #endif
04343 
04344                                                         if(v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].size() < v2i_SetEdgeMap[vi_EdgeSetMap[i_AdjacentEdgeID]].size())
04345                                                         {
04346                                                                 i_SmallerSetID = vi_EdgeSetMap[i_EdgeID];
04347                                                                 i_BiggerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
04348                                                         }
04349                                                         else
04350                                                         {
04351                                                                 i_BiggerSetID = vi_EdgeSetMap[i_EdgeID];
04352                                                                 i_SmallerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
04353                                                         }
04354 
04355                                                         vi_MemberEdges.clear();
04356                                                         vi_MemberEdges.swap(v2i_SetEdgeMap[i_BiggerSetID]);
04357 
04358                                                         vi_DisjointSets[i_BiggerSetID] = _FALSE;
04359 
04360                                                         i_MemberCount = (signed) vi_MemberEdges.size();
04361 
04362                                                         for(l=0; l<i_MemberCount; l++)
04363                                                         {
04364                                                                 vi_EdgeSetMap[vi_MemberEdges[l]] = i_SmallerSetID;
04365 
04366                                                                 v2i_SetEdgeMap[i_SmallerSetID].push_back(vi_MemberEdges[l]);
04367                                                         }
04368 
04369 #endif
04370                                                 }
04371                                         }
04372                                 }
04373                         }
04374 
04375 #if DEBUG == 1462
04376 
04377                         cout<<endl;
04378                         cout<<"DEBUG 1462 | Acyclic Coloring | Vertex Colors | Upto Vertex "<<STEP_UP(i_PresentVertex)<<endl;
04379                         cout<<endl;
04380 
04381                         for(j=0; j<i_VertexCount; j++)
04382                         {
04383                                 cout<<"Vertex "<<STEP_UP(j)<<" = "<<STEP_UP(m_vi_VertexColors[j])<<endl;
04384                         }
04385 #endif
04386 
04387                 }
04388 
04389 
04390 #if DEBUG == 1462
04391 
04392 #if DISJOINT_SETS == _FALSE
04393 
04394                 i_EdgeCount = (signed) v2i_EdgeVertexMap.size();
04395 
04396                 cout<<endl;
04397                 cout<<"DEBUG 1462 | Acyclic Coloring | Edge Set Map"<<endl;
04398                 cout<<endl;
04399 
04400                 for(i=0; i<i_EdgeCount; i++)
04401                 {
04402                         cout<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(vi_EdgeSetMap[i])<<endl;
04403                 }
04404 
04405                 cout<<endl;
04406                 cout<<"DEBUG 1462 | Acyclic Coloring | Set Edge Map"<<endl;
04407                 cout<<endl;
04408 
04409                 for(i=0; i<i_EdgeCount; i++)
04410                 {
04411                         i_MemberCount = (signed) v2i_SetEdgeMap[i].size();
04412 
04413                         if(i_MemberCount == _FALSE)
04414                         {
04415                                 continue;
04416                         }
04417 
04418                         cout<<"Set "<<STEP_UP(i)<<"\t"<<" : ";
04419 
04420                         for(j=0; j<i_MemberCount; j++)
04421                         {
04422                                 if(j == STEP_DOWN(i_MemberCount))
04423                                 {
04424                                         cout<<STEP_UP(v2i_SetEdgeMap[i][j])<<" ("<<i_MemberCount<<")"<<endl;
04425                                 }
04426                                 else
04427                                 {
04428                                         cout<<STEP_UP(v2i_SetEdgeMap[i][j])<<", ";
04429                                 }
04430                         }
04431                 }
04432 
04433                 cout<<endl;
04434 
04435 #endif
04436 
04437 #endif
04438 
04439 #if VERBOSE == _TRUE
04440 
04441                 cout<<endl;
04442 
04443 #endif
04444 
04445 
04446         //cerr<<"START End Coloring ds_DisjointSets.Print()"<<endl;
04447         //m_ds_DisjointSets.Print();
04448         //cerr<<"END ds_DisjointSets.Print()"<<endl;
04449         //Pause();
04450                 return(_TRUE);
04451         }
04452 
04453         //Public Function 1462
04454         int GraphColoring::AcyclicColoring(vector<int> & vi_Sets, map< int, vector<int> > & mivi_VertexSets)
04455         {
04456 //#define DEBUG 1462
04457                 if(CheckVertexColoring("ACYCLIC"))
04458                 {
04459                         return(_TRUE);
04460                 }
04461 
04462                 int i, j, k;
04463 
04464                 int i_VertexCount, i_EdgeCount;
04465 
04466                 int i_AdjacentEdgeID, i_EdgeID, i_SetID;
04467 
04468                 int i_PresentVertex;
04469 
04470                 vector<int> vi_CandidateColors;
04471 
04472                 vector<int> vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree;
04473                 vector<int> vi_FirstVisitedOne, vi_FirstVisitedTwo;
04474 
04475                 map< int, map<int, int> > mimi2_VertexEdgeMap;
04476 
04477 #if DISJOINT_SETS == _FALSE
04478 
04479                 int l;
04480 
04481                 int i_MemberCount;
04482 
04483                 int i_SmallerSetID, i_BiggerSetID;
04484 
04485                 vector<int> vi_DisjointSets;
04486                 vector<int> vi_MemberEdges;
04487                 vector<int> vi_EdgeSetMap;
04488 
04489                 vector< vector<int> > v2i_SetEdgeMap;
04490 
04491 #endif
04492 
04493 #if DISJOINT_SETS == _TRUE
04494 
04495                 int i_SetOneID, i_SetTwoID;
04496 
04497                 //DisjointSets ds_DisjointSets;
04498 
04499 #endif
04500 
04501                 if(m_s_VertexColoringVariant.compare("ALL") != 0)
04502                 {
04503                         m_s_VertexColoringVariant = "ACYCLIC";
04504                 }
04505 
04506                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
04507 
04508                 k=_FALSE;
04509 
04510                 //populate mimi2_VertexEdgeMap
04511                 //Basically assign a number (k = 1, 2, 3 ...) for each edge of the graph
04512                 mimi2_VertexEdgeMap.clear();
04513 
04514                 for(i=0; i<i_VertexCount; i++)
04515                 {
04516                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
04517                         {
04518                                 if(i < m_vi_Edges[j])
04519                                 {
04520                                         mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k;
04521 
04522                                         k++;
04523                                 }
04524                         }
04525                 }
04526 
04527 #if DEBUG == 1462
04528 
04529                 cout<<endl;
04530                 cout<<"DEBUG 1462 | Acyclic Coloring | Edge Vertex Map"<<endl;
04531                 cout<<endl;
04532 
04533                 for(i=0; i<i_VertexCount; i++)
04534                 {
04535                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
04536                         {
04537                                 if(i < m_vi_Edges[j])
04538                                 {
04539                                 cout<<"Edge "<<STEP_UP(mimi2_VertexEdgeMap[i][m_vi_Edges[j]])<<"\t"<<" : "<<STEP_UP(i)<<" - "<<STEP_UP(m_vi_Edges[j])<<endl;
04540                                 }
04541                         }
04542                 }
04543 
04544                 cout<<endl;
04545 
04546 #endif
04547 
04548                 i_EdgeCount = (signed) m_vi_Edges.size();
04549 
04550                 m_vi_VertexColors.clear();
04551                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
04552 
04553                 vi_CandidateColors.clear();
04554                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
04555 
04556                 vi_FirstSeenOne.clear();
04557                 vi_FirstSeenOne.resize((unsigned) i_VertexCount, _UNKNOWN);
04558 
04559                 vi_FirstSeenTwo.clear();
04560                 vi_FirstSeenTwo.resize((unsigned) i_VertexCount, _UNKNOWN);
04561 
04562                 vi_FirstSeenThree.clear();
04563                 vi_FirstSeenThree.resize((unsigned) i_VertexCount, _UNKNOWN);
04564 
04565                 vi_FirstVisitedOne.clear();
04566                 vi_FirstVisitedOne.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
04567 
04568                 vi_FirstVisitedTwo.clear();
04569                 vi_FirstVisitedTwo.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
04570 
04571 //cout<<"*1"<<endl;
04572 #if DISJOINT_SETS == _FALSE
04573 
04574                 vi_MemberEdges.clear();
04575 
04576                 vi_EdgeSetMap.clear();
04577                 vi_EdgeSetMap.resize((unsigned) i_EdgeCount/2, _UNKNOWN);
04578 
04579                 v2i_SetEdgeMap.clear();
04580                 v2i_SetEdgeMap.resize((unsigned) i_EdgeCount/2);
04581 
04582                 vi_DisjointSets.clear();
04583 
04584 #endif
04585 
04586 #if DISJOINT_SETS == _TRUE
04587 
04588                 m_ds_DisjointSets.SetSize(i_EdgeCount/2);
04589 
04590 #endif
04591 
04592 #if VERBOSE == _TRUE
04593 
04594                 cout<<endl;
04595 
04596 #endif
04597 
04598                 m_i_VertexColorCount = _UNKNOWN;
04599 
04600 //cout<<"*11 i_VertexCount="<<i_VertexCount<<endl;
04601                 for(i=0; i<i_VertexCount; i++)
04602                 {
04603 //cout<<"*12 m_vi_OrderedVertices="<<m_vi_OrderedVertices.size()<<endl;
04604                         i_PresentVertex = m_vi_OrderedVertices[i];
04605 //cout<<"*13 i_PresentVertex="<<i_PresentVertex<<endl;
04606 
04607 #if VERBOSE == _TRUE
04608 //#if DEBUG == 1462
04609 
04610                         cout<<"DEBUG 1462 | Acyclic Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
04611 
04612 #endif
04613 
04614                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
04615                         {
04616                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
04617                                 {
04618                                         continue;
04619                                 }
04620 
04621                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
04622                         }
04623 
04624                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
04625                         {
04626                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
04627                                 {
04628                                         continue;
04629                                 }
04630 
04631                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
04632                                 {
04633                                         if(m_vi_Edges[k] == i_PresentVertex)
04634                                         {
04635                                                 continue;
04636                                         }
04637 
04638                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
04639                                         {
04640                                                 continue;
04641                                         }
04642 
04643                                         if(vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] == i_PresentVertex)
04644                                         {
04645                                                 continue;
04646                                         }
04647 
04648 #if DISJOINT_SETS == _TRUE
04649 
04650                                         if(m_vi_Edges[j] < m_vi_Edges[k])
04651                                         {
04652                                                 i_SetID = m_ds_DisjointSets.FindAndCompress(mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]);
04653                                         }
04654                                         else
04655                                         {
04656                                                 i_SetID = m_ds_DisjointSets.FindAndCompress(mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]);
04657                                         }
04658 #endif
04659 
04660 #if DISJOINT_SETS == _FALSE
04661 
04662                                         if(m_vi_Edges[j] < m_vi_Edges[k])
04663                                         {
04664                                                 i_SetID = vi_EdgeSetMap[mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]]];
04665                                         }
04666                                         else
04667                                         {
04668                                                 i_SetID = vi_EdgeSetMap[mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]]];
04669                                         }
04670 #endif
04671 
04672                                         FindCycle(i_PresentVertex, m_vi_Edges[j], m_vi_Edges[k], i_SetID, vi_CandidateColors, vi_FirstVisitedOne, vi_FirstVisitedTwo);
04673                                 }
04674                         }
04675 
04676                         for(j=0; j<i_VertexCount; j++)
04677                         {
04678                                 if(vi_CandidateColors[j] != i_PresentVertex)
04679                                 {
04680                                         m_vi_VertexColors[i_PresentVertex] = j;
04681 
04682                                         if(m_i_VertexColorCount < j)
04683                                         {
04684                                                 m_i_VertexColorCount = j;
04685                                         }
04686 
04687                                         break;
04688                                 }
04689                         }
04690 
04691                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
04692                         {
04693                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
04694                                 {
04695                                         continue;
04696                                 }
04697 
04698                                 if(i_PresentVertex < m_vi_Edges[j])
04699                                 {
04700                                         i_EdgeID = mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]];
04701                                 }
04702                                 else
04703                                 {
04704                                         i_EdgeID = mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex];
04705                                 }
04706 
04707 #if DISJOINT_SETS == _FALSE
04708 
04709                                 vi_DisjointSets.push_back(_TRUE);
04710 
04711                                 vi_EdgeSetMap[i_EdgeID] = STEP_DOWN((signed) vi_DisjointSets.size());
04712 
04713                                 v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].push_back(i_EdgeID);
04714 #endif
04715 
04716 //cout<<"*2"<<endl;
04717                                 i_AdjacentEdgeID = UpdateSet(i_PresentVertex, m_vi_Edges[j], i_PresentVertex, mimi2_VertexEdgeMap, vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree);
04718 
04719                                 if(i_AdjacentEdgeID != _UNKNOWN)
04720                                 {
04721 
04722 #if DISJOINT_SETS == _TRUE
04723 
04724                                         i_SetOneID = m_ds_DisjointSets.FindAndCompress(i_EdgeID);
04725                                         i_SetTwoID = m_ds_DisjointSets.FindAndCompress(i_AdjacentEdgeID);
04726 
04727 #if DEBUG == 1462
04728 
04729                                         cout<<endl;
04730                                         cout<<"DEBUG 1462 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(i_SetOneID)<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(i_SetTwoID)<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
04731                                         cout<<endl;
04732 
04733 #endif
04734 
04735                                         m_ds_DisjointSets.UnionBySize(i_SetOneID, i_SetTwoID);
04736 
04737 #endif
04738 
04739 #if DISJOINT_SETS == _FALSE
04740 
04741 #if DEBUG == 1462
04742 
04743                                         cout<<endl;
04744                                         cout<<"DEBUG 1462 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(vi_EdgeSetMap[i_EdgeID])<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(vi_EdgeSetMap[i_AdjacentEdgeID])<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
04745                                         cout<<endl;
04746 
04747 #endif
04748 
04749                                         if(v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].size() < v2i_SetEdgeMap[vi_EdgeSetMap[i_AdjacentEdgeID]].size())
04750                                         {
04751                                                 i_SmallerSetID = vi_EdgeSetMap[i_EdgeID];
04752                                                 i_BiggerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
04753                                         }
04754                                         else
04755                                         {
04756                                                 i_BiggerSetID = vi_EdgeSetMap[i_EdgeID];
04757                                                 i_SmallerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
04758                                         }
04759 
04760                                         vi_MemberEdges.clear();
04761                                         vi_MemberEdges.swap(v2i_SetEdgeMap[i_BiggerSetID]);
04762 
04763                                         vi_DisjointSets[i_BiggerSetID] = _FALSE;
04764 
04765                                         i_MemberCount = (signed) vi_MemberEdges.size();
04766 
04767                                         for(k=0; k<i_MemberCount; k++)
04768                                         {
04769                                                 vi_EdgeSetMap[vi_MemberEdges[k]] = i_SmallerSetID;
04770 
04771                                                 v2i_SetEdgeMap[i_SmallerSetID].push_back(vi_MemberEdges[k]);
04772                                         }
04773 #endif
04774                                 }
04775                         }
04776 
04777 
04778 //cout<<"*3"<<endl;
04779                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
04780                         {
04781                                 if(m_vi_VertexColors[m_vi_Edges[j]] == _UNKNOWN)
04782                                 {
04783                                         continue;
04784                                 }
04785 
04786                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
04787                                 {
04788                                         if(m_vi_Edges[k] == i_PresentVertex)
04789                                         {
04790                                                 continue;
04791                                         }
04792 
04793                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
04794                                         {
04795                                                 continue;
04796                                         }
04797 
04798                                         if(m_vi_VertexColors[m_vi_Edges[k]] == m_vi_VertexColors[i_PresentVertex])
04799                                         {
04800                                                 if(m_vi_Edges[j] <  m_vi_Edges[k])
04801                                                 {
04802                                                         i_AdjacentEdgeID = mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[k]];
04803                                                 }
04804                                                 else
04805                                                 {
04806                                                         i_AdjacentEdgeID = mimi2_VertexEdgeMap[m_vi_Edges[k]][m_vi_Edges[j]];
04807                                                 }
04808 
04809                                                 i_EdgeID = UpdateSet(i_PresentVertex, m_vi_Edges[j], m_vi_Edges[k], mimi2_VertexEdgeMap, vi_FirstSeenOne, vi_FirstSeenTwo, vi_FirstSeenThree);
04810 
04811                                                 if(i_EdgeID != _UNKNOWN)
04812                                                 {
04813 
04814 #if DISJOINT_SETS == _TRUE
04815 
04816                                                         i_SetOneID = m_ds_DisjointSets.FindAndCompress(i_EdgeID);
04817                                                         i_SetTwoID = m_ds_DisjointSets.FindAndCompress(i_AdjacentEdgeID);
04818 
04819 #if DEBUG == 1462
04820                                                         cout<<endl;
04821                                                         cout<<"DEBUG 1462 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(i_SetOneID)<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(i_SetTwoID)<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
04822                                                         cout<<endl;
04823 
04824 #endif
04825 
04826                                                         m_ds_DisjointSets.UnionBySize(i_SetOneID, i_SetTwoID);
04827 
04828 #endif
04829 
04830 #if DISJOINT_SETS == _FALSE
04831 
04832 #if DEBUG == 1462
04833 
04834                                                         cout<<endl;
04835                                                         cout<<"DEBUG 1462 | Acyclic Coloring | Unify Tree | Tree "<<STEP_UP(vi_EdgeSetMap[i_EdgeID])<<" (Edge "<<STEP_UP(i_EdgeID)<<") and Tree "<<STEP_UP(vi_EdgeSetMap[i_AdjacentEdgeID])<<" (Edge "<<STEP_UP(i_AdjacentEdgeID)<<")"<<endl;
04836                                                         cout<<endl;
04837 
04838 #endif
04839 
04840                                                         if(v2i_SetEdgeMap[vi_EdgeSetMap[i_EdgeID]].size() < v2i_SetEdgeMap[vi_EdgeSetMap[i_AdjacentEdgeID]].size())
04841                                                         {
04842                                                                 i_SmallerSetID = vi_EdgeSetMap[i_EdgeID];
04843                                                                 i_BiggerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
04844                                                         }
04845                                                         else
04846                                                         {
04847                                                                 i_BiggerSetID = vi_EdgeSetMap[i_EdgeID];
04848                                                                 i_SmallerSetID = vi_EdgeSetMap[i_AdjacentEdgeID];
04849                                                         }
04850 
04851                                                         vi_MemberEdges.clear();
04852                                                         vi_MemberEdges.swap(v2i_SetEdgeMap[i_BiggerSetID]);
04853 
04854                                                         vi_DisjointSets[i_BiggerSetID] = _FALSE;
04855 
04856                                                         i_MemberCount = (signed) vi_MemberEdges.size();
04857 
04858                                                         for(l=0; l<i_MemberCount; l++)
04859                                                         {
04860                                                                 vi_EdgeSetMap[vi_MemberEdges[l]] = i_SmallerSetID;
04861 
04862                                                                 v2i_SetEdgeMap[i_SmallerSetID].push_back(vi_MemberEdges[l]);
04863                                                         }
04864 
04865 #endif
04866                                                 }
04867                                         }
04868                                 }
04869                         }
04870 
04871 #if DEBUG == 1462
04872 
04873                         cout<<endl;
04874                         cout<<"DEBUG 1462 | Acyclic Coloring | Vertex Colors | Upto Vertex "<<STEP_UP(i_PresentVertex)<<endl;
04875                         cout<<endl;
04876 
04877                         for(j=0; j<i_VertexCount; j++)
04878                         {
04879                                 cout<<"Vertex "<<STEP_UP(j)<<" = "<<STEP_UP(m_vi_VertexColors[j])<<endl;
04880                         }
04881 #endif
04882 
04883                 }
04884 
04885 
04886 #if DEBUG == 1462
04887 
04888 #if DISJOINT_SETS == _FALSE
04889 
04890                 i_EdgeCount = (signed) v2i_EdgeVertexMap.size();
04891 
04892                 cout<<endl;
04893                 cout<<"DEBUG 1462 | Acyclic Coloring | Edge Set Map"<<endl;
04894                 cout<<endl;
04895 
04896                 for(i=0; i<i_EdgeCount; i++)
04897                 {
04898                         cout<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(vi_EdgeSetMap[i])<<endl;
04899                 }
04900 
04901                 cout<<endl;
04902                 cout<<"DEBUG 1462 | Acyclic Coloring | Set Edge Map"<<endl;
04903                 cout<<endl;
04904 
04905                 for(i=0; i<i_EdgeCount; i++)
04906                 {
04907                         i_MemberCount = (signed) v2i_SetEdgeMap[i].size();
04908 
04909                         if(i_MemberCount == _FALSE)
04910                         {
04911                                 continue;
04912                         }
04913 
04914                         cout<<"Set "<<STEP_UP(i)<<"\t"<<" : ";
04915 
04916                         for(j=0; j<i_MemberCount; j++)
04917                         {
04918                                 if(j == STEP_DOWN(i_MemberCount))
04919                                 {
04920                                         cout<<STEP_UP(v2i_SetEdgeMap[i][j])<<" ("<<i_MemberCount<<")"<<endl;
04921                                 }
04922                                 else
04923                                 {
04924                                         cout<<STEP_UP(v2i_SetEdgeMap[i][j])<<", ";
04925                                 }
04926                         }
04927                 }
04928 
04929                 cout<<endl;
04930 
04931 #endif
04932 
04933 #endif
04934 
04935 #if VERBOSE == _TRUE
04936 
04937                 cout<<endl;
04938 
04939 #endif
04940 
04941 #if DISJOINT_SETS == _TRUE
04942 //cout<<"*Here is the difference"<<endl;
04943 //m_ds_DisjointSets.Print();
04944                 vi_Sets.clear();
04945                 mivi_VertexSets.clear();
04946 
04947                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
04948 
04949                 for(i=0; i<i_VertexCount; i++) // for each vertex A (indexed by i)
04950                 {
04951                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++) // for each of the vertex B that connect to A
04952                         {
04953                                 if(i < m_vi_Edges[j]) // if the index of A (i) is less than the index of B (m_vi_Edges[j])
04954                                                                                 //basic each edge is represented by (vertex with smaller ID, vertex with larger ID). This way, we don't insert a specific edge twice
04955                                 {
04956                                         i_EdgeID = mimi2_VertexEdgeMap[i][m_vi_Edges[j]];
04957 
04958                                         i_SetID = m_ds_DisjointSets.FindAndCompress(i_EdgeID);
04959 
04960                                         if(i_SetID == i_EdgeID) // that edge is the root of the set => create new set
04961                                         {
04962                                                 vi_Sets.push_back(i_SetID);
04963                                         }
04964 
04965                                         mivi_VertexSets[i_SetID].push_back(i);
04966                                         mivi_VertexSets[i_SetID].push_back(m_vi_Edges[j]);
04967                                 }
04968                         }
04969                 }
04970 //cout<<"*Am I here?"<<endl;
04971 
04972 #endif
04973 
04974 #if DISJOINT_SETS == _FALSE
04975 
04976                 vi_Sets.clear();
04977                 mivi_VertexSets.clear();
04978 
04979                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
04980 
04981                 for(i=0; i<i_VertexCount; i++)
04982                 {
04983                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
04984                         {
04985                                 if(i < m_vi_Edges[j])
04986                                 {
04987                                         i_EdgeID = mimi2_VertexEdgeMap[i][m_vi_Edges[j]];
04988 
04989                                         i_SetID = vi_EdgeSetMap[i_EdgeID];
04990 
04991                                         if(mivi_VertexSets[i_SetID].empty())
04992                                         {
04993                                                 vi_Sets.push_back(i_SetID);
04994                                         }
04995 
04996                                         mivi_VertexSets[i_SetID].push_back(i);
04997                                         mivi_VertexSets[i_SetID].push_back(m_vi_Edges[j]);
04998                                 }
04999                         }
05000                 }
05001 
05002 #endif
05003 
05004                 return(_TRUE);
05005         }
05006 
05007 
05008         //Public Function 1463
05009         int GraphColoring::CheckAcyclicColoring()
05010         {
05011                 int i;
05012 
05013                 int i_VertexCount;
05014 
05015                 int i_ViolationCount;
05016 
05017                 vector<int> vi_TouchedVertices;
05018 
05019                 i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
05020 
05021                 i_ViolationCount = _FALSE;
05022 
05023                 for(i=0; i<i_VertexCount; i++)
05024                 {
05025                         vi_TouchedVertices.clear();
05026                         vi_TouchedVertices.resize((unsigned) i_VertexCount, _FALSE);
05027 
05028                         vi_TouchedVertices[i] = _TRUE;
05029 
05030                         i_ViolationCount = SearchDepthFirst(i, i, i, vi_TouchedVertices);
05031                 }
05032 
05033                 if(i_ViolationCount)
05034                 {
05035                         cout<<endl;
05036                         cout<<"[Total Violations = "<<i_ViolationCount<<"]"<<endl;
05037                         cout<<endl;
05038                 }
05039 
05040                 return(i_ViolationCount);
05041         }
05042 
05043 
05044         //Public Function 1464
05045         int GraphColoring::TriangularColoring()
05046         {
05047                 if(CheckVertexColoring("TRIANGULAR"))
05048                 {
05049                         return(_TRUE);
05050                 }
05051 
05052                 int i, j, k, l;
05053 
05054                 int _FOUND;
05055 
05056                 int i_VertexCount, i_VertexDegree;
05057 
05058                 int i_HighestVertexDegree;
05059 
05060                 int i_PresentVertex;
05061 
05062                 vector<int> vi_VertexHierarchy;
05063 
05064                 vector< vector<int> > v2i_VertexAdjacency;
05065 
05066                 i_VertexCount = (signed) m_vi_OrderedVertices.size();
05067 
05068                 vi_VertexHierarchy.clear();
05069                 vi_VertexHierarchy.resize((unsigned) i_VertexCount);
05070 
05071                 v2i_VertexAdjacency.clear();
05072                 v2i_VertexAdjacency.resize((unsigned) i_VertexCount);
05073 
05074                 for(i=0; i<i_VertexCount; i++)
05075                 {
05076                         vi_VertexHierarchy[m_vi_OrderedVertices[i]] = i;
05077                 }
05078 
05079                 //m_vi_VertexColors.clear();
05080                 //m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
05081 
05082                 m_i_VertexColorCount = _UNKNOWN;
05083 
05084                 for(i=0; i<i_VertexCount; i++)
05085                 {
05086                         i_PresentVertex = m_vi_OrderedVertices[i];
05087 
05088 #if VERBOSE == _TRUE
05089 
05090                         cout<<"DEBUG 1464 | Triangular Coloring | Processing Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
05091 
05092 #endif
05093 
05094                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
05095                         {
05096                                 v2i_VertexAdjacency[i_PresentVertex].push_back(m_vi_Edges[j]);
05097 
05098                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
05099                                 {
05100                                         if(m_vi_Edges[k] == i_PresentVertex)
05101                                         {
05102                                                 continue;
05103                                         }
05104 
05105                                         if((vi_VertexHierarchy[m_vi_Edges[j]] > vi_VertexHierarchy[i_PresentVertex]) && (vi_VertexHierarchy[m_vi_Edges[j]] > vi_VertexHierarchy[m_vi_Edges[k]]))
05106                                         {
05107                                                 _FOUND = _FALSE;
05108 
05109                                                 for(l=m_vi_Vertices[m_vi_Edges[k]]; l<m_vi_Vertices[STEP_UP(m_vi_Edges[k])]; l++)
05110                                                 {
05111                                                         if(m_vi_Edges[l] == i_PresentVertex)
05112                                                         {
05113                                                                 _FOUND = TRUE;
05114 
05115                                                                 break;
05116                                                         }
05117                                                 }
05118 
05119                                                 if(_FOUND == _FALSE)
05120                                                 {
05121                                                         v2i_VertexAdjacency[i_PresentVertex].push_back(m_vi_Edges[k]);
05122                                                 }
05123                                         }
05124                                 }
05125                         }
05126                 }
05127 
05128                 m_vi_Vertices.clear();
05129                 m_vi_Edges.clear();
05130 
05131                 i_HighestVertexDegree = _UNKNOWN;
05132 
05133                 for(i=0; i<i_VertexCount; i++)
05134                 {
05135                         m_vi_Vertices.push_back((signed) m_vi_Edges.size());
05136 
05137                         i_VertexDegree = (signed) v2i_VertexAdjacency[i].size();
05138 
05139                         if(i_HighestVertexDegree < i_VertexDegree)
05140                         {
05141                                 i_HighestVertexDegree = i_VertexDegree;
05142                         }
05143 
05144                         for(j=0; j<i_VertexDegree; j++)
05145                         {
05146                                 m_vi_Edges.push_back(v2i_VertexAdjacency[i][j]);
05147                         }
05148 
05149                         v2i_VertexAdjacency[i].clear();
05150                 }
05151 
05152                 m_vi_Vertices.push_back((signed) m_vi_Edges.size());
05153 
05154 #if DEBUG == 1464
05155 
05156                 int i_EdgeCount;
05157 
05158                 cout<<endl;
05159                 cout<<"DEBUG 1464 | Graph Coloring | Induced Matrix"<<endl;
05160                 cout<<endl;
05161 
05162                 i_VertexCount = (signed) m_vi_Vertices.size();
05163                 i_EdgeCount = (signed) m_vi_Edges.size();
05164 
05165                 for(i=0; i<i_VertexCount; i++)
05166                 {
05167                         for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
05168                         {
05169                                 cout<<"Element["<<STEP_UP(i)<<"]["<<STEP_UP(m_vi_Edges[j])<<"] = 1"<<endl;
05170                         }
05171                 }
05172 
05173                 cout<<endl;
05174                 cout<<"[Induced Vertices = "<<STEP_DOWN(i_VertexCount)<<"; Induced Edges = "<<i_EdgeCount<<"]"<<endl;
05175                 cout<<endl;
05176 
05177 #endif
05178 
05179                 SmallestLastOrdering();
05180 
05181                 return(DistanceOneColoring());
05182         }
05183 
05184 
05185 
05186         //Public Function 1465
05187         int GraphColoring::ModifiedTriangularColoring()
05188         {
05189                 if(CheckVertexColoring("MODIFIED TRIANGULAR"))
05190                 {
05191                         return(_TRUE);
05192                 }
05193 
05194                 int i, j, k;
05195 
05196                 int i_VertexCount;
05197 
05198                 int i_HighestColor;
05199 
05200                 int i_PresentVertex;
05201 
05202                 vector<int> vi_CandidateColors;
05203 
05204                 vector<int> vi_VertexHierarchy;
05205 
05206                 i_VertexCount = (signed) m_vi_OrderedVertices.size();
05207 
05208                 vi_VertexHierarchy.clear();
05209                 vi_VertexHierarchy.resize((unsigned) i_VertexCount);
05210 
05211                 for(i=0; i<i_VertexCount; i++)
05212                 {
05213                         vi_VertexHierarchy[m_vi_OrderedVertices[i]] = i;
05214                 }
05215 
05216                 m_vi_VertexColors.clear();
05217                 m_vi_VertexColors.resize((unsigned) i_VertexCount, _UNKNOWN);
05218 
05219                 vi_CandidateColors.clear();
05220                 vi_CandidateColors.resize((unsigned) i_VertexCount, _UNKNOWN);
05221 
05222                 i_HighestColor = _UNKNOWN;
05223 
05224                 for(i=0; i<i_VertexCount; i++)
05225                 {
05226                         i_PresentVertex = m_vi_OrderedVertices[i];
05227 
05228 #if VERBOSE == _TRUE
05229 
05230                         cout<<"DEBUG 1465 | Triangular Coloring | Coloring Vertex "<<STEP_UP(i_PresentVertex)<<"/"<<i_VertexCount<<endl;
05231 
05232 #endif
05233 
05234                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
05235                         {
05236                                 if(m_vi_VertexColors[m_vi_Edges[j]] != _UNKNOWN)
05237                                 {
05238                                         vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[j]]] = i_PresentVertex;
05239                                 }
05240 
05241                                 for(k=m_vi_Vertices[m_vi_Edges[j]]; k<m_vi_Vertices[STEP_UP(m_vi_Edges[j])]; k++)
05242                                 {
05243                                         if(m_vi_Edges[k] == i_PresentVertex)
05244                                         {
05245                                                 continue;
05246                                         }
05247 
05248                                         if(m_vi_VertexColors[m_vi_Edges[k]] == _UNKNOWN)
05249                                         {
05250                                                 continue;
05251                                         }
05252 
05253                                         if((vi_VertexHierarchy[m_vi_Edges[j]] > vi_VertexHierarchy[i_PresentVertex]) && (vi_VertexHierarchy[m_vi_Edges[j]] > vi_VertexHierarchy[m_vi_Edges[k]]))
05254                                         {
05255                                                 vi_CandidateColors[m_vi_VertexColors[m_vi_Edges[k]]] = i_PresentVertex;
05256                                         }
05257                                 }
05258                         }
05259 
05260                         for(j=0; j<i_VertexCount; j++)
05261                         {
05262                                 if(vi_CandidateColors[j] != i_PresentVertex)
05263                                 {
05264                                         m_vi_VertexColors[i_PresentVertex] = j;
05265 
05266                                         if(i_HighestColor < j)
05267                                         {
05268                                                 i_HighestColor = j;
05269                                         }
05270 
05271                                         break;
05272                                 }
05273                         }
05274                 }
05275 
05276                 return(_TRUE);
05277 }
05278 
05279         //Public Function 1466
05280         int GraphColoring::CheckTriangularColoring()
05281         {
05282                 return(CheckAcyclicColoring());
05283         }
05284 
05285 
05286         //Public Function 1467
05287         string GraphColoring::GetVertexColoringVariant()
05288         {
05289                 return(m_s_VertexColoringVariant);
05290         }
05291 
05292         void GraphColoring::SetVertexColoringVariant(string s_VertexColoringVariant)
05293         {
05294                 m_s_VertexColoringVariant = s_VertexColoringVariant;
05295         }
05296 
05297 
05298         //Public Function 1468
05299         int GraphColoring::GetVertexColorCount()
05300         {
05301                 return(STEP_UP(m_i_VertexColorCount));
05302         }
05303 
05304 
05305         //Public Function 1469
05306         void GraphColoring::GetVertexColors(vector<int> &output)
05307         {
05308                 output = (m_vi_VertexColors);
05309         }
05310 
05311 
05312         //Public Function 1470
05313         int GraphColoring::GetHubCount()
05314         {
05315                 if(CheckVertexColoring("STAR"))
05316                 {
05317                         return(m_i_ColoringUnits);
05318                 }
05319                 else
05320                 {
05321                         return(_UNKNOWN);
05322                 }
05323         }
05324 
05325 
05326         //Public Function 1471
05327         int GraphColoring::GetSetCount()
05328         {
05329                 if(CheckVertexColoring("ACYCLIC"))
05330                 {
05331                         return(m_i_ColoringUnits);
05332                 }
05333                 else
05334                 {
05335                         return(_UNKNOWN);
05336                 }
05337         }
05338 
05339         //Public Function 1472
05340         double GraphColoring::GetVertexColoringTime()
05341         {
05342                 return(m_d_ColoringTime);
05343         }
05344 
05345         //Public Function 1473
05346         double GraphColoring::GetVertexColoringCheckingTime()
05347         {
05348                 return(m_d_CheckingTime);
05349         }
05350 
05351         //Public Function 1474
05352         int GraphColoring::PrintVertexColors()
05353         {
05354                 int i;
05355 
05356                 int i_VertexCount;
05357 
05358                 string _SLASH("/");
05359 
05360                 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
05361 
05362                 m_s_InputFile = SlashTokenizer.GetLastToken();
05363 
05364                 i_VertexCount = (signed) m_vi_VertexColors.size();
05365 
05366                 cout<<endl;
05367                 cout<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | Vertex Colors | "<<m_s_InputFile<<endl;
05368                 cout<<endl;
05369 
05370                 for(i=0; i<i_VertexCount; i++)
05371                 {
05372                         cout<<"Vertex "<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(m_vi_VertexColors[i])<<endl;
05373                 }
05374 
05375 #if STATISTICS == _TRUE
05376 
05377                 if(m_s_VertexColoringVariant.compare("STAR") == 0)
05378                 {
05379                         cout<<endl;
05380                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Total Stars = "<<m_i_ColoringUnits<<"]"<<endl;
05381                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05382                         cout<<endl;
05383                 }
05384                 else
05385                 if(m_s_VertexColoringVariant.compare("ACYCLIC") == 0)
05386                 {
05387                         cout<<endl;
05388                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Total Sets = "<<m_i_ColoringUnits<<"]"<<endl;
05389                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05390                         cout<<endl;
05391                 }
05392                 else
05393                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05394                 {
05395                         cout<<endl;
05396                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05397                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05398                         cout<<endl;
05399                 }
05400                 else
05401                 {
05402                         cout<<endl;
05403                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05404                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05405                         cout<<endl;
05406                 }
05407 
05408 #endif
05409 
05410 #if STATISTICS == _FALSE
05411 
05412 
05413                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05414                 {
05415                         cout<<endl;
05416                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05417                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Sequencing Time = "<<m_d_SequencingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05418                         cout<<endl;
05419                 }
05420                 else
05421                 {
05422                         cout<<endl;
05423                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05424                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05425                         cout<<endl;
05426 
05427                 }
05428 
05429 #endif
05430 
05431                 return(_TRUE);
05432         }
05433 
05434 
05435         //Public Function 1475
05436         int GraphColoring::FileVertexColors()
05437         {
05438                 int i;
05439 
05440                 int i_VertexCount;
05441 
05442                 string s_InputFile, s_OutputFile;
05443 
05444                 string s_ColoringExtension, s_OrderingExtension;
05445 
05446                 string _SLASH("/");
05447 
05448                 ofstream OutputStream;
05449 
05450                 //Determine Ordering Suffix
05451 
05452                 if(m_s_VertexOrderingVariant.compare("NATURAL") == 0)
05453                 {
05454                         s_OrderingExtension = ".N.";
05455                 }
05456                 else
05457                 if(m_s_VertexOrderingVariant.compare("LARGEST_FIRST") == 0)
05458                 {
05459                         s_OrderingExtension = ".LF.";
05460                 }
05461                 else
05462                 if(m_s_VertexOrderingVariant.compare("DISTANCE_TWO_LARGEST_FIRST") == 0)
05463                 {
05464                         s_OrderingExtension = ".D2LF.";
05465                 }
05466                 else
05467                 if(m_s_VertexOrderingVariant.compare("SMALLEST_LAST") == 0)
05468                 {
05469                         s_OrderingExtension = ".SL.";
05470                 }
05471                 else
05472                 if(m_s_VertexOrderingVariant.compare("DISTANCE_TWO_SMALLEST_LAST") == 0)
05473                 {
05474                         s_OrderingExtension = ".D2SL.";
05475                 }
05476                 else
05477                 if(m_s_VertexOrderingVariant.compare("INCIDENCE_DEGREE") == 0)
05478                 {
05479                         s_OrderingExtension = ".ID.";
05480                 }
05481                 else
05482                 if(m_s_VertexOrderingVariant.compare("DISTANCE_TWO_INCIDENCE_DEGREE") == 0)
05483                 {
05484                         s_OrderingExtension = ".D2ID.";
05485                 }
05486                 else
05487                 {
05488                         s_OrderingExtension = ".NONE.";
05489                 }
05490 
05491                 //Determine Coloring Suffix
05492 
05493                 if(m_s_VertexColoringVariant.compare("DISTANCE_ONE") == 0)
05494                 {
05495                         s_ColoringExtension = ".D1.";
05496                 }
05497                 else
05498                 if(m_s_VertexColoringVariant.compare("DISTANCE_TWO") == 0)
05499                 {
05500                         s_ColoringExtension = ".D2.";
05501                 }
05502                 else
05503                 if(m_s_VertexColoringVariant.compare("NAIVE_STAR") == 0)
05504                 {
05505                         s_ColoringExtension = ".NS.";
05506                 }
05507                 else
05508                 if(m_s_VertexColoringVariant.compare("RESTRICTED_STAR") == 0)
05509                 {
05510                         s_ColoringExtension = ".RS.";
05511                 }
05512                 else
05513                 if(m_s_VertexColoringVariant.compare("STAR") == 0)
05514                 {
05515                         s_ColoringExtension = ".S.";
05516                 }
05517                 else
05518                 if(m_s_VertexColoringVariant.compare("ACYCLIC") == 0)
05519                 {
05520                         s_ColoringExtension = ".A.";
05521                 }
05522                 else
05523                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05524                 {
05525                         s_ColoringExtension = ".T.";
05526                 }
05527                 else
05528                 {
05529                         s_ColoringExtension = ".NONE.";
05530                 }
05531 
05532                 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
05533 
05534                 s_InputFile = SlashTokenizer.GetLastToken();
05535 
05536                 s_OutputFile = s_InputFile;
05537                 s_OutputFile += s_OrderingExtension;
05538                 s_OutputFile += s_ColoringExtension;
05539                 s_OutputFile += ".out";
05540 
05541                 OutputStream.open(s_OutputFile.c_str());
05542 
05543                 i_VertexCount = (signed) m_vi_VertexColors.size();
05544 
05545                 OutputStream<<endl;
05546                 OutputStream<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | Vertex Colors | "<<m_s_InputFile<<endl;
05547                 OutputStream<<endl;
05548 
05549                 for(i=0; i<i_VertexCount; i++)
05550                 {
05551                         OutputStream<<"Vertex "<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(m_vi_VertexColors[i])<<endl;
05552                 }
05553 
05554 #if STATISTICS == _TRUE
05555 
05556                 if(m_s_VertexColoringVariant.compare("STAR") == 0)
05557                 {
05558                         OutputStream<<endl;
05559                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Total Stars = "<<m_i_ColoringUnits<<"]"<<endl;
05560                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05561                         OutputStream<<endl;
05562                 }
05563                 else
05564                 if(m_s_VertexColoringVariant.compare("ACYCLIC") == 0)
05565                 {
05566                         OutputStream<<endl;
05567                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Total Sets = "<<m_i_ColoringUnits<<"]"<<endl;
05568                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05569                         OutputStream<<endl;
05570                 }
05571                 else
05572                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05573                 {
05574                         OutputStream<<endl;
05575                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05576                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05577                         OutputStream<<endl;
05578                 }
05579                 else
05580                 {
05581                         OutputStream<<endl;
05582                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05583                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05584                         OutputStream<<endl;
05585                 }
05586 
05587 #endif
05588 
05589 #if STATISTICS == _FALSE
05590 
05591                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05592                 {
05593                         OutputStream<<endl;
05594                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05595                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Sequencing Time = "<<m_d_SequencingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05596                         OutputStream<<endl;
05597                 }
05598                 else
05599                 {
05600                         OutputStream<<endl;
05601                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05602                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05603                         OutputStream<<endl;
05604                 }
05605 
05606 #endif
05607 
05608                 OutputStream.close();
05609 
05610                 return(_TRUE);
05611         }
05612 
05613 
05614 
05615         //Public Function 1476
05616         int GraphColoring::PrintVertexColoringMetrics()
05617         {
05618                 cout<<endl;
05619                 cout<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl;
05620                 cout<<endl;
05621 
05622 #if STATISTICS == _TRUE
05623 
05624                 if(m_s_VertexColoringVariant.compare("STAR") == 0)
05625                 {
05626                         cout<<endl;
05627                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Total Stars = "<<m_i_ColoringUnits<<"]"<<endl;
05628                         cout<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()/2<<"]"<<endl;
05629                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05630                         cout<<endl;
05631                 }
05632                 else
05633                 if(m_s_VertexColoringVariant.compare("ACYCLIC") == 0)
05634                 {
05635                         cout<<endl;
05636                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Total Sets = "<<m_i_ColoringUnits<<"]"<<endl;
05637                         cout<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()/2<<"]"<<endl;
05638                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05639                         cout<<endl;
05640                 }
05641                 else
05642                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05643                 {
05644                         cout<<endl;
05645                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05646                         cout<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()<<"]"<<endl;
05647                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05648                         cout<<endl;
05649                 }
05650                 else
05651                 {
05652                         cout<<endl;
05653                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05654                         cout<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()/2<<"]"<<endl;
05655                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05656                         cout<<endl;
05657                 }
05658 
05659 #endif
05660 
05661 #if STATISTICS == _FALSE
05662 
05663                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05664                 {
05665                         cout<<endl;
05666                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05667                         cout<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()/2<<"]"<<endl;
05668                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Sequencing Time = "<<m_d_SequencingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05669                         cout<<endl;
05670                 }
05671                 else
05672                 {
05673                         cout<<endl;
05674                         cout<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05675                         cout<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()/2<<"]"<<endl;
05676                         cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05677                         cout<<endl;
05678 
05679                 }
05680 
05681 #endif
05682 
05683                 return(_TRUE);
05684 
05685         }
05686 
05687         //Public Function 1477
05688         int GraphColoring::FileVertexColoringMetrics()
05689         {
05690                 string s_InputFile, s_OutputFile;
05691 
05692                 string s_ColoringExtension, s_OrderingExtension;
05693 
05694                 string _SLASH("/");
05695 
05696                 ofstream OutputStream;
05697 
05698                 //Determine Ordering Suffix
05699 
05700                 if(m_s_VertexOrderingVariant.compare("ALL") == 0)
05701                 {
05702                         s_OrderingExtension = ".ALL.";
05703                 }
05704                 else
05705                 if(m_s_VertexOrderingVariant.compare("NATURAL") == 0)
05706                 {
05707                         s_OrderingExtension = ".N.";
05708                 }
05709                 else
05710                 if(m_s_VertexOrderingVariant.compare("LARGEST FIRST") == 0)
05711                 {
05712                         s_OrderingExtension = ".LF.";
05713                 }
05714                 else
05715                 if(m_s_VertexOrderingVariant.compare("DISTANCE TWO LARGEST FIRST") == 0)
05716                 {
05717                         s_OrderingExtension = ".D2LF.";
05718                 }
05719                 else
05720                 if(m_s_VertexOrderingVariant.compare("SMALLEST LAST") == 0)
05721                 {
05722                         s_OrderingExtension = ".SL.";
05723                 }
05724                 else
05725                 if(m_s_VertexOrderingVariant.compare("DISTANCE TWO SMALLEST LAST") == 0)
05726                 {
05727                         s_OrderingExtension = ".D2SL.";
05728                 }
05729                 else
05730                 if(m_s_VertexOrderingVariant.compare("INCIDENCE DEGREE") == 0)
05731                 {
05732                         s_OrderingExtension = ".ID.";
05733                 }
05734                 else
05735                 if(m_s_VertexOrderingVariant.compare("DISTANCE TWO INCIDENCE DEGREE") == 0)
05736                 {
05737                         s_OrderingExtension = ".D2ID.";
05738                 }
05739                 else
05740                 {
05741                         s_OrderingExtension = ".NONE.";
05742                 }
05743 
05744                 //Determine Coloring Suffix
05745 
05746                 if(m_s_VertexColoringVariant.compare("ALL") == 0)
05747                 {
05748                         s_ColoringExtension = ".ALL.";
05749                 }
05750                 else
05751                 if(m_s_VertexColoringVariant.compare("DISTANCE ONE") == 0)
05752                 {
05753                         s_ColoringExtension = ".D1.";
05754                 }
05755                 else
05756                 if(m_s_VertexColoringVariant.compare("DISTANCE TWO") == 0)
05757                 {
05758                         s_ColoringExtension = ".D2.";
05759                 }
05760                 else
05761                 if(m_s_VertexColoringVariant.compare("NAIVE STAR") == 0)
05762                 {
05763                         s_ColoringExtension = ".NS.";
05764                 }
05765                 else
05766                 if(m_s_VertexColoringVariant.compare("RESTRICTED STAR") == 0)
05767                 {
05768                         s_ColoringExtension = ".RS.";
05769                 }
05770                 else
05771                 if(m_s_VertexColoringVariant.compare("STAR") == 0)
05772                 {
05773                         s_ColoringExtension = ".S.";
05774                 }
05775                 else
05776                 if(m_s_VertexColoringVariant.compare("ACYCLIC") == 0)
05777                 {
05778                         s_ColoringExtension = ".A.";
05779                 }
05780                 else
05781                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05782                 {
05783                         s_ColoringExtension = ".T.";
05784                 }
05785                 else
05786                 {
05787                         s_ColoringExtension = ".NONE.";
05788                 }
05789 
05790                 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
05791 
05792                 s_InputFile = SlashTokenizer.GetLastToken();
05793 
05794                 s_OutputFile = s_InputFile;
05795                 s_OutputFile += s_OrderingExtension;
05796                 s_OutputFile += s_ColoringExtension;
05797                 s_OutputFile += ".out";
05798 
05799                 OutputStream.open(s_OutputFile.c_str(), ios::app);
05800 
05801                 OutputStream<<endl;
05802                 OutputStream<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl;
05803                 OutputStream<<endl;
05804 
05805 #if STATISTICS == _TRUE
05806 
05807                 if(m_s_VertexColoringVariant.compare("STAR") == 0)
05808                 {
05809                         OutputStream<<endl;
05810                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Total Stars = "<<m_i_ColoringUnits<<"]"<<endl;
05811                         OutputStream<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()<<"]"<<endl;
05812                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05813                         OutputStream<<endl;
05814                 }
05815                 else
05816                 if(m_s_VertexColoringVariant.compare("ACYCLIC") == 0)
05817                 {
05818                         OutputStream<<endl;
05819                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Total Sets = "<<m_i_ColoringUnits<<"]"<<endl;
05820                         OutputStream<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()<<"]"<<endl;
05821                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05822                         OutputStream<<endl;
05823                 }
05824                 else
05825                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05826                 {
05827                         OutputStream<<endl;
05828                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05829                         OutputStream<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()<<"]"<<endl;
05830                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05831                         OutputStream<<endl;
05832                 }
05833                 else
05834                 {
05835                         OutputStream<<endl;
05836                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05837                         OutputStream<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()<<"]"<<endl;
05838                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05839                         OutputStream<<endl;
05840                 }
05841 
05842 #endif
05843 
05844 #if STATISTICS == _FALSE
05845 
05846                 if(m_s_VertexColoringVariant.compare("TRIANGULAR") == 0)
05847                 {
05848                         OutputStream<<endl;
05849                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05850                         OutputStream<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()<<"]"<<endl;
05851                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Sequencing Time = "<<m_d_SequencingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05852                         OutputStream<<endl;
05853                 }
05854                 else
05855                 {
05856                         OutputStream<<endl;
05857                         OutputStream<<"[Total Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
05858                         OutputStream<<"[Vertex Count = "<<STEP_DOWN(m_vi_Vertices.size())<<"; Edge Count = "<<m_vi_Edges.size()<<"]"<<endl;
05859                         OutputStream<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl;
05860                         OutputStream<<endl;
05861                 }
05862 
05863 #endif
05864 
05865                 OutputStream.close();
05866 
05867                 return(_TRUE);
05868 
05869         }
05870 
05871 
05872         //Public Function 1478
05873         void GraphColoring::PrintVertexColorClasses()
05874         {
05875                 if(CalculateVertexColorClasses() != _TRUE)
05876                 {
05877                         cout<<endl;
05878                         cout<<"Vertex Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<" | Vertex Colors Not Set"<<endl;
05879                         cout<<endl;
05880 
05881                         return;
05882                 }
05883 
05884                 cout<<endl;
05885                 cout<<"Vertex Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl;
05886                 cout<<endl;
05887 
05888                 int i_TotalVertexColors = STEP_UP(m_i_VertexColorCount);
05889 
05890                 for(int i = 0; i < i_TotalVertexColors; i++)
05891                 {
05892                         if(m_vi_VertexColorFrequency[i] <= 0)
05893                         {
05894                                 continue;
05895                         }
05896 
05897                         cout<<"Color "<<STEP_UP(i)<<" : "<<m_vi_VertexColorFrequency[i]<<endl;
05898                 }
05899 
05900                 cout<<endl;
05901                 cout<<"[Largest Color Class : "<<STEP_UP(m_i_LargestColorClass)<<"; Largest Color Class Size : "<<m_i_LargestColorClassSize<<"]"<<endl;
05902                 cout<<"[Smallest Color Class : "<<STEP_UP(m_i_SmallestColorClass)<<"; Smallest Color Class Size : "<<m_i_SmallestColorClassSize<<"]"<<endl;
05903                 cout<<"[Average Color Class Size : "<<m_d_AverageColorClassSize<<"]"<<endl;
05904                 cout<<endl;
05905 
05906                 return;
05907         }
05908 
05909         double** GraphColoring::GetSeedMatrix(int* i_SeedRowCount, int* i_SeedColumnCount) {
05910 
05911                 if(seed_available) Seed_reset();
05912 
05913                 dp2_Seed = GetSeedMatrix_unmanaged(i_SeedRowCount, i_SeedColumnCount);
05914                 i_seed_rowCount = *i_SeedRowCount;
05915                 seed_available = true;
05916 
05917                 return dp2_Seed;
05918         }
05919 
05920         double** GraphColoring::GetSeedMatrix_unmanaged(int* i_SeedRowCount, int* i_SeedColumnCount) {
05921 
05922                 int i_size = m_vi_VertexColors.size();
05923                 int i_num_of_colors = m_i_VertexColorCount + 1;
05924                 (*i_SeedRowCount) = i_size;
05925                 (*i_SeedColumnCount) = i_num_of_colors;
05926                 if(i_num_of_colors == 0 || i_size == 0) {return NULL;}
05927                 double** Seed = new double*[i_size];
05928 
05929                 // allocate and initialize Seed matrix
05930                 for (int i=0; i<i_size; i++) {
05931                         Seed[i] = new double[i_num_of_colors];
05932                         for(int j=0; j<i_num_of_colors; j++) Seed[i][j]=0.;
05933                 }
05934 
05935                 // populate Seed matrix
05936                 for (int i=0; i < i_size; i++) {
05937                         Seed[i][m_vi_VertexColors[i]] = 1.;
05938                 }
05939 
05940                 return Seed;
05941         }
05942 
05943         void GraphColoring::Seed_init() {
05944                 seed_available = false;
05945 
05946                 i_seed_rowCount = 0;
05947                 dp2_Seed = NULL;
05948         }
05949 
05950         void GraphColoring::Seed_reset() {
05951                 if(seed_available) {
05952                         seed_available = false;
05953 
05954                         free_2DMatrix(dp2_Seed, i_seed_rowCount);
05955                         dp2_Seed = NULL;
05956                         i_seed_rowCount = 0;
05957                 }
05958         }
05959 
05960 
05961         int GraphColoring::CheckQuickDistanceTwoColoring(int Verbose)
05962         {
05963                 if (m_i_MaximumVertexDegree <= STEP_UP(m_i_VertexColorCount)) return 0;
05964 
05965                 // If the code reaches this place, DistanceTwoColoring() must have run INcorrectly.
05966                 // Find the 2 vertices within distance-2 have the same color
05967                 if (Verbose < 1) return 1;
05968 
05969                 //First, if the vertex with Maximum Degree, i.e. the max number of vertices that a vertex connects to
05970                 int i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
05971                 int i_VertexWithMaxDegree = -1;
05972                 int i_MaximumVertexDegree = -1;
05973                 int i_VertexDegree = -1;
05974 
05975                 for (int i = 0; i < i_VertexCount; i++)
05976                 {
05977                         i_VertexDegree = m_vi_Vertices[i + 1] - m_vi_Vertices[i];
05978 
05979                         if(i_MaximumVertexDegree < i_VertexDegree)
05980                         {
05981                                 i_MaximumVertexDegree = i_VertexDegree;
05982                                 i_VertexWithMaxDegree = i;
05983                         }
05984                 }
05985 
05986                 cout<<"VertexWithMaxDegree = "<< i_VertexWithMaxDegree <<"; MaximumVertexDegree = "<< i_MaximumVertexDegree <<endl;
05987                 if (Verbose < 2) return 1;
05988 
05989                 for (int i = m_vi_Vertices[i_VertexWithMaxDegree]; i < m_vi_Vertices[i_VertexWithMaxDegree + 1] - 1; i++) {
05990                         //printf("\t*i = %d \n",i);
05991                         for (int j = i + 1; j < m_vi_Vertices[i_VertexWithMaxDegree + 1]; j++) {
05992                                 if (m_vi_VertexColors[m_vi_Edges[i]] == m_vi_VertexColors[m_vi_Edges[j]])
05993                                         printf("\t m_vi_VertexColors[m_vi_Edges[i(%d)](%d)](%d) == m_vi_VertexColors[m_vi_Edges[j(%d)](%d)](%d)\n", i, m_vi_Edges[i], m_vi_VertexColors[m_vi_Edges[i]], j, m_vi_Edges[j], m_vi_VertexColors[m_vi_Edges[j]]);
05994                         }
05995                 }
05996 
05997                 return 1;
05998         }
05999 
06000         int GraphColoring::CheckDistanceTwoColoring(int Verbose) {
06001                 //int i = 0;
06002                 int j = 0, k = 0;
06003                 int i_PresentVertex, i_DistanceOneVertex, i_DistanceTwoVertex;
06004                 int i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
06005 
06006                 for(i_PresentVertex=0; i_PresentVertex<i_VertexCount; i_PresentVertex++)
06007                 {
06008 
06009                         //For each Distance-One Vertex, do ...
06010                         for(j=m_vi_Vertices[i_PresentVertex]; j<m_vi_Vertices[STEP_UP(i_PresentVertex)]; j++)
06011                         {
06012                                 i_DistanceOneVertex = m_vi_Edges[j];
06013                                 if(m_vi_VertexColors[i_PresentVertex] == m_vi_VertexColors[i_DistanceOneVertex]) {
06014                                         //Violate the requirement for DistanceTwoColoring(). Print error
06015                                         if (Verbose < 1) return 1;
06016                                         printf("D1 VIOLATION. m_vi_VertexColors[i_PresentVertex(%d)](%d) == m_vi_VertexColors[i_DistanceOneVertex(%d)](%d) \n", i_PresentVertex, m_vi_VertexColors[i_PresentVertex], i_DistanceOneVertex, m_vi_VertexColors[i_DistanceOneVertex]);
06017                                         if (Verbose < 2) return 1;
06018                                 }
06019 
06020                                 //For each Distance-Two Vertex, do ...
06021                                 for(k=m_vi_Vertices[i_DistanceOneVertex]; k<m_vi_Vertices[STEP_UP(i_DistanceOneVertex)]; k++)
06022                                 {
06023                                         i_DistanceTwoVertex = m_vi_Edges[k];
06024 
06025                                         if(i_DistanceTwoVertex == i_PresentVertex) continue; //We don't want to make a loop. Ignore this case
06026 
06027                                         if(m_vi_VertexColors[i_PresentVertex] == m_vi_VertexColors[i_DistanceTwoVertex]) {
06028                                                 //Violate the requirement for DistanceTwoColoring(). Print error
06029                                                 if (Verbose < 1) return 1;
06030                                                 printf("D2 VIOLATION. m_vi_VertexColors[i_PresentVertex(%d)](%d) == m_vi_VertexColors[i_DistanceTwoVertex(%d)](%d) \n", i_PresentVertex, m_vi_VertexColors[i_PresentVertex], i_DistanceTwoVertex, m_vi_VertexColors[i_DistanceTwoVertex]);
06031                                                 printf("\t i_PresentVertex(%d) and i_DistanceTwoVertex(%d) connected through i_DistanceOneVertex(%d) \n", i_PresentVertex, i_DistanceTwoVertex, i_DistanceOneVertex);
06032                                                 if (Verbose < 2) return 1;
06033                                         }
06034                                 }
06035                         }
06036                 }
06037                 return 0;
06038         }
06039 
06040         void GraphColoring::SetStringVertexColoringVariant(string s)
06041         {
06042                 m_s_VertexColoringVariant = s;
06043         }
06044 
06045         void GraphColoring::SetVertexColorCount(int i_VertexColorCount)
06046         {
06047                 m_i_VertexColorCount = i_VertexColorCount;
06048         }
06049 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines