ColPack
|
00001 /************************************************************************************ 00002 Copyright (C) 2005-2008 Assefaw H. Gebremedhin, Arijit Tarafdar, Duc Nguyen, 00003 Alex Pothen 00004 00005 This file is part of ColPack. 00006 00007 ColPack is free software: you can redistribute it and/or modify 00008 it under the terms of the GNU Lesser General Public License as published 00009 by the Free Software Foundation, either version 3 of the License, or 00010 (at your option) any later version. 00011 00012 ColPack is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 GNU Lesser General Public License for more details. 00016 00017 You should have received a copy of the GNU Lesser General Public License 00018 along with ColPack. If not, see <http://www.gnu.org/licenses/>. 00019 ************************************************************************************/ 00020 00021 #include "ColPackHeaders.h" 00022 00023 using namespace std; 00024 00025 namespace ColPack 00026 { 00027 //Private Function 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