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