ColPack
|
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 }