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