ColPack
BipartiteGraphPartialColoring/BipartiteGraphPartialColoring.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 2401
00028         int BipartiteGraphPartialColoring::CalculateVertexColorClasses()
00029         {
00030                 if(m_s_VertexColoringVariant.empty())
00031                 {
00032                         return(_FALSE);
00033                 }
00034 
00035                 if(m_i_LeftVertexColorCount != _UNKNOWN)
00036                 {
00037                         int i_TotalLeftVertexColors = STEP_UP(m_i_LeftVertexColorCount);
00038 
00039                         m_vi_LeftVertexColorFrequency.clear();
00040                         m_vi_LeftVertexColorFrequency.resize((unsigned) i_TotalLeftVertexColors, _FALSE);
00041 
00042                         int i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size());
00043 
00044                         for(int i = 0; i < i_LeftVertexCount; i++)
00045                         {
00046                                 m_vi_LeftVertexColorFrequency[m_vi_LeftVertexColors[i]]++;
00047                         }
00048 
00049                         for(int i = 0; i < i_TotalLeftVertexColors; i++)
00050                         {
00051                                 if(m_i_LargestLeftVertexColorClassSize < m_vi_LeftVertexColorFrequency[i])
00052                                 {
00053                                         m_i_LargestLeftVertexColorClass = i;
00054 
00055                                         m_i_LargestLeftVertexColorClassSize = m_vi_LeftVertexColorFrequency[i];
00056                                 }
00057 
00058                                 if(m_i_SmallestLeftVertexColorClassSize == _UNKNOWN)
00059                                 {
00060                                         m_i_SmallestLeftVertexColorClass = i;
00061 
00062                                         m_i_SmallestLeftVertexColorClassSize = m_vi_LeftVertexColorFrequency[i];
00063                                 }
00064                                 else
00065                                 if(m_i_SmallestLeftVertexColorClassSize > m_vi_LeftVertexColorFrequency[i])
00066                                 {
00067                                         m_i_SmallestLeftVertexColorClass = i;
00068 
00069                                         m_i_SmallestLeftVertexColorClassSize = m_vi_LeftVertexColorFrequency[i];
00070                                 }
00071                         }
00072 
00073                         m_d_AverageLeftVertexColorClassSize = i_LeftVertexCount / i_TotalLeftVertexColors;
00074                 }
00075 
00076                 if(m_i_RightVertexColorCount != _UNKNOWN)
00077                 {
00078                         int i_TotalRightVertexColors = STEP_UP(m_i_RightVertexColorCount);
00079 
00080                         m_vi_RightVertexColorFrequency.clear();
00081                         m_vi_RightVertexColorFrequency.resize((unsigned) i_TotalRightVertexColors, _FALSE);
00082 
00083                         int i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size());
00084 
00085                         for(int i = 0; i < i_RightVertexCount; i++)
00086                         {
00087                                 m_vi_RightVertexColorFrequency[m_vi_RightVertexColors[i]]++;
00088                         }
00089 
00090                         for(int i = 0; i < i_TotalRightVertexColors; i++)
00091                         {
00092                                 if(m_i_LargestRightVertexColorClassSize < m_vi_RightVertexColorFrequency[i])
00093                                 {
00094                                         m_i_LargestRightVertexColorClass = i;
00095 
00096                                         m_i_LargestRightVertexColorClassSize = m_vi_RightVertexColorFrequency[i];
00097                                 }
00098 
00099                                 if(m_i_SmallestRightVertexColorClassSize == _UNKNOWN)
00100                                 {
00101                                         m_i_SmallestRightVertexColorClass = i;
00102 
00103                                         m_i_SmallestRightVertexColorClassSize = m_vi_RightVertexColorFrequency[i];
00104                                 }
00105                                 else
00106                                 if(m_i_SmallestRightVertexColorClassSize > m_vi_RightVertexColorFrequency[i])
00107                                 {
00108                                         m_i_SmallestRightVertexColorClass = i;
00109 
00110                                         m_i_SmallestRightVertexColorClassSize = m_vi_RightVertexColorFrequency[i];
00111                                 }
00112                         }
00113 
00114                         m_d_AverageRightVertexColorClassSize = i_RightVertexCount / i_TotalRightVertexColors;
00115                 }
00116 
00117                 return(_TRUE);
00118         }
00119 
00120 
00121 
00122         //Private Function 2402
00123         int BipartiteGraphPartialColoring::CheckVertexColoring(string s_VertexColoringVariant)
00124         {
00125                 if(m_s_VertexColoringVariant.compare(s_VertexColoringVariant) == 0)
00126                 {
00127                         return(_TRUE);
00128                 }
00129 
00130                 if(m_s_VertexColoringVariant.compare("ALL") != 0)
00131                 {
00132                         m_s_VertexColoringVariant = s_VertexColoringVariant;
00133                 }
00134 
00135                 if(m_s_VertexColoringVariant.compare("ROW_PARTIAL_DISTANCE_TWO") == 0)
00136                 {
00137                         if(m_s_VertexOrderingVariant.empty())
00138                         {
00139                                 RowNaturalOrdering();
00140                         }
00141                 }
00142                 else
00143                 if(m_s_VertexColoringVariant.compare("COLUMN_PARTIAL_DISTANCE_TWO") == 0)
00144                 {
00145                         if(m_s_VertexOrderingVariant.empty())
00146                         {
00147                                 ColumnNaturalOrdering();
00148                         }
00149                 }
00150                 else
00151                 {
00152                         if(m_s_VertexOrderingVariant.empty())
00153                         {
00154                                 RowNaturalOrdering();
00155                         }
00156                 }
00157 
00158                 return(_FALSE);
00159         }
00160 
00161 
00162         //Public Constructor 2451
00163         BipartiteGraphPartialColoring::BipartiteGraphPartialColoring()
00164         {
00165                 Clear();
00166 
00167                 Seed_init();
00168         }
00169 
00170 
00171         //Public Destructor 2452
00172         BipartiteGraphPartialColoring::~BipartiteGraphPartialColoring()
00173         {
00174                 Clear();
00175 
00176                 Seed_reset();
00177         }
00178 
00179         void BipartiteGraphPartialColoring::Seed_init() {
00180                 seed_available = false;
00181 
00182                 i_seed_rowCount = 0;
00183                 dp2_Seed = NULL;
00184         }
00185 
00186         void BipartiteGraphPartialColoring::Seed_reset() {
00187                 if(seed_available) {
00188                         seed_available = false;
00189 
00190                         free_2DMatrix(dp2_Seed, i_seed_rowCount);
00191                         dp2_Seed = NULL;
00192                         i_seed_rowCount = 0;
00193                 }
00194         }
00195 
00196 
00197         //Virtual Function 2453
00198         void BipartiteGraphPartialColoring::Clear()
00199         {
00200                 BipartiteGraphPartialOrdering::Clear();
00201 
00202                 m_i_LeftVertexColorCount = _UNKNOWN;
00203                 m_i_RightVertexColorCount = _UNKNOWN;
00204 
00205                 m_i_VertexColorCount = _UNKNOWN;
00206 
00207                 m_i_ViolationCount =_UNKNOWN;
00208 
00209                 m_i_ColoringUnits = _UNKNOWN;
00210 
00211                 m_i_LargestLeftVertexColorClass = _UNKNOWN;
00212                 m_i_LargestRightVertexColorClass = _UNKNOWN;
00213 
00214                 m_i_LargestLeftVertexColorClassSize = _UNKNOWN;
00215                 m_i_LargestRightVertexColorClassSize = _UNKNOWN;
00216 
00217                 m_i_SmallestLeftVertexColorClass = _UNKNOWN;
00218                 m_i_SmallestRightVertexColorClass = _UNKNOWN;
00219 
00220                 m_i_SmallestLeftVertexColorClassSize = _UNKNOWN;
00221                 m_i_SmallestRightVertexColorClassSize = _UNKNOWN;
00222 
00223                 m_d_AverageLeftVertexColorClassSize = _UNKNOWN;
00224                 m_d_AverageRightVertexColorClassSize = _UNKNOWN;
00225 
00226                 m_d_ColoringTime = _UNKNOWN;
00227                 m_d_CheckingTime = _UNKNOWN;
00228 
00229                 m_s_VertexColoringVariant.clear();
00230 
00231                 m_vi_LeftVertexColors.clear();
00232                 m_vi_RightVertexColors.clear();
00233 
00234                 m_vi_LeftVertexColorFrequency.clear();
00235                 m_vi_RightVertexColorFrequency.clear();
00236 
00237                 return;
00238         }
00239 
00240 
00241         //Virtual Function 2454
00242         void BipartiteGraphPartialColoring::Reset()
00243         {
00244                 BipartiteGraphPartialOrdering::Reset();
00245 
00246                 m_i_LeftVertexColorCount = _UNKNOWN;
00247                 m_i_RightVertexColorCount = _UNKNOWN;
00248 
00249                 m_i_VertexColorCount = _UNKNOWN;
00250 
00251                 m_i_ViolationCount = _UNKNOWN;
00252 
00253                 m_i_ColoringUnits = _UNKNOWN;
00254 
00255                 m_i_LargestLeftVertexColorClass = _UNKNOWN;
00256                 m_i_LargestRightVertexColorClass = _UNKNOWN;
00257 
00258                 m_i_LargestLeftVertexColorClassSize = _UNKNOWN;
00259                 m_i_LargestRightVertexColorClassSize = _UNKNOWN;
00260 
00261                 m_i_SmallestLeftVertexColorClass = _UNKNOWN;
00262                 m_i_SmallestRightVertexColorClass = _UNKNOWN;
00263 
00264                 m_i_SmallestLeftVertexColorClassSize = _UNKNOWN;
00265                 m_i_SmallestRightVertexColorClassSize = _UNKNOWN;
00266 
00267                 m_d_AverageLeftVertexColorClassSize = _UNKNOWN;
00268                 m_d_AverageRightVertexColorClassSize = _UNKNOWN;
00269 
00270                 m_d_ColoringTime = _UNKNOWN;
00271                 m_d_CheckingTime = _UNKNOWN;
00272 
00273                 m_s_VertexColoringVariant.clear();
00274 
00275                 m_vi_LeftVertexColors.clear();
00276                 m_vi_RightVertexColors.clear();
00277 
00278                 m_vi_LeftVertexColorFrequency.clear();
00279                 m_vi_RightVertexColorFrequency.clear();
00280 
00281                 return;
00282         }
00283         
00284         int f(int x) {return x;}
00285 
00286         int BipartiteGraphPartialColoring::PartialDistanceTwoRowColoring_OMP()
00287         {
00288                 if(CheckVertexColoring("ROW_PARTIAL_DISTANCE_TWO"))
00289                 {
00290                         return(_TRUE);
00291                 }
00292 
00293                 int i_LeftVertexCount, i_RightVertexCount, i_CurrentVertex;
00294                 bool cont=false;
00295                 vector<int> vi_forbiddenColors, vi_VerticesToBeColored, vi_verticesNeedNewColor;
00296                 i_LeftVertexCount = (int) m_vi_LeftVertices.size() - 1;
00297                 i_RightVertexCount = (int)m_vi_RightVertices.size () - 1;
00298                 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = m_i_VertexColorCount = 0;
00299 
00300                 // !!! do sections for this part ? forbiddenColors may need to be private for each thread
00301                 // resize the colors
00302                 m_vi_LeftVertexColors.resize ( i_LeftVertexCount, _UNKNOWN );
00303                 // resize the forbidden colors. !!! should be resize to max D2 degree instead
00304                 vi_forbiddenColors.resize ( i_LeftVertexCount, _UNKNOWN );
00305                 //Algo 4 - Line 2: U <- V . U is vi_VerticesToBeColored
00306                 vi_VerticesToBeColored.reserve(i_LeftVertexCount);
00307                 for(int i=0; i<i_LeftVertexCount; i++) {
00308                         vi_VerticesToBeColored.push_back(m_vi_OrderedVertices[i]);
00309                         //vi_VerticesToBeColored.push_back(i);
00310                 }
00311                 // !!! pick reasonable amount to reserve 
00312                 vi_verticesNeedNewColor.reserve(i_LeftVertexCount);
00313 
00314                 int i_NumOfVerticesToBeColored = vi_VerticesToBeColored.size();
00315                 
00316 //              cout<<"m_vi_Edges.size() = "<<m_vi_Edges.size()<<endl;
00317 //              cout<<"m_vi_LeftVertexColors.size() = "<<m_vi_LeftVertexColors.size()<<endl;
00318 
00319                 //Algo 4 - Line 3: while U != 0 ; do
00320                 while(i_NumOfVerticesToBeColored!=0) {
00321 //                cout<<"i_NumOfVerticesToBeColored = "<<i_NumOfVerticesToBeColored<<endl;
00322                         //Phase 1: tentative coloring
00323                         //Algo 4 - Line 4: for each right vertex v in U (in parallel) do
00324 #pragma omp parallel for default(none) schedule(dynamic) shared(cout, i_NumOfVerticesToBeColored, vi_VerticesToBeColored) firstprivate(vi_forbiddenColors)
00325                         for(int i=0; i<i_NumOfVerticesToBeColored; i++) {
00326                                 int v = vi_VerticesToBeColored[i];
00327 //                              CoutLock::set(); cout<<"t"<< omp_get_thread_num() <<": i="<<i<<", left vertex v="<<v<<endl;CoutLock::unset(); 
00328                                 //Algo 4 - Line 5: for each left vertex w in adj (v) do
00329                                 for (int w=m_vi_LeftVertices [v]; w<m_vi_LeftVertices [v+1]; w++ ) {
00330 //                                      CoutLock::set(); 
00331 //                                      cout<<"\t t"<< omp_get_thread_num() <<": w="<<w<<", right vertex m_vi_Edges [w]="<<m_vi_Edges [w]<<endl;
00332 //                                      CoutLock::unset(); 
00333                                         //Algo 4 - Line 6: mark color [w] as forbidden to vertex v. NOTE: !!! Not needed
00334                                         //Algo 4 - Line 7: for each right vertex x in adj (w) and x != v do
00335                                         for (int x=m_vi_RightVertices [m_vi_Edges [w]]; x<m_vi_RightVertices [m_vi_Edges [w]+1]; x++ ) {
00336                                                 //Algo 4 - Line 8: mark color [x] as forbidden to vertex v
00337                                                 if ( m_vi_LeftVertexColors [m_vi_Edges [x]] != _UNKNOWN ) {
00338 //                                                      CoutLock::set(); 
00339 //                                                      cout<<"\t\t t"<< omp_get_thread_num() <<": x="<<x<<endl;
00340 //                                                      if(x>=m_vi_Edges.size()) {
00341 //                                                        cout<<"ERR: x>=m_vi_Edges.size()"<<endl;
00342 //                                                        PrintBipartiteGraph();
00343 //                                                        Pause();
00344 //                                                      }
00345 //                                                      cout<<"\t\t left vertex m_vi_Edges [x] = "<<m_vi_Edges [x]<<endl;
00346 //                                                      cout<<"\t\t m_vi_LeftVertexColors [m_vi_Edges [x]] = "<<m_vi_LeftVertexColors [m_vi_Edges [x]]<<endl;
00347 //                                                      cout<<"\t\t v="<<v<<endl;
00348 //                                                      CoutLock::unset(); 
00349                                                         // !!! each thread should has their own vi_forbiddenColors[] vector just to make sure the don't override each other
00350                                                         vi_forbiddenColors [m_vi_LeftVertexColors [m_vi_Edges [x]]] = v;
00351                                                 }
00352                                         }
00353                                 }
00354                                 //Algo 4 - Line 9: Pick a permissible color c for vertex v using some strategy
00355                                 int i_cadidateColor;
00356                                 // First fit
00357                                 {
00358                                         i_cadidateColor = 0;
00359                                         while(vi_forbiddenColors[i_cadidateColor]==v) i_cadidateColor++;
00360                                 }
00361                                 m_vi_LeftVertexColors[v] = i_cadidateColor;
00362                                 if(m_i_LeftVertexColorCount < i_cadidateColor)  {
00363                                                 m_i_LeftVertexColorCount = i_cadidateColor;
00364                                 }
00365                         }
00366                         
00367                         //Algo 4 - Line 10: R.clear()   ; R denotes the set of vertices to be recolored
00368                         vi_verticesNeedNewColor.clear();
00369                                         
00370                         //Phase 2: conflict detection. For each vertex v in U, check and see if v need to be recolored
00371                         //Algo 4 - Line 11: for each vertex v in U (in parallel) do
00372 #pragma omp parallel for default(none) schedule(dynamic) shared(i_NumOfVerticesToBeColored, vi_VerticesToBeColored,vi_verticesNeedNewColor, cout) private(cont)
00373                         for(int i=0; i<i_NumOfVerticesToBeColored; i++) {
00374                                 //Algo 4 - Line 12: cont  <- true ; cont is used to break from the outer loop below
00375                                 cont = true;
00376                                 int v = vi_VerticesToBeColored[i];
00377                                 //Algo 4 - Line 13: for each vertex w in adj (v) and cont = true do
00378                                 for (int w=m_vi_LeftVertices [v]; (w<m_vi_LeftVertices [v+1]) && (cont == true); w++ ) {
00379                                         //Algo 4 - Line 14: if color [v] = color [w] and f (v) > f (w) then . NOTE: !!! Not needed
00380                                                 //Algo 4 - Line 15: add [v] to R ; break . NOTE: !!! Not needed
00381                                         //Algo 4 - Line 16: for each vertex x in adj (w) and v != x do
00382                                         for (int x=m_vi_RightVertices [m_vi_Edges [w]]; x<m_vi_RightVertices [m_vi_Edges [w]+1]; x++ ) {
00383                                           //cout<<" m_vi_LeftVertexColors [m_vi_Edges [x]="<<x<<"]"<< m_vi_LeftVertexColors [m_vi_Edges [x]] <<endl;
00384                                           // cout<<" m_vi_LeftVertexColors [v="<<v<<"]"<< m_vi_LeftVertexColors [v] <<endl;
00385                                           //cout<<"f(v="<<v<<")="<<f(v)<<endl;
00386                                           //cout<<"f(m_vi_Edges [x]="<<x<<")="<<f(m_vi_Edges [x])<<endl;
00387                                                 //Algo 4 - Line 17: if color [v] = color [x] and f (v) > f (x) then
00388                                           if ( m_vi_LeftVertexColors [m_vi_Edges [x]] == m_vi_LeftVertexColors[v] && f(v) > f(m_vi_Edges [x]) ) {
00389                                                         //Algo 4 - Line 18: add [v] to R ; cont <- false; break
00390 #pragma omp critical
00391                                                         vi_verticesNeedNewColor.push_back(v);
00392 #pragma omp end critical
00393                                                         cont = false;
00394                                                         break;
00395                                                 }
00396                                         }
00397                                 }
00398                         }
00399                         
00400                         //Algo 4 - Line 19: U <- R , i.e., vi_VerticesToBeColored <- vi_verticesNeedNewColor
00401                         vi_VerticesToBeColored.clear();
00402                         i_NumOfVerticesToBeColored = vi_verticesNeedNewColor.size(); 
00403 
00404                         vi_VerticesToBeColored.reserve(vi_verticesNeedNewColor.size());
00405                         for(int i=0; i<vi_verticesNeedNewColor.size(); i++) {
00406                           vi_VerticesToBeColored.push_back(vi_verticesNeedNewColor[i]);
00407                         }
00408 
00409                         /*
00410                         vi_VerticesToBeColored.resize(vi_verticesNeedNewColor.size());
00411 #pragma omp parallel for default(none) schedule(static) shared(i_NumOfVerticesToBeColored,vi_VerticesToBeColored,vi_verticesNeedNewColor) 
00412                         for(int i=0; i<i_NumOfVerticesToBeColored; i++) {
00413                                 vi_VerticesToBeColored[i]=vi_verticesNeedNewColor[i];
00414                         }
00415                         //*/
00416 
00417                 }
00418                 
00419                 // Note that m_i_LeftVertexColorCount has not been updated yet
00420                 m_i_VertexColorCount = m_i_LeftVertexColorCount;
00421                 
00422                 return _TRUE;
00423           
00424         }
00425 
00426         int BipartiteGraphPartialColoring::PartialDistanceTwoRowColoring() {
00427 #ifdef _OPENMP
00428                 return BipartiteGraphPartialColoring::PartialDistanceTwoRowColoring_OMP();
00429 #else
00430                 return BipartiteGraphPartialColoring::PartialDistanceTwoRowColoring_serial();
00431 #endif
00432         }
00433         
00434         //Public Function 2455
00435         int BipartiteGraphPartialColoring::PartialDistanceTwoRowColoring_serial()
00436         {
00437                 if(CheckVertexColoring("ROW_PARTIAL_DISTANCE_TWO"))
00438                 {
00439                         return(_TRUE);
00440                 }
00441 
00442                 int i, w, x, c;
00443                 int i_LeftVertexCount, i_CurrentVertex;
00444                 vector<int> vi_forbiddenColors;
00445 
00446                 i_LeftVertexCount = (int)m_vi_LeftVertices.size () - 1;
00447                 // resize the colors
00448                 m_vi_LeftVertexColors.resize ( i_LeftVertexCount, _UNKNOWN );
00449                 // resize the forbidden colors
00450                 vi_forbiddenColors.resize ( i_LeftVertexCount, _UNKNOWN );
00451 
00452                 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = m_i_VertexColorCount = 0;
00453 
00454                 for ( i=0; i<i_LeftVertexCount; ++i )
00455                 {
00456                         i_CurrentVertex = m_vi_OrderedVertices[i];
00457 
00458                         for ( w=m_vi_LeftVertices [i_CurrentVertex]; w<m_vi_LeftVertices [i_CurrentVertex+1]; ++w )
00459                         {
00460                                 for ( x=m_vi_RightVertices [m_vi_Edges [w]]; x<m_vi_RightVertices [m_vi_Edges [w]+1]; ++x )
00461                                 {
00462                                         if ( m_vi_LeftVertexColors [m_vi_Edges [x]] != _UNKNOWN )
00463                                         {
00464                                                 vi_forbiddenColors [m_vi_LeftVertexColors [m_vi_Edges [x]]] = i_CurrentVertex;
00465                                         }
00466                                 }
00467                         }
00468 
00469                         // do color[vi] <-min {c>0:forbiddenColors[c]=/=vi
00470                         for ( c=0; c<i_LeftVertexCount; ++c )
00471                         {
00472                                 if ( vi_forbiddenColors [c] != i_CurrentVertex )
00473                                 {
00474                                         m_vi_LeftVertexColors [i_CurrentVertex] = c;
00475 
00476                                         if(m_i_LeftVertexColorCount < c)
00477                                         {
00478                                                 m_i_LeftVertexColorCount = c;
00479                                         }
00480 
00481                                         break;
00482                                 }
00483                         }
00484                         //
00485                 }
00486 
00487                 m_i_VertexColorCount = m_i_LeftVertexColorCount;
00488 
00489                 return ( _TRUE );
00490         }
00491 
00492         int BipartiteGraphPartialColoring::PartialDistanceTwoColumnColoring_OMP() {
00493                 if(CheckVertexColoring("COLUMN_PARTIAL_DISTANCE_TWO"))
00494                 {
00495                   return(_TRUE);
00496                 }
00497 
00498                 int i_LeftVertexCount, i_RightVertexCount, i_CurrentVertex;
00499                 bool cont=false;
00500                 vector<int> vi_forbiddenColors, vi_VerticesToBeColored, vi_verticesNeedNewColor;
00501                 i_LeftVertexCount = (int) m_vi_LeftVertices.size() - 1;
00502                 i_RightVertexCount = (int)m_vi_RightVertices.size () - 1;
00503                 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = m_i_VertexColorCount = 0;
00504 
00505                 // !!! do sections for this part ? forbiddenColors may need to be private for each thread
00506                 // resize the colors
00507                 m_vi_RightVertexColors.resize ( i_RightVertexCount, _UNKNOWN );
00508                 // resize the forbidden colors. !!! should be resize to max D2 degree instead
00509                 vi_forbiddenColors.resize ( i_RightVertexCount, _UNKNOWN );
00510                 //Algo 4 - Line 2: U <- V . U is vi_VerticesToBeColored
00511                 vi_VerticesToBeColored.reserve(i_RightVertexCount);
00512                 for(int i=0; i<i_RightVertexCount; i++) {
00513                         vi_VerticesToBeColored.push_back(m_vi_OrderedVertices[i] - i_LeftVertexCount);
00514                         //vi_VerticesToBeColored.push_back(i);
00515                 }
00516                 // !!! pick reasonable amount to reserve 
00517                 vi_verticesNeedNewColor.reserve(i_RightVertexCount);
00518 
00519                 int i_NumOfVerticesToBeColored = vi_VerticesToBeColored.size();
00520 
00521                 //Algo 4 - Line 3: while U != 0 ; do
00522                 while(i_NumOfVerticesToBeColored!=0) {
00523                   //cout<<"i_NumOfVerticesToBeColored = "<<i_NumOfVerticesToBeColored<<endl;
00524                         //Phase 1: tentative coloring
00525                         //Algo 4 - Line 4: for each right vertex v in U (in parallel) do
00526 #pragma omp parallel for default(none) schedule(dynamic) shared(i_NumOfVerticesToBeColored, vi_VerticesToBeColored) firstprivate(vi_forbiddenColors)
00527                         for(int i=0; i<i_NumOfVerticesToBeColored; i++) {
00528                                 int v = vi_VerticesToBeColored[i];
00529                                 //Algo 4 - Line 5: for each left vertex w in adj (v) do
00530                                 for (int w=m_vi_RightVertices [v]; w<m_vi_RightVertices [v+1]; w++ ) {
00531                                         //Algo 4 - Line 6: mark color [w] as forbidden to vertex v. NOTE: !!! Not needed
00532                                         //Algo 4 - Line 7: for each right vertex x in adj (w) and x != v do
00533                                         for (int x=m_vi_LeftVertices [m_vi_Edges [w]]; x<m_vi_LeftVertices [m_vi_Edges [w]+1]; x++ ) {
00534                                                 //Algo 4 - Line 8: mark color [x] as forbidden to vertex v
00535                                                 if ( m_vi_RightVertexColors [m_vi_Edges [x]] != _UNKNOWN ) {
00536                                                         // !!! each thread should has their own vi_forbiddenColors[] vector just to make sure the don't override each other
00537                                                         vi_forbiddenColors [m_vi_RightVertexColors [m_vi_Edges [x]]] = v;
00538                                                 }
00539                                         }
00540                                 }
00541                                 //Algo 4 - Line 9: Pick a permissible color c for vertex v using some strategy
00542                                 int i_cadidateColor;
00543                                 // First fit
00544                                 {
00545                                         i_cadidateColor = 0;
00546                                         while(vi_forbiddenColors[i_cadidateColor]==v) i_cadidateColor++;
00547                                 }
00548                                 m_vi_RightVertexColors[v] = i_cadidateColor;
00549                                 if(m_i_RightVertexColorCount < i_cadidateColor) {
00550                                                 m_i_RightVertexColorCount = i_cadidateColor;
00551                                 }
00552                         }
00553                         
00554                         //Algo 4 - Line 10: R.clear()   ; R denotes the set of vertices to be recolored
00555                         vi_verticesNeedNewColor.clear();
00556                                         
00557                         //Phase 2: conflict detection. For each vertex v in U, check and see if v need to be recolored
00558                         //Algo 4 - Line 11: for each vertex v in U (in parallel) do
00559 #pragma omp parallel for default(none) schedule(dynamic) shared(i_NumOfVerticesToBeColored, vi_VerticesToBeColored,vi_verticesNeedNewColor, cout) private(cont)
00560                         for(int i=0; i<i_NumOfVerticesToBeColored; i++) {
00561                                 //Algo 4 - Line 12: cont  <- true ; cont is used to break from the outer loop below
00562                                 cont = true;
00563                                 int v = vi_VerticesToBeColored[i];
00564                                 //Algo 4 - Line 13: for each vertex w in adj (v) and cont = true do
00565                                 for (int w=m_vi_RightVertices [v]; (w<m_vi_RightVertices [v+1]) && (cont == true); w++ ) {
00566                                         //Algo 4 - Line 14: if color [v] = color [w] and f (v) > f (w) then . NOTE: !!! Not needed
00567                                                 //Algo 4 - Line 15: add [v] to R ; break . NOTE: !!! Not needed
00568                                         //Algo 4 - Line 16: for each vertex x in adj (w) and v != x do
00569                                         for (int x=m_vi_LeftVertices [m_vi_Edges [w]]; x<m_vi_LeftVertices [m_vi_Edges [w]+1]; x++ ) {
00570                                           //cout<<" m_vi_RightVertexColors [m_vi_Edges [x]="<<x<<"]"<< m_vi_RightVertexColors [m_vi_Edges [x]] <<endl;
00571                                           // cout<<" m_vi_RightVertexColors [v="<<v<<"]"<< m_vi_RightVertexColors [v] <<endl;
00572                                           //cout<<"f(v="<<v<<")="<<f(v)<<endl;
00573                                           //cout<<"f(m_vi_Edges [x]="<<x<<")="<<f(m_vi_Edges [x])<<endl;
00574                                                 //Algo 4 - Line 17: if color [v] = color [x] and f (v) > f (x) then
00575                                           if ( m_vi_RightVertexColors [m_vi_Edges [x]] == m_vi_RightVertexColors[v] && f(v) > f(m_vi_Edges [x]) ) {
00576                                                         //Algo 4 - Line 18: add [v] to R ; cont <- false; break
00577 #pragma omp critical
00578                                                         vi_verticesNeedNewColor.push_back(v);
00579 #pragma omp end critical
00580                                                         cont = false;
00581                                                         break;
00582                                                 }
00583                                         }
00584                                 }
00585                         }
00586                         
00587                         //Algo 4 - Line 19: U <- R , i.e., vi_VerticesToBeColored <- vi_verticesNeedNewColor
00588                         vi_VerticesToBeColored.clear();
00589                         i_NumOfVerticesToBeColored = vi_verticesNeedNewColor.size(); 
00590 
00591                         vi_VerticesToBeColored.reserve(vi_verticesNeedNewColor.size());
00592                         for(int i=0; i<vi_verticesNeedNewColor.size(); i++) {
00593                           vi_VerticesToBeColored.push_back(vi_verticesNeedNewColor[i]);
00594                         }
00595 
00596                         /*
00597                         vi_VerticesToBeColored.resize(vi_verticesNeedNewColor.size());
00598 #pragma omp parallel for default(none) schedule(static) shared(i_NumOfVerticesToBeColored,vi_VerticesToBeColored,vi_verticesNeedNewColor) 
00599                         for(int i=0; i<i_NumOfVerticesToBeColored; i++) {
00600                                 vi_VerticesToBeColored[i]=vi_verticesNeedNewColor[i];
00601                         }
00602                         //*/
00603 
00604                 }
00605                 
00606                 //note that m_i_RightVertexColorCount has not been updated yet
00607                 m_i_VertexColorCount = m_i_RightVertexColorCount;
00608                 
00609                 return _TRUE;
00610 
00611         }
00612 
00613         int BipartiteGraphPartialColoring::PartialDistanceTwoColumnColoring() {
00614 #ifdef _OPENMP
00615                 return BipartiteGraphPartialColoring::PartialDistanceTwoColumnColoring_OMP();
00616 #else
00617                 return BipartiteGraphPartialColoring::PartialDistanceTwoColumnColoring_serial();
00618 #endif
00619         }
00620 
00621         //Public Function 2456
00622         int BipartiteGraphPartialColoring::PartialDistanceTwoColumnColoring_serial()
00623         {
00624                 if(CheckVertexColoring("COLUMN_PARTIAL_DISTANCE_TWO"))
00625                 {
00626                         return(_TRUE);
00627                 }
00628 
00629                 int i, w, x, c;
00630                 int i_LeftVertexCount, i_RightVertexCount, i_CurrentVertex;
00631                 vector<int> vi_forbiddenColors;
00632 
00633                 i_LeftVertexCount = (int) m_vi_LeftVertices.size() - 1;
00634                 i_RightVertexCount = (int)m_vi_RightVertices.size () - 1;
00635 
00636                 // resize the colors
00637                 m_vi_RightVertexColors.resize ( i_RightVertexCount, _UNKNOWN );
00638 
00639                 // resize the forbidden colors
00640                 vi_forbiddenColors.resize ( i_RightVertexCount, _UNKNOWN );
00641 
00642                 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = m_i_VertexColorCount = 0;
00643 
00644                 //cout<<" i_RightVertexCount = " <<i_RightVertexCount<<endl;
00645                 for ( i=0; i<i_RightVertexCount; ++i )
00646                 {
00647                         i_CurrentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount;
00648 
00649                         for ( w=m_vi_RightVertices [i_CurrentVertex]; w<m_vi_RightVertices [i_CurrentVertex+1]; ++w )
00650                         {
00651                                 for ( x=m_vi_LeftVertices [m_vi_Edges [w]]; x<m_vi_LeftVertices [m_vi_Edges [w]+1]; ++x )
00652                                 {
00653                                         if ( m_vi_RightVertexColors [m_vi_Edges [x]] != _UNKNOWN )
00654                                         {
00655                                                 vi_forbiddenColors [m_vi_RightVertexColors [m_vi_Edges [x]]] = i_CurrentVertex;
00656                                         }
00657                                 }
00658                         }
00659 
00660                         // do color[vi] <-min {c>0:forbiddenColors[c]=/=vi
00661                         for ( c=0; c<i_RightVertexCount; ++c )
00662                         {
00663                                 if ( vi_forbiddenColors [c] != i_CurrentVertex )
00664                                 {
00665                                         m_vi_RightVertexColors [i_CurrentVertex] = c;
00666 
00667                                         if(m_i_RightVertexColorCount < c)
00668                                         {
00669                                                 m_i_RightVertexColorCount = c;
00670                                         }
00671 
00672                                         break;
00673                                 }
00674                         }
00675                         //
00676                 }
00677 
00678                 m_i_VertexColorCount = m_i_RightVertexColorCount;
00679 
00680                 return ( _TRUE );
00681         }
00682 
00683 
00684 
00685         //Public Function 2457
00686         int BipartiteGraphPartialColoring::CheckPartialDistanceTwoRowColoring()
00687         {
00688                 for(int i=0;i<(signed) m_vi_LeftVertices.size()-1;i++)
00689                 //for each of left vertices, find its D1 neighbour (right vertices)
00690                 {
00691                         for(int j=m_vi_LeftVertices[i];j<m_vi_LeftVertices[i+1];j++)
00692                         {
00693                                 for(int k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[m_vi_Edges[j]+1];k++)
00694                                 //for each of the right vertices, find its D1 neighbour (left vertices exclude the original left)
00695                                 {
00696                                         if(m_vi_Edges[k]==i) continue;
00697                                         if(m_vi_LeftVertexColors[m_vi_Edges[k]]==m_vi_LeftVertexColors[i])
00698                                         {
00699                                                 cout<<"Left vertices "<<i+1<<" and "<<m_vi_Edges[k]+1<< " (connected by right vectex "<<m_vi_Edges[j]+1<<") have the same color ("<<m_vi_LeftVertexColors[i]<<")"<<endl;
00700 
00701                                                 return _FALSE;
00702                                         }
00703                                 }
00704                         }
00705                 }
00706 
00707                 return _TRUE;
00708         }
00709 
00710 
00711         //Public Function 2458
00712         int BipartiteGraphPartialColoring::CheckPartialDistanceTwoColumnColoring()
00713         {
00714                 for(int i=0;i<(signed) m_vi_RightVertices.size()-1;i++)
00715                 //for each of right vertices, find its D1 neighbour (left vertices)
00716                 {
00717                         for(int j=m_vi_RightVertices[i];j<m_vi_RightVertices[i+1];j++)
00718                         {
00719                                 for(int k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[m_vi_Edges[j]+1];k++)
00720                                 //for each of the left vertices, find its D1 neighbour (right vertices exclude the original right)
00721                                 {
00722                                         if(m_vi_Edges[k]==i) continue;
00723                                         if(m_vi_RightVertexColors[m_vi_Edges[k]]==m_vi_RightVertexColors[i])
00724                                         {
00725                                                 cout<<"Right vertices "<<i+1<<" and "<<m_vi_Edges[k]+1<< " (connected by left vectex "<<m_vi_Edges[j]+1<<") have the same color ("<<m_vi_RightVertexColors[i]<<")"<<endl;
00726                                                 return _FALSE;
00727                                         }
00728                                 }
00729                         }
00730                 }
00731 
00732                 return (_TRUE);
00733         }
00734 
00735         //Public Function 2459
00736         int BipartiteGraphPartialColoring::GetLeftVertexColorCount()
00737         {
00738           if(m_i_LeftVertexColorCount<0 && GetVertexColoringVariant() == "Row Partial Distance Two" ) {
00739             for(int i=0; i<m_vi_LeftVertexColors.size();i++) {
00740               if(m_i_LeftVertexColorCount<m_vi_LeftVertexColors[i]) m_i_LeftVertexColorCount = m_vi_LeftVertexColors[i];
00741             }
00742           }
00743                 return(STEP_UP(m_i_LeftVertexColorCount));
00744         }
00745 
00746         //Public Function 2460
00747         int BipartiteGraphPartialColoring::GetRightVertexColorCount()
00748         {
00749           if(m_i_RightVertexColorCount<0 && GetVertexColoringVariant() == "Column Partial Distance Two" ) {
00750             for(int i=0; i<m_vi_RightVertexColors.size();i++) {
00751               if(m_i_RightVertexColorCount<m_vi_RightVertexColors[i]) m_i_RightVertexColorCount = m_vi_RightVertexColors[i];
00752             }
00753           }
00754                 return(STEP_UP(m_i_RightVertexColorCount));
00755         }
00756 
00757 
00758         //Public Function 2461
00759         int BipartiteGraphPartialColoring::GetVertexColorCount()
00760         {
00761           if(m_i_VertexColorCount<0 && GetVertexColoringVariant() != "Unknown" ) {
00762             if(GetVertexColoringVariant() == "Row Partial Distance Two") {
00763               m_i_VertexColorCount = GetLeftVertexColorCount() - 1;
00764             }
00765             else { // GetVertexColoringVariant() == "Column Partial Distance Two"
00766               m_i_VertexColorCount = GetRightVertexColorCount() - 1;
00767             }
00768           }
00769                 return(STEP_UP(m_i_VertexColorCount));
00770         }
00771 
00772 
00773         //Public Function 2462
00774         string BipartiteGraphPartialColoring::GetVertexColoringVariant()
00775         {
00776                 if(m_s_VertexColoringVariant.compare("ROW_PARTIAL_DISTANCE_TWO") == 0)
00777                 {
00778                         return("Row Partial Distance Two");
00779                 }
00780                 else
00781                 if(m_s_VertexColoringVariant.compare("COLUMN_PARTIAL_DISTANCE_TWO") == 0)
00782                 {
00783                         return("Column Partial Distance Two");
00784                 }
00785                 else
00786                 {
00787                         return("Unknown");
00788                 }
00789         }
00790 
00791         //Public Function 2463
00792         void BipartiteGraphPartialColoring::GetLeftVertexColors(vector<int> &output)
00793         {
00794                 output = (m_vi_LeftVertexColors);
00795         }
00796 
00797         //Public Function 2464
00798         void BipartiteGraphPartialColoring::GetRightVertexColors(vector<int> &output)
00799         {
00800                 output = (m_vi_RightVertexColors);
00801         }
00802 
00803 
00804 
00805         //Public Function 2465
00806         void BipartiteGraphPartialColoring::PrintRowPartialColors()
00807         {
00808                 int i;
00809 
00810                 int i_LeftVertexCount;
00811 
00812                 string _SLASH("/");
00813 
00814                 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
00815 
00816                 m_s_InputFile = SlashTokenizer.GetLastToken();
00817 
00818                 i_LeftVertexCount = (signed) m_vi_LeftVertexColors.size();
00819 
00820                 cout<<endl;
00821                 cout<<"Bipartite Graph | Row Partial Coloring | Row Vertices | Vertex Colors "<<m_s_InputFile<<endl;
00822                 cout<<endl;
00823 
00824                 for(i=0; i<i_LeftVertexCount; i++)
00825                 {
00826                         cout<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(m_vi_LeftVertexColors[i])<<endl;
00827                 }
00828 
00829                 cout<<endl;
00830                 cout<<"[Total Row Colors = "<<GetLeftVertexColorCount()<<"]"<<endl;
00831                 cout<<endl;
00832 
00833                 return;
00834         }
00835 
00836         //Public Function 2466
00837         void BipartiteGraphPartialColoring::PrintColumnPartialColors()
00838         {
00839                 int i;
00840 
00841                 int i_RightVertexCount;
00842 
00843                 string _SLASH("/");
00844 
00845                 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
00846 
00847                 m_s_InputFile = SlashTokenizer.GetLastToken();
00848 
00849                 i_RightVertexCount = (signed) m_vi_RightVertexColors.size();
00850 
00851                 cout<<endl;
00852                 cout<<"Bipartite Graph | Column Partial Coloring | Column Vertices | Vertex Colors | "<<m_s_InputFile<<endl;
00853                 cout<<endl;
00854 
00855                 for(i=0; i<i_RightVertexCount; i++)
00856                 {
00857                         cout<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(m_vi_RightVertexColors[i])<<endl;
00858                 }
00859 
00860                 cout<<endl;
00861                 cout<<"[Total Column Colors = "<<GetRightVertexColorCount()<<"]"<<endl;
00862                 cout<<endl;
00863 
00864                 return;
00865         }
00866 
00867 
00868 
00869         //Public Function 2467
00870         void BipartiteGraphPartialColoring::PrintRowPartialColoringMetrics()
00871         {
00872                 string _SLASH("/");
00873 
00874                 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
00875 
00876                 string s_InputFile = SlashTokenizer.GetLastToken();
00877 
00878                 cout<<endl;
00879                 cout<<GetVertexColoringVariant()<<" Bicoloring | "<<GetVertexOrderingVariant()<<" Ordering | "<<s_InputFile<<endl;
00880                 cout<<endl;
00881 
00882                 cout<<endl;
00883                 cout<<"[Total Row Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Violation Count = "<<m_i_ViolationCount<<"]"<<endl;
00884                 cout<<"[Row Vertex Count = "<<STEP_DOWN(m_vi_LeftVertices.size())<<"; Column Vertex Count = "<<STEP_DOWN(m_vi_RightVertices.size())<<endl;
00885                 cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"; Checking Time = "<<m_d_CheckingTime<<"]"<<endl;
00886                 cout<<endl;
00887         }
00888 
00889 
00890         //Public Function 2468
00891         void BipartiteGraphPartialColoring::PrintColumnPartialColoringMetrics()
00892         {
00893                 string _SLASH("/");
00894 
00895                 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
00896 
00897                 string s_InputFile = SlashTokenizer.GetLastToken();
00898 
00899                 cout<<endl;
00900                 cout<<GetVertexColoringVariant()<<" Bicoloring | "<<GetVertexOrderingVariant()<<" Ordering | "<<s_InputFile<<endl;
00901                 cout<<endl;
00902 
00903                 cout<<endl;
00904                 cout<<"[Total Column Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Violation Count = "<<m_i_ViolationCount<<"]"<<endl;
00905                 cout<<"[Row Vertex Count = "<<STEP_DOWN(m_vi_LeftVertices.size())<<"; Column Vertex Count = "<<STEP_DOWN(m_vi_RightVertices.size())<<endl;
00906                 cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"; Checking Time = "<<m_d_CheckingTime<<"]"<<endl;
00907                 cout<<endl;
00908         }
00909 
00910         //Public Function 2469
00911         void BipartiteGraphPartialColoring::PrintVertexPartialColorClasses()
00912         {
00913                 if(CalculateVertexColorClasses() != _TRUE)
00914                 {
00915                         cout<<endl;
00916                         cout<<"Vertex Partial Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<" | Vertex Partial Colors Not Set"<<endl;
00917                         cout<<endl;
00918 
00919                         return;
00920                 }
00921 
00922                 if(m_i_LeftVertexColorCount != _UNKNOWN)
00923                 {
00924 
00925                         cout<<endl;
00926                         cout<<"Row Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl;
00927                         cout<<endl;
00928 
00929                         int i_TotalLeftVertexColors = STEP_UP(m_i_LeftVertexColorCount);
00930 
00931                         for(int i = 0; i < i_TotalLeftVertexColors; i++)
00932                         {
00933                                 if(m_vi_LeftVertexColorFrequency[i] <= 0)
00934                                 {
00935                                         continue;
00936                                 }
00937 
00938                                 cout<<"Color "<<STEP_UP(i)<<" : "<<m_vi_LeftVertexColorFrequency[i]<<endl;
00939                         }
00940 
00941                         cout<<endl;
00942                         cout<<"[Largest Row Color Class : "<<STEP_UP(m_i_LargestLeftVertexColorClass)<<"; Largest Row Color Class Size : "<<m_i_LargestLeftVertexColorClassSize<<"]"<<endl;
00943                         cout<<"[Smallest Row Color Class : "<<STEP_UP(m_i_SmallestLeftVertexColorClass)<<"; Smallest Row Color Class Size : "<<m_i_SmallestLeftVertexColorClassSize<<"]"<<endl;
00944                         cout<<"[Average Row Color Class Size : "<<m_d_AverageLeftVertexColorClassSize<<"]"<<endl;
00945                         cout<<endl;
00946                 }
00947 
00948                 if(m_i_RightVertexColorCount != _UNKNOWN)
00949                 {
00950                         cout<<endl;
00951                         cout<<"Column Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl;
00952                         cout<<endl;
00953 
00954                         int i_TotalRightVertexColors = STEP_UP(m_i_RightVertexColorCount);
00955 
00956                         for(int i = 0; i < i_TotalRightVertexColors; i++)
00957                         {
00958                                 if(m_vi_RightVertexColorFrequency[i] <= 0)
00959                                 {
00960                                         continue;
00961                                 }
00962 
00963                                 cout<<"Color "<<STEP_UP(i)<<" : "<<m_vi_RightVertexColorFrequency[i]<<endl;
00964                         }
00965 
00966                         cout<<endl;
00967                         cout<<"[Largest Column Color Class : "<<STEP_UP(m_i_LargestRightVertexColorClass)<<"; Largest Column Color Class Size : "<<m_i_LargestRightVertexColorClassSize<<"]"<<endl;
00968                         cout<<"[Smallest Column Color Class : "<<STEP_UP(m_i_SmallestRightVertexColorClass)<<"; Smallest Column Color Class Size : "<<m_i_SmallestRightVertexColorClassSize<<"]"<<endl;
00969                         cout<<"[Average Column Color Class Size : "<<m_d_AverageRightVertexColorClassSize<<"]"<<endl;
00970                         cout<<endl;
00971                 }
00972 
00973                 return;
00974         }
00975 
00976 
00977         double** BipartiteGraphPartialColoring::GetLeftSeedMatrix(int* i_SeedRowCount, int* i_SeedColumnCount) {
00978 
00979                 if(seed_available) Seed_reset();
00980 
00981                 dp2_Seed = GetLeftSeedMatrix_unmanaged(i_SeedRowCount, i_SeedColumnCount);
00982                 i_seed_rowCount = *i_SeedRowCount;
00983                 seed_available = true;
00984 
00985                 return dp2_Seed;
00986         }
00987 
00988         double** BipartiteGraphPartialColoring::GetRightSeedMatrix(int* i_SeedRowCount, int* i_SeedColumnCount) {
00989 
00990                 if(seed_available) Seed_reset();
00991 
00992                 dp2_Seed = GetRightSeedMatrix_unmanaged(i_SeedRowCount, i_SeedColumnCount);
00993                 i_seed_rowCount = *i_SeedRowCount;
00994                 seed_available = true;
00995 
00996                 return dp2_Seed;
00997         }
00998 
00999         double** BipartiteGraphPartialColoring::GetLeftSeedMatrix_unmanaged(int* i_SeedRowCount, int* i_SeedColumnCount) {
01000 
01001                 int i_size = m_vi_LeftVertexColors.size();
01002                 int i_num_of_colors = GetLeftVertexColorCount();
01003                 (*i_SeedRowCount) = i_num_of_colors;
01004                 (*i_SeedColumnCount) = i_size;
01005                 if(i_num_of_colors == 0 || i_size == 0) return NULL;
01006                 double** Seed = new double*[i_num_of_colors];
01007 
01008                 // allocate and initialize Seed matrix
01009                 for (int i=0; i<i_num_of_colors; i++) {
01010                         Seed[i] = new double[i_size];
01011                         for(int j=0; j<i_size; j++) Seed[i][j]=0.;
01012                 }
01013 
01014                 // populate Seed matrix
01015                 for (int i=0; i < i_size; i++) {
01016                         Seed[m_vi_LeftVertexColors[i]][i] = 1.;
01017                 }
01018 
01019                 return Seed;
01020         }
01021 
01022         double** BipartiteGraphPartialColoring::GetRightSeedMatrix_unmanaged(int* i_SeedRowCount, int* i_SeedColumnCount) {
01023 
01024                 int i_size = m_vi_RightVertexColors.size();
01025                 int i_num_of_colors = GetRightVertexColorCount();
01026                 (*i_SeedRowCount) = i_size;
01027                 (*i_SeedColumnCount) = i_num_of_colors;
01028                 if(i_num_of_colors == 0 || i_size == 0) return NULL;
01029                 double** Seed = new double*[i_size];
01030 
01031                 // allocate and initialize Seed matrix
01032                 for (int i=0; i<i_size; i++) {
01033                         Seed[i] = new double[i_num_of_colors];
01034                         for(int j=0; j<i_num_of_colors; j++) Seed[i][j]=0.;
01035                 }
01036 
01037                 // populate Seed matrix
01038                 for (int i=0; i < i_size; i++) {
01039 //                      if(m_vi_RightVertexColors[i]>=i_num_of_colors) {
01040 //                              cout<<"i="<<i<<endl;
01041 //                              cout<<"m_vi_RightVertexColors[i]="<<m_vi_RightVertexColors[i]<<endl;
01042 //                              cout<<"i_num_of_colors="<<i_num_of_colors<<endl;
01043 //                      }
01044                         Seed[i][m_vi_RightVertexColors[i]] = 1.;
01045                 }
01046 
01047                 return Seed;
01048         }
01049 
01050         void BipartiteGraphPartialColoring::PrintPartialColoringMetrics() {
01051                 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
01052                         PrintColumnPartialColoringMetrics();
01053                 }
01054                 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
01055                         PrintRowPartialColoringMetrics();
01056                 }
01057                 else { // Unrecognized Coloring Method
01058                         cerr<<" Unknown Partial Distance Two Coloring Method "<<m_s_VertexColoringVariant
01059                                 <<". Please use a legal Method before calling PrintPartialColors()."<<endl;
01060                 }
01061         }
01062 
01063         double** BipartiteGraphPartialColoring::GetSeedMatrix(int* i_SeedRowCount, int* i_SeedColumnCount) {
01064 
01065                 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
01066                         return GetRightSeedMatrix(i_SeedRowCount, i_SeedColumnCount);
01067                 }
01068                 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
01069                         return GetLeftSeedMatrix(i_SeedRowCount, i_SeedColumnCount);
01070                 }
01071                 else { // Unrecognized Coloring Method
01072                         cerr<<" Unknown Partial Distance Two Coloring Method "<<m_s_VertexColoringVariant
01073                                 <<". Please use a legal Method before calling PrintPartialColors()."<<endl;
01074                 }
01075                 return NULL;
01076         }
01077 
01078         double** BipartiteGraphPartialColoring::GetSeedMatrix_unmanaged(int* i_SeedRowCount, int* i_SeedColumnCount) {
01079 
01080                 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
01081                         return GetRightSeedMatrix_unmanaged(i_SeedRowCount, i_SeedColumnCount);
01082                 }
01083                 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
01084                         return GetLeftSeedMatrix_unmanaged(i_SeedRowCount, i_SeedColumnCount);
01085                 }
01086                 else { // Unrecognized Coloring Method
01087                         cerr<<" Unknown Partial Distance Two Coloring Method "<<m_s_VertexColoringVariant
01088                                 <<". Please use a legal Method before calling PrintPartialColors()."<<endl;
01089                 }
01090                 return NULL;
01091         }
01092 
01093         void BipartiteGraphPartialColoring::GetVertexPartialColors(vector<int> &output)
01094         {
01095                 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
01096                         GetRightVertexColors(output);
01097                 }
01098                 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
01099                         GetLeftVertexColors(output);
01100                 }
01101                 else { // Unrecognized Coloring Method
01102                         cerr<<" Unknown Partial Distance Two Coloring Method: "<<m_s_VertexColoringVariant
01103                                 <<". Please use a legal Method before calling GetVertexColors()."<<endl;
01104                 }
01105         }
01106 
01107         void BipartiteGraphPartialColoring::PrintPartialColors() {
01108                 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
01109                         PrintColumnPartialColors();
01110                 }
01111                 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
01112                         PrintRowPartialColors();
01113                 }
01114                 else { // Unrecognized Coloring Method
01115                         cerr<<" Unknown Partial Distance Two Coloring Method "<<m_s_VertexColoringVariant
01116                                 <<". Please use a legal Method before calling PrintPartialColors()."<<endl;
01117                 }
01118         }
01119 
01120         int BipartiteGraphPartialColoring::CheckPartialDistanceTwoColoring() {
01121                 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
01122                         return CheckPartialDistanceTwoColumnColoring();
01123                 }
01124                 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
01125                         return CheckPartialDistanceTwoRowColoring();
01126                 }
01127                 else { // Unrecognized Coloring Method
01128                         cerr<<" Unknown Partial Distance Two Coloring Method: "<<m_s_VertexColoringVariant
01129                                 <<". Please use a legal Method before calling CheckPartialDistanceTwoColoring()."<<endl;
01130                         return _FALSE;
01131                 }
01132         }
01133 
01134         
01135         double BipartiteGraphPartialColoring::GetVertexColoringTime() {
01136           return m_d_ColoringTime;
01137         }
01138         
01139         void BipartiteGraphPartialColoring::SetVertexColoringVariant(string s_VertexColoringVariant) {
01140           m_s_VertexColoringVariant = s_VertexColoringVariant;
01141         }
01142 }
01143 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines