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. 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 3501 00028 void BipartiteGraphBicoloring::PresetCoveredVertexColors() 00029 { 00030 int i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 00031 int i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 00032 00033 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = m_i_VertexColorCount = _UNKNOWN; 00034 00035 m_vi_LeftVertexColors.clear(); 00036 m_vi_LeftVertexColors.resize((unsigned) i_LeftVertexCount, _FALSE); 00037 00038 m_vi_RightVertexColors.clear(); 00039 m_vi_RightVertexColors.resize((unsigned) i_RightVertexCount, _FALSE); 00040 00041 int i_CoveredLeftVertexCount = m_vi_CoveredLeftVertices.size(); 00042 int i_CoveredRightVertexCount = m_vi_CoveredRightVertices.size(); 00043 00044 for(int i=0; i<i_CoveredLeftVertexCount; i++) 00045 { 00046 m_vi_LeftVertexColors[m_vi_CoveredLeftVertices[i]] = _UNKNOWN; 00047 } 00048 00049 for(int i=0; i<i_CoveredRightVertexCount; i++) 00050 { 00051 m_vi_RightVertexColors[m_vi_CoveredRightVertices[i]] = _UNKNOWN; 00052 } 00053 00054 return; 00055 } 00056 00057 00058 00059 //Private Function 3506 00060 int BipartiteGraphBicoloring::CheckVertexColoring(string s_VertexColoringVariant) 00061 { 00062 if(m_s_VertexColoringVariant.compare(s_VertexColoringVariant) == 0) 00063 { 00064 return(_TRUE); 00065 } 00066 00067 if(m_s_VertexColoringVariant.compare("ALL") != 0) 00068 { 00069 m_s_VertexColoringVariant = s_VertexColoringVariant; 00070 } 00071 00072 if(m_s_VertexOrderingVariant.empty()) 00073 { 00074 NaturalOrdering(); 00075 } 00076 00077 return(_FALSE); 00078 } 00079 00080 00081 //Private Function 3507 00082 int BipartiteGraphBicoloring::CalculateVertexColorClasses() 00083 { 00084 if(m_s_VertexColoringVariant.empty()) 00085 { 00086 return(_FALSE); 00087 } 00088 00089 m_vi_LeftVertexColorFrequency.clear(); 00090 m_vi_LeftVertexColorFrequency.resize((unsigned) m_i_LeftVertexColorCount, _FALSE); 00091 00092 int i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 00093 00094 for(int i = 0; i < i_LeftVertexCount; i++) 00095 { 00096 m_vi_LeftVertexColorFrequency[m_vi_LeftVertexColors[i]]++; 00097 } 00098 00099 for(int i = 0; i < m_i_LeftVertexColorCount; i++) 00100 { 00101 if(m_i_LargestLeftVertexColorClassSize < m_vi_LeftVertexColorFrequency[i]) 00102 { 00103 m_i_LargestLeftVertexColorClass = i; 00104 00105 m_i_LargestLeftVertexColorClassSize = m_vi_LeftVertexColorFrequency[i]; 00106 } 00107 00108 if(m_i_SmallestLeftVertexColorClassSize == _UNKNOWN) 00109 { 00110 m_i_SmallestLeftVertexColorClass = i; 00111 00112 m_i_SmallestLeftVertexColorClassSize = m_vi_LeftVertexColorFrequency[i]; 00113 } 00114 else 00115 if(m_i_SmallestLeftVertexColorClassSize > m_vi_LeftVertexColorFrequency[i]) 00116 { 00117 m_i_SmallestLeftVertexColorClass = i; 00118 00119 m_i_SmallestLeftVertexColorClassSize = m_vi_LeftVertexColorFrequency[i]; 00120 } 00121 } 00122 00123 m_vi_RightVertexColorFrequency.clear(); 00124 m_vi_RightVertexColorFrequency.resize((unsigned) m_i_RightVertexColorCount, _FALSE); 00125 00126 int i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 00127 00128 for(int i = 0; i < i_RightVertexCount; i++) 00129 { 00130 m_vi_RightVertexColorFrequency[m_vi_RightVertexColors[i]]++; 00131 } 00132 00133 for(int i = 0; i < m_i_RightVertexColorCount; i++) 00134 { 00135 if(m_i_LargestRightVertexColorClassSize < m_vi_RightVertexColorFrequency[i]) 00136 { 00137 m_i_LargestRightVertexColorClass = i; 00138 00139 m_i_LargestRightVertexColorClassSize = m_vi_RightVertexColorFrequency[i]; 00140 } 00141 00142 if(m_i_SmallestRightVertexColorClassSize == _UNKNOWN) 00143 { 00144 m_i_SmallestRightVertexColorClass = i; 00145 00146 m_i_SmallestRightVertexColorClassSize = m_vi_RightVertexColorFrequency[i]; 00147 } 00148 else 00149 if(m_i_SmallestRightVertexColorClassSize > m_vi_RightVertexColorFrequency[i]) 00150 { 00151 m_i_SmallestRightVertexColorClass = i; 00152 00153 m_i_SmallestRightVertexColorClassSize = m_vi_RightVertexColorFrequency[i]; 00154 } 00155 } 00156 00157 m_i_LargestVertexColorClassSize = m_i_LargestLeftVertexColorClassSize>m_i_LargestRightVertexColorClassSize?m_i_LargestLeftVertexColorClassSize:m_i_LargestRightVertexColorClassSize; 00158 m_i_LargestVertexColorClass = m_i_LargestVertexColorClassSize==m_i_LargestLeftVertexColorClassSize?m_i_LargestLeftVertexColorClass:m_i_LargestRightVertexColorClass; 00159 00160 m_i_SmallestVertexColorClassSize = m_i_SmallestLeftVertexColorClassSize<m_i_SmallestRightVertexColorClassSize?m_i_SmallestLeftVertexColorClassSize:m_i_SmallestRightVertexColorClassSize; 00161 m_i_SmallestVertexColorClass = m_i_SmallestVertexColorClassSize==m_i_SmallestLeftVertexColorClassSize?m_i_SmallestLeftVertexColorClass:m_i_SmallestRightVertexColorClass; 00162 00163 m_d_AverageLeftVertexColorClassSize = i_LeftVertexCount / m_i_LeftVertexColorCount; 00164 m_d_AverageRightVertexColorClassSize = i_RightVertexCount / m_i_RightVertexColorCount; 00165 m_d_AverageVertexColorClassSize = (i_LeftVertexCount + i_RightVertexCount) / m_i_VertexColorCount; 00166 00167 return(_TRUE); 00168 } 00169 00170 00171 //Private Function 3508 00172 int BipartiteGraphBicoloring::FixMinimalCoverStarBicoloring() 00173 { 00174 int i, j, k, l, m, n; 00175 00176 int i_FirstColor, i_SecondColor, i_ThirdColor, i_FourthColor; 00177 00178 int i_ColorViolationCount, i_PathViolationCount, i_TotalViolationCount; 00179 00180 vector<int> vi_CandidateColors, vi_VertexColors; 00181 00182 int i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 00183 int i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 00184 00185 int i_LeftVertexCoverSize = (signed) m_vi_CoveredLeftVertices.size(); 00186 int i_RightVertexCoverSize = (signed) m_vi_CoveredRightVertices.size(); 00187 00188 m_i_VertexColorCount = STEP_UP(i_LeftVertexCoverSize) + STEP_UP(i_RightVertexCoverSize); 00189 00190 vi_VertexColors.clear(); 00191 vi_VertexColors.resize((unsigned) i_LeftVertexCount + i_RightVertexCount, _FALSE); 00192 00193 vi_CandidateColors.clear(); 00194 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 00195 00196 i_ColorViolationCount = _FALSE; 00197 00198 for(i=0; i<i_LeftVertexCount; i++) 00199 { 00200 vi_VertexColors[m_vi_LeftVertexColors[i]] = _TRUE; 00201 } 00202 00203 for(i=0; i<i_RightVertexCount; i++) 00204 { 00205 if(vi_VertexColors[m_vi_RightVertexColors[i]] == _TRUE) 00206 { 00207 i_ColorViolationCount++; 00208 00209 #if DEBUG == 3508 00210 00211 cout<<"Color Violation "<<i_ColorViolationCount<<" | Right Vertex "<<STEP_UP(i)<<" | Conflicting Color "<<m_vi_RightVertexColors[i]<<endl; 00212 00213 #endif 00214 00215 for(j=m_vi_RightVertices[i]; j<m_vi_RightVertices[STEP_UP(i)]; j++) 00216 { 00217 for(k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[STEP_UP(m_vi_Edges[j])]; k++) 00218 { 00219 if(m_vi_Edges[k] == i) 00220 { 00221 continue; 00222 } 00223 00224 vi_CandidateColors[m_vi_RightVertexColors[m_vi_Edges[k]]] = i; 00225 } 00226 } 00227 00228 for(j=STEP_UP(i_LeftVertexCoverSize); j<m_i_VertexColorCount; j++) 00229 { 00230 if(vi_CandidateColors[j] != i) 00231 { 00232 m_vi_RightVertexColors[i] = j; 00233 00234 if(m_i_RightVertexColorCount < j) 00235 { 00236 m_i_RightVertexColorCount = j; 00237 } 00238 00239 break; 00240 } 00241 } 00242 00243 #if DEBUG == 3508 00244 00245 cout<<"Fixed Color Violation "<<i_ColorViolationCount<<" | Right Vertex "<<STEP_UP(i)<<" | Changed Right Vertex Color "<<m_vi_RightVertexColors[i]<<endl; 00246 00247 #endif 00248 00249 } 00250 } 00251 00252 i_PathViolationCount = _FALSE; 00253 00254 for(i=0; i<i_LeftVertexCount; i++) 00255 { 00256 i_FirstColor = m_vi_LeftVertexColors[i]; 00257 00258 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 00259 { 00260 i_SecondColor = m_vi_RightVertexColors[m_vi_Edges[j]]; 00261 00262 for(k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[STEP_UP(m_vi_Edges[j])]; k++) 00263 { 00264 if(m_vi_Edges[k] == i) 00265 { 00266 continue; 00267 } 00268 00269 i_ThirdColor = m_vi_LeftVertexColors[m_vi_Edges[k]]; 00270 00271 if(i_ThirdColor == i_FirstColor) 00272 { 00273 for(l=m_vi_LeftVertices[m_vi_Edges[k]]; l<m_vi_LeftVertices[STEP_UP(m_vi_Edges[k])]; l++) 00274 { 00275 if(m_vi_Edges[l] == m_vi_Edges[j]) 00276 { 00277 continue; 00278 } 00279 00280 i_FourthColor = m_vi_RightVertexColors[m_vi_Edges[l]]; 00281 00282 if(i_FourthColor == i_SecondColor) 00283 { 00284 i_PathViolationCount++; 00285 00286 #if DEBUG == 3508 00287 00288 cout<<"Path Violation "<<i_PathViolationCount<<" | "<<STEP_UP(i)<<" ["<<i_FirstColor<<"] - "<<STEP_UP(m_vi_Edges[j])<<" ["<<i_SecondColor<<"] - "<<STEP_UP(m_vi_Edges[k])<<" ["<<i_ThirdColor<<"] - "<<STEP_UP(m_vi_Edges[l])<<" ["<<i_FourthColor<<"]"<<endl; 00289 00290 #endif 00291 00292 for(m=m_vi_RightVertices[m_vi_Edges[l]]; m<m_vi_RightVertices[STEP_UP(m_vi_Edges[l])]; m++) 00293 { 00294 for(n=m_vi_LeftVertices[m_vi_Edges[m]]; n<m_vi_LeftVertices[STEP_UP(m_vi_Edges[m])]; n++) 00295 { 00296 if(m_vi_Edges[n] == m_vi_Edges[l]) 00297 { 00298 continue; 00299 } 00300 00301 vi_CandidateColors[m_vi_RightVertexColors[m_vi_Edges[n]]] = m_vi_Edges[l]; 00302 } 00303 } 00304 00305 for(m=STEP_UP(i_LeftVertexCoverSize); m<m_i_VertexColorCount; m++) 00306 { 00307 if(vi_CandidateColors[m] != m_vi_Edges[l]) 00308 { 00309 m_vi_RightVertexColors[m_vi_Edges[l]] = m; 00310 00311 if(m_i_RightVertexColorCount < m) 00312 { 00313 m_i_RightVertexColorCount = m; 00314 } 00315 00316 break; 00317 } 00318 } 00319 00320 #if DEBUG == 3508 00321 00322 cout<<"Fixed Path Violation "<<i_PathViolationCount<<" | "<<STEP_UP(i)<<" ["<<i_FirstColor<<"] - "<<STEP_UP(m_vi_Edges[j])<<" ["<<i_SecondColor<<"] - "<<STEP_UP(m_vi_Edges[k])<<" ["<<i_ThirdColor<<"] - "<<STEP_UP(m_vi_Edges[l])<<" ["<<m_vi_RightVertexColors[m_vi_Edges[l]]<<"]"<<endl; 00323 00324 #endif 00325 00326 } 00327 } 00328 } 00329 } 00330 } 00331 } 00332 00333 i_TotalViolationCount = i_ColorViolationCount + i_PathViolationCount; 00334 00335 #if _DEBUG == 3508 00336 00337 if(i_TotalViolationCount) 00338 { 00339 cout<<endl; 00340 cout<<"[Total Violations = "<<i_TotalViolationCount<<"]"<<endl; 00341 cout<<endl; 00342 } 00343 00344 #endif 00345 00346 return(i_TotalViolationCount); 00347 } 00348 00349 00350 00351 //Public Constructor 3551 00352 BipartiteGraphBicoloring::BipartiteGraphBicoloring() 00353 { 00354 Clear(); 00355 00356 Seed_init(); 00357 } 00358 00359 00360 //Public Destructor 3552 00361 BipartiteGraphBicoloring::~BipartiteGraphBicoloring() 00362 { 00363 Clear(); 00364 00365 Seed_reset(); 00366 } 00367 00368 void BipartiteGraphBicoloring::Seed_init() { 00369 lseed_available = false; 00370 i_lseed_rowCount = 0; 00371 dp2_lSeed = NULL; 00372 00373 rseed_available = false; 00374 i_rseed_rowCount = 0; 00375 dp2_rSeed = NULL; 00376 } 00377 00378 void BipartiteGraphBicoloring::Seed_reset() { 00379 if(lseed_available) { 00380 lseed_available = false; 00381 00382 if(i_lseed_rowCount>0) { 00383 free_2DMatrix(dp2_lSeed, i_lseed_rowCount); 00384 } 00385 else { 00386 cerr<<"ERR: freeing left seed matrix with 0 row"<<endl; 00387 exit(-1); 00388 } 00389 dp2_lSeed = NULL; 00390 i_lseed_rowCount = 0; 00391 } 00392 00393 if(rseed_available) { 00394 rseed_available = false; 00395 00396 if(i_rseed_rowCount>0) { 00397 free_2DMatrix(dp2_rSeed, i_rseed_rowCount); 00398 } 00399 else { 00400 cerr<<"ERR: freeing right seed matrix with 0 row"<<endl; 00401 exit(-1); 00402 } 00403 dp2_rSeed = NULL; 00404 i_rseed_rowCount = 0; 00405 } 00406 } 00407 00408 00409 //Virtual Function 3553 00410 void BipartiteGraphBicoloring::Clear() 00411 { 00412 BipartiteGraphOrdering::Clear(); 00413 00414 //m_i_ColoringUnits = _UNKNOWN; 00415 00416 m_i_LeftVertexColorCount = _UNKNOWN; 00417 m_i_RightVertexColorCount = _UNKNOWN; 00418 00419 m_i_VertexColorCount = _UNKNOWN; 00420 00421 m_i_ViolationCount = _UNKNOWN; 00422 00423 m_i_LargestLeftVertexColorClass = _UNKNOWN; 00424 m_i_LargestRightVertexColorClass = _UNKNOWN; 00425 00426 m_i_LargestLeftVertexColorClassSize = _UNKNOWN; 00427 m_i_LargestRightVertexColorClassSize = _UNKNOWN; 00428 00429 m_i_SmallestLeftVertexColorClass = _UNKNOWN; 00430 m_i_SmallestRightVertexColorClass = _UNKNOWN; 00431 00432 m_i_SmallestLeftVertexColorClassSize = _UNKNOWN; 00433 m_i_SmallestRightVertexColorClassSize = _UNKNOWN; 00434 00435 m_i_LargestVertexColorClass = _UNKNOWN; 00436 m_i_SmallestVertexColorClass = _UNKNOWN; 00437 00438 m_i_LargestVertexColorClassSize = _UNKNOWN; 00439 m_i_SmallestVertexColorClassSize = _UNKNOWN; 00440 00441 m_d_AverageLeftVertexColorClassSize = _UNKNOWN; 00442 m_d_AverageRightVertexColorClassSize = _UNKNOWN; 00443 m_d_AverageVertexColorClassSize = _UNKNOWN; 00444 00445 m_d_ColoringTime = _UNKNOWN; 00446 m_d_CheckingTime = _UNKNOWN; 00447 00448 m_s_VertexColoringVariant.clear(); 00449 00450 m_vi_LeftVertexColors.clear(); 00451 m_vi_RightVertexColors.clear(); 00452 00453 m_vi_LeftVertexColorFrequency.clear(); 00454 m_vi_RightVertexColorFrequency.clear(); 00455 00456 return; 00457 } 00458 00459 00460 //Virtual Function 3554 00461 void BipartiteGraphBicoloring::Reset() 00462 { 00463 BipartiteGraphOrdering::Reset(); 00464 00465 //m_i_ColoringUnits = _UNKNOWN; 00466 00467 m_i_LeftVertexColorCount = _UNKNOWN; 00468 m_i_RightVertexColorCount = _UNKNOWN; 00469 00470 m_i_VertexColorCount = _UNKNOWN; 00471 00472 m_i_ViolationCount = _UNKNOWN; 00473 00474 m_i_LargestLeftVertexColorClass = _UNKNOWN; 00475 m_i_LargestRightVertexColorClass = _UNKNOWN; 00476 00477 m_i_LargestLeftVertexColorClassSize = _UNKNOWN; 00478 m_i_LargestRightVertexColorClassSize = _UNKNOWN; 00479 00480 m_i_SmallestLeftVertexColorClass = _UNKNOWN; 00481 m_i_SmallestRightVertexColorClass = _UNKNOWN; 00482 00483 m_i_SmallestLeftVertexColorClassSize = _UNKNOWN; 00484 m_i_SmallestRightVertexColorClassSize = _UNKNOWN; 00485 00486 m_i_LargestVertexColorClass = _UNKNOWN; 00487 m_i_SmallestVertexColorClass = _UNKNOWN; 00488 00489 m_i_LargestVertexColorClassSize = _UNKNOWN; 00490 m_i_SmallestVertexColorClassSize = _UNKNOWN; 00491 00492 m_d_AverageLeftVertexColorClassSize = _UNKNOWN; 00493 m_d_AverageRightVertexColorClassSize = _UNKNOWN; 00494 m_d_AverageVertexColorClassSize = _UNKNOWN; 00495 00496 m_d_ColoringTime = _UNKNOWN; 00497 m_d_CheckingTime = _UNKNOWN; 00498 00499 m_s_VertexColoringVariant.clear(); 00500 00501 m_vi_LeftVertexColors.clear(); 00502 m_vi_RightVertexColors.clear(); 00503 00504 m_vi_LeftVertexColorFrequency.clear(); 00505 m_vi_RightVertexColorFrequency.clear(); 00506 00507 return; 00508 } 00509 00510 00511 //Public Function 3556 00512 int BipartiteGraphBicoloring::MinimalCoveringRowMajorStarBicoloring() 00513 { 00514 if(CheckVertexColoring("MINIMAL_COVER_ROW_STAR")) 00515 { 00516 return(_TRUE); 00517 } 00518 00519 int i, j, k; 00520 00521 int _FOUND; 00522 00523 int i_ColorID, i_StarID; 00524 00525 int i_EdgeCount; 00526 00527 int i_FirstNeighborOne, i_FirstNeighborTwo; 00528 00529 int i_LeftVertexCount, i_RightVertexCount; 00530 00531 int i_LargerVertexCount; 00532 00533 int i_LeftVertexCoverSize, i_RightVertexCoverSize; 00534 00535 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex; 00536 00537 vector<int> vi_CandidateColors; 00538 00539 vector<int> vi_EdgeStarMap, vi_LeftStarHubMap, vi_RightStarHubMap; 00540 00541 vector<int> vi_FirstTreated; 00542 00543 vector<int> vi_FirstNeighborOne, vi_FirstNeighborTwo; 00544 00545 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 00546 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 00547 00548 i_LargerVertexCount = i_LeftVertexCount>i_RightVertexCount?i_LeftVertexCount:i_RightVertexCount; 00549 00550 i_EdgeCount = (signed) m_vi_Edges.size()/2; 00551 00552 vi_EdgeStarMap.clear(); 00553 vi_EdgeStarMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 00554 00555 m_mimi2_VertexEdgeMap.clear(); 00556 00557 k=_FALSE; 00558 00559 for(i=0; i<i_LeftVertexCount; i++) 00560 { 00561 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 00562 { 00563 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k; 00564 00565 vi_EdgeStarMap[k] = k; 00566 00567 k++; 00568 } 00569 } 00570 00571 Timer m_T_Timer; 00572 00573 m_T_Timer.Start(); 00574 00575 CoverMinimalVertex(); 00576 00577 m_T_Timer.Stop(); 00578 00579 m_d_CoveringTime = m_T_Timer.GetWallTime(); 00580 00581 PresetCoveredVertexColors(); 00582 00583 #if DEBUG == 3556 00584 00585 cout<<"DEBUG 3556 | Left Star Bicoloring | Left Vertex Cover Size = "<<m_vi_CoveredLeftVertices.size()<<"; Right Vertex Cover Size = "<<m_vi_CoveredRightVertices.size()<<endl; 00586 00587 #endif 00588 00589 #if DEBUG == 3556 00590 00591 cout<<endl; 00592 cout<<"DEBUG 3556 | Left Star Bicoloring | Initial Vertex Colors | Left Vertices"<<endl; 00593 cout<<endl; 00594 00595 for(i=0; i<i_LeftVertexCount; i++) 00596 { 00597 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 00598 } 00599 00600 cout<<endl; 00601 cout<<"DEBUG 3556 | Left Star Bicoloring | Initial Vertex Colors | Right Vertices"<<endl; 00602 cout<<endl; 00603 00604 for(i=0; i<i_RightVertexCount; i++) 00605 { 00606 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 00607 } 00608 00609 #endif 00610 00611 i_LeftVertexCoverSize = (signed) m_vi_CoveredLeftVertices.size(); 00612 i_RightVertexCoverSize = (signed) m_vi_CoveredRightVertices.size(); 00613 00614 m_i_VertexColorCount = STEP_UP(i_LeftVertexCoverSize + i_RightVertexCoverSize); 00615 00616 vi_CandidateColors.clear(); 00617 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 00618 00619 vi_LeftStarHubMap.clear(); 00620 vi_LeftStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 00621 00622 vi_RightStarHubMap.clear(); 00623 vi_RightStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 00624 00625 vi_FirstNeighborOne.clear(); 00626 vi_FirstNeighborOne.resize((unsigned) i_LargerVertexCount, _UNKNOWN); 00627 00628 vi_FirstNeighborTwo.clear(); 00629 vi_FirstNeighborTwo.resize((unsigned) i_LargerVertexCount, _UNKNOWN); 00630 00631 vi_FirstTreated.clear(); 00632 vi_FirstTreated.resize((unsigned) i_LargerVertexCount, _UNKNOWN); 00633 00634 m_i_LeftVertexColorCount = _UNKNOWN; 00635 00636 for(i=0; i<i_LeftVertexCoverSize; i++) 00637 { 00638 i_PresentVertex = m_vi_CoveredLeftVertices[i]; 00639 00640 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 00641 { 00642 i_NeighboringVertex = m_vi_Edges[j]; 00643 00644 if(m_vi_RightVertexColors[i_NeighboringVertex] == _FALSE) 00645 { 00646 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 00647 { 00648 i_SecondNeighboringVertex = m_vi_Edges[k]; 00649 00650 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] > _FALSE) 00651 { 00652 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 00653 } 00654 } 00655 } 00656 } 00657 00658 for(j=_TRUE; j<STEP_UP(i_LeftVertexCoverSize); j++) 00659 { 00660 if(vi_CandidateColors[j] != i_PresentVertex) 00661 { 00662 m_vi_LeftVertexColors[i_PresentVertex] = j; 00663 00664 if(m_i_LeftVertexColorCount < j) 00665 { 00666 m_i_LeftVertexColorCount = j; 00667 } 00668 00669 break; 00670 } 00671 } 00672 } 00673 00674 m_i_RightVertexColorCount = _UNKNOWN; 00675 00676 for(i=0; i<i_RightVertexCoverSize; i++) 00677 { 00678 i_PresentVertex = m_vi_CoveredRightVertices[i]; 00679 00680 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 00681 { 00682 i_NeighboringVertex = m_vi_Edges[j]; 00683 00684 i_ColorID = m_vi_LeftVertexColors[i_NeighboringVertex]; 00685 00686 if(i_ColorID == _UNKNOWN) 00687 { 00688 continue; 00689 } 00690 00691 if(i_ColorID == _FALSE) 00692 { 00693 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 00694 { 00695 i_SecondNeighboringVertex = m_vi_Edges[k]; 00696 00697 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 00698 { 00699 continue; 00700 } 00701 00702 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] != _FALSE) 00703 { 00704 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 00705 } 00706 } 00707 } 00708 else 00709 { 00710 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 00711 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 00712 00713 if(i_FirstNeighborOne == i_PresentVertex) 00714 { 00715 if(vi_FirstTreated[i_FirstNeighborTwo] != i_PresentVertex) 00716 { 00717 for(k=m_vi_LeftVertices[i_FirstNeighborTwo]; k<m_vi_LeftVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 00718 { 00719 if(m_vi_Edges[k] == i_PresentVertex) 00720 { 00721 continue; 00722 } 00723 00724 if(m_vi_RightVertexColors[m_vi_Edges[k]] == _UNKNOWN) 00725 { 00726 continue; 00727 } 00728 00729 vi_CandidateColors[m_vi_RightVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 00730 } 00731 00732 vi_FirstTreated[i_FirstNeighborTwo] = i_PresentVertex; 00733 } 00734 00735 for(k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[STEP_UP(m_vi_Edges[j])]; k++) 00736 { 00737 if(m_vi_Edges[k] == i_PresentVertex) 00738 { 00739 continue; 00740 } 00741 00742 if(m_vi_RightVertexColors[m_vi_Edges[k]] == _UNKNOWN) 00743 { 00744 continue; 00745 } 00746 00747 vi_CandidateColors[m_vi_RightVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 00748 00749 } 00750 00751 vi_FirstTreated[i_NeighboringVertex] = i_PresentVertex; 00752 } 00753 else 00754 { 00755 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 00756 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 00757 00758 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 00759 { 00760 i_SecondNeighboringVertex = m_vi_Edges[k]; 00761 00762 if(i_SecondNeighboringVertex == i_PresentVertex) 00763 { 00764 continue; 00765 } 00766 00767 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 00768 { 00769 continue; 00770 } 00771 00772 if(vi_RightStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]] == i_SecondNeighboringVertex) 00773 { 00774 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 00775 00776 } 00777 } 00778 } 00779 } 00780 } 00781 00782 for(j=STEP_UP(i_LeftVertexCoverSize); j<m_i_VertexColorCount; j++) 00783 { 00784 if(vi_CandidateColors[j] != i_PresentVertex) 00785 { 00786 m_vi_RightVertexColors[i_PresentVertex] = j; 00787 00788 if(m_i_RightVertexColorCount < j) 00789 { 00790 m_i_RightVertexColorCount = j; 00791 } 00792 00793 break; 00794 } 00795 } 00796 00797 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 00798 { 00799 _FOUND = _FALSE; 00800 00801 i_NeighboringVertex = m_vi_Edges[j]; 00802 00803 if(m_vi_LeftVertexColors[i_NeighboringVertex] == _UNKNOWN) 00804 { 00805 continue; 00806 } 00807 00808 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 00809 { 00810 i_SecondNeighboringVertex = m_vi_Edges[k]; 00811 00812 if(i_SecondNeighboringVertex == i_PresentVertex) 00813 { 00814 continue; 00815 } 00816 00817 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 00818 { 00819 continue; 00820 } 00821 00822 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == m_vi_RightVertexColors[i_PresentVertex]) 00823 { 00824 _FOUND = _TRUE; 00825 00826 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]; 00827 00828 vi_LeftStarHubMap[i_StarID] = i_NeighboringVertex; 00829 00830 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 00831 00832 break; 00833 } 00834 } 00835 00836 if (!_FOUND) 00837 { 00838 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_LeftVertexColors[i_NeighboringVertex]]; 00839 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_LeftVertexColors[i_NeighboringVertex]]; 00840 00841 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 00842 { 00843 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_FirstNeighborTwo][i_PresentVertex]]; 00844 00845 vi_RightStarHubMap[i_StarID] = i_PresentVertex; 00846 00847 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 00848 } 00849 } 00850 } 00851 } 00852 00853 m_i_VertexColorCount = m_i_LeftVertexColorCount + m_i_RightVertexColorCount - i_LeftVertexCoverSize; 00854 00855 #if DEBUG == 3556 00856 00857 cout<<endl; 00858 cout<<"DEBUG 3556 | Left Star Bicoloring | Vertex Colors | Left Vertices"<<endl; 00859 cout<<endl; 00860 00861 for(i=0; i<i_LeftVertexCount; i++) 00862 { 00863 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 00864 } 00865 00866 cout<<endl; 00867 cout<<"DEBUG 3556 | Left Star Bicoloring | Vertex Colors | Right Vertices"<<endl; 00868 cout<<endl; 00869 00870 for(i=0; i<i_RightVertexCount; i++) 00871 { 00872 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 00873 } 00874 00875 #endif 00876 00877 return(_TRUE); 00878 } 00879 00880 00881 00882 //Public Function 3557 00883 int BipartiteGraphBicoloring::MinimalCoveringColumnMajorStarBicoloring() 00884 { 00885 if(CheckVertexColoring("MINIMAL_COVER_COLUMN_STAR")) 00886 { 00887 return(_TRUE); 00888 } 00889 00890 int i, j, k; 00891 00892 int _FOUND; 00893 00894 int i_ColorID, i_StarID; 00895 00896 int i_EdgeCount; 00897 00898 int i_FirstNeighborOne, i_FirstNeighborTwo; 00899 00900 int i_LeftVertexCount, i_RightVertexCount; 00901 00902 int i_LargerVertexCount; 00903 00904 int i_LeftVertexCoverSize, i_RightVertexCoverSize; 00905 00906 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex; 00907 00908 vector<int> vi_CandidateColors; 00909 00910 vector<int> vi_EdgeStarMap, vi_LeftStarHubMap, vi_RightStarHubMap; 00911 00912 vector<int> vi_FirstTreated; 00913 00914 vector<int> vi_FirstNeighborOne, vi_FirstNeighborTwo; 00915 00916 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 00917 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 00918 00919 i_LargerVertexCount = i_LeftVertexCount>i_RightVertexCount?i_LeftVertexCount:i_RightVertexCount; 00920 00921 i_EdgeCount = (signed) m_vi_Edges.size()/2; 00922 00923 vi_EdgeStarMap.clear(); 00924 vi_EdgeStarMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 00925 00926 m_mimi2_VertexEdgeMap.clear(); 00927 00928 k=_FALSE; 00929 00930 for(i=0; i<i_LeftVertexCount; i++) 00931 { 00932 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 00933 { 00934 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k; 00935 00936 vi_EdgeStarMap[k] = k; 00937 00938 k++; 00939 } 00940 } 00941 00942 Timer m_T_Timer; 00943 00944 m_T_Timer.Start(); 00945 00946 CoverMinimalVertex(); 00947 00948 m_T_Timer.Stop(); 00949 00950 m_d_CoveringTime = m_T_Timer.GetWallTime(); 00951 00952 PresetCoveredVertexColors(); 00953 00954 #if DEBUG == 3557 00955 00956 cout<<"DEBUG 3557 | Right Star Bicoloring | Left Vertex Cover Size = "<<m_vi_CoveredLeftVertices.size()<<"; Right Vertex Cover Size = "<<m_vi_CoveredRightVertices.size()<<endl; 00957 00958 #endif 00959 00960 #if DEBUG == 3557 00961 00962 cout<<endl; 00963 cout<<"DEBUG 3557 | Right Star Bicoloring | Initial Vertex Colors | Left Vertices"<<endl; 00964 cout<<endl; 00965 00966 for(i=0; i<i_LeftVertexCount; i++) 00967 { 00968 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 00969 } 00970 00971 cout<<endl; 00972 cout<<"DEBUG 3557 | Right Star Bicoloring | Initial Vertex Colors | Right Vertices"<<endl; 00973 cout<<endl; 00974 00975 for(i=0; i<i_RightVertexCount; i++) 00976 { 00977 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 00978 } 00979 00980 #endif 00981 00982 i_LeftVertexCoverSize = (signed) m_vi_CoveredLeftVertices.size(); 00983 i_RightVertexCoverSize = (signed) m_vi_CoveredRightVertices.size(); 00984 00985 m_i_VertexColorCount = STEP_UP(i_LeftVertexCoverSize + i_RightVertexCoverSize); 00986 00987 vi_CandidateColors.clear(); 00988 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 00989 00990 vi_LeftStarHubMap.clear(); 00991 vi_LeftStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 00992 00993 vi_RightStarHubMap.clear(); 00994 vi_RightStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 00995 00996 vi_FirstNeighborOne.clear(); 00997 vi_FirstNeighborOne.resize((unsigned) i_LargerVertexCount, _UNKNOWN); 00998 00999 vi_FirstNeighborTwo.clear(); 01000 vi_FirstNeighborTwo.resize((unsigned) i_LargerVertexCount, _UNKNOWN); 01001 01002 vi_FirstTreated.clear(); 01003 vi_FirstTreated.resize((unsigned) i_LargerVertexCount, _UNKNOWN); 01004 01005 m_i_RightVertexColorCount = _UNKNOWN; 01006 01007 for(i=0; i<i_RightVertexCoverSize; i++) 01008 { 01009 i_PresentVertex = m_vi_CoveredRightVertices[i]; 01010 01011 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 01012 { 01013 i_NeighboringVertex = m_vi_Edges[j]; 01014 01015 if(m_vi_LeftVertexColors[i_NeighboringVertex] == _FALSE) 01016 { 01017 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 01018 { 01019 i_SecondNeighboringVertex = m_vi_Edges[k]; 01020 01021 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] > _FALSE) 01022 { 01023 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01024 } 01025 } 01026 } 01027 } 01028 01029 for(j=_TRUE; j<STEP_UP(i_RightVertexCoverSize); j++) 01030 { 01031 if(vi_CandidateColors[j] != i_PresentVertex) 01032 { 01033 m_vi_RightVertexColors[i_PresentVertex] = j; 01034 01035 if(m_i_RightVertexColorCount < j) 01036 { 01037 m_i_RightVertexColorCount = j; 01038 } 01039 01040 break; 01041 } 01042 } 01043 } 01044 01045 #if DEBUG == 3557 01046 01047 cout<<endl; 01048 cout<<"DEBUG 3557 | Right Star Bicoloring | Present Vertex Colors | Left Vertices"<<endl; 01049 cout<<endl; 01050 01051 for(i=0; i<i_LeftVertexCount; i++) 01052 { 01053 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 01054 } 01055 01056 cout<<endl; 01057 cout<<"DEBUG 3557 | Right Star Bicoloring | Present Vertex Colors | Right Vertices"<<endl; 01058 cout<<endl; 01059 01060 for(i=0; i<i_RightVertexCount; i++) 01061 { 01062 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 01063 } 01064 01065 #endif 01066 01067 m_i_LeftVertexColorCount = _UNKNOWN; 01068 01069 for(i=0; i<i_LeftVertexCoverSize; i++) 01070 { 01071 i_PresentVertex = m_vi_CoveredLeftVertices[i]; 01072 01073 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 01074 { 01075 i_NeighboringVertex = m_vi_Edges[j]; 01076 01077 i_ColorID = m_vi_RightVertexColors[i_NeighboringVertex]; 01078 01079 if(i_ColorID == _UNKNOWN) 01080 { 01081 continue; 01082 } 01083 01084 if(i_ColorID == _FALSE) 01085 { 01086 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 01087 { 01088 i_SecondNeighboringVertex = m_vi_Edges[k]; 01089 01090 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01091 { 01092 continue; 01093 } 01094 01095 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] != _FALSE) 01096 { 01097 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01098 } 01099 } 01100 } 01101 else 01102 { 01103 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 01104 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 01105 01106 if(i_FirstNeighborOne == i_PresentVertex) 01107 { 01108 if(vi_FirstTreated[i_FirstNeighborTwo] != i_PresentVertex) 01109 { 01110 for(k=m_vi_RightVertices[i_FirstNeighborTwo]; k<m_vi_RightVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 01111 { 01112 if(m_vi_Edges[k] == i_PresentVertex) 01113 { 01114 continue; 01115 } 01116 01117 if(m_vi_LeftVertexColors[m_vi_Edges[k]] == _UNKNOWN) 01118 { 01119 continue; 01120 } 01121 01122 vi_CandidateColors[m_vi_LeftVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 01123 01124 } 01125 01126 vi_FirstTreated[i_FirstNeighborTwo] = i_PresentVertex; 01127 01128 } 01129 01130 for(k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[STEP_UP(m_vi_Edges[j])]; k++) 01131 { 01132 if(m_vi_Edges[k] == i_PresentVertex) 01133 { 01134 continue; 01135 } 01136 01137 if(m_vi_LeftVertexColors[m_vi_Edges[k]] == _UNKNOWN) 01138 { 01139 continue; 01140 } 01141 01142 vi_CandidateColors[m_vi_LeftVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 01143 01144 } 01145 01146 vi_FirstTreated[i_NeighboringVertex] = i_PresentVertex; 01147 } 01148 else 01149 { 01150 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 01151 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 01152 01153 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 01154 { 01155 i_SecondNeighboringVertex = m_vi_Edges[k]; 01156 01157 if(i_SecondNeighboringVertex == i_PresentVertex) 01158 { 01159 continue; 01160 } 01161 01162 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01163 { 01164 continue; 01165 } 01166 01167 if(vi_LeftStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]] == i_SecondNeighboringVertex) 01168 { 01169 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01170 } 01171 } 01172 } 01173 } 01174 } 01175 01176 for(j=STEP_UP(i_RightVertexCoverSize); j<m_i_VertexColorCount; j++) 01177 { 01178 if(vi_CandidateColors[j] != i_PresentVertex) 01179 { 01180 m_vi_LeftVertexColors[i_PresentVertex] = j; 01181 01182 if(m_i_LeftVertexColorCount < j) 01183 { 01184 m_i_LeftVertexColorCount = j; 01185 } 01186 01187 break; 01188 } 01189 } 01190 01191 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 01192 { 01193 _FOUND = _FALSE; 01194 01195 i_NeighboringVertex = m_vi_Edges[j]; 01196 01197 if(m_vi_RightVertexColors[i_NeighboringVertex] == _UNKNOWN) 01198 { 01199 continue; 01200 } 01201 01202 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 01203 { 01204 i_SecondNeighboringVertex = m_vi_Edges[k]; 01205 01206 if(i_SecondNeighboringVertex == i_PresentVertex) 01207 { 01208 continue; 01209 } 01210 01211 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01212 { 01213 continue; 01214 } 01215 01216 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == m_vi_LeftVertexColors[i_PresentVertex]) 01217 { 01218 _FOUND = _TRUE; 01219 01220 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]; 01221 01222 vi_RightStarHubMap[i_StarID] = i_NeighboringVertex; 01223 01224 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 01225 01226 break; 01227 } 01228 } 01229 01230 if (!_FOUND) 01231 { 01232 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_RightVertexColors[i_NeighboringVertex]]; 01233 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_RightVertexColors[i_NeighboringVertex]]; 01234 01235 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 01236 { 01237 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_FirstNeighborTwo]]; 01238 01239 vi_LeftStarHubMap[i_StarID] = i_PresentVertex; 01240 01241 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 01242 } 01243 } 01244 } 01245 } 01246 01247 m_i_VertexColorCount = m_i_RightVertexColorCount + m_i_LeftVertexColorCount - i_RightVertexCoverSize; 01248 01249 #if DEBUG == 3557 01250 01251 cout<<endl; 01252 cout<<"DEBUG 3557 | Right Star Bicoloring | Vertex Colors | Left Vertices"<<endl; 01253 cout<<endl; 01254 01255 for(i=0; i<i_LeftVertexCount; i++) 01256 { 01257 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 01258 } 01259 01260 cout<<endl; 01261 cout<<"DEBUG 3557 | Right Star Bicoloring | Vertex Colors | Right Vertices"<<endl; 01262 cout<<endl; 01263 01264 for(i=0; i<i_RightVertexCount; i++) 01265 { 01266 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 01267 } 01268 01269 #endif 01270 01271 return(_TRUE); 01272 } 01273 01274 01275 //Public Function 3558 01276 int BipartiteGraphBicoloring::ExplicitCoveringModifiedStarBicoloring() 01277 { 01278 if(CheckVertexColoring("EXPLICIT_COVER_MODIFIED_STAR")) 01279 { 01280 return(_TRUE); 01281 } 01282 01283 int i, j, k, l; 01284 01285 int i_EdgeID, i_NeighboringEdgeID; 01286 01287 int i_EdgeCount; 01288 01289 int i_LeftVertexCount, i_RightVertexCount; 01290 01291 int i_LeftVertexCoverSize, i_RightVertexCoverSize; 01292 01293 int i_OrderedVertexCount; 01294 01295 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex, i_ThirdNeighboringVertex; 01296 01297 vector<int> vi_CandidateColors; 01298 01299 vector<int> vi_EdgeCodes; 01300 01301 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 01302 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 01303 01304 i_EdgeCount = (signed) m_vi_Edges.size()/2; 01305 01306 m_mimi2_VertexEdgeMap.clear(); 01307 01308 k=_FALSE; 01309 01310 for(i=0; i<i_LeftVertexCount; i++) 01311 { 01312 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 01313 { 01314 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k; 01315 01316 k++; 01317 } 01318 } 01319 01320 01321 Timer m_T_Timer; 01322 01323 m_T_Timer.Start(); 01324 01325 CoverVertex(vi_EdgeCodes); 01326 01327 m_T_Timer.Stop(); 01328 01329 m_d_CoveringTime = m_T_Timer.GetWallTime(); 01330 01331 PresetCoveredVertexColors(); 01332 01333 i_LeftVertexCoverSize = (signed) m_vi_CoveredLeftVertices.size(); 01334 i_RightVertexCoverSize = (signed) m_vi_CoveredRightVertices.size(); 01335 01336 m_i_VertexColorCount = STEP_UP(i_LeftVertexCoverSize + i_RightVertexCoverSize); 01337 01338 vi_CandidateColors.clear(); 01339 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 01340 01341 #if DEBUG == 3558 01342 01343 int i_EdgeCodeZero, i_EdgeCodeOne, i_EdgeCodeTwo, i_EdgeCodeThree; 01344 01345 i_EdgeCodeZero = i_EdgeCodeOne = i_EdgeCodeTwo = i_EdgeCodeThree = _FALSE; 01346 01347 cout<<endl; 01348 cout<<"DEBUG 3558 | Bipartite Graph Bicoloring | Edge Codes"<<endl; 01349 cout<<endl; 01350 01351 for(i=0; i<i_LeftVertexCount; i++) 01352 { 01353 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 01354 { 01355 i_EdgeID = m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]]; 01356 01357 cout<<"Edge "<<STEP_UP(i_EdgeID)<<"\t"<<" : "<<vi_EdgeCodes[i_EdgeID]<<endl; 01358 01359 if(vi_EdgeCodes[i_EdgeID] == 0) 01360 { 01361 i_EdgeCodeZero++; 01362 } 01363 else 01364 if(vi_EdgeCodes[i_EdgeID] == 1) 01365 { 01366 i_EdgeCodeOne++; 01367 } 01368 else 01369 if(vi_EdgeCodes[i_EdgeID] == 2) 01370 { 01371 i_EdgeCodeTwo++; 01372 } 01373 else 01374 if(vi_EdgeCodes[i_EdgeID] == 3) 01375 { 01376 i_EdgeCodeThree++; 01377 } 01378 } 01379 } 01380 01381 cout<<endl; 01382 cout<<"Code Zero Edges = "<<i_EdgeCodeZero<<"; Code One Edges = "<<i_EdgeCodeOne<<"; Code Two Edges = "<<i_EdgeCodeTwo<<"; Code Three Edges = "<<i_EdgeCodeThree<<endl; 01383 cout<<endl; 01384 01385 #endif 01386 01387 #if DEBUG == 3558 01388 01389 cout<<"DEBUG 3558 | Star Bicoloring | Left Vertex Cover Size = "<<m_vi_CoveredLeftVertices.size()<<"; Right Vertex Cover Size = "<<m_vi_CoveredRightVertices.size()<<endl; 01390 01391 #endif 01392 01393 i_OrderedVertexCount = (signed) m_vi_OrderedVertices.size(); 01394 01395 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = _UNKNOWN; 01396 01397 for(i=0; i<i_OrderedVertexCount; i++) 01398 { 01399 01400 #if DEBUG == 3558 01401 01402 cout<<"DEBUG 3558 | Star Bicoloring | Present Vertex | "<<STEP_UP(m_vi_OrderedVertices[i])<<endl; 01403 01404 #endif 01405 01406 if(m_vi_OrderedVertices[i] < i_LeftVertexCount) 01407 { 01408 if(m_vi_IncludedLeftVertices[m_vi_OrderedVertices[i]] == _FALSE) 01409 { 01410 continue; 01411 } 01412 01413 i_PresentVertex = m_vi_OrderedVertices[i]; 01414 01415 #if DEBUG == 3558 01416 01417 cout<<"DEBUG 3558 | Star Bicoloring | Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 01418 #endif 01419 01420 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 01421 { 01422 i_NeighboringVertex = m_vi_Edges[j]; 01423 01424 i_EdgeID = m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]; 01425 01426 if((vi_EdgeCodes[i_EdgeID] == 2)) 01427 { 01428 continue; 01429 } 01430 01431 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 01432 { 01433 i_SecondNeighboringVertex = m_vi_Edges[k]; 01434 01435 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01436 { 01437 continue; 01438 } 01439 01440 i_NeighboringEdgeID = m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]; 01441 01442 if(vi_EdgeCodes[i_NeighboringEdgeID] != 2) 01443 { 01444 if(m_vi_RightVertexColors[i_NeighboringVertex] <= _FALSE) 01445 { 01446 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01447 } 01448 else 01449 { 01450 for(l=m_vi_LeftVertices[i_SecondNeighboringVertex]; l<m_vi_LeftVertices[STEP_UP(i_SecondNeighboringVertex)]; l++) 01451 { 01452 i_ThirdNeighboringVertex = m_vi_Edges[l]; 01453 01454 if(m_vi_RightVertexColors[i_ThirdNeighboringVertex] == _UNKNOWN) 01455 { 01456 continue; 01457 } 01458 01459 if(m_vi_RightVertexColors[i_ThirdNeighboringVertex] == m_vi_RightVertexColors[i_NeighboringVertex]) 01460 { 01461 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01462 } 01463 } 01464 } 01465 } 01466 } 01467 } 01468 01469 for(j=_TRUE; j<STEP_UP(i_LeftVertexCoverSize); j++) 01470 { 01471 if(vi_CandidateColors[j] != i_PresentVertex) 01472 { 01473 m_vi_LeftVertexColors[i_PresentVertex] = j; 01474 01475 if(m_i_LeftVertexColorCount < j) 01476 { 01477 m_i_LeftVertexColorCount = j; 01478 } 01479 01480 break; 01481 } 01482 } 01483 } 01484 else 01485 { 01486 if(m_vi_IncludedRightVertices[m_vi_OrderedVertices[i] - i_LeftVertexCount] == _FALSE) 01487 { 01488 continue; 01489 } 01490 01491 i_PresentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount; 01492 01493 #if DEBUG == 3558 01494 01495 cout<<"DEBUG 3558 | Star Bicoloring | Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 01496 #endif 01497 01498 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 01499 { 01500 i_NeighboringVertex = m_vi_Edges[j]; 01501 01502 i_EdgeID = m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]; 01503 01504 if(vi_EdgeCodes[i_EdgeID] == 3) 01505 { 01506 continue; 01507 } 01508 01509 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 01510 { 01511 i_SecondNeighboringVertex = m_vi_Edges[k]; 01512 01513 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01514 { 01515 continue; 01516 } 01517 01518 i_NeighboringEdgeID = m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]; 01519 01520 if(vi_EdgeCodes[i_NeighboringEdgeID] != 3) 01521 { 01522 if(m_vi_LeftVertexColors[i_NeighboringVertex] <= _FALSE) 01523 { 01524 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01525 } 01526 else 01527 { 01528 for(l=m_vi_RightVertices[i_SecondNeighboringVertex]; l<m_vi_RightVertices[STEP_UP(i_SecondNeighboringVertex)]; l++) 01529 { 01530 i_ThirdNeighboringVertex = m_vi_Edges[l]; 01531 01532 if(m_vi_LeftVertexColors[i_ThirdNeighboringVertex] == _UNKNOWN) 01533 { 01534 continue; 01535 } 01536 01537 if(m_vi_LeftVertexColors[i_ThirdNeighboringVertex] == m_vi_LeftVertexColors[i_NeighboringVertex]) 01538 { 01539 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01540 } 01541 } 01542 } 01543 } 01544 } 01545 } 01546 01547 for(j=STEP_UP(i_LeftVertexCoverSize); j<m_i_VertexColorCount; j++) 01548 { 01549 if(vi_CandidateColors[j] != i_PresentVertex) 01550 { 01551 m_vi_RightVertexColors[i_PresentVertex] = j; 01552 01553 if(m_i_RightVertexColorCount < j) 01554 { 01555 m_i_RightVertexColorCount = j; 01556 } 01557 01558 break; 01559 } 01560 } 01561 } 01562 } 01563 01564 i_LeftVertexDefaultColor = _FALSE; 01565 i_RightVertexDefaultColor = _FALSE; 01566 01567 for(i=0; i<i_LeftVertexCount; i++) 01568 { 01569 if(m_vi_LeftVertexColors[i] == _FALSE) 01570 { 01571 i_LeftVertexDefaultColor = _TRUE; 01572 } 01573 } 01574 01575 for(i=0; i<i_RightVertexCount; i++) 01576 { 01577 if(m_vi_RightVertexColors[i] == FALSE) 01578 { 01579 m_vi_RightVertexColors[i] = m_i_VertexColorCount; 01580 01581 i_RightVertexDefaultColor = _TRUE; 01582 } 01583 } 01584 01585 if(m_i_LeftVertexColorCount == _UNKNOWN) 01586 { 01587 m_i_LeftVertexColorCount = _TRUE; 01588 } 01589 else 01590 { 01591 m_i_LeftVertexColorCount = m_i_LeftVertexColorCount + i_LeftVertexDefaultColor; 01592 } 01593 01594 if(m_i_RightVertexColorCount == _UNKNOWN) 01595 { 01596 m_i_RightVertexColorCount = _TRUE; 01597 } 01598 else 01599 { 01600 m_i_RightVertexColorCount = m_i_RightVertexColorCount + i_RightVertexDefaultColor - i_LeftVertexCoverSize; 01601 } 01602 01603 m_i_VertexColorCount = m_i_LeftVertexColorCount + m_i_RightVertexColorCount; 01604 01605 #if DEBUG == 3558 01606 01607 cout<<endl; 01608 cout<<"DEBUG 3558 | Modified Star Bicoloring | Left Vertex Colors"<<endl; 01609 cout<<endl; 01610 01611 for(i=0; i<i_LeftVertexCount; i++) 01612 { 01613 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 01614 } 01615 01616 cout<<endl; 01617 cout<<"DEBUG 3558 | Modified Star Bicoloring | Right Vertex Colors"<<endl; 01618 cout<<endl; 01619 01620 for(i=0; i<i_RightVertexCount; i++) 01621 { 01622 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 01623 } 01624 01625 cout<<endl; 01626 cout<<"[Total Vertex Colors = "<<m_i_VertexColorCount<<"]"<<endl; 01627 cout<<endl; 01628 01629 #endif 01630 01631 return(_TRUE); 01632 } 01633 01634 01635 01636 //Public Function 3559 01637 int BipartiteGraphBicoloring::ExplicitCoveringStarBicoloring() 01638 { 01639 if(CheckVertexColoring("EXPLICIT_COVER_STAR")) 01640 { 01641 return(_TRUE); 01642 } 01643 01644 int i, j, k; 01645 01646 int _FOUND; 01647 01648 int i_ColorID, i_StarID; 01649 01650 int i_EdgeCount; 01651 01652 int i_OrderedVertexCount; 01653 01654 int i_FirstNeighborOne, i_FirstNeighborTwo; 01655 01656 int i_LeftVertexCount, i_RightVertexCount; 01657 01658 int i_LeftVertexCoverSize, i_RightVertexCoverSize; 01659 01660 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex; 01661 01662 vector<int> vi_CandidateColors; 01663 01664 vector<int> vi_EdgeStarMap, vi_LeftStarHubMap, vi_RightStarHubMap; 01665 01666 vector<int> vi_LeftTreated, vi_RightTreated; 01667 01668 vector<int> vi_FirstNeighborOne, vi_FirstNeighborTwo; 01669 01670 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 01671 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 01672 01673 i_EdgeCount = (signed) m_vi_Edges.size()/2; 01674 01675 vi_EdgeStarMap.clear(); 01676 vi_EdgeStarMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 01677 01678 m_mimi2_VertexEdgeMap.clear(); 01679 01680 k=_FALSE; 01681 01682 for(i=0; i<i_LeftVertexCount; i++) 01683 { 01684 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 01685 { 01686 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k; 01687 01688 vi_EdgeStarMap[k] = k; 01689 01690 k++; 01691 } 01692 } 01693 01694 Timer m_T_Timer; 01695 01696 m_T_Timer.Start(); 01697 01698 CoverVertex(); 01699 01700 m_T_Timer.Stop(); 01701 01702 m_d_CoveringTime = m_T_Timer.GetWallTime(); 01703 01704 PresetCoveredVertexColors(); 01705 01706 #if DEBUG == 3559 01707 01708 cout<<"DEBUG 3559 | Combined Star Bicoloring | Left Vertex Cover Size = "<<m_vi_CoveredLeftVertices.size()<<"; Right Vertex Cover Size = "<<m_vi_CoveredRightVertices.size()<<endl; 01709 01710 #endif 01711 01712 i_LeftVertexCoverSize = (signed) m_vi_CoveredLeftVertices.size(); 01713 i_RightVertexCoverSize = (signed) m_vi_CoveredRightVertices.size(); 01714 01715 m_i_VertexColorCount = STEP_UP(i_LeftVertexCoverSize + i_RightVertexCoverSize); 01716 01717 vi_CandidateColors.clear(); 01718 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 01719 01720 vi_LeftStarHubMap.clear(); 01721 vi_LeftStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 01722 01723 vi_RightStarHubMap.clear(); 01724 vi_RightStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 01725 01726 vi_FirstNeighborOne.clear(); 01727 vi_FirstNeighborOne.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 01728 01729 vi_FirstNeighborTwo.clear(); 01730 vi_FirstNeighborTwo.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 01731 01732 vi_LeftTreated.clear(); 01733 vi_LeftTreated.resize((unsigned) i_RightVertexCount, _UNKNOWN); 01734 01735 vi_RightTreated.clear(); 01736 vi_RightTreated.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 01737 01738 #if DEBUG == 3559 01739 01740 cout<<endl; 01741 cout<<"DEBUG 3559 | Star Bicoloring | Initial Vertex Colors | Left Vertices"<<endl; 01742 cout<<endl; 01743 01744 for(i=0; i<i_LeftVertexCount; i++) 01745 { 01746 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<" ["<<m_vi_IncludedLeftVertices[i]<<"]"<<endl; 01747 } 01748 01749 cout<<endl; 01750 cout<<"DEBUG 3559 | Star Bicoloring | Initial Vertex Colors | Right Vertices"<<endl; 01751 cout<<endl; 01752 01753 for(i=0; i<i_RightVertexCount; i++) 01754 { 01755 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<" ["<<m_vi_IncludedRightVertices[i]<<"]"<<endl; 01756 } 01757 01758 cout<<endl; 01759 01760 #endif 01761 01762 i_OrderedVertexCount = (signed) m_vi_OrderedVertices.size(); 01763 01764 for(i=0; i<i_OrderedVertexCount; i++) 01765 { 01766 01767 #if DEBUG == 3559 01768 01769 cout<<"DEBUG 3559 | Star Bicoloring | Present Vertex | "<<STEP_UP(m_vi_OrderedVertices[i])<<endl; 01770 01771 #endif 01772 01773 if(m_vi_OrderedVertices[i] < i_LeftVertexCount) 01774 { 01775 if(m_vi_IncludedLeftVertices[m_vi_OrderedVertices[i]] == _FALSE) 01776 { 01777 continue; 01778 } 01779 01780 i_PresentVertex = m_vi_OrderedVertices[i]; 01781 01782 #if DEBUG == 3559 01783 01784 cout<<"DEBUG 3559 | Star Bicoloring | Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 01785 #endif 01786 01787 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 01788 { 01789 i_NeighboringVertex = m_vi_Edges[j]; 01790 01791 i_ColorID = m_vi_RightVertexColors[i_NeighboringVertex]; 01792 01793 if(i_ColorID == _UNKNOWN) 01794 { 01795 continue; 01796 } 01797 01798 if(i_ColorID == _FALSE) 01799 { 01800 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 01801 { 01802 i_SecondNeighboringVertex = m_vi_Edges[k]; 01803 01804 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01805 { 01806 continue; 01807 } 01808 01809 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] != _FALSE) 01810 { 01811 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01812 } 01813 } 01814 } 01815 else 01816 { 01817 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 01818 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 01819 01820 if(i_FirstNeighborOne == i_PresentVertex) 01821 { 01822 if(vi_LeftTreated[i_FirstNeighborTwo] != i_PresentVertex) 01823 { 01824 for(k=m_vi_RightVertices[i_FirstNeighborTwo]; k<m_vi_RightVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 01825 { 01826 if(m_vi_Edges[k] == i_PresentVertex) 01827 { 01828 continue; 01829 } 01830 01831 if(m_vi_LeftVertexColors[m_vi_Edges[k]] == _UNKNOWN) 01832 { 01833 continue; 01834 } 01835 01836 vi_CandidateColors[m_vi_LeftVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 01837 01838 } 01839 01840 vi_LeftTreated[i_FirstNeighborTwo] = i_PresentVertex; 01841 } 01842 01843 for(k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[STEP_UP(m_vi_Edges[j])]; k++) 01844 { 01845 if(m_vi_Edges[k] == i_PresentVertex) 01846 { 01847 continue; 01848 } 01849 01850 if(m_vi_LeftVertexColors[m_vi_Edges[k]] == _UNKNOWN) 01851 { 01852 continue; 01853 } 01854 01855 vi_CandidateColors[m_vi_LeftVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 01856 } 01857 01858 vi_LeftTreated[i_NeighboringVertex] = i_PresentVertex; 01859 } 01860 else 01861 { 01862 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 01863 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 01864 01865 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 01866 { 01867 i_SecondNeighboringVertex = m_vi_Edges[k]; 01868 01869 if(i_SecondNeighboringVertex == i_PresentVertex) 01870 { 01871 continue; 01872 } 01873 01874 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01875 { 01876 continue; 01877 } 01878 01879 if(vi_LeftStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]] == i_SecondNeighboringVertex) 01880 { 01881 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01882 } 01883 } 01884 } 01885 } 01886 } 01887 01888 for(j=_TRUE; j<STEP_UP(i_LeftVertexCoverSize); j++) 01889 { 01890 if(vi_CandidateColors[j] != i_PresentVertex) 01891 { 01892 m_vi_LeftVertexColors[i_PresentVertex] = j; 01893 01894 if(m_i_LeftVertexColorCount < j) 01895 { 01896 m_i_LeftVertexColorCount = j; 01897 } 01898 01899 break; 01900 } 01901 } 01902 01903 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 01904 { 01905 _FOUND = _FALSE; 01906 01907 i_NeighboringVertex = m_vi_Edges[j]; 01908 01909 if(m_vi_RightVertexColors[i_NeighboringVertex] == _UNKNOWN) 01910 { 01911 continue; 01912 } 01913 01914 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 01915 { 01916 i_SecondNeighboringVertex = m_vi_Edges[k]; 01917 01918 if(i_SecondNeighboringVertex == i_PresentVertex) 01919 { 01920 continue; 01921 } 01922 01923 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01924 { 01925 continue; 01926 } 01927 01928 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == m_vi_LeftVertexColors[i_PresentVertex]) 01929 { 01930 _FOUND = _TRUE; 01931 01932 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]; 01933 01934 vi_RightStarHubMap[i_StarID] = i_NeighboringVertex; 01935 01936 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 01937 01938 break; 01939 } 01940 } 01941 01942 if (!_FOUND) 01943 { 01944 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_RightVertexColors[i_NeighboringVertex]]; 01945 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_RightVertexColors[i_NeighboringVertex]]; 01946 01947 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 01948 { 01949 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_FirstNeighborTwo]]; 01950 01951 vi_LeftStarHubMap[i_StarID] = i_PresentVertex; 01952 01953 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 01954 } 01955 } 01956 } 01957 } 01958 else 01959 { 01960 if(m_vi_IncludedRightVertices[m_vi_OrderedVertices[i] - i_LeftVertexCount] == _FALSE) 01961 { 01962 continue; 01963 } 01964 01965 i_PresentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount; 01966 01967 #if DEBUG == 3559 01968 01969 cout<<"DEBUG 3559 | Star Bicoloring | Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 01970 #endif 01971 01972 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 01973 { 01974 i_NeighboringVertex = m_vi_Edges[j]; 01975 01976 i_ColorID = m_vi_LeftVertexColors[i_NeighboringVertex]; 01977 01978 if(i_ColorID == _UNKNOWN) 01979 { 01980 continue; 01981 } 01982 01983 if(i_ColorID == _FALSE) 01984 { 01985 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 01986 { 01987 i_SecondNeighboringVertex = m_vi_Edges[k]; 01988 01989 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 01990 { 01991 continue; 01992 } 01993 01994 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] != _FALSE) 01995 { 01996 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 01997 } 01998 } 01999 } 02000 else 02001 { 02002 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 02003 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 02004 02005 if(i_FirstNeighborOne == i_PresentVertex) 02006 { 02007 if(vi_RightTreated[i_FirstNeighborTwo] != i_PresentVertex) 02008 { 02009 for(k=m_vi_LeftVertices[i_FirstNeighborTwo]; k<m_vi_LeftVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 02010 { 02011 if(m_vi_Edges[k] == i_PresentVertex) 02012 { 02013 continue; 02014 } 02015 02016 if(m_vi_RightVertexColors[m_vi_Edges[k]] == _UNKNOWN) 02017 { 02018 continue; 02019 } 02020 02021 vi_CandidateColors[m_vi_RightVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 02022 02023 } 02024 02025 vi_RightTreated[i_FirstNeighborTwo] = i_PresentVertex; 02026 } 02027 02028 for(k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[STEP_UP(m_vi_Edges[j])]; k++) 02029 { 02030 if(m_vi_Edges[k] == i_PresentVertex) 02031 { 02032 continue; 02033 } 02034 02035 if(m_vi_RightVertexColors[m_vi_Edges[k]] == _UNKNOWN) 02036 { 02037 continue; 02038 } 02039 02040 vi_CandidateColors[m_vi_RightVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 02041 02042 } 02043 02044 vi_RightTreated[i_NeighboringVertex] = i_PresentVertex; 02045 } 02046 else 02047 { 02048 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 02049 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 02050 02051 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 02052 { 02053 i_SecondNeighboringVertex = m_vi_Edges[k]; 02054 02055 if(i_SecondNeighboringVertex == i_PresentVertex) 02056 { 02057 continue; 02058 } 02059 02060 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02061 { 02062 continue; 02063 } 02064 02065 if(vi_RightStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]] == i_SecondNeighboringVertex) 02066 { 02067 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 02068 02069 } 02070 } 02071 } 02072 } 02073 } 02074 02075 for(j=STEP_UP(i_LeftVertexCoverSize); j<m_i_VertexColorCount; j++) 02076 { 02077 if(vi_CandidateColors[j] != i_PresentVertex) 02078 { 02079 m_vi_RightVertexColors[i_PresentVertex] = j; 02080 02081 if(m_i_RightVertexColorCount < j) 02082 { 02083 m_i_RightVertexColorCount = j; 02084 } 02085 02086 break; 02087 } 02088 } 02089 02090 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 02091 { 02092 _FOUND = _FALSE; 02093 02094 i_NeighboringVertex = m_vi_Edges[j]; 02095 02096 if(m_vi_LeftVertexColors[i_NeighboringVertex] == _UNKNOWN) 02097 { 02098 continue; 02099 } 02100 02101 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 02102 { 02103 i_SecondNeighboringVertex = m_vi_Edges[k]; 02104 02105 if(i_SecondNeighboringVertex == i_PresentVertex) 02106 { 02107 continue; 02108 } 02109 02110 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02111 { 02112 continue; 02113 } 02114 02115 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == m_vi_RightVertexColors[i_PresentVertex]) 02116 { 02117 _FOUND = _TRUE; 02118 02119 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]; 02120 02121 vi_LeftStarHubMap[i_StarID] = i_NeighboringVertex; 02122 02123 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 02124 02125 break; 02126 } 02127 } 02128 02129 if (!_FOUND) 02130 { 02131 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_LeftVertexColors[i_NeighboringVertex]]; 02132 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_LeftVertexColors[i_NeighboringVertex]]; 02133 02134 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 02135 { 02136 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_FirstNeighborTwo][i_PresentVertex]]; 02137 02138 vi_RightStarHubMap[i_StarID] = i_PresentVertex; 02139 02140 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 02141 } 02142 } 02143 } 02144 } 02145 } 02146 02147 i_LeftVertexDefaultColor = _FALSE; 02148 i_RightVertexDefaultColor = _FALSE; 02149 02150 for(i=0; i<i_LeftVertexCount; i++) 02151 { 02152 if(m_vi_LeftVertexColors[i] == _FALSE) 02153 { 02154 i_LeftVertexDefaultColor = _TRUE; 02155 } 02156 } 02157 02158 for(i=0; i<i_RightVertexCount; i++) 02159 { 02160 if(m_vi_RightVertexColors[i] == FALSE) 02161 { 02162 m_vi_RightVertexColors[i] = m_i_VertexColorCount; 02163 02164 i_RightVertexDefaultColor = _TRUE; 02165 } 02166 } 02167 02168 if(m_i_LeftVertexColorCount == _UNKNOWN) 02169 { 02170 m_i_LeftVertexColorCount = _TRUE; 02171 } 02172 else 02173 { 02174 m_i_LeftVertexColorCount = m_i_LeftVertexColorCount + i_LeftVertexDefaultColor; 02175 } 02176 02177 if(m_i_RightVertexColorCount == _UNKNOWN) 02178 { 02179 m_i_RightVertexColorCount = _TRUE; 02180 } 02181 else 02182 { 02183 m_i_RightVertexColorCount = m_i_RightVertexColorCount + i_RightVertexDefaultColor - i_LeftVertexCoverSize; 02184 } 02185 02186 m_i_VertexColorCount = m_i_LeftVertexColorCount + m_i_RightVertexColorCount; 02187 02188 #if DEBUG == 3559 02189 02190 cout<<endl; 02191 cout<<"DEBUG 3559 | Right Star Bicoloring | Vertex Colors | Left Vertices"<<endl; 02192 cout<<endl; 02193 02194 for(i=0; i<i_LeftVertexCount; i++) 02195 { 02196 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 02197 } 02198 02199 cout<<endl; 02200 cout<<"DEBUG 3559 | Right Star Bicoloring | Vertex Colors | Right Vertices"<<endl; 02201 cout<<endl; 02202 02203 for(i=0; i<i_RightVertexCount; i++) 02204 { 02205 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 02206 } 02207 02208 #endif 02209 02210 return(_TRUE); 02211 02212 } 02213 02214 //Public Function 3560 02215 int BipartiteGraphBicoloring::MinimalCoveringStarBicoloring() 02216 { 02217 if(CheckVertexColoring("MINIMAL_COVER_STAR")) 02218 { 02219 return(_TRUE); 02220 } 02221 02222 int i, j, k; 02223 02224 int _FOUND; 02225 02226 int i_ColorID, i_StarID; 02227 02228 int i_EdgeCount; 02229 02230 int i_OrderedVertexCount; 02231 02232 int i_FirstNeighborOne, i_FirstNeighborTwo; 02233 02234 int i_LeftVertexCount, i_RightVertexCount; 02235 02236 int i_LeftVertexCoverSize, i_RightVertexCoverSize; 02237 02238 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex; 02239 02240 vector<int> vi_CandidateColors; 02241 02242 vector<int> vi_EdgeStarMap, vi_LeftStarHubMap, vi_RightStarHubMap; 02243 02244 vector<int> vi_LeftTreated, vi_RightTreated; 02245 02246 vector<int> vi_FirstNeighborOne, vi_FirstNeighborTwo; 02247 02248 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 02249 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 02250 02251 i_EdgeCount = (signed) m_vi_Edges.size()/2; 02252 02253 vi_EdgeStarMap.clear(); 02254 vi_EdgeStarMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 02255 02256 m_mimi2_VertexEdgeMap.clear(); 02257 02258 k=_FALSE; 02259 02260 for(i=0; i<i_LeftVertexCount; i++) 02261 { 02262 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 02263 { 02264 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = k; 02265 02266 vi_EdgeStarMap[k] = k; 02267 02268 k++; 02269 } 02270 } 02271 02272 Timer m_T_Timer; 02273 02274 m_T_Timer.Start(); 02275 02276 CoverMinimalVertex(); 02277 02278 m_T_Timer.Stop(); 02279 02280 m_d_CoveringTime = m_T_Timer.GetWallTime(); 02281 02282 PresetCoveredVertexColors(); 02283 02284 #if DEBUG == 3560 02285 02286 cout<<"DEBUG 3560 | Combined Star Bicoloring | Left Vertex Cover Size = "<<m_vi_CoveredLeftVertices.size()<<"; Right Vertex Cover Size = "<<m_vi_CoveredRightVertices.size()<<endl; 02287 02288 #endif 02289 02290 i_LeftVertexCoverSize = (signed) m_vi_CoveredLeftVertices.size(); 02291 i_RightVertexCoverSize = (signed) m_vi_CoveredRightVertices.size(); 02292 02293 m_i_VertexColorCount = STEP_UP(i_LeftVertexCoverSize + i_RightVertexCoverSize); 02294 02295 vi_CandidateColors.clear(); 02296 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 02297 02298 vi_LeftStarHubMap.clear(); 02299 vi_LeftStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 02300 02301 vi_RightStarHubMap.clear(); 02302 vi_RightStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 02303 02304 vi_FirstNeighborOne.clear(); 02305 vi_FirstNeighborOne.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 02306 02307 vi_FirstNeighborTwo.clear(); 02308 vi_FirstNeighborTwo.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 02309 02310 vi_LeftTreated.clear(); 02311 vi_LeftTreated.resize((unsigned) i_RightVertexCount, _UNKNOWN); 02312 02313 vi_RightTreated.clear(); 02314 vi_RightTreated.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 02315 02316 #if DEBUG == 3560 02317 02318 cout<<endl; 02319 cout<<"DEBUG 3560 | Star Bicoloring | Initial Vertex Colors | Left Vertices"<<endl; 02320 cout<<endl; 02321 02322 for(i=0; i<i_LeftVertexCount; i++) 02323 { 02324 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<" ["<<m_vi_IncludedLeftVertices[i]<<"]"<<endl; 02325 } 02326 02327 cout<<endl; 02328 cout<<"DEBUG 3560 | Star Bicoloring | Initial Vertex Colors | Right Vertices"<<endl; 02329 cout<<endl; 02330 02331 for(i=0; i<i_RightVertexCount; i++) 02332 { 02333 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<" ["<<m_vi_IncludedRightVertices[i]<<"]"<<endl; 02334 } 02335 02336 cout<<endl; 02337 02338 #endif 02339 02340 i_OrderedVertexCount = (signed) m_vi_OrderedVertices.size(); 02341 02342 for(i=0; i<i_OrderedVertexCount; i++) 02343 { 02344 02345 #if DEBUG == 3560 02346 02347 cout<<"DEBUG 3560 | Star Bicoloring | Present Vertex | "<<STEP_UP(m_vi_OrderedVertices[i])<<endl; 02348 02349 #endif 02350 02351 if(m_vi_OrderedVertices[i] < i_LeftVertexCount) 02352 { 02353 if(m_vi_IncludedLeftVertices[m_vi_OrderedVertices[i]] == _FALSE) 02354 { 02355 continue; 02356 } 02357 02358 i_PresentVertex = m_vi_OrderedVertices[i]; 02359 02360 #if DEBUG == 3560 02361 02362 cout<<"DEBUG 3560 | Star Bicoloring | Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 02363 #endif 02364 02365 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 02366 { 02367 i_NeighboringVertex = m_vi_Edges[j]; 02368 02369 i_ColorID = m_vi_RightVertexColors[i_NeighboringVertex]; 02370 02371 if(i_ColorID == _UNKNOWN) 02372 { 02373 continue; 02374 } 02375 02376 if(i_ColorID == _FALSE) 02377 { 02378 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 02379 { 02380 i_SecondNeighboringVertex = m_vi_Edges[k]; 02381 02382 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02383 { 02384 continue; 02385 } 02386 02387 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] != _FALSE) 02388 { 02389 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 02390 } 02391 } 02392 } 02393 else 02394 { 02395 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 02396 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 02397 02398 if(i_FirstNeighborOne == i_PresentVertex) 02399 { 02400 if(vi_LeftTreated[i_FirstNeighborTwo] != i_PresentVertex) 02401 { 02402 for(k=m_vi_RightVertices[i_FirstNeighborTwo]; k<m_vi_RightVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 02403 { 02404 if(m_vi_Edges[k] == i_PresentVertex) 02405 { 02406 continue; 02407 } 02408 02409 if(m_vi_LeftVertexColors[m_vi_Edges[k]] == _UNKNOWN) 02410 { 02411 continue; 02412 } 02413 02414 vi_CandidateColors[m_vi_LeftVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 02415 02416 } 02417 02418 vi_LeftTreated[i_FirstNeighborTwo] = i_PresentVertex; 02419 } 02420 02421 for(k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[STEP_UP(m_vi_Edges[j])]; k++) 02422 { 02423 if(m_vi_Edges[k] == i_PresentVertex) 02424 { 02425 continue; 02426 } 02427 02428 if(m_vi_LeftVertexColors[m_vi_Edges[k]] == _UNKNOWN) 02429 { 02430 continue; 02431 } 02432 02433 vi_CandidateColors[m_vi_LeftVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 02434 } 02435 02436 vi_LeftTreated[i_NeighboringVertex] = i_PresentVertex; 02437 } 02438 else 02439 { 02440 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 02441 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 02442 02443 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 02444 { 02445 i_SecondNeighboringVertex = m_vi_Edges[k]; 02446 02447 if(i_SecondNeighboringVertex == i_PresentVertex) 02448 { 02449 continue; 02450 } 02451 02452 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02453 { 02454 continue; 02455 } 02456 02457 if(vi_LeftStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]] == i_SecondNeighboringVertex) 02458 { 02459 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 02460 } 02461 } 02462 } 02463 } 02464 } 02465 02466 for(j=_TRUE; j<STEP_UP(i_LeftVertexCoverSize); j++) 02467 { 02468 if(vi_CandidateColors[j] != i_PresentVertex) 02469 { 02470 m_vi_LeftVertexColors[i_PresentVertex] = j; 02471 02472 if(m_i_LeftVertexColorCount < j) 02473 { 02474 m_i_LeftVertexColorCount = j; 02475 } 02476 02477 break; 02478 } 02479 } 02480 02481 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 02482 { 02483 _FOUND = _FALSE; 02484 02485 i_NeighboringVertex = m_vi_Edges[j]; 02486 02487 if(m_vi_RightVertexColors[i_NeighboringVertex] == _UNKNOWN) 02488 { 02489 continue; 02490 } 02491 02492 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 02493 { 02494 i_SecondNeighboringVertex = m_vi_Edges[k]; 02495 02496 if(i_SecondNeighboringVertex == i_PresentVertex) 02497 { 02498 continue; 02499 } 02500 02501 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02502 { 02503 continue; 02504 } 02505 02506 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == m_vi_LeftVertexColors[i_PresentVertex]) 02507 { 02508 _FOUND = _TRUE; 02509 02510 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]; 02511 02512 vi_RightStarHubMap[i_StarID] = i_NeighboringVertex; 02513 02514 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 02515 02516 break; 02517 } 02518 } 02519 02520 if (!_FOUND) 02521 { 02522 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_RightVertexColors[i_NeighboringVertex]]; 02523 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_RightVertexColors[i_NeighboringVertex]]; 02524 02525 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 02526 { 02527 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_FirstNeighborTwo]]; 02528 02529 vi_LeftStarHubMap[i_StarID] = i_PresentVertex; 02530 02531 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 02532 } 02533 } 02534 } 02535 } 02536 else 02537 { 02538 if(m_vi_IncludedRightVertices[m_vi_OrderedVertices[i] - i_LeftVertexCount] == _FALSE) 02539 { 02540 continue; 02541 } 02542 02543 i_PresentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount; 02544 02545 #if DEBUG == 3560 02546 02547 cout<<"DEBUG 3560 | Star Bicoloring | Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 02548 #endif 02549 02550 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 02551 { 02552 i_NeighboringVertex = m_vi_Edges[j]; 02553 02554 i_ColorID = m_vi_LeftVertexColors[i_NeighboringVertex]; 02555 02556 if(i_ColorID == _UNKNOWN) 02557 { 02558 continue; 02559 } 02560 02561 if(i_ColorID == _FALSE) 02562 { 02563 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 02564 { 02565 i_SecondNeighboringVertex = m_vi_Edges[k]; 02566 02567 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02568 { 02569 continue; 02570 } 02571 02572 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] != _FALSE) 02573 { 02574 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 02575 } 02576 } 02577 } 02578 else 02579 { 02580 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 02581 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 02582 02583 if(i_FirstNeighborOne == i_PresentVertex) 02584 { 02585 if(vi_RightTreated[i_FirstNeighborTwo] != i_PresentVertex) 02586 { 02587 for(k=m_vi_LeftVertices[i_FirstNeighborTwo]; k<m_vi_LeftVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 02588 { 02589 if(m_vi_Edges[k] == i_PresentVertex) 02590 { 02591 continue; 02592 } 02593 02594 if(m_vi_RightVertexColors[m_vi_Edges[k]] == _UNKNOWN) 02595 { 02596 continue; 02597 } 02598 02599 vi_CandidateColors[m_vi_RightVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 02600 02601 } 02602 02603 vi_RightTreated[i_FirstNeighborTwo] = i_PresentVertex; 02604 } 02605 02606 for(k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[STEP_UP(m_vi_Edges[j])]; k++) 02607 { 02608 if(m_vi_Edges[k] == i_PresentVertex) 02609 { 02610 continue; 02611 } 02612 02613 if(m_vi_RightVertexColors[m_vi_Edges[k]] == _UNKNOWN) 02614 { 02615 continue; 02616 } 02617 02618 vi_CandidateColors[m_vi_RightVertexColors[m_vi_Edges[k]]] = i_PresentVertex; 02619 02620 } 02621 02622 vi_RightTreated[i_NeighboringVertex] = i_PresentVertex; 02623 } 02624 else 02625 { 02626 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 02627 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 02628 02629 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 02630 { 02631 i_SecondNeighboringVertex = m_vi_Edges[k]; 02632 02633 if(i_SecondNeighboringVertex == i_PresentVertex) 02634 { 02635 continue; 02636 } 02637 02638 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02639 { 02640 continue; 02641 } 02642 02643 if(vi_RightStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]] == i_SecondNeighboringVertex) 02644 { 02645 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 02646 02647 } 02648 } 02649 } 02650 } 02651 } 02652 02653 for(j=STEP_UP(i_LeftVertexCoverSize); j<m_i_VertexColorCount; j++) 02654 { 02655 if(vi_CandidateColors[j] != i_PresentVertex) 02656 { 02657 m_vi_RightVertexColors[i_PresentVertex] = j; 02658 02659 if(m_i_RightVertexColorCount < j) 02660 { 02661 m_i_RightVertexColorCount = j; 02662 } 02663 02664 break; 02665 } 02666 } 02667 02668 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 02669 { 02670 _FOUND = _FALSE; 02671 02672 i_NeighboringVertex = m_vi_Edges[j]; 02673 02674 if(m_vi_LeftVertexColors[i_NeighboringVertex] == _UNKNOWN) 02675 { 02676 continue; 02677 } 02678 02679 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 02680 { 02681 i_SecondNeighboringVertex = m_vi_Edges[k]; 02682 02683 if(i_SecondNeighboringVertex == i_PresentVertex) 02684 { 02685 continue; 02686 } 02687 02688 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02689 { 02690 continue; 02691 } 02692 02693 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == m_vi_RightVertexColors[i_PresentVertex]) 02694 { 02695 _FOUND = _TRUE; 02696 02697 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]; 02698 02699 vi_LeftStarHubMap[i_StarID] = i_NeighboringVertex; 02700 02701 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 02702 02703 break; 02704 } 02705 } 02706 02707 if (!_FOUND) 02708 { 02709 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_LeftVertexColors[i_NeighboringVertex]]; 02710 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_LeftVertexColors[i_NeighboringVertex]]; 02711 02712 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 02713 { 02714 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_FirstNeighborTwo][i_PresentVertex]]; 02715 02716 vi_RightStarHubMap[i_StarID] = i_PresentVertex; 02717 02718 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 02719 } 02720 } 02721 } 02722 } 02723 } 02724 02725 for(i=0; i<i_RightVertexCount; i++) 02726 { 02727 if(m_vi_RightVertexColors[i] == FALSE) 02728 { 02729 m_vi_RightVertexColors[i] = m_i_VertexColorCount; 02730 } 02731 } 02732 02733 FixMinimalCoverStarBicoloring(); 02734 02735 i_LeftVertexDefaultColor = _FALSE; 02736 i_RightVertexDefaultColor = _FALSE; 02737 02738 for(i=0; i<i_LeftVertexCount; i++) 02739 { 02740 if(m_vi_LeftVertexColors[i] == _FALSE) 02741 { 02742 i_LeftVertexDefaultColor = _TRUE; 02743 } 02744 } 02745 02746 for(i=0; i<i_RightVertexCount; i++) 02747 { 02748 if(m_vi_RightVertexColors[i] == m_i_VertexColorCount) 02749 { 02750 i_RightVertexDefaultColor = _TRUE; 02751 } 02752 } 02753 02754 if(m_i_LeftVertexColorCount == _UNKNOWN) 02755 { 02756 m_i_LeftVertexColorCount = _TRUE; 02757 } 02758 else 02759 { 02760 m_i_LeftVertexColorCount = m_i_LeftVertexColorCount + i_LeftVertexDefaultColor; 02761 } 02762 02763 if(m_i_RightVertexColorCount == _UNKNOWN) 02764 { 02765 m_i_RightVertexColorCount = _TRUE; 02766 } 02767 else 02768 { 02769 m_i_RightVertexColorCount = m_i_RightVertexColorCount + i_RightVertexDefaultColor - i_LeftVertexCoverSize; 02770 } 02771 02772 m_i_VertexColorCount = m_i_LeftVertexColorCount + m_i_RightVertexColorCount; 02773 02774 #if DEBUG == 3560 02775 02776 cout<<endl; 02777 cout<<"DEBUG 3560 | Right Star Bicoloring | Vertex Colors | Left Vertices"<<endl; 02778 cout<<endl; 02779 02780 for(i=0; i<i_LeftVertexCount; i++) 02781 { 02782 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 02783 } 02784 02785 cout<<endl; 02786 cout<<"DEBUG 3560 | Right Star Bicoloring | Vertex Colors | Right Vertices"<<endl; 02787 cout<<endl; 02788 02789 for(i=0; i<i_RightVertexCount; i++) 02790 { 02791 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 02792 } 02793 02794 #endif 02795 02796 return(_TRUE); 02797 02798 } 02799 02800 02801 02802 //Public Function 3561 02803 int BipartiteGraphBicoloring::ImplicitCoveringConservativeStarBicoloring() 02804 { 02805 if(CheckVertexColoring("IMPLICIT_COVER_CONSERVATIVE_STAR")) 02806 { 02807 return(_TRUE); 02808 } 02809 02810 int i, j, k; 02811 02812 int _FOUND; 02813 02814 int i_ColorID, i_StarID; 02815 02816 int i_EdgeCount, i_IncludedEdgeCount; 02817 02818 int i_FirstNeighborOne, i_FirstNeighborTwo; 02819 02820 int i_LeftVertexCount, i_RightVertexCount; 02821 02822 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex; 02823 02824 int i_PresentEdge; 02825 02826 vector<int> vi_IncludedEdges; 02827 02828 vector<int> vi_CandidateColors; 02829 02830 vector<int> vi_EdgeStarMap, vi_LeftStarHubMap, vi_RightStarHubMap; 02831 02832 vector<int> vi_LeftTreated, vi_RightTreated; 02833 02834 vector<int> vi_FirstNeighborOne, vi_FirstNeighborTwo; 02835 02836 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 02837 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 02838 02839 i_EdgeCount = (signed) m_vi_Edges.size()/2; 02840 02841 vi_EdgeStarMap.clear(); 02842 vi_EdgeStarMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 02843 02844 m_mimi2_VertexEdgeMap.clear(); 02845 02846 i_IncludedEdgeCount =_FALSE; 02847 02848 for(i=0; i<i_LeftVertexCount; i++) 02849 { 02850 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 02851 { 02852 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = i_IncludedEdgeCount; 02853 02854 vi_EdgeStarMap[i_IncludedEdgeCount] = i_IncludedEdgeCount; 02855 02856 i_IncludedEdgeCount++; 02857 } 02858 } 02859 02860 m_i_VertexColorCount = STEP_UP(i_LeftVertexCount + i_RightVertexCount); 02861 02862 vi_IncludedEdges.clear(); 02863 vi_IncludedEdges.resize((unsigned) i_EdgeCount, _FALSE); 02864 02865 vi_CandidateColors.clear(); 02866 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 02867 02868 m_vi_LeftVertexColors.clear(); 02869 m_vi_LeftVertexColors.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 02870 02871 m_vi_RightVertexColors.clear(); 02872 m_vi_RightVertexColors.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 02873 02874 vi_LeftStarHubMap.clear(); 02875 vi_LeftStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 02876 02877 vi_RightStarHubMap.clear(); 02878 vi_RightStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 02879 02880 vi_FirstNeighborOne.clear(); 02881 vi_FirstNeighborOne.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 02882 02883 vi_FirstNeighborTwo.clear(); 02884 vi_FirstNeighborTwo.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 02885 02886 vi_LeftTreated.clear(); 02887 vi_LeftTreated.resize((unsigned) i_RightVertexCount, _UNKNOWN); 02888 02889 vi_RightTreated.clear(); 02890 vi_RightTreated.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 02891 02892 i_IncludedEdgeCount = _FALSE; 02893 02894 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = _UNKNOWN; 02895 02896 for(i=0; i<i_LeftVertexCount + i_RightVertexCount; i++) 02897 { 02898 02899 #if DEBUG == 3561 02900 02901 cout<<"DEBUG 3561 | Star Bicoloring | Present Vertex | "<<STEP_UP(m_vi_OrderedVertices[i])<<endl; 02902 02903 #endif 02904 02905 if(m_vi_OrderedVertices[i] < i_LeftVertexCount) 02906 { 02907 i_PresentVertex = m_vi_OrderedVertices[i]; 02908 02909 _FOUND = _FALSE; 02910 02911 for(j= m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 02912 { 02913 i_PresentEdge = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]; 02914 02915 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 02916 { 02917 _FOUND = _TRUE; 02918 02919 break; 02920 } 02921 } 02922 02923 if(_FOUND == _FALSE) 02924 { 02925 02926 #if DEBUG == 3561 02927 02928 cout<<"DEBUG 3561 | Star Bicoloring | Ignored Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 02929 02930 #endif 02931 02932 continue; 02933 } 02934 02935 #if DEBUG == 3561 02936 02937 cout<<"DEBUG 3561 | Star Bicoloring | Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 02938 02939 #endif 02940 02941 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 02942 { 02943 i_NeighboringVertex = m_vi_Edges[j]; 02944 02945 i_ColorID = m_vi_RightVertexColors[i_NeighboringVertex]; 02946 02947 if(i_ColorID == _UNKNOWN) 02948 { 02949 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 02950 { 02951 i_SecondNeighboringVertex = m_vi_Edges[k]; 02952 02953 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02954 { 02955 continue; 02956 } 02957 02958 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 02959 } 02960 02961 continue; 02962 } 02963 else 02964 { 02965 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 02966 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 02967 02968 if(i_FirstNeighborOne == i_PresentVertex) 02969 { 02970 if(vi_LeftTreated[i_FirstNeighborTwo] != i_PresentVertex) 02971 { 02972 for(k=m_vi_RightVertices[i_FirstNeighborTwo]; k<m_vi_RightVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 02973 { 02974 i_SecondNeighboringVertex = m_vi_Edges[k]; 02975 02976 if(i_SecondNeighboringVertex == i_PresentVertex) 02977 { 02978 continue; 02979 } 02980 02981 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 02982 { 02983 continue; 02984 } 02985 02986 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 02987 02988 #if DEBUG == 3561 02989 02990 cout<<"DEBUG 3561 | Star Bicoloring | Visited Same Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(i_FirstNeighborTwo)<<endl; 02991 02992 #endif 02993 } 02994 02995 vi_LeftTreated[i_FirstNeighborTwo] = i_PresentVertex; 02996 } 02997 02998 for(k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[STEP_UP(m_vi_Edges[j])]; k++) 02999 { 03000 i_SecondNeighboringVertex = m_vi_Edges[k]; 03001 03002 if(i_SecondNeighboringVertex == i_PresentVertex) 03003 { 03004 continue; 03005 } 03006 03007 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03008 { 03009 continue; 03010 } 03011 03012 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03013 03014 #if DEBUG == 3561 03015 03016 cout<<"DEBUG 3561 | Star Bicoloring | Restricted Same Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(m_vi_Edges[j])<<endl; 03017 03018 #endif 03019 } 03020 03021 vi_LeftTreated[i_NeighboringVertex] = i_PresentVertex; 03022 } 03023 else 03024 { 03025 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 03026 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 03027 03028 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 03029 { 03030 03031 i_SecondNeighboringVertex = m_vi_Edges[k]; 03032 03033 if(i_SecondNeighboringVertex == i_PresentVertex) 03034 { 03035 continue; 03036 } 03037 03038 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03039 { 03040 continue; 03041 } 03042 03043 if(vi_LeftStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]] == i_SecondNeighboringVertex) 03044 { 03045 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03046 03047 #if DEBUG == 3561 03048 03049 cout<<"DEBUG 3561 | Star Bicoloring | Restricted Hub Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(i_NeighboringVertex)<<endl; 03050 03051 #endif 03052 } 03053 } 03054 } 03055 } 03056 } 03057 03058 for(j=_TRUE; j<STEP_UP(i_LeftVertexCount); j++) 03059 { 03060 if(vi_CandidateColors[j] != i_PresentVertex) 03061 { 03062 m_vi_LeftVertexColors[i_PresentVertex] = j; 03063 03064 if(m_i_LeftVertexColorCount < j) 03065 { 03066 m_i_LeftVertexColorCount = j; 03067 } 03068 03069 for(k=m_vi_LeftVertices[i_PresentVertex]; k<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; k++) 03070 { 03071 i_PresentEdge = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[k]]; 03072 03073 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 03074 { 03075 vi_IncludedEdges[i_PresentEdge] = _TRUE; 03076 03077 i_IncludedEdgeCount++; 03078 } 03079 } 03080 03081 break; 03082 } 03083 } 03084 03085 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 03086 { 03087 _FOUND = _FALSE; 03088 03089 i_NeighboringVertex = m_vi_Edges[j]; 03090 03091 if(m_vi_RightVertexColors[i_NeighboringVertex] == _UNKNOWN) 03092 { 03093 continue; 03094 } 03095 03096 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 03097 { 03098 i_SecondNeighboringVertex = m_vi_Edges[k]; 03099 03100 if(i_SecondNeighboringVertex == i_PresentVertex) 03101 { 03102 continue; 03103 } 03104 03105 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03106 { 03107 continue; 03108 } 03109 03110 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == m_vi_LeftVertexColors[i_PresentVertex]) 03111 { 03112 _FOUND = _TRUE; 03113 03114 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]; 03115 03116 vi_RightStarHubMap[i_StarID] = i_NeighboringVertex; 03117 03118 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 03119 03120 break; 03121 } 03122 } 03123 03124 if (!_FOUND) 03125 { 03126 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_RightVertexColors[i_NeighboringVertex]]; 03127 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_RightVertexColors[i_NeighboringVertex]]; 03128 03129 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 03130 { 03131 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_FirstNeighborTwo]]; 03132 03133 vi_LeftStarHubMap[i_StarID] = i_PresentVertex; 03134 03135 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 03136 } 03137 } 03138 } 03139 } 03140 else 03141 { 03142 i_PresentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount; 03143 03144 _FOUND = _FALSE; 03145 03146 for(j= m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 03147 { 03148 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]; 03149 03150 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 03151 { 03152 _FOUND = _TRUE; 03153 03154 break; 03155 } 03156 } 03157 03158 if(_FOUND == _FALSE) 03159 { 03160 03161 #if DEBUG == 3561 03162 03163 cout<<"DEBUG 3561 | Star Bicoloring | Ignored Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 03164 #endif 03165 03166 continue; 03167 } 03168 03169 #if DEBUG == 3561 03170 03171 cout<<"DEBUG 3561 | Star Bicoloring | Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 03172 03173 #endif 03174 03175 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 03176 { 03177 i_NeighboringVertex = m_vi_Edges[j]; 03178 03179 i_ColorID = m_vi_LeftVertexColors[i_NeighboringVertex]; 03180 03181 if(i_ColorID == _UNKNOWN) 03182 { 03183 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 03184 { 03185 i_SecondNeighboringVertex = m_vi_Edges[k]; 03186 03187 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03188 { 03189 continue; 03190 } 03191 03192 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03193 } 03194 03195 continue; 03196 } 03197 else 03198 { 03199 03200 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 03201 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 03202 03203 if(i_FirstNeighborOne == i_PresentVertex) 03204 { 03205 if(vi_RightTreated[i_FirstNeighborTwo] != i_PresentVertex) 03206 { 03207 for(k=m_vi_LeftVertices[i_FirstNeighborTwo]; k<m_vi_LeftVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 03208 { 03209 i_SecondNeighboringVertex = m_vi_Edges[k]; 03210 03211 if(i_SecondNeighboringVertex == i_PresentVertex) 03212 { 03213 continue; 03214 } 03215 03216 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03217 { 03218 continue; 03219 } 03220 03221 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03222 03223 #if DEBUG == 3561 03224 03225 cout<<"DEBUG 3561 | Star Bicoloring | Visited Same Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Right Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(i_FirstNeighborTwo)<<endl; 03226 03227 #endif 03228 } 03229 03230 vi_RightTreated[i_FirstNeighborTwo] = i_PresentVertex; 03231 } 03232 03233 for(k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[STEP_UP(m_vi_Edges[j])]; k++) 03234 { 03235 i_SecondNeighboringVertex = m_vi_Edges[k]; 03236 03237 if(i_SecondNeighboringVertex == i_PresentVertex) 03238 { 03239 continue; 03240 } 03241 03242 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03243 { 03244 continue; 03245 } 03246 03247 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03248 03249 #if DEBUG == 3561 03250 03251 cout<<"DEBUG 3561 | Star Bicoloring | Restricted Same Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Right Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(m_vi_Edges[j])<<endl; 03252 03253 #endif 03254 } 03255 03256 vi_RightTreated[i_NeighboringVertex] = i_PresentVertex; 03257 } 03258 else 03259 { 03260 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 03261 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 03262 03263 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 03264 { 03265 i_SecondNeighboringVertex = m_vi_Edges[k]; 03266 03267 if(i_SecondNeighboringVertex == i_PresentVertex) 03268 { 03269 continue; 03270 } 03271 03272 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03273 { 03274 continue; 03275 } 03276 03277 if(vi_RightStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]] == i_SecondNeighboringVertex) 03278 { 03279 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03280 03281 #if DEBUG == 3561 03282 03283 cout<<"DEBUG 3561 | Star Bicoloring | Restricted Hub Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(i_NeighboringVertex)<<endl; 03284 03285 #endif 03286 } 03287 } 03288 } 03289 } 03290 } 03291 03292 for(j=STEP_UP(i_LeftVertexCount); j<m_i_VertexColorCount; j++) 03293 { 03294 if(vi_CandidateColors[j] != i_PresentVertex) 03295 { 03296 m_vi_RightVertexColors[i_PresentVertex] = j; 03297 03298 if(m_i_RightVertexColorCount < j) 03299 { 03300 m_i_RightVertexColorCount = j; 03301 } 03302 03303 for(k=m_vi_RightVertices[i_PresentVertex]; k<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; k++) 03304 { 03305 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[k]][i_PresentVertex]; 03306 03307 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 03308 { 03309 vi_IncludedEdges[i_PresentEdge] = _TRUE; 03310 03311 i_IncludedEdgeCount++; 03312 } 03313 } 03314 03315 break; 03316 } 03317 } 03318 03319 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 03320 { 03321 _FOUND = _FALSE; 03322 03323 i_NeighboringVertex = m_vi_Edges[j]; 03324 03325 if(m_vi_LeftVertexColors[i_NeighboringVertex] == _UNKNOWN) 03326 { 03327 continue; 03328 } 03329 03330 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 03331 { 03332 i_SecondNeighboringVertex = m_vi_Edges[k]; 03333 03334 if(i_SecondNeighboringVertex == i_PresentVertex) 03335 { 03336 continue; 03337 } 03338 03339 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03340 { 03341 continue; 03342 } 03343 03344 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == m_vi_RightVertexColors[i_PresentVertex]) 03345 { 03346 _FOUND = _TRUE; 03347 03348 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]; 03349 03350 vi_LeftStarHubMap[i_StarID] = i_NeighboringVertex; 03351 03352 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 03353 03354 break; 03355 } 03356 } 03357 03358 if (!_FOUND) 03359 { 03360 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_LeftVertexColors[i_NeighboringVertex]]; 03361 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_LeftVertexColors[i_NeighboringVertex]]; 03362 03363 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 03364 { 03365 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_FirstNeighborTwo][i_PresentVertex]]; 03366 03367 vi_RightStarHubMap[i_StarID] = i_PresentVertex; 03368 03369 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 03370 } 03371 } 03372 } 03373 } 03374 03375 if(i_IncludedEdgeCount >= i_EdgeCount) 03376 { 03377 break; 03378 } 03379 } 03380 03381 i_LeftVertexDefaultColor = _FALSE; 03382 i_RightVertexDefaultColor = _FALSE; 03383 03384 for(i=0; i<i_LeftVertexCount; i++) 03385 { 03386 if(m_vi_LeftVertexColors[i] == _UNKNOWN) 03387 { 03388 m_vi_LeftVertexColors[i] = _FALSE; 03389 03390 i_LeftVertexDefaultColor = _TRUE; 03391 } 03392 } 03393 03394 for(i=0; i<i_RightVertexCount; i++) 03395 { 03396 if(m_vi_RightVertexColors[i] == _UNKNOWN) 03397 { 03398 m_vi_RightVertexColors[i] = m_i_VertexColorCount; 03399 03400 i_RightVertexDefaultColor = _TRUE; 03401 } 03402 } 03403 03404 if(m_i_LeftVertexColorCount == _UNKNOWN) 03405 { 03406 m_i_LeftVertexColorCount = _TRUE; 03407 } 03408 else 03409 { 03410 m_i_LeftVertexColorCount = m_i_LeftVertexColorCount + i_LeftVertexDefaultColor; 03411 } 03412 03413 if(m_i_RightVertexColorCount == _UNKNOWN) 03414 { 03415 m_i_RightVertexColorCount = _TRUE; 03416 } 03417 else 03418 { 03419 m_i_RightVertexColorCount = m_i_RightVertexColorCount + i_RightVertexDefaultColor - i_LeftVertexCount; 03420 } 03421 03422 m_i_VertexColorCount = m_i_LeftVertexColorCount + m_i_RightVertexColorCount; 03423 03424 #if DEBUG == 3561 03425 03426 cout<<endl; 03427 cout<<"DEBUG 3561 | Star Bicoloring | Vertex Colors | Left Vertices"<<endl; 03428 cout<<endl; 03429 03430 for(i=0; i<i_LeftVertexCount; i++) 03431 { 03432 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 03433 } 03434 03435 cout<<endl; 03436 cout<<"DEBUG 3561 | Star Bicoloring | Vertex Colors | Right Vertices"<<endl; 03437 cout<<endl; 03438 03439 for(i=0; i<i_RightVertexCount; i++) 03440 { 03441 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 03442 } 03443 03444 #endif 03445 03446 return(_TRUE); 03447 } 03448 03449 03450 //Public Function 3562 03451 int BipartiteGraphBicoloring::ImplicitCoveringStarBicoloring() 03452 { 03453 if(CheckVertexColoring("IMPLICIT_COVER_STAR")) 03454 { 03455 return(_TRUE); 03456 } 03457 03458 int i, j, k; 03459 03460 int _FOUND; 03461 03462 int i_ColorID, i_StarID; 03463 03464 int i_EdgeCount, i_IncludedEdgeCount; 03465 03466 int i_FirstNeighborOne, i_FirstNeighborTwo; 03467 03468 int i_LeftVertexCount, i_RightVertexCount; 03469 03470 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex; 03471 03472 int i_PresentEdge; 03473 03474 vector<int> vi_IncludedEdges; 03475 03476 vector<int> vi_CandidateColors; 03477 03478 vector<int> vi_EdgeStarMap, vi_LeftStarHubMap, vi_RightStarHubMap; 03479 03480 vector<int> vi_LeftTreated, vi_RightTreated; 03481 03482 vector<int> vi_FirstNeighborOne, vi_FirstNeighborTwo; 03483 03484 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 03485 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 03486 03487 i_EdgeCount = (signed) m_vi_Edges.size()/2; 03488 03489 vi_EdgeStarMap.clear(); 03490 vi_EdgeStarMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 03491 03492 m_mimi2_VertexEdgeMap.clear(); 03493 03494 i_IncludedEdgeCount =_FALSE; 03495 03496 for(i=0; i<i_LeftVertexCount; i++) 03497 { 03498 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 03499 { 03500 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = i_IncludedEdgeCount; 03501 03502 vi_EdgeStarMap[i_IncludedEdgeCount] = i_IncludedEdgeCount; 03503 03504 i_IncludedEdgeCount++; 03505 } 03506 } 03507 03508 m_i_VertexColorCount = STEP_UP(i_LeftVertexCount + i_RightVertexCount); 03509 03510 vi_IncludedEdges.clear(); 03511 vi_IncludedEdges.resize((unsigned) i_EdgeCount, _FALSE); 03512 03513 vi_CandidateColors.clear(); 03514 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 03515 03516 m_vi_LeftVertexColors.clear(); 03517 m_vi_LeftVertexColors.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 03518 03519 m_vi_RightVertexColors.clear(); 03520 m_vi_RightVertexColors.resize((unsigned) i_RightVertexCount, _UNKNOWN); 03521 03522 vi_LeftStarHubMap.clear(); 03523 vi_LeftStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 03524 03525 vi_RightStarHubMap.clear(); 03526 vi_RightStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 03527 03528 vi_FirstNeighborOne.clear(); 03529 vi_FirstNeighborOne.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 03530 03531 vi_FirstNeighborTwo.clear(); 03532 vi_FirstNeighborTwo.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 03533 03534 vi_LeftTreated.clear(); 03535 vi_LeftTreated.resize((unsigned) i_RightVertexCount, _UNKNOWN); 03536 03537 vi_RightTreated.clear(); 03538 vi_RightTreated.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 03539 03540 i_IncludedEdgeCount = _FALSE; 03541 03542 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = _UNKNOWN; 03543 03544 for(i=0; i<i_LeftVertexCount + i_RightVertexCount; i++) 03545 { 03546 03547 #if DEBUG == 3562 03548 03549 cout<<"DEBUG 3562 | Star Bicoloring | Present Vertex | "<<STEP_UP(m_vi_OrderedVertices[i])<<endl; 03550 03551 #endif 03552 03553 if(m_vi_OrderedVertices[i] < i_LeftVertexCount) 03554 { 03555 i_PresentVertex = m_vi_OrderedVertices[i]; 03556 03557 _FOUND = _FALSE; 03558 03559 for(j= m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 03560 { 03561 i_PresentEdge = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]; 03562 03563 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 03564 { 03565 _FOUND = _TRUE; 03566 03567 break; 03568 } 03569 } 03570 03571 if(_FOUND == _FALSE) 03572 { 03573 03574 #if DEBUG == 3562 03575 03576 cout<<"DEBUG 3562 | Star Bicoloring | Ignored Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 03577 #endif 03578 03579 continue; 03580 } 03581 03582 #if DEBUG == 3562 03583 03584 cout<<"DEBUG 3562 | Star Bicoloring | Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 03585 #endif 03586 03587 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 03588 { 03589 i_NeighboringVertex = m_vi_Edges[j]; 03590 03591 i_ColorID = m_vi_RightVertexColors[i_NeighboringVertex]; 03592 03593 if(i_ColorID == _UNKNOWN) 03594 { 03595 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 03596 { 03597 i_SecondNeighboringVertex = m_vi_Edges[k]; 03598 03599 if(i_SecondNeighboringVertex == i_PresentVertex) 03600 { 03601 continue; 03602 } 03603 03604 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03605 { 03606 continue; 03607 } 03608 03609 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03610 } 03611 } 03612 else 03613 { 03614 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 03615 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 03616 03617 if(i_FirstNeighborOne == i_PresentVertex) 03618 { 03619 if(vi_LeftTreated[i_FirstNeighborTwo] != i_PresentVertex) 03620 { 03621 for(k=m_vi_RightVertices[i_FirstNeighborTwo]; k<m_vi_RightVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 03622 { 03623 i_SecondNeighboringVertex = m_vi_Edges[k]; 03624 03625 if(i_SecondNeighboringVertex == i_PresentVertex) 03626 { 03627 continue; 03628 } 03629 03630 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03631 { 03632 continue; 03633 } 03634 03635 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03636 03637 #if DEBUG == 3562 03638 03639 cout<<"DEBUG 3562 | Star Bicoloring | Visited Same Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(i_FirstNeighborTwo)<<endl; 03640 03641 #endif 03642 } 03643 03644 vi_LeftTreated[i_FirstNeighborTwo] = i_PresentVertex; 03645 } 03646 03647 for(k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[STEP_UP(m_vi_Edges[j])]; k++) 03648 { 03649 i_SecondNeighboringVertex = m_vi_Edges[k]; 03650 03651 if(i_SecondNeighboringVertex == i_PresentVertex) 03652 { 03653 continue; 03654 } 03655 03656 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03657 { 03658 continue; 03659 } 03660 03661 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03662 03663 #if DEBUG == 3562 03664 03665 cout<<"DEBUG 3562 | Star Bicoloring | Restricted Same Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(m_vi_Edges[j])<<endl; 03666 03667 #endif 03668 } 03669 03670 vi_LeftTreated[i_NeighboringVertex] = i_PresentVertex; 03671 03672 } 03673 else 03674 { 03675 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 03676 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 03677 03678 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 03679 { 03680 i_SecondNeighboringVertex = m_vi_Edges[k]; 03681 03682 if(i_SecondNeighboringVertex == i_PresentVertex) 03683 { 03684 continue; 03685 } 03686 03687 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03688 { 03689 continue; 03690 } 03691 03692 if(vi_LeftStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]] == i_SecondNeighboringVertex) 03693 { 03694 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03695 03696 #if DEBUG == 3562 03697 03698 cout<<"DEBUG 3562 | Star Bicoloring | Restricted Hub Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(i_NeighboringVertex)<<endl; 03699 03700 #endif 03701 } 03702 } 03703 } 03704 } 03705 } 03706 03707 for(j=_TRUE; j<STEP_UP(i_LeftVertexCount); j++) 03708 { 03709 if(vi_CandidateColors[j] != i_PresentVertex) 03710 { 03711 m_vi_LeftVertexColors[i_PresentVertex] = j; 03712 03713 if(m_i_LeftVertexColorCount < j) 03714 { 03715 m_i_LeftVertexColorCount = j; 03716 } 03717 03718 for(k=m_vi_LeftVertices[i_PresentVertex]; k<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; k++) 03719 { 03720 i_PresentEdge = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[k]]; 03721 03722 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 03723 { 03724 vi_IncludedEdges[i_PresentEdge] = _TRUE; 03725 03726 i_IncludedEdgeCount++; 03727 } 03728 } 03729 03730 break; 03731 } 03732 } 03733 03734 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 03735 { 03736 _FOUND = _FALSE; 03737 03738 i_NeighboringVertex = m_vi_Edges[j]; 03739 03740 if(m_vi_RightVertexColors[i_NeighboringVertex] == _UNKNOWN) 03741 { 03742 continue; 03743 } 03744 03745 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 03746 { 03747 i_SecondNeighboringVertex = m_vi_Edges[k]; 03748 03749 if(i_SecondNeighboringVertex == i_PresentVertex) 03750 { 03751 continue; 03752 } 03753 03754 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03755 { 03756 continue; 03757 } 03758 03759 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == m_vi_LeftVertexColors[i_PresentVertex]) 03760 { 03761 _FOUND = _TRUE; 03762 03763 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]; 03764 03765 vi_RightStarHubMap[i_StarID] = i_NeighboringVertex; 03766 03767 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 03768 03769 break; 03770 } 03771 } 03772 03773 if (!_FOUND) 03774 { 03775 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_RightVertexColors[i_NeighboringVertex]]; 03776 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_RightVertexColors[i_NeighboringVertex]]; 03777 03778 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 03779 { 03780 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_FirstNeighborTwo]]; 03781 03782 vi_LeftStarHubMap[i_StarID] = i_PresentVertex; 03783 03784 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 03785 } 03786 } 03787 } 03788 } 03789 else 03790 { 03791 i_PresentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount; 03792 03793 _FOUND = _FALSE; 03794 03795 for(j= m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 03796 { 03797 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]; 03798 03799 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 03800 { 03801 _FOUND = _TRUE; 03802 03803 break; 03804 } 03805 } 03806 03807 if(_FOUND == _FALSE) 03808 { 03809 03810 #if DEBUG == 3562 03811 03812 cout<<"DEBUG 3562 | Star Bicoloring | Ignored Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 03813 #endif 03814 03815 continue; 03816 } 03817 03818 #if DEBUG == 3562 03819 03820 cout<<"DEBUG 3562 | Star Bicoloring | Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 03821 03822 #endif 03823 03824 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 03825 { 03826 i_NeighboringVertex = m_vi_Edges[j]; 03827 03828 i_ColorID = m_vi_LeftVertexColors[i_NeighboringVertex]; 03829 03830 if(i_ColorID == _UNKNOWN) 03831 { 03832 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 03833 { 03834 i_SecondNeighboringVertex = m_vi_Edges[k]; 03835 03836 if(i_SecondNeighboringVertex == i_PresentVertex) 03837 { 03838 continue; 03839 } 03840 03841 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03842 { 03843 continue; 03844 } 03845 03846 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03847 } 03848 } 03849 else 03850 { 03851 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 03852 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 03853 03854 if(i_FirstNeighborOne == i_PresentVertex) 03855 { 03856 if(vi_RightTreated[i_FirstNeighborTwo] != i_PresentVertex) 03857 { 03858 for(k=m_vi_LeftVertices[i_FirstNeighborTwo]; k<m_vi_LeftVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 03859 { 03860 i_SecondNeighboringVertex = m_vi_Edges[k]; 03861 03862 if(i_SecondNeighboringVertex == i_PresentVertex) 03863 { 03864 continue; 03865 } 03866 03867 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03868 { 03869 continue; 03870 } 03871 03872 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03873 03874 #if DEBUG == 3562 03875 03876 cout<<"DEBUG 3562 | Star Bicoloring | Visited Same Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Right Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(i_FirstNeighborTwo)<<endl; 03877 03878 #endif 03879 } 03880 03881 vi_RightTreated[i_FirstNeighborTwo] = i_PresentVertex; 03882 } 03883 03884 for(k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[STEP_UP(m_vi_Edges[j])]; k++) 03885 { 03886 i_SecondNeighboringVertex = m_vi_Edges[k]; 03887 03888 if(i_SecondNeighboringVertex == i_PresentVertex) 03889 { 03890 continue; 03891 } 03892 03893 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03894 { 03895 continue; 03896 } 03897 03898 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03899 03900 #if DEBUG == 3562 03901 03902 cout<<"DEBUG 3562 | Star Bicoloring | Restricted Same Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Right Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(m_vi_Edges[j])<<endl; 03903 03904 #endif 03905 } 03906 03907 vi_RightTreated[i_NeighboringVertex] = i_PresentVertex; 03908 } 03909 else 03910 { 03911 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 03912 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 03913 03914 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 03915 { 03916 i_SecondNeighboringVertex = m_vi_Edges[k]; 03917 03918 if(i_SecondNeighboringVertex == i_PresentVertex) 03919 { 03920 continue; 03921 } 03922 03923 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03924 { 03925 continue; 03926 } 03927 03928 if(vi_RightStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]] == i_SecondNeighboringVertex) 03929 { 03930 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 03931 03932 #if DEBUG == 3562 03933 03934 cout<<"DEBUG 3562 | Star Bicoloring | Restricted Hub Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(i_NeighboringVertex)<<endl; 03935 03936 #endif 03937 } 03938 } 03939 } 03940 } 03941 } 03942 03943 for(j=STEP_UP(i_LeftVertexCount); j<m_i_VertexColorCount; j++) 03944 { 03945 if(vi_CandidateColors[j] != i_PresentVertex) 03946 { 03947 m_vi_RightVertexColors[i_PresentVertex] = j; 03948 03949 if(m_i_RightVertexColorCount < j) 03950 { 03951 m_i_RightVertexColorCount = j; 03952 } 03953 03954 for(k=m_vi_RightVertices[i_PresentVertex]; k<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; k++) 03955 { 03956 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[k]][i_PresentVertex]; 03957 03958 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 03959 { 03960 vi_IncludedEdges[i_PresentEdge] = _TRUE; 03961 03962 i_IncludedEdgeCount++; 03963 } 03964 } 03965 03966 break; 03967 } 03968 } 03969 03970 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 03971 { 03972 _FOUND = _FALSE; 03973 03974 i_NeighboringVertex = m_vi_Edges[j]; 03975 03976 if(m_vi_LeftVertexColors[i_NeighboringVertex] == _UNKNOWN) 03977 { 03978 continue; 03979 } 03980 03981 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 03982 { 03983 i_SecondNeighboringVertex = m_vi_Edges[k]; 03984 03985 if(i_SecondNeighboringVertex == i_PresentVertex) 03986 { 03987 continue; 03988 } 03989 03990 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 03991 { 03992 continue; 03993 } 03994 03995 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == m_vi_RightVertexColors[i_PresentVertex]) 03996 { 03997 _FOUND = _TRUE; 03998 03999 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]; 04000 04001 vi_LeftStarHubMap[i_StarID] = i_NeighboringVertex; 04002 04003 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 04004 04005 break; 04006 } 04007 } 04008 04009 if (!_FOUND) 04010 { 04011 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_LeftVertexColors[i_NeighboringVertex]]; 04012 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_LeftVertexColors[i_NeighboringVertex]]; 04013 04014 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 04015 { 04016 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_FirstNeighborTwo][i_PresentVertex]]; 04017 04018 vi_RightStarHubMap[i_StarID] = i_PresentVertex; 04019 04020 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 04021 } 04022 } 04023 } 04024 } 04025 04026 if(i_IncludedEdgeCount >= i_EdgeCount) 04027 { 04028 break; 04029 } 04030 04031 } 04032 04033 i_LeftVertexDefaultColor = _FALSE; 04034 i_RightVertexDefaultColor = _FALSE; 04035 04036 for(i=0; i<i_LeftVertexCount; i++) 04037 { 04038 if(m_vi_LeftVertexColors[i] == _UNKNOWN) 04039 { 04040 m_vi_LeftVertexColors[i] = _FALSE; 04041 04042 i_LeftVertexDefaultColor = _TRUE; 04043 } 04044 } 04045 04046 for(i=0; i<i_RightVertexCount; i++) 04047 { 04048 if(m_vi_RightVertexColors[i] == _UNKNOWN) 04049 { 04050 m_vi_RightVertexColors[i] = m_i_VertexColorCount; // m_i_VertexColorCount == (i_LeftVertexCount + i_RightVertexCount + 1) 04051 04052 i_RightVertexDefaultColor = _TRUE; 04053 } 04054 } 04055 04056 if(m_i_LeftVertexColorCount == _UNKNOWN) 04057 { 04058 m_i_LeftVertexColorCount = _TRUE; 04059 } 04060 else 04061 { 04062 m_i_LeftVertexColorCount = m_i_LeftVertexColorCount + i_LeftVertexDefaultColor; 04063 } 04064 04065 if(m_i_RightVertexColorCount == _UNKNOWN) 04066 { 04067 m_i_RightVertexColorCount = _TRUE; 04068 } 04069 else 04070 { 04071 m_i_RightVertexColorCount = m_i_RightVertexColorCount + i_RightVertexDefaultColor - i_LeftVertexCount; 04072 } 04073 04074 04075 m_i_VertexColorCount = m_i_LeftVertexColorCount + m_i_RightVertexColorCount; 04076 04077 #if DEBUG == 3562 04078 04079 cout<<endl; 04080 cout<<"DEBUG 3562 | Star Bicoloring | Vertex Colors | Left Vertices"<<endl; 04081 cout<<endl; 04082 04083 for(i=0; i<i_LeftVertexCount; i++) 04084 { 04085 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 04086 } 04087 04088 cout<<endl; 04089 cout<<"DEBUG 3562 | Star Bicoloring | Vertex Colors | Right Vertices"<<endl; 04090 cout<<endl; 04091 04092 for(i=0; i<i_RightVertexCount; i++) 04093 { 04094 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 04095 } 04096 04097 #endif 04098 04099 return(_TRUE); 04100 } 04101 04102 //Public Function 3563 04103 int BipartiteGraphBicoloring::ImplicitCoveringRestrictedStarBicoloring() 04104 { 04105 if(CheckVertexColoring("IMPLICIT_COVER_RESTRICTED_STAR")) 04106 { 04107 return(_TRUE); 04108 } 04109 04110 int i, j, k; 04111 04112 int _FOUND; 04113 04114 int i_ColorID, i_StarID; 04115 04116 int i_EdgeCount, i_IncludedEdgeCount; 04117 04118 int i_FirstNeighborOne, i_FirstNeighborTwo; 04119 04120 int i_LeftVertexCount, i_RightVertexCount; 04121 04122 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex; 04123 04124 int i_PresentEdge; 04125 04126 vector<int> vi_IncludedEdges; 04127 04128 vector<int> vi_CandidateColors; 04129 04130 vector<int> vi_EdgeStarMap, vi_LeftStarHubMap, vi_RightStarHubMap; 04131 04132 vector<int> vi_LeftTreated, vi_RightTreated; 04133 04134 vector<int> vi_FirstNeighborOne, vi_FirstNeighborTwo; 04135 04136 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 04137 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 04138 04139 i_EdgeCount = (signed) m_vi_Edges.size()/2; 04140 04141 vi_EdgeStarMap.clear(); 04142 vi_EdgeStarMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 04143 04144 m_mimi2_VertexEdgeMap.clear(); 04145 04146 i_IncludedEdgeCount =_FALSE; 04147 04148 for(i=0; i<i_LeftVertexCount; i++) 04149 { 04150 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 04151 { 04152 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = i_IncludedEdgeCount; 04153 04154 vi_EdgeStarMap[i_IncludedEdgeCount] = i_IncludedEdgeCount; 04155 04156 i_IncludedEdgeCount++; 04157 } 04158 } 04159 04160 m_i_VertexColorCount = STEP_UP(i_LeftVertexCount + i_RightVertexCount); 04161 04162 vi_IncludedEdges.clear(); 04163 vi_IncludedEdges.resize((unsigned) i_EdgeCount, _FALSE); 04164 04165 vi_CandidateColors.clear(); 04166 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 04167 04168 m_vi_LeftVertexColors.clear(); 04169 m_vi_LeftVertexColors.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 04170 04171 m_vi_RightVertexColors.clear(); 04172 m_vi_RightVertexColors.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 04173 04174 vi_LeftStarHubMap.clear(); 04175 vi_LeftStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 04176 04177 vi_RightStarHubMap.clear(); 04178 vi_RightStarHubMap.resize((unsigned) i_EdgeCount, _UNKNOWN); 04179 04180 vi_FirstNeighborOne.clear(); 04181 vi_FirstNeighborOne.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 04182 04183 vi_FirstNeighborTwo.clear(); 04184 vi_FirstNeighborTwo.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 04185 04186 vi_LeftTreated.clear(); 04187 vi_LeftTreated.resize((unsigned) i_RightVertexCount, _UNKNOWN); 04188 04189 vi_RightTreated.clear(); 04190 vi_RightTreated.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 04191 04192 i_IncludedEdgeCount = _FALSE; 04193 04194 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = _UNKNOWN; 04195 04196 for(i=0; i<i_LeftVertexCount + i_RightVertexCount; i++) 04197 { 04198 04199 #if DEBUG == 3563 04200 04201 cout<<"DEBUG 3563 | Star Bicoloring | Present Vertex | "<<STEP_UP(m_vi_OrderedVertices[i])<<endl; 04202 #endif 04203 04204 if(m_vi_OrderedVertices[i] < i_LeftVertexCount) 04205 { 04206 i_PresentVertex = m_vi_OrderedVertices[i]; 04207 04208 _FOUND = _FALSE; 04209 04210 for(j= m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 04211 { 04212 i_PresentEdge = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]; 04213 04214 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 04215 { 04216 _FOUND = _TRUE; 04217 04218 break; 04219 } 04220 } 04221 04222 if(_FOUND == _FALSE) 04223 { 04224 04225 #if DEBUG == 3563 04226 04227 cout<<"DEBUG 3563 | Star Bicoloring | Ignored Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 04228 #endif 04229 04230 continue; 04231 } 04232 04233 #if DEBUG == 3563 04234 04235 cout<<"DEBUG 3563 | Star Bicoloring | Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 04236 04237 #endif 04238 04239 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 04240 { 04241 i_NeighboringVertex = m_vi_Edges[j]; 04242 04243 i_ColorID = m_vi_RightVertexColors[i_NeighboringVertex]; 04244 04245 if(i_ColorID == _UNKNOWN) 04246 { 04247 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 04248 { 04249 i_SecondNeighboringVertex = m_vi_Edges[k]; 04250 04251 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04252 { 04253 continue; 04254 } 04255 04256 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04257 } 04258 04259 continue; 04260 } 04261 else 04262 { 04263 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 04264 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 04265 04266 if(i_FirstNeighborOne == i_PresentVertex) 04267 { 04268 if(vi_LeftTreated[i_FirstNeighborTwo] != i_PresentVertex) 04269 { 04270 for(k=m_vi_RightVertices[i_FirstNeighborTwo]; k<m_vi_RightVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 04271 { 04272 i_SecondNeighboringVertex = m_vi_Edges[k]; 04273 04274 if(i_SecondNeighboringVertex == i_PresentVertex) 04275 { 04276 continue; 04277 } 04278 04279 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04280 { 04281 continue; 04282 } 04283 04284 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04285 04286 #if DEBUG == 3563 04287 04288 cout<<"DEBUG 3563 | Star Bicoloring | Visited Same Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(i_FirstNeighborTwo)<<endl; 04289 04290 #endif 04291 } 04292 04293 vi_LeftTreated[i_FirstNeighborTwo] = i_PresentVertex; 04294 } 04295 04296 for(k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[STEP_UP(m_vi_Edges[j])]; k++) 04297 { 04298 i_SecondNeighboringVertex = m_vi_Edges[k]; 04299 04300 if(i_SecondNeighboringVertex == i_PresentVertex) 04301 { 04302 continue; 04303 } 04304 04305 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04306 { 04307 continue; 04308 } 04309 04310 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04311 04312 #if DEBUG == 3563 04313 04314 cout<<"DEBUG 3563 | Star Bicoloring | Restricted Same Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(m_vi_Edges[j])<<endl; 04315 04316 #endif 04317 } 04318 04319 vi_LeftTreated[i_NeighboringVertex] = i_PresentVertex; 04320 } 04321 else 04322 { 04323 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 04324 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 04325 04326 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 04327 { 04328 i_SecondNeighboringVertex = m_vi_Edges[k]; 04329 04330 if(i_SecondNeighboringVertex == i_PresentVertex) 04331 { 04332 continue; 04333 } 04334 04335 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04336 { 04337 continue; 04338 } 04339 04340 if(vi_LeftStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]] == i_SecondNeighboringVertex) 04341 { 04342 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04343 04344 #if DEBUG == 3563 04345 04346 cout<<"DEBUG 3563 | Star Bicoloring | Restricted Hub Color Neighbor | Preventing Color "<<m_vi_LeftVertexColors[i_SecondNeighboringVertex]<<" of Left Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Right Neighboring Vertex "<<STEP_UP(i_NeighboringVertex)<<endl; 04347 04348 #endif 04349 } 04350 } 04351 } 04352 } 04353 } 04354 04355 for(j=_TRUE; j<STEP_UP(i_LeftVertexCount); j++) 04356 { 04357 if(vi_CandidateColors[j] != i_PresentVertex) 04358 { 04359 m_vi_LeftVertexColors[i_PresentVertex] = j; 04360 04361 if(m_i_LeftVertexColorCount < j) 04362 { 04363 m_i_LeftVertexColorCount = j; 04364 } 04365 04366 for(k=m_vi_LeftVertices[i_PresentVertex]; k<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; k++) 04367 { 04368 i_PresentEdge = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[k]]; 04369 04370 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 04371 { 04372 vi_IncludedEdges[i_PresentEdge] = _TRUE; 04373 04374 i_IncludedEdgeCount++; 04375 } 04376 } 04377 04378 break; 04379 } 04380 } 04381 04382 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 04383 { 04384 _FOUND = _FALSE; 04385 04386 i_NeighboringVertex = m_vi_Edges[j]; 04387 04388 if(m_vi_RightVertexColors[i_NeighboringVertex] == _UNKNOWN) 04389 { 04390 continue; 04391 } 04392 04393 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 04394 { 04395 i_SecondNeighboringVertex = m_vi_Edges[k]; 04396 04397 if(i_SecondNeighboringVertex == i_PresentVertex) 04398 { 04399 continue; 04400 } 04401 04402 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04403 { 04404 continue; 04405 } 04406 04407 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == m_vi_LeftVertexColors[i_PresentVertex]) 04408 { 04409 _FOUND = _TRUE; 04410 04411 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_SecondNeighboringVertex][i_NeighboringVertex]]; 04412 04413 vi_RightStarHubMap[i_StarID] = i_NeighboringVertex; 04414 04415 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 04416 04417 break; 04418 } 04419 } 04420 04421 if (!_FOUND) 04422 { 04423 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_RightVertexColors[i_NeighboringVertex]]; 04424 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_RightVertexColors[i_NeighboringVertex]]; 04425 04426 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 04427 { 04428 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_FirstNeighborTwo]]; 04429 04430 vi_LeftStarHubMap[i_StarID] = i_PresentVertex; 04431 04432 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_PresentVertex][i_NeighboringVertex]] = i_StarID; 04433 } 04434 } 04435 } 04436 } 04437 else 04438 { 04439 i_PresentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount; 04440 04441 _FOUND = _FALSE; 04442 04443 for(j= m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 04444 { 04445 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]; 04446 04447 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 04448 { 04449 _FOUND = _TRUE; 04450 04451 break; 04452 } 04453 } 04454 04455 if(_FOUND == _FALSE) 04456 { 04457 04458 #if DEBUG == 3563 04459 04460 cout<<"DEBUG 3563 | Star Bicoloring | Ignored Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 04461 #endif 04462 04463 continue; 04464 } 04465 04466 #if DEBUG == 3563 04467 04468 cout<<"DEBUG 3563 | Star Bicoloring | Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 04469 04470 #endif 04471 04472 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 04473 { 04474 i_NeighboringVertex = m_vi_Edges[j]; 04475 04476 i_ColorID = m_vi_LeftVertexColors[i_NeighboringVertex]; 04477 04478 if(i_ColorID == _UNKNOWN) 04479 { 04480 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 04481 { 04482 i_SecondNeighboringVertex = m_vi_Edges[k]; 04483 04484 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04485 { 04486 continue; 04487 } 04488 04489 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04490 } 04491 04492 continue; 04493 } 04494 else 04495 { 04496 i_FirstNeighborOne = vi_FirstNeighborOne[i_ColorID]; 04497 i_FirstNeighborTwo = vi_FirstNeighborTwo[i_ColorID]; 04498 04499 if(i_FirstNeighborOne == i_PresentVertex) 04500 { 04501 if(vi_RightTreated[i_FirstNeighborTwo] != i_PresentVertex) 04502 { 04503 for(k=m_vi_LeftVertices[i_FirstNeighborTwo]; k<m_vi_LeftVertices[STEP_UP(i_FirstNeighborTwo)]; k++) 04504 { 04505 i_SecondNeighboringVertex = m_vi_Edges[k]; 04506 04507 if(i_SecondNeighboringVertex == i_PresentVertex) 04508 { 04509 continue; 04510 } 04511 04512 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04513 { 04514 continue; 04515 } 04516 04517 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04518 04519 #if DEBUG == 3563 04520 04521 cout<<"DEBUG 3563 | Star Bicoloring | Visited Same Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Right Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(i_FirstNeighborTwo)<<endl; 04522 04523 #endif 04524 } 04525 04526 vi_RightTreated[i_FirstNeighborTwo] = i_PresentVertex; 04527 } 04528 04529 for(k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[STEP_UP(m_vi_Edges[j])]; k++) 04530 { 04531 i_SecondNeighboringVertex = m_vi_Edges[k]; 04532 04533 if(i_SecondNeighboringVertex == i_PresentVertex) 04534 { 04535 continue; 04536 } 04537 04538 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04539 { 04540 continue; 04541 } 04542 04543 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04544 04545 #if DEBUG == 3563 04546 04547 cout<<"DEBUG 3563 | Star Bicoloring | Restricted Same Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Right Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(m_vi_Edges[j])<<endl; 04548 04549 #endif 04550 } 04551 04552 vi_RightTreated[i_NeighboringVertex] = i_PresentVertex; 04553 } 04554 else 04555 { 04556 vi_FirstNeighborOne[i_ColorID] = i_PresentVertex; 04557 vi_FirstNeighborTwo[i_ColorID] = i_NeighboringVertex; 04558 04559 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 04560 { 04561 i_SecondNeighboringVertex = m_vi_Edges[k]; 04562 04563 if(i_SecondNeighboringVertex == i_PresentVertex) 04564 { 04565 continue; 04566 } 04567 04568 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04569 { 04570 continue; 04571 } 04572 04573 if(vi_RightStarHubMap[vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]] == i_SecondNeighboringVertex) 04574 { 04575 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04576 04577 #if DEBUG == 3563 04578 04579 cout<<"DEBUG 3563 | Star Bicoloring | Restricted Hub Color Neighbor | Preventing Color "<<m_vi_RightVertexColors[i_SecondNeighboringVertex]<<" of Neighboring Vertex "<<STEP_UP(i_SecondNeighboringVertex)<<" coming from Left Neighboring Vertex "<<STEP_UP(i_NeighboringVertex)<<endl; 04580 04581 #endif 04582 } 04583 } 04584 } 04585 } 04586 } 04587 04588 for(j=STEP_UP(i_LeftVertexCount); j<m_i_VertexColorCount; j++) 04589 { 04590 if(vi_CandidateColors[j] != i_PresentVertex) 04591 { 04592 m_vi_RightVertexColors[i_PresentVertex] = j; 04593 04594 if(m_i_RightVertexColorCount < j) 04595 { 04596 m_i_RightVertexColorCount = j; 04597 } 04598 04599 for(k=m_vi_RightVertices[i_PresentVertex]; k<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; k++) 04600 { 04601 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[k]][i_PresentVertex]; 04602 04603 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 04604 { 04605 vi_IncludedEdges[i_PresentEdge] = _TRUE; 04606 04607 i_IncludedEdgeCount++; 04608 } 04609 } 04610 04611 break; 04612 } 04613 } 04614 04615 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 04616 { 04617 _FOUND = _FALSE; 04618 04619 i_NeighboringVertex = m_vi_Edges[j]; 04620 04621 if(m_vi_LeftVertexColors[i_NeighboringVertex] == _UNKNOWN) 04622 { 04623 continue; 04624 } 04625 04626 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 04627 { 04628 i_SecondNeighboringVertex = m_vi_Edges[k]; 04629 04630 if(i_SecondNeighboringVertex == i_PresentVertex) 04631 { 04632 continue; 04633 } 04634 04635 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04636 { 04637 continue; 04638 } 04639 04640 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == m_vi_RightVertexColors[i_PresentVertex]) 04641 { 04642 _FOUND = _TRUE; 04643 04644 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_SecondNeighboringVertex]]; 04645 04646 vi_LeftStarHubMap[i_StarID] = i_NeighboringVertex; 04647 04648 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 04649 04650 break; 04651 } 04652 } 04653 04654 if (!_FOUND) 04655 { 04656 i_FirstNeighborOne = vi_FirstNeighborOne[m_vi_LeftVertexColors[i_NeighboringVertex]]; 04657 i_FirstNeighborTwo = vi_FirstNeighborTwo[m_vi_LeftVertexColors[i_NeighboringVertex]]; 04658 04659 if((i_FirstNeighborOne == i_PresentVertex) && (i_FirstNeighborTwo != i_NeighboringVertex)) 04660 { 04661 i_StarID = vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_FirstNeighborTwo][i_PresentVertex]]; 04662 04663 vi_RightStarHubMap[i_StarID] = i_PresentVertex; 04664 04665 vi_EdgeStarMap[m_mimi2_VertexEdgeMap[i_NeighboringVertex][i_PresentVertex]] = i_StarID; 04666 } 04667 } 04668 } 04669 } 04670 04671 if(i_IncludedEdgeCount >= i_EdgeCount) 04672 { 04673 break; 04674 } 04675 } 04676 04677 i_LeftVertexDefaultColor = _FALSE; 04678 i_RightVertexDefaultColor = _FALSE; 04679 04680 for(i=0; i<i_LeftVertexCount; i++) 04681 { 04682 if(m_vi_LeftVertexColors[i] == _UNKNOWN) 04683 { 04684 m_vi_LeftVertexColors[i] = _FALSE; 04685 04686 i_LeftVertexDefaultColor = _TRUE; 04687 } 04688 } 04689 04690 for(i=0; i<i_RightVertexCount; i++) 04691 { 04692 if(m_vi_RightVertexColors[i] == _UNKNOWN) 04693 { 04694 m_vi_RightVertexColors[i] = m_i_VertexColorCount; 04695 04696 i_RightVertexDefaultColor = _TRUE; 04697 } 04698 } 04699 04700 if(m_i_LeftVertexColorCount == _UNKNOWN) 04701 { 04702 m_i_LeftVertexColorCount = _TRUE; 04703 } 04704 else 04705 { 04706 m_i_LeftVertexColorCount = m_i_LeftVertexColorCount + i_LeftVertexDefaultColor; 04707 } 04708 04709 if(m_i_RightVertexColorCount == _UNKNOWN) 04710 { 04711 m_i_RightVertexColorCount = _TRUE; 04712 } 04713 else 04714 { 04715 m_i_RightVertexColorCount = m_i_RightVertexColorCount + i_RightVertexDefaultColor - i_LeftVertexCount; 04716 } 04717 04718 04719 m_i_VertexColorCount = m_i_LeftVertexColorCount + m_i_RightVertexColorCount; 04720 04721 #if DEBUG == 3563 04722 04723 cout<<endl; 04724 cout<<"DEBUG 3563 | Star Bicoloring | Vertex Colors | Left Vertices"<<endl; 04725 cout<<endl; 04726 04727 for(i=0; i<i_LeftVertexCount; i++) 04728 { 04729 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 04730 } 04731 04732 cout<<endl; 04733 cout<<"DEBUG 3563 | Star Bicoloring | Vertex Colors | Right Vertices"<<endl; 04734 cout<<endl; 04735 04736 for(i=0; i<i_RightVertexCount; i++) 04737 { 04738 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 04739 } 04740 04741 #endif 04742 04743 return(_TRUE); 04744 } 04745 04746 04747 //Public Function 3564 04748 int BipartiteGraphBicoloring::ImplicitCoveringGreedyStarBicoloring() 04749 { 04750 if(CheckVertexColoring("IMPLICIT_COVER_GREEDY_STAR")) 04751 { 04752 return(_TRUE); 04753 } 04754 04755 int i, j, k, l; 04756 04757 int _FOUND; 04758 04759 int i_LeftVertexCount, i_RightVertexCount; 04760 04761 int i_OrderedVertexCount; 04762 04763 int i_EdgeCount, i_IncludedEdgeCount; 04764 04765 int i_PresentEdge; 04766 04767 int i_PresentVertex, i_NeighboringVertex, i_SecondNeighboringVertex, i_ThirdNeighboringVertex; 04768 04769 vector<int> vi_CandidateColors; 04770 04771 vector<int> vi_IncludedEdges; 04772 04773 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 04774 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 04775 04776 i_EdgeCount = (signed) m_vi_Edges.size()/2; 04777 04778 m_mimi2_VertexEdgeMap.clear(); 04779 04780 i_IncludedEdgeCount =_FALSE; 04781 04782 for(i=0; i<i_LeftVertexCount; i++) 04783 { 04784 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 04785 { 04786 m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]] = i_IncludedEdgeCount; 04787 04788 i_IncludedEdgeCount++; 04789 } 04790 } 04791 04792 m_i_VertexColorCount = STEP_UP(i_LeftVertexCount + i_RightVertexCount); 04793 04794 vi_IncludedEdges.clear(); 04795 vi_IncludedEdges.resize((unsigned) i_EdgeCount, _FALSE); 04796 04797 vi_CandidateColors.clear(); 04798 vi_CandidateColors.resize((unsigned) m_i_VertexColorCount, _UNKNOWN); 04799 04800 m_vi_LeftVertexColors.clear(); 04801 m_vi_LeftVertexColors.resize((unsigned) i_LeftVertexCount, _UNKNOWN); 04802 04803 m_vi_RightVertexColors.clear(); 04804 m_vi_RightVertexColors.resize((unsigned) i_RightVertexCount, _UNKNOWN); 04805 04806 i_OrderedVertexCount = (signed) m_vi_OrderedVertices.size(); 04807 04808 i_IncludedEdgeCount = _FALSE; 04809 04810 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = _UNKNOWN; 04811 04812 for(i=0; i<i_OrderedVertexCount; i++) 04813 { 04814 04815 #if DEBUG == 3564 04816 04817 cout<<"DEBUG 3564 | Greedy Star Bicoloring | Present Vertex | "<<STEP_UP(m_vi_OrderedVertices[i])<<endl; 04818 04819 #endif 04820 04821 if(m_vi_OrderedVertices[i] < i_LeftVertexCount) 04822 { 04823 i_PresentVertex = m_vi_OrderedVertices[i]; 04824 04825 _FOUND = _FALSE; 04826 04827 for(j= m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 04828 { 04829 i_PresentEdge = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[j]]; 04830 04831 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 04832 { 04833 _FOUND = _TRUE; 04834 04835 break; 04836 } 04837 } 04838 04839 if(_FOUND == _FALSE) 04840 { 04841 04842 #if DEBUG == 3564 04843 04844 cout<<"DEBUG 3564 | Greedy Star Bicoloring | Ignored Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 04845 #endif 04846 04847 continue; 04848 } 04849 04850 #if DEBUG == 3564 04851 04852 cout<<"DEBUG 3564 | Greedy Star Bicoloring | Present Left Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 04853 #endif 04854 04855 for(j=m_vi_LeftVertices[i_PresentVertex]; j<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; j++) 04856 { 04857 i_NeighboringVertex = m_vi_Edges[j]; 04858 04859 for(k=m_vi_RightVertices[i_NeighboringVertex]; k<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; k++) 04860 { 04861 i_SecondNeighboringVertex = m_vi_Edges[k]; 04862 04863 if(m_vi_LeftVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04864 { 04865 continue; 04866 } 04867 04868 if(m_vi_RightVertexColors[i_NeighboringVertex] == _UNKNOWN) 04869 { 04870 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04871 } 04872 else 04873 { 04874 04875 for(l=m_vi_LeftVertices[i_SecondNeighboringVertex]; l<m_vi_LeftVertices[STEP_UP(i_SecondNeighboringVertex)]; l++) 04876 { 04877 i_ThirdNeighboringVertex = m_vi_Edges[l]; 04878 04879 if(m_vi_RightVertexColors[i_ThirdNeighboringVertex] == _UNKNOWN) 04880 { 04881 continue; 04882 } 04883 04884 if(m_vi_RightVertexColors[i_ThirdNeighboringVertex] == m_vi_RightVertexColors[i_NeighboringVertex]) 04885 { 04886 vi_CandidateColors[m_vi_LeftVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04887 } 04888 } 04889 } 04890 } 04891 } 04892 04893 for(j=_TRUE; j<STEP_UP(i_LeftVertexCount); j++) 04894 { 04895 if(vi_CandidateColors[j] != i_PresentVertex) 04896 { 04897 m_vi_LeftVertexColors[i_PresentVertex] = j; 04898 04899 if(m_i_LeftVertexColorCount < j) 04900 { 04901 m_i_LeftVertexColorCount = j; 04902 } 04903 04904 for(k=m_vi_LeftVertices[i_PresentVertex]; k<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; k++) 04905 { 04906 i_PresentEdge = m_mimi2_VertexEdgeMap[i_PresentVertex][m_vi_Edges[k]]; 04907 04908 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 04909 { 04910 vi_IncludedEdges[i_PresentEdge] = _TRUE; 04911 04912 i_IncludedEdgeCount++; 04913 } 04914 } 04915 04916 break; 04917 } 04918 } 04919 } 04920 else 04921 { 04922 i_PresentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount; 04923 04924 _FOUND = _FALSE; 04925 04926 for(j= m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 04927 { 04928 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][i_PresentVertex]; 04929 04930 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 04931 { 04932 _FOUND = _TRUE; 04933 04934 break; 04935 } 04936 } 04937 04938 if(_FOUND == _FALSE) 04939 { 04940 04941 #if DEBUG == 3564 04942 04943 cout<<"DEBUG 3564 | Greedy Star Bicoloring | Ignored Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 04944 #endif 04945 04946 continue; 04947 } 04948 04949 #if DEBUG == 3564 04950 04951 cout<<"DEBUG 3564 | Greedy Star Bicoloring | Present Right Vertex | "<<STEP_UP(i_PresentVertex)<<endl; 04952 #endif 04953 04954 for(j=m_vi_RightVertices[i_PresentVertex]; j<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; j++) 04955 { 04956 i_NeighboringVertex = m_vi_Edges[j]; 04957 04958 for(k=m_vi_LeftVertices[i_NeighboringVertex]; k<m_vi_LeftVertices[STEP_UP(i_NeighboringVertex)]; k++) 04959 { 04960 i_SecondNeighboringVertex = m_vi_Edges[k]; 04961 04962 if(m_vi_RightVertexColors[i_SecondNeighboringVertex] == _UNKNOWN) 04963 { 04964 continue; 04965 } 04966 04967 if(m_vi_LeftVertexColors[i_NeighboringVertex] == _UNKNOWN) 04968 { 04969 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04970 } 04971 else 04972 { 04973 for(l=m_vi_RightVertices[i_SecondNeighboringVertex]; l<m_vi_RightVertices[STEP_UP(i_SecondNeighboringVertex)]; l++) 04974 { 04975 i_ThirdNeighboringVertex = m_vi_Edges[l]; 04976 04977 if(m_vi_LeftVertexColors[i_ThirdNeighboringVertex] == _UNKNOWN) 04978 { 04979 continue; 04980 } 04981 04982 if(m_vi_LeftVertexColors[i_ThirdNeighboringVertex] == m_vi_LeftVertexColors[i_NeighboringVertex]) 04983 { 04984 vi_CandidateColors[m_vi_RightVertexColors[i_SecondNeighboringVertex]] = i_PresentVertex; 04985 } 04986 } 04987 } 04988 } 04989 } 04990 04991 for(j=STEP_UP(i_LeftVertexCount); j<m_i_VertexColorCount; j++) 04992 { 04993 if(vi_CandidateColors[j] != i_PresentVertex) 04994 { 04995 m_vi_RightVertexColors[i_PresentVertex] = j; 04996 04997 if(m_i_RightVertexColorCount < j) 04998 { 04999 m_i_RightVertexColorCount = j; 05000 } 05001 05002 for(k=m_vi_RightVertices[i_PresentVertex]; k<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; k++) 05003 { 05004 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[k]][i_PresentVertex]; 05005 05006 if(vi_IncludedEdges[i_PresentEdge] == _FALSE) 05007 { 05008 vi_IncludedEdges[i_PresentEdge] = _TRUE; 05009 05010 i_IncludedEdgeCount++; 05011 } 05012 } 05013 05014 break; 05015 } 05016 } 05017 } 05018 05019 if(i_IncludedEdgeCount >= i_EdgeCount) 05020 { 05021 break; 05022 } 05023 } 05024 05025 i_LeftVertexDefaultColor = _FALSE; 05026 i_RightVertexDefaultColor = _FALSE; 05027 05028 for(i=0; i<i_LeftVertexCount; i++) 05029 { 05030 if(m_vi_LeftVertexColors[i] == _UNKNOWN) 05031 { 05032 m_vi_LeftVertexColors[i] = _FALSE; 05033 05034 i_LeftVertexDefaultColor = _TRUE; 05035 } 05036 } 05037 05038 for(i=0; i<i_RightVertexCount; i++) 05039 { 05040 if(m_vi_RightVertexColors[i] == _UNKNOWN) 05041 { 05042 m_vi_RightVertexColors[i] = m_i_VertexColorCount; 05043 05044 i_RightVertexDefaultColor = _TRUE; 05045 } 05046 } 05047 05048 if(m_i_LeftVertexColorCount == _UNKNOWN) 05049 { 05050 m_i_LeftVertexColorCount = _TRUE; 05051 } 05052 else 05053 { 05054 m_i_LeftVertexColorCount = m_i_LeftVertexColorCount + i_LeftVertexDefaultColor; 05055 } 05056 05057 if(m_i_RightVertexColorCount == _UNKNOWN) 05058 { 05059 m_i_RightVertexColorCount = _TRUE; 05060 } 05061 else 05062 { 05063 m_i_RightVertexColorCount = m_i_RightVertexColorCount + i_RightVertexDefaultColor - i_LeftVertexCount; 05064 } 05065 05066 m_i_VertexColorCount = m_i_LeftVertexColorCount + m_i_RightVertexColorCount; 05067 05068 #if DEBUG == 3564 05069 05070 cout<<endl; 05071 cout<<"DEBUG 3564 | Greedy Star Bicoloring | Left Vertex Colors"<<endl; 05072 cout<<endl; 05073 05074 for(i=0; i<i_LeftVertexCount; i++) 05075 { 05076 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 05077 } 05078 05079 cout<<endl; 05080 cout<<"DEBUG 3564 | Greedy Star Bicoloring | Right Vertex Colors"<<endl; 05081 cout<<endl; 05082 05083 for(i=0; i<i_RightVertexCount; i++) 05084 { 05085 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 05086 } 05087 05088 cout<<endl; 05089 cout<<"[Total Vertex Colors = "<<m_i_VertexColorCount<<"]"<<endl; 05090 cout<<endl; 05091 05092 #endif 05093 05094 return(_TRUE); 05095 } 05096 05097 05098 //Public Function 3565 05099 int BipartiteGraphBicoloring::CheckStarBicoloring() 05100 { 05101 int i, j, k, l; 05102 05103 int i_MaximumColorCount; 05104 05105 int i_FirstColor, i_SecondColor, i_ThirdColor, i_FourthColor; 05106 05107 int i_LeftVertexCount, i_RightVertexCount; 05108 05109 int i_ColorViolationCount, i_PathViolationCount, i_TotalViolationCount; 05110 05111 vector<int> vi_VertexColors; 05112 05113 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size()); 05114 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size()); 05115 05116 i_MaximumColorCount = STEP_UP(i_LeftVertexCount) + STEP_UP(i_RightVertexCount); 05117 05118 vi_VertexColors.clear(); 05119 vi_VertexColors.resize((unsigned) i_MaximumColorCount, _FALSE); 05120 05121 i_ColorViolationCount = _FALSE; 05122 05123 for(i=0; i<i_LeftVertexCount; i++) 05124 { 05125 vi_VertexColors[m_vi_LeftVertexColors[i]] = _TRUE; 05126 } 05127 05128 for(i=0; i<i_RightVertexCount; i++) 05129 { 05130 if(vi_VertexColors[m_vi_RightVertexColors[i]] == _TRUE) 05131 { 05132 i_ColorViolationCount++; 05133 05134 if(i_ColorViolationCount == _TRUE) 05135 { 05136 cout<<endl; 05137 cout<<"Star Bicoloring | Violation Check | Vertex Colors | "<<m_s_InputFile<<endl; 05138 cout<<endl; 05139 } 05140 05141 cout<<"Color Violation "<<i_ColorViolationCount<<" | Right Vertex "<<STEP_UP(i)<<" | Conflicting Color "<<m_vi_RightVertexColors[i]<<endl; 05142 } 05143 } 05144 05145 i_PathViolationCount = _FALSE; 05146 05147 for(i=0; i<i_LeftVertexCount; i++) 05148 { 05149 i_FirstColor = m_vi_LeftVertexColors[i]; 05150 05151 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++) 05152 { 05153 i_SecondColor = m_vi_RightVertexColors[m_vi_Edges[j]]; 05154 05155 for(k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[STEP_UP(m_vi_Edges[j])]; k++) 05156 { 05157 if(m_vi_Edges[k] == i) 05158 { 05159 continue; 05160 } 05161 05162 i_ThirdColor = m_vi_LeftVertexColors[m_vi_Edges[k]]; 05163 05164 if(i_ThirdColor == i_FirstColor) 05165 { 05166 for(l=m_vi_LeftVertices[m_vi_Edges[k]]; l<m_vi_LeftVertices[STEP_UP(m_vi_Edges[k])]; l++) 05167 { 05168 if(m_vi_Edges[l] == m_vi_Edges[j]) 05169 { 05170 continue; 05171 } 05172 05173 i_FourthColor = m_vi_RightVertexColors[m_vi_Edges[l]]; 05174 05175 if(i_FourthColor == i_SecondColor) 05176 { 05177 i_PathViolationCount++; 05178 05179 if(i_PathViolationCount == _TRUE) 05180 { 05181 cout<<endl; 05182 cout<<"Star Bicoloring | Violation Check | Path Colors | "<<m_s_InputFile<<endl; 05183 cout<<endl; 05184 } 05185 05186 cout<<"Path Violation "<<i_PathViolationCount<<" | "<<STEP_UP(i)<<" ["<<i_FirstColor<<"] - "<<STEP_UP(m_vi_Edges[j])<<" ["<<i_SecondColor<<"] - "<<STEP_UP(m_vi_Edges[k])<<" ["<<i_ThirdColor<<"] - "<<STEP_UP(m_vi_Edges[l])<<" ["<<i_FourthColor<<"]"<<endl; 05187 } 05188 } 05189 } 05190 } 05191 } 05192 } 05193 05194 i_TotalViolationCount = i_ColorViolationCount + i_PathViolationCount; 05195 05196 if(i_TotalViolationCount) 05197 { 05198 cout<<endl; 05199 cout<<"[Total Violations = "<<i_TotalViolationCount<<"]"<<endl; 05200 cout<<endl; 05201 } 05202 05203 m_i_ViolationCount = i_TotalViolationCount; 05204 05205 return(i_TotalViolationCount); 05206 } 05207 05208 05209 05210 //Public Function 3568 05211 int BipartiteGraphBicoloring::GetLeftVertexColorCount() 05212 { 05213 return(m_i_LeftVertexColorCount); 05214 } 05215 05216 //Public Function 3569 05217 int BipartiteGraphBicoloring::GetRightVertexColorCount() 05218 { 05219 return(m_i_RightVertexColorCount); 05220 } 05221 05222 05223 //Public Function 3570 05224 int BipartiteGraphBicoloring::GetVertexColorCount() 05225 { 05226 return(m_i_VertexColorCount); 05227 } 05228 05229 05230 //Public Function 3571 05231 int BipartiteGraphBicoloring::GetViolationCount() 05232 { 05233 return(m_i_ViolationCount); 05234 } 05235 05236 int BipartiteGraphBicoloring::GetRightVertexDefaultColor() 05237 { 05238 return(i_RightVertexDefaultColor); 05239 } 05240 05241 string BipartiteGraphBicoloring::GetVertexColoringVariant() 05242 { 05243 return GetVertexBicoloringVariant(); 05244 } 05245 05246 //Public Function 3572 05247 string BipartiteGraphBicoloring::GetVertexBicoloringVariant() 05248 { 05249 if(m_s_VertexColoringVariant.compare("MINIMAL_COVER_ROW_STAR") == 0) 05250 { 05251 return("Minimal Cover Row Star"); 05252 } 05253 else 05254 if(m_s_VertexColoringVariant.compare("MINIMAL_COVER_COLUMN_STAR") == 0) 05255 { 05256 return("Minimal Cover Column Star"); 05257 } 05258 else 05259 if(m_s_VertexColoringVariant.compare("EXPLICIT_COVER_MODIFIED_STAR") == 0) 05260 { 05261 return("Explicit Cover Modified Star"); 05262 } 05263 else 05264 if(m_s_VertexColoringVariant.compare("EXPLICIT_COVER_STAR") == 0) 05265 { 05266 return("Explicit Cover Star"); 05267 } 05268 else 05269 if(m_s_VertexColoringVariant.compare("MINIMAL_COVER_STAR") == 0) 05270 { 05271 return("Minimal Cover Star"); 05272 } 05273 else 05274 if(m_s_VertexColoringVariant.compare("IMPLICIT_COVER_CONSERVATIVE_STAR") == 0) 05275 { 05276 return("Implicit Cover Conservative Star"); 05277 } 05278 else 05279 if(m_s_VertexColoringVariant.compare("IMPLICIT_COVER_STAR") == 0) 05280 { 05281 return("Implicit Cover Star"); 05282 } 05283 else 05284 if(m_s_VertexColoringVariant.compare("IMPLICIT_COVER_RESTRICTED_STAR") == 0) 05285 { 05286 return("Implicit Cover Restricted Star"); 05287 } 05288 else 05289 if(m_s_VertexColoringVariant.compare("IMPLICIT_COVER_GREEDY_STAR") == 0) 05290 { 05291 return("Implicit Cover Greedy Star"); 05292 } 05293 else 05294 if(m_s_VertexColoringVariant.compare("IMPLICIT_COVER_ACYCLIC") == 0) 05295 { 05296 return("Implicit Cover Acyclic"); 05297 } 05298 else 05299 { 05300 return("Unknown"); 05301 } 05302 } 05303 05304 05305 //Public Function 3573 05306 void BipartiteGraphBicoloring::GetLeftVertexColors(vector<int> &output) 05307 { 05308 output = m_vi_LeftVertexColors; 05309 } 05310 05311 05312 //Public Function 3574 05313 void BipartiteGraphBicoloring::GetRightVertexColors(vector<int> &output) 05314 { 05315 output = m_vi_RightVertexColors; 05316 } 05317 05318 void BipartiteGraphBicoloring::GetRightVertexColors_Transformed(vector<int> &output) 05319 { 05320 int rowCount = GetRowVertexCount(); 05321 int columnCount = GetColumnVertexCount(); 05322 05323 output = m_vi_RightVertexColors; 05324 05325 for (int i=0; i < output.size(); i++) { 05326 output[i] -= rowCount; 05327 if (output[i] == columnCount + 1) output[i] = 0; //color 0, the rows with this color should be ignored. 05328 } 05329 } 05330 05331 //Public Function 3575 05332 void BipartiteGraphBicoloring::PrintVertexBicolorClasses() 05333 { 05334 if(CalculateVertexColorClasses() != _TRUE) 05335 { 05336 cout<<endl; 05337 cout<<"Vertex Bicolor Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<" | Vertex Bicolors Not Set"<<endl; 05338 cout<<endl; 05339 05340 return; 05341 } 05342 05343 cout<<endl; 05344 cout<<"Row Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl; 05345 cout<<endl; 05346 05347 int i_TotalLeftVertexColors = STEP_UP(m_i_LeftVertexColorCount); 05348 05349 for(int i = 0; i < i_TotalLeftVertexColors; i++) 05350 { 05351 if(m_vi_LeftVertexColorFrequency[i] <= 0) 05352 { 05353 continue; 05354 } 05355 05356 cout<<"Color "<<STEP_UP(i)<<" : "<<m_vi_LeftVertexColorFrequency[i]<<endl; 05357 } 05358 05359 cout<<endl; 05360 cout<<"[Largest Row Color Class : "<<STEP_UP(m_i_LargestLeftVertexColorClass)<<"; Largest Row Color Class Size : "<<m_i_LargestLeftVertexColorClassSize<<"]"<<endl; 05361 cout<<"[Smallest Row Color Class : "<<STEP_UP(m_i_SmallestLeftVertexColorClass)<<"; Smallest Row Color Class Size : "<<m_i_SmallestLeftVertexColorClassSize<<"]"<<endl; 05362 cout<<"[Average Row Color Class Size : "<<m_d_AverageLeftVertexColorClassSize<<"]"<<endl; 05363 cout<<endl; 05364 05365 cout<<endl; 05366 cout<<"Column Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl; 05367 cout<<endl; 05368 05369 int i_TotalRightVertexColors = STEP_UP(m_i_RightVertexColorCount); 05370 05371 for(int i = 0; i < i_TotalRightVertexColors; i++) 05372 { 05373 if(m_vi_RightVertexColorFrequency[i] <= 0) 05374 { 05375 continue; 05376 } 05377 05378 cout<<"Color "<<STEP_UP(i)<<" : "<<m_vi_RightVertexColorFrequency[i]<<endl; 05379 } 05380 05381 cout<<endl; 05382 cout<<"[Largest Column Color Class : "<<STEP_UP(m_i_LargestRightVertexColorClass)<<"; Largest Column Color Class Size : "<<m_i_LargestRightVertexColorClassSize<<"]"<<endl; 05383 cout<<"[Smallest Column Color Class : "<<STEP_UP(m_i_SmallestRightVertexColorClass)<<"; Smallest Column Color Class Size : "<<m_i_SmallestRightVertexColorClassSize<<"]"<<endl; 05384 cout<<"[Average Column Color Class Size : "<<m_d_AverageRightVertexColorClassSize<<"]"<<endl; 05385 cout<<endl; 05386 05387 cout<<endl; 05388 cout<<"[Largest Vertex Color Class : "<<STEP_UP(m_i_LargestVertexColorClass)<<"; Largest Vertex Color Class Size : "<<m_i_LargestVertexColorClassSize<<"]"<<endl; 05389 cout<<"[Smallest Vertex Color Class : "<<STEP_UP(m_i_SmallestVertexColorClass)<<"; Smallest Vertex Color Class Size : "<<m_i_SmallestVertexColorClassSize<<"]"<<endl; 05390 cout<<"[Average Color Class Size : "<<m_d_AverageVertexColorClassSize<<"]"<<endl; 05391 cout<<endl; 05392 05393 return; 05394 } 05395 05396 //Public Function 3576 05397 void BipartiteGraphBicoloring::PrintVertexBicolors() 05398 { 05399 int i; 05400 05401 int i_LeftVertexCount, i_RightVertexCount; 05402 05403 string _SLASH("/"); 05404 05405 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH); 05406 05407 string s_InputFile = SlashTokenizer.GetLastToken(); 05408 05409 i_LeftVertexCount = (signed) m_vi_LeftVertexColors.size(); 05410 i_RightVertexCount = (signed) m_vi_RightVertexColors.size(); 05411 05412 cout<<endl; 05413 cout<<GetVertexBicoloringVariant()<<" Bicoloring | "<<GetVertexOrderingVariant()<<" Ordering | Row Vertex Colors | "<<s_InputFile<<endl; 05414 cout<<endl; 05415 05416 for(i=0; i<i_LeftVertexCount; i++) 05417 { 05418 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_LeftVertexColors[i]<<endl; 05419 } 05420 05421 cout<<endl; 05422 cout<<GetVertexBicoloringVariant()<<" Bicoloring | "<<GetVertexOrderingVariant()<<" Ordering | Column Vertex Colors | "<<s_InputFile<<endl; 05423 cout<<endl; 05424 05425 for(i=0; i<i_RightVertexCount; i++) 05426 { 05427 cout<<STEP_UP(i)<<"\t"<<" : "<<m_vi_RightVertexColors[i]<<endl; 05428 } 05429 05430 cout<<endl; 05431 cout<<"[Total Vertex Colors = "<<m_i_VertexColorCount<<", Violation Count = "<<m_i_ViolationCount<<"]"<<endl; 05432 cout<<endl; 05433 05434 return; 05435 } 05436 05437 05438 //Public Function 3577 05439 void BipartiteGraphBicoloring::PrintVertexBicoloringMetrics() 05440 { 05441 string _SLASH("/"); 05442 05443 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH); 05444 05445 string s_InputFile = SlashTokenizer.GetLastToken(); 05446 05447 cout<<endl; 05448 cout<<GetVertexBicoloringVariant()<<" Bicoloring | "<<GetVertexOrderingVariant()<<" Ordering | "<<s_InputFile<<endl; 05449 cout<<endl; 05450 05451 cout<<endl; 05452 cout<<"[Total Colors = "<<m_i_VertexColorCount<<"; Violation Count = "<<m_i_ViolationCount<<"]"<<endl; 05453 cout<<"[Row Vertex Count = "<<STEP_DOWN(m_vi_LeftVertices.size())<<"; Column Vertex Count = "<<STEP_DOWN(m_vi_RightVertices.size())<<endl; 05454 cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Covering Time = "<<m_d_CoveringTime<<"; Coloring Time = "<<m_d_ColoringTime<<"]"<<endl; 05455 cout<<endl; 05456 05457 return; 05458 05459 } 05460 05461 double** BipartiteGraphBicoloring::GetLeftSeedMatrix(int* ip1_SeedRowCount, int* ip1_SeedColumnCount) { 05462 //#define DEBUG asdf 05463 05464 if(lseed_available) Seed_reset(); 05465 05466 dp2_lSeed = GetLeftSeedMatrix_unmanaged(ip1_SeedRowCount, ip1_SeedColumnCount); 05467 if(dp2_lSeed == NULL) return NULL; 05468 05469 i_lseed_rowCount = *ip1_SeedRowCount; 05470 lseed_available = true; 05471 05472 return dp2_lSeed; 05473 } 05474 05475 double** BipartiteGraphBicoloring::GetRightSeedMatrix(int* ip1_SeedRowCount, int* ip1_SeedColumnCount) { 05476 05477 if(rseed_available) Seed_reset(); 05478 05479 dp2_rSeed = GetRightSeedMatrix_unmanaged(ip1_SeedRowCount, ip1_SeedColumnCount); 05480 if(dp2_rSeed == NULL) return NULL; 05481 05482 i_rseed_rowCount = *ip1_SeedRowCount; 05483 rseed_available = true; 05484 05485 return dp2_rSeed; 05486 } 05487 05488 double** BipartiteGraphBicoloring::GetLeftSeedMatrix_unmanaged(int* ip1_SeedRowCount, int* ip1_SeedColumnCount) { 05489 //#define DEBUG asdf 05490 05491 int i_size = GetLeftVertexCount(); 05492 int i_num_of_colors = m_i_LeftVertexColorCount; 05493 if (i_LeftVertexDefaultColor == 1) i_num_of_colors--; //color ID 0 is used, ignore it 05494 (*ip1_SeedRowCount) = i_num_of_colors; 05495 (*ip1_SeedColumnCount) = i_size; 05496 if((*ip1_SeedRowCount) == 0 || (*ip1_SeedColumnCount) == 0) return NULL; 05497 05498 #if DEBUG != _UNKNOWN 05499 printf("Seed[%d][%d] \n",(*ip1_SeedRowCount),(*ip1_SeedColumnCount)); 05500 #endif 05501 05502 // allocate and initialize Seed matrix 05503 double** Seed = new double*[(*ip1_SeedRowCount)]; 05504 for (int i=0; i<(*ip1_SeedRowCount); i++) { 05505 Seed[i] = new double[(*ip1_SeedColumnCount)]; 05506 for(int j=0; j<(*ip1_SeedColumnCount); j++) Seed[i][j]=0.; 05507 } 05508 05509 // populate Seed matrix 05510 for (int i=0; i < (*ip1_SeedColumnCount); i++) { 05511 #if DEBUG != _UNKNOWN 05512 if(m_vi_LeftVertexColors[i]>(*ip1_SeedColumnCount)) { 05513 printf("**WARNING: Out of bound: Seed[%d >= %d][%d] = 1. \n",m_vi_LeftVertexColors[i]-1,(*ip1_SeedColumnCount), i); 05514 } 05515 #endif 05516 if(m_vi_LeftVertexColors[i] != 0) { //ignore color 0 05517 Seed[m_vi_LeftVertexColors[i]-1][i] = 1.; 05518 } 05519 } 05520 05521 return Seed; 05522 } 05523 05524 double** BipartiteGraphBicoloring::GetRightSeedMatrix_unmanaged(int* ip1_SeedRowCount, int* ip1_SeedColumnCount) { 05525 05526 int i_size = GetRightVertexCount(); 05527 vector<int> RightVertexColors_Transformed; 05528 GetRightVertexColors_Transformed(RightVertexColors_Transformed); 05529 int i_num_of_colors = m_i_RightVertexColorCount; 05530 if (i_RightVertexDefaultColor == 1) i_num_of_colors--; //color ID 0 is used, ignore it 05531 (*ip1_SeedRowCount) = i_size; 05532 (*ip1_SeedColumnCount) = i_num_of_colors; 05533 if((*ip1_SeedRowCount) == 0 || (*ip1_SeedColumnCount) == 0) return NULL; 05534 05535 #if DEBUG != _UNKNOWN 05536 printf("Seed[%d][%d] \n",(*ip1_SeedRowCount),(*ip1_SeedColumnCount)); 05537 #endif 05538 05539 // allocate and initialize Seed matrix 05540 double** Seed = new double*[(*ip1_SeedRowCount)]; 05541 for (int i=0; i<(*ip1_SeedRowCount); i++) { 05542 Seed[i] = new double[(*ip1_SeedColumnCount)]; 05543 for(int j=0; j<(*ip1_SeedColumnCount); j++) Seed[i][j]=0.; 05544 } 05545 05546 // populate Seed matrix 05547 for (int i=0; i < (*ip1_SeedRowCount); i++) { 05548 #if DEBUG != _UNKNOWN 05549 if(RightVertexColors_Transformed[i]>(*ip1_SeedRowCount)) { 05550 printf("**WARNING: Out of bound: Seed[%d][%d >= %d] = 1. \n",i, RightVertexColors_Transformed[i] - 1, (*ip1_SeedRowCount)); 05551 } 05552 #endif 05553 if(RightVertexColors_Transformed[i] != 0) { //ignore color 0 05554 Seed[i][RightVertexColors_Transformed[i] - 1] = 1.; 05555 } 05556 } 05557 05558 return Seed; 05559 } 05560 05561 double BipartiteGraphBicoloring::GetVertexColoringTime() { 05562 return m_d_ColoringTime; 05563 } 05564 05565 void BipartiteGraphBicoloring::GetSeedMatrix(double*** dp3_LeftSeed, int* ip1_LeftSeedRowCount, int* ip1_LeftSeedColumnCount, double*** dp3_RightSeed, int* ip1_RightSeedRowCount, int* ip1_RightSeedColumnCount) { 05566 (*dp3_LeftSeed) = GetLeftSeedMatrix(ip1_LeftSeedRowCount, ip1_LeftSeedColumnCount); 05567 (*dp3_RightSeed) = GetRightSeedMatrix(ip1_RightSeedRowCount, ip1_RightSeedColumnCount); 05568 } 05569 05570 void BipartiteGraphBicoloring::GetSeedMatrix_unmanaged(double*** dp3_LeftSeed, int* ip1_LeftSeedRowCount, int* ip1_LeftSeedColumnCount, double*** dp3_RightSeed, int* ip1_RightSeedRowCount, int* ip1_RightSeedColumnCount) { 05571 (*dp3_LeftSeed) = GetLeftSeedMatrix_unmanaged(ip1_LeftSeedRowCount, ip1_LeftSeedColumnCount); 05572 (*dp3_RightSeed) = GetRightSeedMatrix_unmanaged(ip1_RightSeedRowCount, ip1_RightSeedColumnCount); 05573 } 05574 }