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 BipartiteGraphVertexCover::BipartiteGraphVertexCover()
00029 {
00030 Clear();
00031 }
00032
00033
00034
00035 BipartiteGraphVertexCover::~BipartiteGraphVertexCover()
00036 {
00037 Clear();
00038 }
00039
00040
00041
00042 void BipartiteGraphVertexCover::Clear()
00043 {
00044 BipartiteGraphInputOutput::Clear();
00045
00046 m_d_CoveringTime = _UNKNOWN;
00047
00048 m_vi_IncludedLeftVertices.clear();
00049 m_vi_IncludedRightVertices.clear();
00050
00051 m_vi_CoveredLeftVertices.clear();
00052 m_vi_CoveredRightVertices.clear();
00053
00054 return;
00055 }
00056
00057
00058
00059 void BipartiteGraphVertexCover::Reset()
00060 {
00061 m_d_CoveringTime = _UNKNOWN;
00062
00063 m_vi_IncludedLeftVertices.clear();
00064 m_vi_IncludedRightVertices.clear();
00065
00066 m_vi_CoveredLeftVertices.clear();
00067 m_vi_CoveredRightVertices.clear();
00068
00069 return;
00070 }
00071
00072
00073
00074 int BipartiteGraphVertexCover::CoverVertex()
00075 {
00076 int i, j;
00077
00078 int i_EdgeCount, i_CodeZeroEdgeCount;
00079
00080 int i_CandidateLeftVertex, i_CandidateRightVertex;
00081
00082 int i_LeftVertexCount, i_RightVertexCount;
00083
00084 int i_PresentEdge, i_NeighboringEdge;
00085
00086 int i_QuotientOne, i_QuotientTwo;
00087
00088 int i_VertexDegree, i_CodeZeroDegreeVertexCount;
00089
00090 int i_CodeZeroOneLeftVertexDegree, i_CodeZeroOneRightVertexDegree;
00091
00092 int i_HighestCodeZeroLeftVertexDegree, i_LowestCodeZeroLeftVertexDegree;
00093
00094 int i_HighestCodeZeroRightVertexDegree, i_LowestCodeZeroRightVertexDegree;
00095
00096 int i_HighestCodeTwoLeftVertexDegree, i_HighestCodeThreeRightVertexDegree;
00097
00098 vector<int> vi_EdgeCodes;
00099
00100 vector<int> vi_LeftVertexDegree, vi_CodeZeroLeftVertexDegree, vi_CodeOneLeftVertexDegree, vi_CodeTwoLeftVertexDegree, vi_CodeThreeLeftVertexDegree;
00101
00102 vector<int> vi_RightVertexDegree, vi_CodeZeroRightVertexDegree, vi_CodeOneRightVertexDegree, vi_CodeTwoRightVertexDegree, vi_CodeThreeRightVertexDegree;
00103
00104 vector< list<int> > vli_GroupedCodeZeroLeftVertexDegree, vli_GroupedCodeZeroRightVertexDegree;
00105
00106 vector< list<int>::iterator > vlit_CodeZeroLeftVertexLocation, vlit_CodeZeroRightVertexLocation;
00107
00108 list<int>::iterator lit_ListIterator;
00109
00110 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size());
00111 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size());
00112
00113 m_vi_IncludedLeftVertices.clear();
00114 m_vi_IncludedLeftVertices.resize((unsigned) i_LeftVertexCount, _TRUE);
00115
00116 m_vi_IncludedRightVertices.clear();
00117 m_vi_IncludedRightVertices.resize((unsigned) i_RightVertexCount, _TRUE);
00118
00119 #if DEBUG == 3355
00120
00121 cout<<endl;
00122 cout<<"DEBUG 3355 | Star Bicoloring | Edge Codes | Left and Right Vertices"<<endl;
00123 cout<<endl;
00124
00125 for(i=0; i<i_LeftVertexCount; i++)
00126 {
00127 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++)
00128 {
00129 cout<<STEP_UP(m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]])<<"\t"<<" : "<<STEP_UP(i)<<" - "<<STEP_UP(m_vi_Edges[j])<<endl;
00130 }
00131 }
00132
00133 #endif
00134
00135 i_EdgeCount = (signed) m_vi_Edges.size()/2;
00136
00137 vi_EdgeCodes.clear();
00138 vi_EdgeCodes.resize((unsigned) i_EdgeCount, _FALSE);
00139
00140 vi_LeftVertexDegree.clear();
00141 vi_LeftVertexDegree.resize((unsigned) i_LeftVertexCount);
00142
00143 vi_CodeZeroLeftVertexDegree.clear();
00144
00145 vli_GroupedCodeZeroLeftVertexDegree.clear();
00146 vli_GroupedCodeZeroLeftVertexDegree.resize((unsigned) STEP_UP(i_RightVertexCount));
00147
00148 vlit_CodeZeroLeftVertexLocation.clear();
00149
00150 i_HighestCodeZeroLeftVertexDegree = _FALSE;
00151 i_LowestCodeZeroLeftVertexDegree = i_RightVertexCount;
00152
00153 for(i=0; i<i_LeftVertexCount; i++)
00154 {
00155 i_VertexDegree = m_vi_LeftVertices[STEP_UP(i)] - m_vi_LeftVertices[i];
00156
00157 vi_LeftVertexDegree[i] = i_VertexDegree;
00158
00159 vi_CodeZeroLeftVertexDegree.push_back(i_VertexDegree);
00160
00161 vli_GroupedCodeZeroLeftVertexDegree[i_VertexDegree].push_front(i);
00162
00163 vlit_CodeZeroLeftVertexLocation.push_back(vli_GroupedCodeZeroLeftVertexDegree[i_VertexDegree].begin());
00164
00165 if(i_HighestCodeZeroLeftVertexDegree < i_VertexDegree)
00166 {
00167 i_HighestCodeZeroLeftVertexDegree = i_VertexDegree;
00168 }
00169
00170 if(i_LowestCodeZeroLeftVertexDegree > i_VertexDegree)
00171 {
00172 i_LowestCodeZeroLeftVertexDegree = i_VertexDegree;
00173 }
00174 }
00175
00176 vi_RightVertexDegree.clear();
00177 vi_RightVertexDegree.resize((unsigned) i_RightVertexCount);
00178
00179 vi_CodeZeroRightVertexDegree.clear();
00180
00181 vli_GroupedCodeZeroRightVertexDegree.clear();
00182 vli_GroupedCodeZeroRightVertexDegree.resize((unsigned) STEP_UP(i_LeftVertexCount));
00183
00184 vlit_CodeZeroRightVertexLocation.clear();
00185
00186 i_HighestCodeZeroRightVertexDegree = _FALSE;
00187 i_LowestCodeZeroRightVertexDegree = i_RightVertexCount;
00188
00189 for(i=0; i<i_RightVertexCount; i++)
00190 {
00191 i_VertexDegree = m_vi_RightVertices[STEP_UP(i)] - m_vi_RightVertices[i];
00192
00193 vi_RightVertexDegree[i] = i_VertexDegree;
00194
00195 vi_CodeZeroRightVertexDegree.push_back(i_VertexDegree);
00196
00197 vli_GroupedCodeZeroRightVertexDegree[i_VertexDegree].push_front(i);
00198
00199 vlit_CodeZeroRightVertexLocation.push_back(vli_GroupedCodeZeroRightVertexDegree[i_VertexDegree].begin());
00200
00201 if(i_HighestCodeZeroRightVertexDegree < i_VertexDegree)
00202 {
00203 i_HighestCodeZeroRightVertexDegree = i_VertexDegree;
00204 }
00205
00206 if(i_LowestCodeZeroRightVertexDegree > i_VertexDegree)
00207 {
00208 i_LowestCodeZeroRightVertexDegree = i_VertexDegree;
00209 }
00210 }
00211
00212 vi_CodeOneLeftVertexDegree.clear();
00213 vi_CodeOneLeftVertexDegree.resize((unsigned) i_LeftVertexCount, _FALSE);
00214
00215 vi_CodeTwoLeftVertexDegree.clear();
00216 vi_CodeTwoLeftVertexDegree.resize((unsigned) i_LeftVertexCount, _FALSE);
00217
00218 vi_CodeThreeLeftVertexDegree.clear();
00219 vi_CodeThreeLeftVertexDegree.resize((unsigned) i_LeftVertexCount, _FALSE);
00220
00221 vi_CodeOneRightVertexDegree.clear();
00222 vi_CodeOneRightVertexDegree.resize((unsigned) i_RightVertexCount, _FALSE);
00223
00224 vi_CodeTwoRightVertexDegree.clear();
00225 vi_CodeTwoRightVertexDegree.resize((unsigned) i_RightVertexCount, _FALSE);
00226
00227 vi_CodeThreeRightVertexDegree.clear();
00228 vi_CodeThreeRightVertexDegree.resize((unsigned) i_RightVertexCount, _FALSE);
00229
00230
00231 #if DEBUG == 3355
00232
00233 cout<<endl;
00234 cout<<"DEBUG 3355 | Star Bicoloring | Code Zero Vertex Degrees | Left Vertices"<<endl;
00235 cout<<endl;
00236
00237 for(i=0; i<STEP_UP(i_HighestCodeZeroLeftVertexDegree); i++)
00238 {
00239 cout<<"Code Zero Degree "<<i<<"\t"<<" : ";
00240
00241 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroLeftVertexDegree[i].size();
00242
00243 j = _FALSE;
00244
00245 for(lit_ListIterator = vli_GroupedCodeZeroLeftVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroLeftVertexDegree[i].end(); lit_ListIterator++)
00246 {
00247 if(j==STEP_DOWN(i_CodeZeroDegreeVertexCount))
00248 {
00249 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_CodeZeroDegreeVertexCount<<")";
00250 }
00251 else
00252 {
00253 cout<<STEP_UP(*lit_ListIterator)<<", ";
00254 }
00255
00256 j++;
00257 }
00258
00259 cout<<endl;
00260 }
00261
00262 cout<<endl;
00263 cout<<"DEBUG 3355 | Star Bicoloring | Code Zero Vertex Degrees | Right Vertices"<<endl;
00264 cout<<endl;
00265
00266 for(i=0; i<STEP_UP(i_HighestCodeZeroRightVertexDegree); i++)
00267 {
00268 cout<<"Code Zero Degree "<<i<<"\t"<<" : ";
00269
00270 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroRightVertexDegree[i].size();
00271
00272 j = _FALSE;
00273
00274 for(lit_ListIterator = vli_GroupedCodeZeroRightVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroRightVertexDegree[i].end(); lit_ListIterator++)
00275 {
00276 if(j==STEP_DOWN(i_CodeZeroDegreeVertexCount))
00277 {
00278 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_CodeZeroDegreeVertexCount<<")";
00279 }
00280 else
00281 {
00282 cout<<STEP_UP(*lit_ListIterator)<<", ";
00283 }
00284
00285 j++;
00286 }
00287
00288 cout<<endl;
00289 }
00290
00291 cout<<endl;
00292
00293 #endif
00294
00295 i_HighestCodeTwoLeftVertexDegree = i_HighestCodeThreeRightVertexDegree = _FALSE;
00296
00297 i_CodeZeroEdgeCount = i_EdgeCount;
00298
00299 while(i_CodeZeroEdgeCount)
00300 {
00301 i_CandidateLeftVertex = i_CandidateRightVertex = _UNKNOWN;
00302
00303 for(i=0; i<STEP_UP(i_HighestCodeZeroLeftVertexDegree); i++)
00304 {
00305 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroLeftVertexDegree[i].size();
00306
00307 if(i_CodeZeroDegreeVertexCount != _FALSE)
00308 {
00309 i_VertexDegree = _UNKNOWN;
00310
00311 for(lit_ListIterator = vli_GroupedCodeZeroLeftVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroLeftVertexDegree[i].end(); lit_ListIterator++)
00312 {
00313 if(i_VertexDegree == _UNKNOWN)
00314 {
00315 i_VertexDegree = vi_LeftVertexDegree[*lit_ListIterator];
00316
00317 i_CandidateLeftVertex = *lit_ListIterator;
00318 }
00319 else
00320 {
00321 if(i_VertexDegree > vi_LeftVertexDegree[*lit_ListIterator])
00322 {
00323 i_VertexDegree = vi_LeftVertexDegree[*lit_ListIterator];
00324
00325 i_CandidateLeftVertex = *lit_ListIterator;
00326 }
00327 }
00328 }
00329
00330 break;
00331 }
00332 }
00333
00334 for(i=0; i<STEP_UP(i_HighestCodeZeroRightVertexDegree); i++)
00335 {
00336 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroRightVertexDegree[i].size();
00337
00338 if(i_CodeZeroDegreeVertexCount != _FALSE)
00339 {
00340 i_VertexDegree = _UNKNOWN;
00341
00342 for(lit_ListIterator = vli_GroupedCodeZeroRightVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroRightVertexDegree[i].end(); lit_ListIterator++)
00343 {
00344 if(i_VertexDegree == _UNKNOWN)
00345 {
00346 i_VertexDegree = vi_RightVertexDegree[*lit_ListIterator];
00347
00348 i_CandidateRightVertex = *lit_ListIterator;
00349 }
00350 else
00351 {
00352 if(i_VertexDegree > vi_RightVertexDegree[*lit_ListIterator])
00353 {
00354 i_VertexDegree = vi_RightVertexDegree[*lit_ListIterator];
00355
00356 i_CandidateRightVertex = *lit_ListIterator;
00357 }
00358 }
00359 }
00360
00361 break;
00362 }
00363 }
00364
00365 #if DEBUG == 3355
00366
00367 cout<<endl;
00368 cout<<"DEBUG 3355 | Star Bicoloring | Candidate Vertices"<<endl;
00369 cout<<endl;
00370
00371 cout<<"Candidate Left Vertex = "<<STEP_UP(i_CandidateLeftVertex)<<"; Candidate Right Vertex = "<<STEP_UP(i_CandidateRightVertex)<<endl;
00372 cout<<endl;
00373
00374 #endif
00375
00376 i_CodeZeroOneLeftVertexDegree = vi_CodeZeroLeftVertexDegree[i_CandidateLeftVertex] + vi_CodeOneLeftVertexDegree[i_CandidateLeftVertex];
00377
00378 i_CodeZeroOneRightVertexDegree = vi_CodeZeroRightVertexDegree[i_CandidateRightVertex] + vi_CodeOneRightVertexDegree[i_CandidateRightVertex];
00379
00380
00381 i_QuotientOne = i_HighestCodeTwoLeftVertexDegree>i_CodeZeroOneLeftVertexDegree?i_HighestCodeTwoLeftVertexDegree:i_CodeZeroOneLeftVertexDegree;
00382 i_QuotientOne += i_HighestCodeThreeRightVertexDegree;
00383
00384 i_QuotientTwo = i_HighestCodeThreeRightVertexDegree>i_CodeZeroOneRightVertexDegree?i_HighestCodeThreeRightVertexDegree:i_CodeZeroOneRightVertexDegree;
00385 i_QuotientTwo += i_HighestCodeTwoLeftVertexDegree;
00386
00387 #if DEBUG == 3355
00388
00389 cout<<endl;
00390 cout<<"DEBUG 3355 | Star Bicoloring | Decision Quotients"<<endl;
00391 cout<<endl;
00392
00393 cout<<"Quotient One = "<<i_QuotientOne<<"; Quotient Two = "<<i_QuotientTwo<<endl;
00394
00395 #endif
00396
00397 if(i_QuotientOne < i_QuotientTwo)
00398 {
00399 i_CandidateRightVertex = _UNKNOWN;
00400 }
00401 else
00402 {
00403 i_CandidateLeftVertex = _UNKNOWN;
00404 }
00405
00406 #if DEBUG == 3355
00407
00408 cout<<endl;
00409 cout<<"DEBUG 3355 | Star Bicoloring | Selected Vertex"<<endl;
00410 cout<<endl;
00411
00412 cout<<"Selected Left Vertex = "<<STEP_UP(i_CandidateLeftVertex)<<"; Selected Right Vertex = "<<STEP_UP(i_CandidateRightVertex)<<endl;
00413
00414 #endif
00415
00416 #if DEBUG == 3355
00417
00418 cout<<endl;
00419 cout<<"DEBUG 3355 | Star Bicoloring | Edge Code Changes"<<endl;
00420 cout<<endl;
00421
00422 #endif
00423
00424 if(i_CandidateRightVertex == _UNKNOWN)
00425 {
00426 m_vi_IncludedLeftVertices[i_CandidateLeftVertex] = _FALSE;
00427
00428 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[i_CandidateLeftVertex]].erase(vlit_CodeZeroLeftVertexLocation[i_CandidateLeftVertex]);
00429
00430 for(i=m_vi_LeftVertices[i_CandidateLeftVertex]; i<m_vi_LeftVertices[STEP_UP(i_CandidateLeftVertex)]; i++)
00431 {
00432 i_PresentEdge = m_mimi2_VertexEdgeMap[i_CandidateLeftVertex][m_vi_Edges[i]];
00433
00434 if((vi_EdgeCodes[i_PresentEdge] == _FALSE) || (vi_EdgeCodes[i_PresentEdge] == _TRUE))
00435 {
00436 if(vi_EdgeCodes[i_PresentEdge] == _FALSE)
00437 {
00438 i_CodeZeroEdgeCount = STEP_DOWN(i_CodeZeroEdgeCount);
00439
00440 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
00441 {
00442 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]].erase(vlit_CodeZeroRightVertexLocation[m_vi_Edges[i]]);
00443 }
00444
00445 vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] = _UNKNOWN;
00446 }
00447 else
00448 {
00449 vi_CodeOneRightVertexDegree[m_vi_Edges[i]] = STEP_DOWN(vi_CodeOneRightVertexDegree[m_vi_Edges[i]]);
00450 }
00451
00452 #if DEBUG == 3355
00453
00454 cout<<"Edge "<<STEP_UP(i_CandidateLeftVertex)<<" - "<<STEP_UP(m_vi_Edges[i])<<" ["<<STEP_UP(i_PresentEdge)<<"] : Code Changed From "<<vi_EdgeCodes[i_PresentEdge]<<" To 2"<<endl;
00455
00456 #endif
00457
00458 vi_EdgeCodes[i_PresentEdge] = 2;
00459
00460 vi_CodeTwoLeftVertexDegree[i_CandidateLeftVertex] = STEP_UP(vi_CodeTwoLeftVertexDegree[i_CandidateLeftVertex]);
00461
00462 if(i_HighestCodeTwoLeftVertexDegree < vi_CodeTwoLeftVertexDegree[i_CandidateLeftVertex])
00463 {
00464 i_HighestCodeTwoLeftVertexDegree = vi_CodeTwoLeftVertexDegree[i_CandidateLeftVertex];
00465 }
00466
00467 vi_CodeTwoRightVertexDegree[m_vi_Edges[i]] = STEP_UP(vi_CodeTwoRightVertexDegree[m_vi_Edges[i]]);
00468
00469 for(j=m_vi_RightVertices[m_vi_Edges[i]]; j<m_vi_RightVertices[STEP_UP(m_vi_Edges[i])]; j++)
00470 {
00471 if(m_vi_Edges[j] == i_CandidateLeftVertex)
00472 {
00473 continue;
00474 }
00475
00476 i_NeighboringEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[i]];
00477
00478 if(vi_EdgeCodes[i_NeighboringEdge] == _FALSE)
00479 {
00480 i_CodeZeroEdgeCount = STEP_DOWN(i_CodeZeroEdgeCount);
00481
00482 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]] > _UNKNOWN)
00483 {
00484 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]]].erase(vlit_CodeZeroLeftVertexLocation[m_vi_Edges[j]]);
00485 }
00486
00487 vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]] = STEP_DOWN(vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]]);
00488
00489 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]] > _UNKNOWN)
00490 {
00491 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]]].push_front(m_vi_Edges[j]);
00492
00493 vlit_CodeZeroLeftVertexLocation[m_vi_Edges[j]] = vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]]].begin();
00494 }
00495
00496 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
00497 {
00498 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]].erase(vlit_CodeZeroRightVertexLocation[m_vi_Edges[i]]);
00499 }
00500
00501 vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] = STEP_DOWN(vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]);
00502
00503 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
00504 {
00505 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]].push_front(m_vi_Edges[i]);
00506
00507 vlit_CodeZeroRightVertexLocation[m_vi_Edges[i]] = vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]].begin();
00508 }
00509
00510 #if DEBUG == 3355
00511
00512 cout<<"Edge "<<STEP_UP(m_vi_Edges[j])<<" - "<<STEP_UP(m_vi_Edges[i])<<" ["<<STEP_UP(i_NeighboringEdge)<<"] : Code Changed From "<<vi_EdgeCodes[i_NeighboringEdge]<<" To 1"<<endl;
00513
00514 #endif
00515
00516 vi_EdgeCodes[i_NeighboringEdge] = _TRUE;
00517
00518 vi_CodeOneLeftVertexDegree[m_vi_Edges[j]] = STEP_UP(vi_CodeOneLeftVertexDegree[m_vi_Edges[j]]);
00519
00520 vi_CodeOneRightVertexDegree[m_vi_Edges[i]] = STEP_UP(vi_CodeOneRightVertexDegree[m_vi_Edges[i]]);
00521
00522 }
00523 }
00524 }
00525 }
00526 }
00527 else
00528 if(i_CandidateLeftVertex == _UNKNOWN)
00529 {
00530 m_vi_IncludedRightVertices[i_CandidateRightVertex] = _FALSE;
00531
00532 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[i_CandidateRightVertex]].erase(vlit_CodeZeroRightVertexLocation[i_CandidateRightVertex]);
00533
00534 for(i=m_vi_RightVertices[i_CandidateRightVertex]; i<m_vi_RightVertices[STEP_UP(i_CandidateRightVertex)]; i++)
00535 {
00536 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[i]][i_CandidateRightVertex];
00537
00538 if((vi_EdgeCodes[i_PresentEdge] == _FALSE) || (vi_EdgeCodes[i_PresentEdge] == _TRUE))
00539 {
00540 if(vi_EdgeCodes[i_PresentEdge] == _FALSE)
00541 {
00542 i_CodeZeroEdgeCount = STEP_DOWN(i_CodeZeroEdgeCount);
00543
00544 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
00545 {
00546 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]].erase(vlit_CodeZeroLeftVertexLocation[m_vi_Edges[i]]);
00547 }
00548
00549 vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] = _UNKNOWN;
00550 }
00551 else
00552 {
00553 vi_CodeOneLeftVertexDegree[m_vi_Edges[i]] = STEP_DOWN(vi_CodeOneLeftVertexDegree[m_vi_Edges[i]]);
00554 }
00555
00556
00557 #if DEBUG == 3355
00558 cout<<"Edge "<<STEP_UP(m_vi_Edges[i])<<" - "<<STEP_UP(i_CandidateRightVertex)<<" ["<<STEP_UP(i_PresentEdge)<<"] : Code Changed From "<<vi_EdgeCodes[i_PresentEdge]<<" To 3"<<endl;
00559 #endif
00560
00561 vi_EdgeCodes[i_PresentEdge] = 3;
00562
00563 vi_CodeThreeLeftVertexDegree[m_vi_Edges[i]] = STEP_UP(vi_CodeThreeLeftVertexDegree[m_vi_Edges[i]]);
00564
00565 vi_CodeThreeRightVertexDegree[i_CandidateRightVertex] = STEP_UP(vi_CodeThreeRightVertexDegree[i_CandidateRightVertex]);
00566
00567 if(i_HighestCodeThreeRightVertexDegree < vi_CodeThreeRightVertexDegree[i_CandidateRightVertex])
00568 {
00569 i_HighestCodeThreeRightVertexDegree = vi_CodeThreeRightVertexDegree[i_CandidateRightVertex];
00570 }
00571
00572 for(j=m_vi_LeftVertices[m_vi_Edges[i]]; j<m_vi_LeftVertices[STEP_UP(m_vi_Edges[i])]; j++)
00573 {
00574 if(m_vi_Edges[j] == i_CandidateRightVertex)
00575 {
00576 continue;
00577 }
00578
00579 i_NeighboringEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[i]][m_vi_Edges[j]];
00580
00581 if(vi_EdgeCodes[i_NeighboringEdge] == _FALSE)
00582 {
00583 i_CodeZeroEdgeCount = STEP_DOWN(i_CodeZeroEdgeCount);
00584
00585 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
00586 {
00587 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]].erase(vlit_CodeZeroLeftVertexLocation[m_vi_Edges[i]]);
00588 }
00589
00590 vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] = STEP_DOWN(vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]);
00591
00592 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
00593 {
00594 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]].push_front(m_vi_Edges[i]);
00595
00596 vlit_CodeZeroLeftVertexLocation[m_vi_Edges[i]] = vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]].begin();
00597 }
00598
00599 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[j]] > _UNKNOWN)
00600 {
00601 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[j]]].erase(vlit_CodeZeroRightVertexLocation[m_vi_Edges[j]]);
00602 }
00603
00604 vi_CodeZeroRightVertexDegree[m_vi_Edges[j]] = STEP_DOWN(vi_CodeZeroRightVertexDegree[m_vi_Edges[j]]);
00605
00606 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[j]] > _UNKNOWN)
00607 {
00608 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[j]]].push_front(m_vi_Edges[j]);
00609
00610 vlit_CodeZeroRightVertexLocation[m_vi_Edges[j]] = vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[j]]].begin();
00611
00612 }
00613
00614 #if DEBUG == 3355
00615
00616 cout<<"Edge "<<STEP_UP(m_vi_Edges[i])<<" - "<<STEP_UP(m_vi_Edges[j])<<" ["<<STEP_UP(i_NeighboringEdge)<<"] : Code Changed From "<<vi_EdgeCodes[i_NeighboringEdge]<<" To 1"<<endl;
00617
00618 #endif
00619 vi_EdgeCodes[i_NeighboringEdge] = _TRUE;
00620
00621 vi_CodeOneLeftVertexDegree[m_vi_Edges[i]] = STEP_UP(vi_CodeOneLeftVertexDegree[m_vi_Edges[i]]);
00622
00623 vi_CodeOneRightVertexDegree[m_vi_Edges[j]] = STEP_UP(vi_CodeOneRightVertexDegree[m_vi_Edges[j]]);
00624
00625 }
00626 }
00627 }
00628 }
00629 }
00630
00631 #if DEBUG == 3355
00632
00633 cout<<endl;
00634 cout<<"DEBUG 3355 | Star Bicoloring | Code Zero Vertex Degrees | Left Vertices"<<endl;
00635 cout<<endl;
00636
00637 for(i=0; i<STEP_UP(i_HighestCodeZeroLeftVertexDegree); i++)
00638 {
00639 cout<<"Code Zero Degree "<<i<<"\t"<<" : ";
00640
00641 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroLeftVertexDegree[i].size();
00642
00643 j = _FALSE;
00644
00645 for(lit_ListIterator = vli_GroupedCodeZeroLeftVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroLeftVertexDegree[i].end(); lit_ListIterator++)
00646 {
00647 if(j==STEP_DOWN(i_CodeZeroDegreeVertexCount))
00648 {
00649 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_CodeZeroDegreeVertexCount<<")";
00650 }
00651 else
00652 {
00653 cout<<STEP_UP(*lit_ListIterator)<<", ";
00654 }
00655
00656 j++;
00657 }
00658
00659 cout<<endl;
00660 }
00661
00662 cout<<endl;
00663 cout<<"DEBUG 3355 | Star Bicoloring | Code Zero Vertex Degrees | Right Vertices"<<endl;
00664 cout<<endl;
00665
00666 for(i=0; i<STEP_UP(i_HighestCodeZeroRightVertexDegree); i++)
00667 {
00668 cout<<"Code Zero Degree "<<i<<"\t"<<" : ";
00669
00670 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroRightVertexDegree[i].size();
00671
00672 j = _FALSE;
00673
00674 for(lit_ListIterator = vli_GroupedCodeZeroRightVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroRightVertexDegree[i].end(); lit_ListIterator++)
00675 {
00676 if(j==STEP_DOWN(i_CodeZeroDegreeVertexCount))
00677 {
00678 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_CodeZeroDegreeVertexCount<<")";
00679 }
00680 else
00681 {
00682 cout<<STEP_UP(*lit_ListIterator)<<", ";
00683 }
00684
00685 j++;
00686 }
00687
00688 cout<<endl;
00689 }
00690
00691 cout<<endl;
00692 cout<<"[Edges Left = "<<i_CodeZeroEdgeCount<<"]"<<endl;
00693 cout<<endl;
00694
00695 #endif
00696
00697 }
00698
00699 m_vi_CoveredLeftVertices.clear();
00700 m_vi_CoveredRightVertices.clear();
00701
00702 for(i=0; i<i_LeftVertexCount; i++)
00703 {
00704 if(m_vi_IncludedLeftVertices[i] == _TRUE)
00705 {
00706 m_vi_CoveredLeftVertices.push_back(i);
00707 }
00708 }
00709
00710 for(i=0; i<i_RightVertexCount; i++)
00711 {
00712 if(m_vi_IncludedRightVertices[i] == _TRUE)
00713 {
00714 m_vi_CoveredRightVertices.push_back(i);
00715 }
00716 }
00717
00718
00719 #if DEBUG == 3355
00720
00721 int k;
00722
00723 int i_CoveredEdgeCount;
00724
00725 int i_LeftVertexCoverSize, i_RightVertexCoverSize;
00726
00727 i_CoveredEdgeCount = _FALSE;
00728
00729 cout<<endl;
00730 cout<<"DEBUG 3355 | Star Bicoloring | Vertex Cover | Left Vertices"<<endl;
00731 cout<<endl;
00732
00733 i_LeftVertexCoverSize = m_vi_CoveredLeftVertices.size();
00734
00735 if(!i_LeftVertexCoverSize)
00736 {
00737 cout<<endl;
00738 cout<<"No Left Vertex Included"<<endl;
00739 cout<<endl;
00740 }
00741
00742 for(i=0; i<i_LeftVertexCoverSize; i++)
00743 {
00744 cout<<STEP_UP(m_vi_CoveredLeftVertices[i])<<"\t"<<" : ";
00745
00746 i_VertexDegree = m_vi_LeftVertices[STEP_UP(m_vi_CoveredLeftVertices[i])] - m_vi_LeftVertices[m_vi_CoveredLeftVertices[i]];
00747
00748 k = _FALSE;
00749
00750 for(j=m_vi_LeftVertices[m_vi_CoveredLeftVertices[i]]; j<m_vi_LeftVertices[STEP_UP(m_vi_CoveredLeftVertices[i])]; j++)
00751 {
00752 if(k == STEP_DOWN(i_VertexDegree))
00753 {
00754 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_CoveredLeftVertices[i]][m_vi_Edges[j]])<<" ("<<i_VertexDegree<<") ";
00755 }
00756 else
00757 {
00758 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_CoveredLeftVertices[i]][m_vi_Edges[j]])<<", ";
00759 }
00760
00761 k++;
00762 }
00763
00764 cout<<endl;
00765
00766 i_CoveredEdgeCount += k;
00767
00768 }
00769
00770 cout<<endl;
00771 cout<<"DEBUG 3355 | Star Bicoloring | Vertex Cover | Right Vertices"<<endl;
00772 cout<<endl;
00773
00774 i_RightVertexCoverSize = m_vi_CoveredRightVertices.size();
00775
00776 if(!i_RightVertexCoverSize)
00777 {
00778 cout<<endl;
00779 cout<<"No Right Vertex Included"<<endl;
00780 cout<<endl;
00781 }
00782
00783 for(i=0; i<i_RightVertexCoverSize; i++)
00784 {
00785 cout<<STEP_UP(m_vi_CoveredRightVertices[i])<<"\t"<<" : ";
00786
00787 i_VertexDegree = m_vi_RightVertices[STEP_UP(m_vi_CoveredRightVertices[i])] - m_vi_RightVertices[m_vi_CoveredRightVertices[i]];
00788
00789 k = _FALSE;
00790
00791 for(j=m_vi_RightVertices[m_vi_CoveredRightVertices[i]]; j<m_vi_RightVertices[STEP_UP(m_vi_CoveredRightVertices[i])]; j++)
00792 {
00793 if(k == STEP_DOWN(i_VertexDegree))
00794 {
00795 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_CoveredRightVertices[i]])<<" ("<<i_VertexDegree<<")";
00796 }
00797 else
00798 {
00799 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_CoveredRightVertices[i]])<<", ";
00800 }
00801
00802 k++;
00803 }
00804
00805 cout<<endl;
00806
00807 i_CoveredEdgeCount += k;
00808 }
00809
00810 cout<<endl;
00811 cout<<"[Left Vertex Cover Size = "<<i_LeftVertexCoverSize<<"; Right Vertex Cover Size = "<<i_RightVertexCoverSize<<"; Edges Covered = "<<i_CoveredEdgeCount<<"]"<<endl;
00812 cout<<endl;
00813
00814 #endif
00815
00816 return(_TRUE);
00817 }
00818
00819
00820
00821 int BipartiteGraphVertexCover::CoverVertex(vector<int> & vi_EdgeCodes)
00822 {
00823 int i, j;
00824
00825 int i_EdgeCount, i_CodeZeroEdgeCount;
00826
00827 int i_CandidateLeftVertex, i_CandidateRightVertex;
00828
00829 int i_LeftVertexCount, i_RightVertexCount;
00830
00831 int i_PresentEdge, i_NeighboringEdge;
00832
00833 int i_QuotientOne, i_QuotientTwo;
00834
00835 int i_VertexDegree, i_CodeZeroDegreeVertexCount;
00836
00837 int i_CodeZeroOneLeftVertexDegree, i_CodeZeroOneRightVertexDegree;
00838
00839 int i_HighestCodeZeroLeftVertexDegree, i_LowestCodeZeroLeftVertexDegree;
00840
00841 int i_HighestCodeZeroRightVertexDegree, i_LowestCodeZeroRightVertexDegree;
00842
00843 int i_HighestCodeTwoLeftVertexDegree, i_HighestCodeThreeRightVertexDegree;
00844
00845 vector<int> vi_LeftVertexDegree, vi_CodeZeroLeftVertexDegree, vi_CodeOneLeftVertexDegree, vi_CodeTwoLeftVertexDegree, vi_CodeThreeLeftVertexDegree;
00846
00847 vector<int> vi_RightVertexDegree, vi_CodeZeroRightVertexDegree, vi_CodeOneRightVertexDegree, vi_CodeTwoRightVertexDegree, vi_CodeThreeRightVertexDegree;
00848
00849 vector< list<int> > vli_GroupedCodeZeroLeftVertexDegree, vli_GroupedCodeZeroRightVertexDegree;
00850
00851 vector< list<int>::iterator > vlit_CodeZeroLeftVertexLocation, vlit_CodeZeroRightVertexLocation;
00852
00853 list<int>::iterator lit_ListIterator;
00854
00855 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size());
00856 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size());
00857
00858 m_vi_IncludedLeftVertices.clear();
00859 m_vi_IncludedLeftVertices.resize((unsigned) i_LeftVertexCount, _TRUE);
00860
00861 m_vi_IncludedRightVertices.clear();
00862 m_vi_IncludedRightVertices.resize((unsigned) i_RightVertexCount, _TRUE);
00863
00864 #if DEBUG == 3356
00865
00866 cout<<endl;
00867 cout<<"DEBUG 3356 | Star Bicoloring | Edge Codes | Left and Right Vertices"<<endl;
00868 cout<<endl;
00869
00870 for(i=0; i<i_LeftVertexCount; i++)
00871 {
00872 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++)
00873 {
00874 cout<<STEP_UP(m_mimi2_VertexEdgeMap[i][m_vi_Edges[j]])<<"\t"<<" : "<<STEP_UP(i)<<" - "<<STEP_UP(m_vi_Edges[j])<<endl;
00875 }
00876 }
00877
00878 #endif
00879
00880 i_EdgeCount = (signed) m_vi_Edges.size()/2;
00881
00882 vi_EdgeCodes.clear();
00883 vi_EdgeCodes.resize((unsigned) i_EdgeCount, _FALSE);
00884
00885 vi_LeftVertexDegree.clear();
00886 vi_LeftVertexDegree.resize((unsigned) i_LeftVertexCount);
00887
00888 vi_CodeZeroLeftVertexDegree.clear();
00889
00890 vli_GroupedCodeZeroLeftVertexDegree.clear();
00891 vli_GroupedCodeZeroLeftVertexDegree.resize((unsigned) STEP_UP(i_RightVertexCount));
00892
00893 vlit_CodeZeroLeftVertexLocation.clear();
00894
00895 i_HighestCodeZeroLeftVertexDegree = _FALSE;
00896 i_LowestCodeZeroLeftVertexDegree = i_RightVertexCount;
00897
00898 for(i=0; i<i_LeftVertexCount; i++)
00899 {
00900 i_VertexDegree = m_vi_LeftVertices[STEP_UP(i)] - m_vi_LeftVertices[i];
00901
00902 vi_LeftVertexDegree[i] = i_VertexDegree;
00903
00904 vi_CodeZeroLeftVertexDegree.push_back(i_VertexDegree);
00905
00906 vli_GroupedCodeZeroLeftVertexDegree[i_VertexDegree].push_front(i);
00907
00908 vlit_CodeZeroLeftVertexLocation.push_back(vli_GroupedCodeZeroLeftVertexDegree[i_VertexDegree].begin());
00909
00910 if(i_HighestCodeZeroLeftVertexDegree < i_VertexDegree)
00911 {
00912 i_HighestCodeZeroLeftVertexDegree = i_VertexDegree;
00913 }
00914
00915 if(i_LowestCodeZeroLeftVertexDegree > i_VertexDegree)
00916 {
00917 i_LowestCodeZeroLeftVertexDegree = i_VertexDegree;
00918 }
00919 }
00920
00921 vi_RightVertexDegree.clear();
00922 vi_RightVertexDegree.resize((unsigned) i_RightVertexCount);
00923
00924 vi_CodeZeroRightVertexDegree.clear();
00925
00926 vli_GroupedCodeZeroRightVertexDegree.clear();
00927 vli_GroupedCodeZeroRightVertexDegree.resize((unsigned) STEP_UP(i_LeftVertexCount));
00928
00929 vlit_CodeZeroRightVertexLocation.clear();
00930
00931 i_HighestCodeZeroRightVertexDegree = _FALSE;
00932 i_LowestCodeZeroRightVertexDegree = i_RightVertexCount;
00933
00934 for(i=0; i<i_RightVertexCount; i++)
00935 {
00936 i_VertexDegree = m_vi_RightVertices[STEP_UP(i)] - m_vi_RightVertices[i];
00937
00938 vi_RightVertexDegree[i] = i_VertexDegree;
00939
00940 vi_CodeZeroRightVertexDegree.push_back(i_VertexDegree);
00941
00942 vli_GroupedCodeZeroRightVertexDegree[i_VertexDegree].push_front(i);
00943
00944 vlit_CodeZeroRightVertexLocation.push_back(vli_GroupedCodeZeroRightVertexDegree[i_VertexDegree].begin());
00945
00946 if(i_HighestCodeZeroRightVertexDegree < i_VertexDegree)
00947 {
00948 i_HighestCodeZeroRightVertexDegree = i_VertexDegree;
00949 }
00950
00951 if(i_LowestCodeZeroRightVertexDegree > i_VertexDegree)
00952 {
00953 i_LowestCodeZeroRightVertexDegree = i_VertexDegree;
00954 }
00955 }
00956
00957 vi_CodeOneLeftVertexDegree.clear();
00958 vi_CodeOneLeftVertexDegree.resize((unsigned) i_LeftVertexCount, _FALSE);
00959
00960 vi_CodeTwoLeftVertexDegree.clear();
00961 vi_CodeTwoLeftVertexDegree.resize((unsigned) i_LeftVertexCount, _FALSE);
00962
00963 vi_CodeThreeLeftVertexDegree.clear();
00964 vi_CodeThreeLeftVertexDegree.resize((unsigned) i_LeftVertexCount, _FALSE);
00965
00966 vi_CodeOneRightVertexDegree.clear();
00967 vi_CodeOneRightVertexDegree.resize((unsigned) i_RightVertexCount, _FALSE);
00968
00969 vi_CodeTwoRightVertexDegree.clear();
00970 vi_CodeTwoRightVertexDegree.resize((unsigned) i_RightVertexCount, _FALSE);
00971
00972 vi_CodeThreeRightVertexDegree.clear();
00973 vi_CodeThreeRightVertexDegree.resize((unsigned) i_RightVertexCount, _FALSE);
00974
00975
00976 #if DEBUG == 3356
00977
00978 cout<<endl;
00979 cout<<"DEBUG 3356 | Star Bicoloring | Code Zero Vertex Degrees | Left Vertices"<<endl;
00980 cout<<endl;
00981
00982 for(i=0; i<STEP_UP(i_HighestCodeZeroLeftVertexDegree); i++)
00983 {
00984 cout<<"Code Zero Degree "<<i<<"\t"<<" : ";
00985
00986 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroLeftVertexDegree[i].size();
00987
00988 j = _FALSE;
00989
00990 for(lit_ListIterator = vli_GroupedCodeZeroLeftVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroLeftVertexDegree[i].end(); lit_ListIterator++)
00991 {
00992 if(j==STEP_DOWN(i_CodeZeroDegreeVertexCount))
00993 {
00994 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_CodeZeroDegreeVertexCount<<")";
00995 }
00996 else
00997 {
00998 cout<<STEP_UP(*lit_ListIterator)<<", ";
00999 }
01000
01001 j++;
01002 }
01003
01004 cout<<endl;
01005 }
01006
01007 cout<<endl;
01008 cout<<"DEBUG 3356 | Star Bicoloring | Code Zero Vertex Degrees | Right Vertices"<<endl;
01009 cout<<endl;
01010
01011 for(i=0; i<STEP_UP(i_HighestCodeZeroRightVertexDegree); i++)
01012 {
01013 cout<<"Code Zero Degree "<<i<<"\t"<<" : ";
01014
01015 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroRightVertexDegree[i].size();
01016
01017 j = _FALSE;
01018
01019 for(lit_ListIterator = vli_GroupedCodeZeroRightVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroRightVertexDegree[i].end(); lit_ListIterator++)
01020 {
01021 if(j==STEP_DOWN(i_CodeZeroDegreeVertexCount))
01022 {
01023 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_CodeZeroDegreeVertexCount<<")";
01024 }
01025 else
01026 {
01027 cout<<STEP_UP(*lit_ListIterator)<<", ";
01028 }
01029
01030 j++;
01031 }
01032
01033 cout<<endl;
01034 }
01035
01036 cout<<endl;
01037
01038 #endif
01039
01040 i_HighestCodeTwoLeftVertexDegree = i_HighestCodeThreeRightVertexDegree = _FALSE;
01041
01042 i_CodeZeroEdgeCount = i_EdgeCount;
01043
01044 while(i_CodeZeroEdgeCount)
01045 {
01046 i_CandidateLeftVertex = i_CandidateRightVertex = _UNKNOWN;
01047
01048 for(i=0; i<STEP_UP(i_HighestCodeZeroLeftVertexDegree); i++)
01049 {
01050 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroLeftVertexDegree[i].size();
01051
01052 if(i_CodeZeroDegreeVertexCount != _FALSE)
01053 {
01054 i_VertexDegree = _UNKNOWN;
01055
01056 for(lit_ListIterator = vli_GroupedCodeZeroLeftVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroLeftVertexDegree[i].end(); lit_ListIterator++)
01057 {
01058 if(i_VertexDegree == _UNKNOWN)
01059 {
01060 i_VertexDegree = vi_LeftVertexDegree[*lit_ListIterator];
01061
01062 i_CandidateLeftVertex = *lit_ListIterator;
01063 }
01064 else
01065 {
01066 if(i_VertexDegree > vi_LeftVertexDegree[*lit_ListIterator])
01067 {
01068 i_VertexDegree = vi_LeftVertexDegree[*lit_ListIterator];
01069
01070 i_CandidateLeftVertex = *lit_ListIterator;
01071 }
01072 }
01073 }
01074
01075 break;
01076 }
01077 }
01078
01079 for(i=0; i<STEP_UP(i_HighestCodeZeroRightVertexDegree); i++)
01080 {
01081 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroRightVertexDegree[i].size();
01082
01083 if(i_CodeZeroDegreeVertexCount != _FALSE)
01084 {
01085 i_VertexDegree = _UNKNOWN;
01086
01087 for(lit_ListIterator = vli_GroupedCodeZeroRightVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroRightVertexDegree[i].end(); lit_ListIterator++)
01088 {
01089 if(i_VertexDegree == _UNKNOWN)
01090 {
01091 i_VertexDegree = vi_RightVertexDegree[*lit_ListIterator];
01092
01093 i_CandidateRightVertex = *lit_ListIterator;
01094 }
01095 else
01096 {
01097 if(i_VertexDegree > vi_RightVertexDegree[*lit_ListIterator])
01098 {
01099 i_VertexDegree = vi_RightVertexDegree[*lit_ListIterator];
01100
01101 i_CandidateRightVertex = *lit_ListIterator;
01102 }
01103 }
01104 }
01105
01106 break;
01107 }
01108 }
01109
01110 #if DEBUG == 3356
01111
01112 cout<<endl;
01113 cout<<"DEBUG 3356 | Star Bicoloring | Candidate Vertices"<<endl;
01114 cout<<endl;
01115
01116 cout<<"Candidate Left Vertex = "<<STEP_UP(i_CandidateLeftVertex)<<"; Candidate Right Vertex = "<<STEP_UP(i_CandidateRightVertex)<<endl;
01117 cout<<endl;
01118
01119 #endif
01120
01121 i_CodeZeroOneLeftVertexDegree = vi_CodeZeroLeftVertexDegree[i_CandidateLeftVertex] + vi_CodeOneLeftVertexDegree[i_CandidateLeftVertex];
01122
01123 i_CodeZeroOneRightVertexDegree = vi_CodeZeroRightVertexDegree[i_CandidateRightVertex] + vi_CodeOneRightVertexDegree[i_CandidateRightVertex];
01124
01125
01126 i_QuotientOne = i_HighestCodeTwoLeftVertexDegree>i_CodeZeroOneLeftVertexDegree?i_HighestCodeTwoLeftVertexDegree:i_CodeZeroOneLeftVertexDegree;
01127 i_QuotientOne += i_HighestCodeThreeRightVertexDegree;
01128
01129 i_QuotientTwo = i_HighestCodeThreeRightVertexDegree>i_CodeZeroOneRightVertexDegree?i_HighestCodeThreeRightVertexDegree:i_CodeZeroOneRightVertexDegree;
01130 i_QuotientTwo += i_HighestCodeTwoLeftVertexDegree;
01131
01132 #if DEBUG == 3356
01133
01134 cout<<endl;
01135 cout<<"DEBUG 3356 | Star Bicoloring | Decision Quotients"<<endl;
01136 cout<<endl;
01137
01138 cout<<"Quotient One = "<<i_QuotientOne<<"; Quotient Two = "<<i_QuotientTwo<<endl;
01139
01140 #endif
01141
01142 if(i_QuotientOne < i_QuotientTwo)
01143 {
01144 i_CandidateRightVertex = _UNKNOWN;
01145 }
01146 else
01147 {
01148 i_CandidateLeftVertex = _UNKNOWN;
01149 }
01150
01151 #if DEBUG == 3356
01152
01153 cout<<endl;
01154 cout<<"DEBUG 3356 | Star Bicoloring | Selected Vertex"<<endl;
01155 cout<<endl;
01156
01157 cout<<"Selected Left Vertex = "<<STEP_UP(i_CandidateLeftVertex)<<"; Selected Right Vertex = "<<STEP_UP(i_CandidateRightVertex)<<endl;
01158
01159 #endif
01160
01161 #if DEBUG == 3356
01162
01163 cout<<endl;
01164 cout<<"DEBUG 3356 | Star Bicoloring | Edge Code Changes"<<endl;
01165 cout<<endl;
01166
01167 #endif
01168
01169 if(i_CandidateRightVertex == _UNKNOWN)
01170 {
01171 m_vi_IncludedLeftVertices[i_CandidateLeftVertex] = _FALSE;
01172
01173 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[i_CandidateLeftVertex]].erase(vlit_CodeZeroLeftVertexLocation[i_CandidateLeftVertex]);
01174
01175 for(i=m_vi_LeftVertices[i_CandidateLeftVertex]; i<m_vi_LeftVertices[STEP_UP(i_CandidateLeftVertex)]; i++)
01176 {
01177 i_PresentEdge = m_mimi2_VertexEdgeMap[i_CandidateLeftVertex][m_vi_Edges[i]];
01178
01179 if((vi_EdgeCodes[i_PresentEdge] == _FALSE) || (vi_EdgeCodes[i_PresentEdge] == _TRUE))
01180 {
01181 if(vi_EdgeCodes[i_PresentEdge] == _FALSE)
01182 {
01183 i_CodeZeroEdgeCount = STEP_DOWN(i_CodeZeroEdgeCount);
01184
01185 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
01186 {
01187 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]].erase(vlit_CodeZeroRightVertexLocation[m_vi_Edges[i]]);
01188 }
01189
01190 vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] = _UNKNOWN;
01191
01192 }
01193 else
01194 {
01195 vi_CodeOneRightVertexDegree[m_vi_Edges[i]] = STEP_DOWN(vi_CodeOneRightVertexDegree[m_vi_Edges[i]]);
01196 }
01197
01198 #if DEBUG == 3356
01199
01200 cout<<"Edge "<<STEP_UP(i_CandidateLeftVertex)<<" - "<<STEP_UP(m_vi_Edges[i])<<" ["<<STEP_UP(i_PresentEdge)<<"] : Code Changed From "<<vi_EdgeCodes[i_PresentEdge]<<" To 2"<<endl;
01201
01202 #endif
01203 vi_EdgeCodes[i_PresentEdge] = 2;
01204
01205 vi_CodeTwoLeftVertexDegree[i_CandidateLeftVertex] = STEP_UP(vi_CodeTwoLeftVertexDegree[i_CandidateLeftVertex]);
01206
01207 if(i_HighestCodeTwoLeftVertexDegree < vi_CodeTwoLeftVertexDegree[i_CandidateLeftVertex])
01208 {
01209 i_HighestCodeTwoLeftVertexDegree = vi_CodeTwoLeftVertexDegree[i_CandidateLeftVertex];
01210 }
01211
01212 vi_CodeTwoRightVertexDegree[m_vi_Edges[i]] = STEP_UP(vi_CodeTwoRightVertexDegree[m_vi_Edges[i]]);
01213
01214
01215 for(j=m_vi_RightVertices[m_vi_Edges[i]]; j<m_vi_RightVertices[STEP_UP(m_vi_Edges[i])]; j++)
01216 {
01217 if(m_vi_Edges[j] == i_CandidateLeftVertex)
01218 {
01219 continue;
01220 }
01221
01222 i_NeighboringEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_Edges[i]];
01223
01224 if(vi_EdgeCodes[i_NeighboringEdge] == _FALSE)
01225 {
01226 i_CodeZeroEdgeCount = STEP_DOWN(i_CodeZeroEdgeCount);
01227
01228 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]] > _UNKNOWN)
01229 {
01230 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]]].erase(vlit_CodeZeroLeftVertexLocation[m_vi_Edges[j]]);
01231 }
01232
01233 vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]] = STEP_DOWN(vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]]);
01234
01235 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]] > _UNKNOWN)
01236 {
01237 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]]].push_front(m_vi_Edges[j]);
01238
01239 vlit_CodeZeroLeftVertexLocation[m_vi_Edges[j]] = vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[j]]].begin();
01240 }
01241
01242 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
01243 {
01244 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]].erase(vlit_CodeZeroRightVertexLocation[m_vi_Edges[i]]);
01245 }
01246
01247 vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] = STEP_DOWN(vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]);
01248
01249 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
01250 {
01251 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]].push_front(m_vi_Edges[i]);
01252
01253 vlit_CodeZeroRightVertexLocation[m_vi_Edges[i]] = vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[i]]].begin();
01254 }
01255
01256
01257 #if DEBUG == 3356
01258
01259 cout<<"Edge "<<STEP_UP(m_vi_Edges[j])<<" - "<<STEP_UP(m_vi_Edges[i])<<" ["<<STEP_UP(i_NeighboringEdge)<<"] : Code Changed From "<<vi_EdgeCodes[i_NeighboringEdge]<<" To 1"<<endl;
01260
01261 #endif
01262
01263 vi_EdgeCodes[i_NeighboringEdge] = _TRUE;
01264
01265 vi_CodeOneLeftVertexDegree[m_vi_Edges[j]] = STEP_UP(vi_CodeOneLeftVertexDegree[m_vi_Edges[j]]);
01266
01267 vi_CodeOneRightVertexDegree[m_vi_Edges[i]] = STEP_UP(vi_CodeOneRightVertexDegree[m_vi_Edges[i]]);
01268
01269 }
01270 }
01271 }
01272 }
01273 }
01274 else
01275 if(i_CandidateLeftVertex == _UNKNOWN)
01276 {
01277 m_vi_IncludedRightVertices[i_CandidateRightVertex] = _FALSE;
01278
01279 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[i_CandidateRightVertex]].erase(vlit_CodeZeroRightVertexLocation[i_CandidateRightVertex]);
01280
01281 for(i=m_vi_RightVertices[i_CandidateRightVertex]; i<m_vi_RightVertices[STEP_UP(i_CandidateRightVertex)]; i++)
01282 {
01283 i_PresentEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[i]][i_CandidateRightVertex];
01284
01285 if((vi_EdgeCodes[i_PresentEdge] == _FALSE) || (vi_EdgeCodes[i_PresentEdge] == _TRUE))
01286 {
01287 if(vi_EdgeCodes[i_PresentEdge] == _FALSE)
01288 {
01289 i_CodeZeroEdgeCount = STEP_DOWN(i_CodeZeroEdgeCount);
01290
01291 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
01292 {
01293 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]].erase(vlit_CodeZeroLeftVertexLocation[m_vi_Edges[i]]);
01294 }
01295
01296 vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] = _UNKNOWN;
01297 }
01298 else
01299 {
01300 vi_CodeOneLeftVertexDegree[m_vi_Edges[i]] = STEP_DOWN(vi_CodeOneLeftVertexDegree[m_vi_Edges[i]]);
01301 }
01302
01303
01304 #if DEBUG == 3356
01305
01306 cout<<"Edge "<<STEP_UP(m_vi_Edges[i])<<" - "<<STEP_UP(i_CandidateRightVertex)<<" ["<<STEP_UP(i_PresentEdge)<<"] : Code Changed From "<<vi_EdgeCodes[i_PresentEdge]<<" To 3"<<endl;
01307
01308 #endif
01309
01310 vi_EdgeCodes[i_PresentEdge] = 3;
01311
01312 vi_CodeThreeLeftVertexDegree[m_vi_Edges[i]] = STEP_UP(vi_CodeThreeLeftVertexDegree[m_vi_Edges[i]]);
01313
01314 vi_CodeThreeRightVertexDegree[i_CandidateRightVertex] = STEP_UP(vi_CodeThreeRightVertexDegree[i_CandidateRightVertex]);
01315
01316 if(i_HighestCodeThreeRightVertexDegree < vi_CodeThreeRightVertexDegree[i_CandidateRightVertex])
01317 {
01318 i_HighestCodeThreeRightVertexDegree = vi_CodeThreeRightVertexDegree[i_CandidateRightVertex];
01319 }
01320
01321 for(j=m_vi_LeftVertices[m_vi_Edges[i]]; j<m_vi_LeftVertices[STEP_UP(m_vi_Edges[i])]; j++)
01322 {
01323 if(m_vi_Edges[j] == i_CandidateRightVertex)
01324 {
01325 continue;
01326 }
01327
01328 i_NeighboringEdge = m_mimi2_VertexEdgeMap[m_vi_Edges[i]][m_vi_Edges[j]];
01329
01330 if(vi_EdgeCodes[i_NeighboringEdge] == _FALSE)
01331 {
01332 i_CodeZeroEdgeCount = STEP_DOWN(i_CodeZeroEdgeCount);
01333
01334 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
01335 {
01336 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]].erase(vlit_CodeZeroLeftVertexLocation[m_vi_Edges[i]]);
01337 }
01338
01339 vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] = STEP_DOWN(vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]);
01340
01341 if(vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]] > _UNKNOWN)
01342 {
01343 vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]].push_front(m_vi_Edges[i]);
01344
01345 vlit_CodeZeroLeftVertexLocation[m_vi_Edges[i]] = vli_GroupedCodeZeroLeftVertexDegree[vi_CodeZeroLeftVertexDegree[m_vi_Edges[i]]].begin();
01346 }
01347
01348 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[j]] > _UNKNOWN)
01349 {
01350 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[j]]].erase(vlit_CodeZeroRightVertexLocation[m_vi_Edges[j]]);
01351 }
01352
01353 vi_CodeZeroRightVertexDegree[m_vi_Edges[j]] = STEP_DOWN(vi_CodeZeroRightVertexDegree[m_vi_Edges[j]]);
01354
01355 if(vi_CodeZeroRightVertexDegree[m_vi_Edges[j]] > _UNKNOWN)
01356 {
01357 vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[j]]].push_front(m_vi_Edges[j]);
01358
01359 vlit_CodeZeroRightVertexLocation[m_vi_Edges[j]] = vli_GroupedCodeZeroRightVertexDegree[vi_CodeZeroRightVertexDegree[m_vi_Edges[j]]].begin();
01360 }
01361
01362
01363 #if DEBUG == 3356
01364
01365 cout<<"Edge "<<STEP_UP(m_vi_Edges[i])<<" - "<<STEP_UP(m_vi_Edges[j])<<" ["<<STEP_UP(i_NeighboringEdge)<<"] : Code Changed From "<<vi_EdgeCodes[i_NeighboringEdge]<<" To 1"<<endl;
01366
01367 #endif
01368 vi_EdgeCodes[i_NeighboringEdge] = _TRUE;
01369
01370 vi_CodeOneLeftVertexDegree[m_vi_Edges[i]] = STEP_UP(vi_CodeOneLeftVertexDegree[m_vi_Edges[i]]);
01371
01372 vi_CodeOneRightVertexDegree[m_vi_Edges[j]] = STEP_UP(vi_CodeOneRightVertexDegree[m_vi_Edges[j]]);
01373
01374 }
01375 }
01376 }
01377 }
01378 }
01379
01380 #if DEBUG == 3356
01381
01382 cout<<endl;
01383 cout<<"DEBUG 3356 | Star Bicoloring | Code Zero Vertex Degrees | Left Vertices"<<endl;
01384 cout<<endl;
01385
01386 for(i=0; i<STEP_UP(i_HighestCodeZeroLeftVertexDegree); i++)
01387 {
01388 cout<<"Code Zero Degree "<<i<<"\t"<<" : ";
01389
01390 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroLeftVertexDegree[i].size();
01391
01392 j = _FALSE;
01393
01394 for(lit_ListIterator = vli_GroupedCodeZeroLeftVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroLeftVertexDegree[i].end(); lit_ListIterator++)
01395 {
01396 if(j==STEP_DOWN(i_CodeZeroDegreeVertexCount))
01397 {
01398 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_CodeZeroDegreeVertexCount<<")";
01399 }
01400 else
01401 {
01402 cout<<STEP_UP(*lit_ListIterator)<<", ";
01403 }
01404
01405 j++;
01406 }
01407
01408 cout<<endl;
01409 }
01410
01411 cout<<endl;
01412 cout<<"DEBUG 3356 | Star Bicoloring | Code Zero Vertex Degrees | Right Vertices"<<endl;
01413 cout<<endl;
01414
01415 for(i=0; i<STEP_UP(i_HighestCodeZeroRightVertexDegree); i++)
01416 {
01417 cout<<"Code Zero Degree "<<i<<"\t"<<" : ";
01418
01419 i_CodeZeroDegreeVertexCount = (signed) vli_GroupedCodeZeroRightVertexDegree[i].size();
01420
01421 j = _FALSE;
01422
01423 for(lit_ListIterator = vli_GroupedCodeZeroRightVertexDegree[i].begin(); lit_ListIterator != vli_GroupedCodeZeroRightVertexDegree[i].end(); lit_ListIterator++)
01424 {
01425 if(j==STEP_DOWN(i_CodeZeroDegreeVertexCount))
01426 {
01427 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_CodeZeroDegreeVertexCount<<")";
01428 }
01429 else
01430 {
01431 cout<<STEP_UP(*lit_ListIterator)<<", ";
01432 }
01433
01434 j++;
01435 }
01436
01437 cout<<endl;
01438 }
01439
01440 cout<<endl;
01441 cout<<"[Edges Left = "<<i_CodeZeroEdgeCount<<"]"<<endl;
01442 cout<<endl;
01443
01444 #endif
01445
01446 }
01447
01448 m_vi_CoveredLeftVertices.clear();
01449 m_vi_CoveredRightVertices.clear();
01450
01451 for(i=0; i<i_LeftVertexCount; i++)
01452 {
01453 if(m_vi_IncludedLeftVertices[i] == _TRUE)
01454 {
01455 m_vi_CoveredLeftVertices.push_back(i);
01456 }
01457 }
01458
01459 for(i=0; i<i_RightVertexCount; i++)
01460 {
01461 if(m_vi_IncludedRightVertices[i] == _TRUE)
01462 {
01463 m_vi_CoveredRightVertices.push_back(i);
01464 }
01465 }
01466
01467
01468 #if DEBUG == 3356
01469
01470 int k;
01471
01472 int i_CoveredEdgeCount;
01473
01474 int i_LeftVertexCoverSize, i_RightVertexCoverSize;
01475
01476 i_CoveredEdgeCount = _FALSE;
01477
01478 cout<<endl;
01479 cout<<"DEBUG 3356 | Star Bicoloring | Vertex Cover | Left Vertices"<<endl;
01480 cout<<endl;
01481
01482 i_LeftVertexCoverSize = m_vi_CoveredLeftVertices.size();
01483
01484 if(!i_LeftVertexCoverSize)
01485 {
01486 cout<<endl;
01487 cout<<"No Left Vertex Included"<<endl;
01488 cout<<endl;
01489 }
01490
01491 for(i=0; i<i_LeftVertexCoverSize; i++)
01492 {
01493 cout<<STEP_UP(m_vi_CoveredLeftVertices[i])<<"\t"<<" : ";
01494
01495 i_VertexDegree = m_vi_LeftVertices[STEP_UP(m_vi_CoveredLeftVertices[i])] - m_vi_LeftVertices[m_vi_CoveredLeftVertices[i]];
01496
01497 k = _FALSE;
01498
01499 for(j=m_vi_LeftVertices[m_vi_CoveredLeftVertices[i]]; j<m_vi_LeftVertices[STEP_UP(m_vi_CoveredLeftVertices[i])]; j++)
01500 {
01501 if(k == STEP_DOWN(i_VertexDegree))
01502 {
01503 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_CoveredLeftVertices[i]][m_vi_Edges[j]])<<" ("<<i_VertexDegree<<") ";
01504 }
01505 else
01506 {
01507 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_CoveredLeftVertices[i]][m_vi_Edges[j]])<<", ";
01508 }
01509
01510 k++;
01511 }
01512
01513 cout<<endl;
01514
01515 i_CoveredEdgeCount += k;
01516
01517 }
01518
01519 cout<<endl;
01520 cout<<"DEBUG 3356 | Star Bicoloring | Vertex Cover | Right Vertices"<<endl;
01521 cout<<endl;
01522
01523 i_RightVertexCoverSize = m_vi_CoveredRightVertices.size();
01524
01525 if(!i_RightVertexCoverSize)
01526 {
01527 cout<<endl;
01528 cout<<"No Right Vertex Included"<<endl;
01529 cout<<endl;
01530 }
01531
01532 for(i=0; i<i_RightVertexCoverSize; i++)
01533 {
01534 cout<<STEP_UP(m_vi_CoveredRightVertices[i])<<"\t"<<" : ";
01535
01536 i_VertexDegree = m_vi_RightVertices[STEP_UP(m_vi_CoveredRightVertices[i])] - m_vi_RightVertices[m_vi_CoveredRightVertices[i]];
01537
01538 k = _FALSE;
01539
01540 for(j=m_vi_RightVertices[m_vi_CoveredRightVertices[i]]; j<m_vi_RightVertices[STEP_UP(m_vi_CoveredRightVertices[i])]; j++)
01541 {
01542 if(k == STEP_DOWN(i_VertexDegree))
01543 {
01544 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_CoveredRightVertices[i]])<<" ("<<i_VertexDegree<<")";
01545 }
01546 else
01547 {
01548 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_CoveredRightVertices[i]])<<", ";
01549 }
01550
01551 k++;
01552 }
01553
01554 cout<<endl;
01555
01556 i_CoveredEdgeCount += k;
01557 }
01558
01559 cout<<endl;
01560 cout<<"[Left Vertex Cover Size = "<<i_LeftVertexCoverSize<<"; Right Vertex Cover Size = "<<i_RightVertexCoverSize<<"; Edges Covered = "<<i_CoveredEdgeCount<<"]"<<endl;
01561 cout<<endl;
01562
01563 #endif
01564
01565 return(_TRUE);
01566 }
01567
01568
01569
01570 int BipartiteGraphVertexCover::CoverMinimalVertex()
01571 {
01572 int i, j;
01573
01574 int i_AvailableVertexCount;
01575
01576 int i_LeftVertexCount, i_RightVertexCount;
01577
01578 int i_PresentVertex, i_SelectedVertex, i_NeighboringVertex, i_SecondNeighboringVertex;
01579
01580 int i_VertexDegree, i_VertexCount;
01581
01582 vector<int> vi_AvailableVertices;
01583
01584 vector<int> vi_IndependentSet;
01585
01586 vector<int> vi_VertexDegree;
01587
01588 vector< list<int> > vli_GroupedVertexDegree;
01589
01590 vector< list<int>::iterator > vlit_VertexLocation;
01591
01592 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size());
01593 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size());
01594
01595 vi_VertexDegree.clear();
01596
01597 vli_GroupedVertexDegree.clear();
01598 vli_GroupedVertexDegree.resize(STEP_UP(i_LeftVertexCount + i_RightVertexCount));
01599
01600 vlit_VertexLocation.clear();
01601
01602 m_i_MaximumVertexDegree = _UNKNOWN;
01603
01604 for(i=0; i<i_LeftVertexCount; i++)
01605 {
01606 i_VertexDegree = m_vi_LeftVertices[STEP_UP(i)] - m_vi_LeftVertices[i];
01607
01608 vi_VertexDegree.push_back(i_VertexDegree);
01609
01610 vli_GroupedVertexDegree[i_VertexDegree].push_front(i);
01611
01612 vlit_VertexLocation.push_back(vli_GroupedVertexDegree[i_VertexDegree].begin());
01613
01614 if(m_i_MaximumVertexDegree < i_VertexDegree)
01615 {
01616 m_i_MaximumVertexDegree = i_VertexDegree;
01617 }
01618 }
01619
01620 for(i=0; i<i_RightVertexCount; i++)
01621 {
01622 i_VertexDegree = m_vi_RightVertices[STEP_UP(i)] - m_vi_RightVertices[i];
01623
01624 vi_VertexDegree.push_back(i_VertexDegree);
01625
01626 vli_GroupedVertexDegree[i_VertexDegree].push_front(i + i_LeftVertexCount);
01627
01628 vlit_VertexLocation.push_back(vli_GroupedVertexDegree[i_VertexDegree].begin());
01629
01630 if(m_i_MaximumVertexDegree < i_VertexDegree)
01631 {
01632 m_i_MaximumVertexDegree = i_VertexDegree;
01633 }
01634 }
01635
01636 i_AvailableVertexCount = i_LeftVertexCount + i_RightVertexCount;
01637
01638 vi_AvailableVertices.clear();
01639 vi_AvailableVertices.resize((unsigned) i_AvailableVertexCount, _TRUE);
01640
01641 m_vi_IncludedLeftVertices.clear();
01642 m_vi_IncludedLeftVertices.resize((unsigned) i_LeftVertexCount, _TRUE);
01643
01644 m_vi_IncludedRightVertices.clear();
01645 m_vi_IncludedRightVertices.resize((unsigned) i_RightVertexCount, _TRUE);
01646
01647 vi_IndependentSet.clear();
01648
01649 i_SelectedVertex = _UNKNOWN;
01650
01651 while(i_AvailableVertexCount)
01652 {
01653 for(i=0; i<STEP_UP(m_i_MaximumVertexDegree); i++)
01654 {
01655 i_VertexCount = vli_GroupedVertexDegree[i].size();
01656
01657 if(i_VertexCount)
01658 {
01659 i_SelectedVertex = vli_GroupedVertexDegree[i].front();
01660
01661 vli_GroupedVertexDegree[i].pop_front();
01662
01663 vi_VertexDegree[i_SelectedVertex] = _UNKNOWN;
01664
01665 vi_IndependentSet.push_back(i_SelectedVertex);
01666
01667 i_AvailableVertexCount--;
01668
01669 break;
01670 }
01671 }
01672
01673 if( vi_AvailableVertices[i_SelectedVertex] == _FALSE)
01674 {
01675 if(i_SelectedVertex < i_LeftVertexCount)
01676 {
01677 m_vi_IncludedLeftVertices[i_SelectedVertex] = _FALSE;
01678 }
01679 else
01680 {
01681 m_vi_IncludedLeftVertices[i_SelectedVertex - i_LeftVertexCount] = _FALSE;
01682 }
01683
01684 continue;
01685 }
01686 else
01687 {
01688 vi_AvailableVertices[i_SelectedVertex] = _FALSE;
01689 }
01690
01691 if(i_SelectedVertex < i_LeftVertexCount)
01692 {
01693 i_PresentVertex = i_SelectedVertex;
01694
01695 m_vi_IncludedLeftVertices[i_PresentVertex] = _FALSE;
01696
01697 for(i=m_vi_LeftVertices[i_PresentVertex]; i<m_vi_LeftVertices[STEP_UP(i_PresentVertex)]; i++)
01698 {
01699 i_NeighboringVertex = m_vi_Edges[i];
01700
01701 if(vi_AvailableVertices[i_NeighboringVertex + i_LeftVertexCount] == _FALSE)
01702 {
01703 continue;
01704 }
01705
01706 for(j=m_vi_RightVertices[i_NeighboringVertex]; j<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; j++)
01707 {
01708 i_SecondNeighboringVertex = m_vi_Edges[j];
01709
01710 if(i_SecondNeighboringVertex == i_PresentVertex)
01711 {
01712 continue;
01713 }
01714
01715 if(vi_AvailableVertices[i_SecondNeighboringVertex] == _FALSE)
01716 {
01717 continue;
01718 }
01719
01720 vli_GroupedVertexDegree[vi_VertexDegree[i_SecondNeighboringVertex]].erase(vlit_VertexLocation[i_SecondNeighboringVertex]);
01721
01722 vi_VertexDegree[i_SecondNeighboringVertex] = STEP_DOWN(vi_VertexDegree[i_SecondNeighboringVertex]);
01723
01724 vli_GroupedVertexDegree[vi_VertexDegree[i_SecondNeighboringVertex]].push_front(i_SecondNeighboringVertex);
01725
01726 vlit_VertexLocation[i_SecondNeighboringVertex] = vli_GroupedVertexDegree[vi_VertexDegree[i_SecondNeighboringVertex]].begin();
01727
01728 if(vi_VertexDegree[i_SecondNeighboringVertex] == _FALSE)
01729 {
01730 vi_AvailableVertices[i_SecondNeighboringVertex] = _FALSE;
01731 }
01732
01733 }
01734
01735 vli_GroupedVertexDegree[vi_VertexDegree[i_NeighboringVertex + i_LeftVertexCount]].erase(vlit_VertexLocation[i_NeighboringVertex + i_LeftVertexCount]);
01736
01737 vi_VertexDegree[i_NeighboringVertex + i_LeftVertexCount] = _UNKNOWN;
01738
01739 vi_AvailableVertices[i_NeighboringVertex + i_LeftVertexCount] = _FALSE;
01740
01741 i_AvailableVertexCount--;
01742 }
01743
01744 }
01745 else
01746 {
01747 i_PresentVertex = i_SelectedVertex - i_LeftVertexCount;
01748
01749 m_vi_IncludedRightVertices[i_PresentVertex] = _FALSE;
01750
01751 for(i=m_vi_RightVertices[i_PresentVertex]; i<m_vi_RightVertices[STEP_UP(i_PresentVertex)]; i++)
01752 {
01753 i_NeighboringVertex = m_vi_Edges[i];
01754
01755 if(vi_AvailableVertices[i_NeighboringVertex] == _FALSE)
01756 {
01757 continue;
01758 }
01759
01760 for(j=m_vi_RightVertices[i_NeighboringVertex]; j<m_vi_RightVertices[STEP_UP(i_NeighboringVertex)]; j++)
01761 {
01762 i_SecondNeighboringVertex = m_vi_Edges[j];
01763
01764 if(i_SecondNeighboringVertex == i_PresentVertex)
01765 {
01766 continue;
01767 }
01768
01769 if(vi_AvailableVertices[i_SecondNeighboringVertex + i_LeftVertexCount] == _FALSE)
01770 {
01771 continue;
01772 }
01773
01774 vli_GroupedVertexDegree[vi_VertexDegree[i_SecondNeighboringVertex + i_LeftVertexCount]].erase(vlit_VertexLocation[i_SecondNeighboringVertex + i_LeftVertexCount]);
01775
01776 vi_VertexDegree[i_SecondNeighboringVertex + i_LeftVertexCount] = STEP_DOWN(vi_VertexDegree[i_SecondNeighboringVertex + i_LeftVertexCount]);
01777
01778 vli_GroupedVertexDegree[vi_VertexDegree[i_SecondNeighboringVertex + i_LeftVertexCount]].push_front(i_SecondNeighboringVertex + i_LeftVertexCount);
01779
01780 vlit_VertexLocation[i_SecondNeighboringVertex + i_LeftVertexCount] = vli_GroupedVertexDegree[vi_VertexDegree[i_SecondNeighboringVertex + i_LeftVertexCount]].begin();
01781
01782 if(vi_VertexDegree[i_SecondNeighboringVertex + i_LeftVertexCount] == _FALSE)
01783 {
01784 vi_AvailableVertices[i_SecondNeighboringVertex + i_LeftVertexCount] = _FALSE;
01785 }
01786 }
01787
01788 vli_GroupedVertexDegree[vi_VertexDegree[i_NeighboringVertex]].erase(vlit_VertexLocation[i_NeighboringVertex]);
01789
01790 vi_VertexDegree[i_NeighboringVertex] = _UNKNOWN;
01791
01792 vi_AvailableVertices[i_NeighboringVertex] = _FALSE;
01793
01794 i_AvailableVertexCount--;
01795 }
01796 }
01797 }
01798
01799 m_vi_CoveredLeftVertices.clear();
01800 m_vi_CoveredRightVertices.clear();
01801
01802
01803 for(i=0; i<i_LeftVertexCount; i++)
01804 {
01805 if(m_vi_IncludedLeftVertices[i] == _TRUE)
01806 {
01807 m_vi_CoveredLeftVertices.push_back(i);
01808 }
01809 }
01810
01811 for(i=0; i<i_RightVertexCount; i++)
01812 {
01813 if(m_vi_IncludedRightVertices[i] == _TRUE)
01814 {
01815 m_vi_CoveredRightVertices.push_back(i);
01816 }
01817 }
01818
01819 #if DEBUG == 3357
01820
01821 int k;
01822
01823 int i_CoveredEdgeCount, i_EdgeCount;
01824
01825 int i_LeftVertexCoverSize, i_RightVertexCoverSize;
01826
01827 int i_IndependentSetSize;
01828
01829 i_CoveredEdgeCount = _FALSE;
01830
01831 cout<<endl;
01832 cout<<"DEBUG 3357 | Star Bicoloring | Minimal Vertex Cover | Left Vertices"<<endl;
01833 cout<<endl;
01834
01835 i_LeftVertexCoverSize = m_vi_CoveredLeftVertices.size();
01836
01837 if(!i_LeftVertexCoverSize)
01838 {
01839 cout<<endl;
01840 cout<<"No Left Vertex Included"<<endl;
01841 cout<<endl;
01842 }
01843
01844 for(i=0; i<i_LeftVertexCoverSize; i++)
01845 {
01846 cout<<STEP_UP(m_vi_CoveredLeftVertices[i])<<"\t"<<" : ";
01847
01848 i_VertexDegree = m_vi_LeftVertices[STEP_UP(m_vi_CoveredLeftVertices[i])] - m_vi_LeftVertices[m_vi_CoveredLeftVertices[i]];
01849
01850 k = _FALSE;
01851
01852 for(j=m_vi_LeftVertices[m_vi_CoveredLeftVertices[i]]; j<m_vi_LeftVertices[STEP_UP(m_vi_CoveredLeftVertices[i])]; j++)
01853 {
01854 if(k == STEP_DOWN(i_VertexDegree))
01855 {
01856 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_CoveredLeftVertices[i]][m_vi_Edges[j]])<<" ("<<i_VertexDegree<<") ";
01857 }
01858 else
01859 {
01860 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_CoveredLeftVertices[i]][m_vi_Edges[j]])<<", ";
01861 }
01862
01863 k++;
01864 }
01865
01866 cout<<endl;
01867
01868 i_CoveredEdgeCount += k;
01869
01870 }
01871
01872 cout<<endl;
01873 cout<<"DEBUG 3357 | Star Bicoloring | Minimal Vertex Cover | Right Vertices"<<endl;
01874 cout<<endl;
01875
01876 i_RightVertexCoverSize = m_vi_CoveredRightVertices.size();
01877
01878 if(!i_RightVertexCoverSize)
01879 {
01880 cout<<endl;
01881 cout<<"No Right Vertex Included"<<endl;
01882 cout<<endl;
01883 }
01884
01885 for(i=0; i<i_RightVertexCoverSize; i++)
01886 {
01887 cout<<STEP_UP(m_vi_CoveredRightVertices[i])<<"\t"<<" : ";
01888
01889 i_VertexDegree = m_vi_RightVertices[STEP_UP(m_vi_CoveredRightVertices[i])] - m_vi_RightVertices[m_vi_CoveredRightVertices[i]];
01890
01891 k = _FALSE;
01892
01893 for(j=m_vi_RightVertices[m_vi_CoveredRightVertices[i]]; j<m_vi_RightVertices[STEP_UP(m_vi_CoveredRightVertices[i])]; j++)
01894 {
01895 if(k == STEP_DOWN(i_VertexDegree))
01896 {
01897 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_CoveredRightVertices[i]])<<" ("<<i_VertexDegree<<")";
01898 }
01899 else
01900 {
01901 cout<<STEP_UP(m_mimi2_VertexEdgeMap[m_vi_Edges[j]][m_vi_CoveredRightVertices[i]])<<", ";
01902 }
01903
01904 k++;
01905 }
01906
01907 cout<<endl;
01908
01909 i_CoveredEdgeCount += k;
01910 }
01911
01912 i_EdgeCount = ((signed) m_vi_Edges.size())/2;
01913
01914 i_IndependentSetSize = (signed) vi_IndependentSet.size();
01915
01916 cout<<endl;
01917 cout<<"[Vertex Covers Size = "<<i_LeftVertexCoverSize + i_RightVertexCoverSize<<"; Independent Set Size = "<<i_IndependentSetSize<<"; Vertex Count = "<<i_LeftVertexCount + i_RightVertexCount<<"]"<<endl;
01918 cout<<"[Left Vertex Cover Size = "<<i_LeftVertexCoverSize<<"; Right Vertex Cover Size = "<<i_RightVertexCoverSize<<"; Edges Covered = "<<i_CoveredEdgeCount<<"/"<<i_EdgeCount<<"]"<<endl;
01919 cout<<endl;
01920
01921 #endif
01922
01923 return(_TRUE);
01924 }
01925
01926
01927
01928 void BipartiteGraphVertexCover::PrintBicoloringVertexCover()
01929 {
01930 int i, j, k;
01931
01932 int i_CoveredEdgeCount;
01933
01934 int i_LeftVertexCoverSize, i_RightVertexCoverSize;
01935
01936 int i_VertexDegree;
01937
01938 i_CoveredEdgeCount = _FALSE;
01939
01940 cout<<endl;
01941 cout<<"Star Bicoloring | Left Vertex Cover | "<<m_s_InputFile<<endl;
01942 cout<<endl;
01943
01944 i_LeftVertexCoverSize = m_vi_CoveredLeftVertices.size();
01945
01946 if(!i_LeftVertexCoverSize)
01947 {
01948 cout<<endl;
01949 cout<<"No Left Vertex Included"<<endl;
01950 cout<<endl;
01951 }
01952
01953 for(i=0; i<i_LeftVertexCoverSize; i++)
01954 {
01955 cout<<STEP_UP(m_vi_CoveredLeftVertices[i])<<"\t"<<" : ";
01956
01957 i_VertexDegree = m_vi_LeftVertices[STEP_UP(m_vi_CoveredLeftVertices[i])] - m_vi_LeftVertices[m_vi_CoveredLeftVertices[i]];
01958
01959 k = _FALSE;
01960
01961 for(j=m_vi_LeftVertices[m_vi_CoveredLeftVertices[i]]; j<m_vi_LeftVertices[STEP_UP(m_vi_CoveredLeftVertices[i])]; j++)
01962 {
01963 if(k == STEP_DOWN(i_VertexDegree))
01964 {
01965 cout<<STEP_UP(m_vi_Edges[j])<<" ("<<i_VertexDegree<<") ";
01966 }
01967 else
01968 {
01969 cout<<STEP_UP(m_vi_Edges[j])<<", ";
01970 }
01971
01972 k++;
01973 }
01974
01975 cout<<endl;
01976
01977 i_CoveredEdgeCount += k;
01978
01979 }
01980
01981 cout<<endl;
01982 cout<<"Star Bicoloring | Right Vertex Cover | "<<m_s_InputFile<<endl;
01983 cout<<endl;
01984
01985 i_RightVertexCoverSize = m_vi_CoveredRightVertices.size();
01986
01987 if(!i_RightVertexCoverSize)
01988 {
01989 cout<<endl;
01990 cout<<"No Right Vertex Included"<<endl;
01991 cout<<endl;
01992 }
01993
01994 for(i=0; i<i_RightVertexCoverSize; i++)
01995 {
01996 cout<<STEP_UP(m_vi_CoveredRightVertices[i])<<"\t"<<" : ";
01997
01998 i_VertexDegree = m_vi_RightVertices[STEP_UP(m_vi_CoveredRightVertices[i])] - m_vi_RightVertices[m_vi_CoveredRightVertices[i]];
01999
02000 k = _FALSE;
02001
02002 for(j=m_vi_RightVertices[m_vi_CoveredRightVertices[i]]; j<m_vi_RightVertices[STEP_UP(m_vi_CoveredRightVertices[i])]; j++)
02003 {
02004 if(k == STEP_DOWN(i_VertexDegree))
02005 {
02006 cout<<STEP_UP(m_vi_Edges[j])<<" ("<<i_VertexDegree<<")";
02007 }
02008 else
02009 {
02010 cout<<STEP_UP(m_vi_Edges[j])<<", ";
02011 }
02012
02013 k++;
02014 }
02015
02016 cout<<endl;
02017
02018 i_CoveredEdgeCount += k;
02019 }
02020
02021 cout<<endl;
02022 cout<<"[Left Vertex Cover Size = "<<i_LeftVertexCoverSize<<"; Right Vertex Cover Size = "<<i_RightVertexCoverSize<<"; Edges Covered = "<<i_CoveredEdgeCount<<"]"<<endl;
02023 cout<<endl;
02024
02025 }
02026
02027
02028
02029 void BipartiteGraphVertexCover::GetIncludedLeftVertices(vector<int> &output)
02030 {
02031 output = (m_vi_IncludedLeftVertices);
02032 }
02033
02034
02035 void BipartiteGraphVertexCover::GetIncludedRightVertices(vector<int> &output)
02036 {
02037 output = (m_vi_IncludedRightVertices);
02038 }
02039
02040
02041
02042 void BipartiteGraphVertexCover::GetCoveredLeftVertices(vector<int> &output)
02043 {
02044 output = (m_vi_CoveredLeftVertices);
02045 }
02046
02047
02048
02049 void BipartiteGraphVertexCover::GetCoveredRightVertices(vector<int> &output)
02050 {
02051 output = (m_vi_CoveredRightVertices);
02052 }
02053
02054
02055 }