|
ColPack
|
|
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 00028 GraphColoringInterface::GraphColoringInterface(int i_type, ...) 00029 { 00030 //cout<<"IN GraphColoringInterface(int i_type, ...)"<<endl; 00031 Clear(); 00032 00033 if (i_type == SRC_WAIT) return; 00034 00035 //---------CONVERT INPUT TO ColPack's GRAPH------------- 00036 va_list ap; /*will point to each unnamed argument in turn*/ 00037 va_start(ap,i_type); /* point to first element after i_type*/ 00038 00039 if (i_type == SRC_MEM_ADOLC) { 00040 //get unsigned int ** uip2_HessianSparsityPattern, int i_RowCount 00041 unsigned int ** uip2_HessianSparsityPattern = va_arg(ap,unsigned int **); 00042 int i_RowCount = va_arg(ap,int); 00043 00044 #ifdef _COLPACK_CHECKPOINT_ 00045 string s_postfix = "-GraphColoringInterface_Constructor"; 00046 //cout<<"*WriteMatrixMarket_ADOLCInput("<<s_postfix<<", 0, uip2_HessianSparsityPattern, "<< i_RowCount <<", " << i_RowCount <<endl; 00047 WriteMatrixMarket_ADOLCInput(s_postfix, 0, uip2_HessianSparsityPattern, i_RowCount, i_RowCount); 00048 #endif 00049 BuildGraphFromRowCompressedFormat(uip2_HessianSparsityPattern, i_RowCount); 00050 } 00051 else if (i_type == SRC_MEM_ADIC) { 00053 cerr<<"ERR: GraphColoringInterface(): s_inputSource \"ADIC\" is not supported yet"<<endl; 00054 00055 va_end(ap); /*cleanup*/ 00056 return; 00057 } 00058 else if (i_type == SRC_FILE) { 00059 // get string s_InputFile, string s_fileFormat 00060 string s_InputFile ( va_arg(ap,char *) ); 00061 string s_fileFormat ( va_arg(ap,char *) ); 00062 00063 ReadAdjacencyGraph(s_InputFile, s_fileFormat); 00064 } 00065 else { 00066 cerr<<"ERR: GraphColoringInterface(): i_type =\""<< i_type <<"\" unknown or unspecified"<<endl; 00067 00068 va_end(ap); /*cleanup*/ 00069 return; 00070 } 00071 #ifdef _COLPACK_CHECKPOINT_ 00072 string s_OutputFile = "-ColPack_debug.mtx"; 00073 s_OutputFile = "GraphColoringInterface-InternalGraph"+s_OutputFile; 00074 WriteMatrixMarket(s_OutputFile); 00075 #endif 00076 00077 //cout<<"START PrintGraph()"<<endl; 00078 //PrintGraph(); 00079 //cout<<"END"<<endl; 00080 /* 00081 // get string s_OrderingVariant 00082 string s_OrderingVariant( va_arg(ap,char *) ); 00083 if (s_OrderingVariant.compare("WAIT") == 0) { 00084 va_end(ap); //cleanup 00085 return; 00086 } 00087 00088 //---------ORDERING------------- 00089 m_T_Timer.Start(); 00090 00091 int i_OrderingStatus = OrderVertices(s_OrderingVariant); 00092 00093 m_T_Timer.Stop(); 00094 00095 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00096 //PrintVertexOrdering(); 00097 //Pause(); 00098 00099 if(i_OrderingStatus != _TRUE) 00100 { 00101 cerr<<endl<<"*ERROR: "<<s_OrderingVariant<<" Ordering Failed"<<endl; 00102 return; 00103 } 00104 00105 // get string s_ColoringVariant 00106 string s_ColoringVariant( va_arg(ap,char *) ); 00107 s_ColoringVariant = toUpper(s_ColoringVariant); 00108 if (s_ColoringVariant.compare("WAIT") == 0) { 00109 va_end(ap); //cleanup 00110 return; 00111 } 00112 00113 //---------COLORING------------- 00114 m_T_Timer.Start(); 00115 00116 if(s_ColoringVariant == "DISTANCE_ONE") DistanceOneColoring(); 00117 else if (s_ColoringVariant == "ACYCLIC") AcyclicColoring(); 00118 else if (s_ColoringVariant == "STAR") StarColoring(); 00119 else if (s_ColoringVariant == "RESTRICTED_STAR") RestrictedStarColoring(); 00120 else if (s_ColoringVariant == "DISTANCE_TWO") DistanceTwoColoring(); 00121 else { 00122 cerr<<endl<<"*ERROR: Unknown Coloring Method "<<s_ColoringVariant<<". Please use a legal Coloring Method."<<endl; 00123 return; 00124 } 00125 00126 m_T_Timer.Stop(); 00127 00128 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00129 00130 //*/ 00131 va_end(ap); //cleanup 00132 return; 00133 } 00134 00135 int GraphColoringInterface::CalculateVertexColorClasses() { 00136 return GraphColoring::CalculateVertexColorClasses(); 00137 } 00138 00139 void GraphColoringInterface::GetOrderedVertices(vector<int> &output) { 00140 GraphOrdering::GetOrderedVertices(output); 00141 } 00142 00143 double** GraphColoringInterface::GetSeedMatrix(int* ip1_SeedRowCount, int* ip1_SeedColumnCount) { 00144 return GraphColoring::GetSeedMatrix(ip1_SeedRowCount, ip1_SeedColumnCount); 00145 } 00146 00147 //Public Destructor 1602 00148 GraphColoringInterface::~GraphColoringInterface() 00149 { 00150 Clear(); 00151 00152 Seed_reset(); 00153 } 00154 00155 //Virtual Function 1603 00156 void GraphColoringInterface::Clear() 00157 { 00158 GraphColoring::Clear(); 00159 00160 return; 00161 } 00162 00163 //Public Function 1604 00164 int GraphColoringInterface::DistanceOneColoring(string s_OrderingVariant) 00165 { 00166 m_T_Timer.Start(); 00167 00168 int i_OrderingStatus = OrderVertices(s_OrderingVariant); 00169 00170 m_T_Timer.Stop(); 00171 00172 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00173 00174 if(i_OrderingStatus != _TRUE) 00175 { 00176 cerr<<endl; 00177 cerr<<s_OrderingVariant<<" Ordering Failed"; 00178 cerr<<endl; 00179 00180 return(1); 00181 } 00182 00183 m_T_Timer.Start(); 00184 00185 int i_ColoringStatus = GraphColoring::DistanceOneColoring(); 00186 00187 m_T_Timer.Stop(); 00188 00189 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00190 00191 return(i_ColoringStatus); 00192 } 00193 00194 //Public Function 1605 00195 int GraphColoringInterface::DistanceTwoColoring(string s_OrderingVariant) 00196 { 00197 m_T_Timer.Start(); 00198 00199 int i_OrderingStatus = OrderVertices(s_OrderingVariant); 00200 00201 m_T_Timer.Stop(); 00202 00203 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00204 00205 if(i_OrderingStatus != _TRUE) 00206 { 00207 cerr<<endl; 00208 cerr<<s_OrderingVariant<<" Ordering Failed"; 00209 cerr<<endl; 00210 00211 return(1); 00212 } 00213 00214 m_T_Timer.Start(); 00215 00216 int i_ColoringStatus = GraphColoring::DistanceTwoColoring(); 00217 00218 m_T_Timer.Stop(); 00219 00220 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00221 00222 return(i_ColoringStatus); 00223 } 00224 00225 //Public Function 1606 00226 int GraphColoringInterface::NaiveStarColoring(string s_OrderingVariant) 00227 { 00228 m_T_Timer.Start(); 00229 00230 int i_OrderingStatus = OrderVertices(s_OrderingVariant); 00231 00232 m_T_Timer.Stop(); 00233 00234 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00235 00236 if(i_OrderingStatus != _TRUE) 00237 { 00238 cerr<<endl; 00239 cerr<<s_OrderingVariant<<" Ordering Failed"; 00240 cerr<<endl; 00241 00242 return(1); 00243 } 00244 00245 m_T_Timer.Start(); 00246 00247 int i_ColoringStatus = GraphColoring::NaiveStarColoring(); 00248 00249 m_T_Timer.Stop(); 00250 00251 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00252 00253 return(i_ColoringStatus); 00254 } 00255 00256 //Public Function 1607 00257 int GraphColoringInterface::RestrictedStarColoring(string s_OrderingVariant) 00258 { 00259 m_T_Timer.Start(); 00260 00261 int i_OrderingVariant = OrderVertices(s_OrderingVariant); 00262 00263 m_T_Timer.Stop(); 00264 00265 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00266 00267 if(i_OrderingVariant != _TRUE) 00268 { 00269 cerr<<endl; 00270 cerr<<s_OrderingVariant<<" Ordering Failed"; 00271 cerr<<endl; 00272 00273 return(_TRUE); 00274 } 00275 00276 m_T_Timer.Start(); 00277 00278 int i_ColoringStatus = GraphColoring::RestrictedStarColoring(); 00279 00280 m_T_Timer.Stop(); 00281 00282 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00283 00284 return(i_ColoringStatus); 00285 } 00286 00287 //Public Function 1608 00288 int GraphColoringInterface::StarColoring(string s_OrderingVariant) 00289 { 00290 m_T_Timer.Start(); 00291 00292 int i_OrderingStatus = OrderVertices(s_OrderingVariant); 00293 00294 m_T_Timer.Stop(); 00295 00296 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00297 00298 if(i_OrderingStatus != _TRUE) 00299 { 00300 cerr<<endl; 00301 cerr<<s_OrderingVariant<<" Ordering Failed"; 00302 cerr<<endl; 00303 00304 return(1); 00305 } 00306 00307 m_T_Timer.Start(); 00308 00309 int i_ColoringStatus = GraphColoring::StarColoring(); 00310 00311 m_T_Timer.Stop(); 00312 00313 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00314 00315 return(i_ColoringStatus); 00316 } 00317 00318 //Public Function 1609 00319 int GraphColoringInterface::AcyclicColoring_ForIndirectRecovery(string s_OrderingVariant) 00320 { 00321 m_T_Timer.Start(); 00322 00323 int i_OrderingStatus = OrderVertices(s_OrderingVariant); 00324 00325 m_T_Timer.Stop(); 00326 00327 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00328 00329 if(i_OrderingStatus != _TRUE) 00330 { 00331 cerr<<endl; 00332 cerr<<s_OrderingVariant<<" Ordering Failed"; 00333 cerr<<endl; 00334 00335 return(1); 00336 } 00337 00338 m_T_Timer.Start(); 00339 00340 int i_ColoringStatus = GraphColoring::AcyclicColoring_ForIndirectRecovery(); 00341 00342 m_T_Timer.Stop(); 00343 00344 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00345 00346 return(i_ColoringStatus); 00347 } 00348 00349 //Public Function 1609 00350 int GraphColoringInterface::AcyclicColoring(string s_OrderingVariant) 00351 { 00352 m_T_Timer.Start(); 00353 00354 int i_OrderingStatus = OrderVertices(s_OrderingVariant); 00355 00356 m_T_Timer.Stop(); 00357 00358 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00359 00360 if(i_OrderingStatus != _TRUE) 00361 { 00362 cerr<<endl; 00363 cerr<<s_OrderingVariant<<" Ordering Failed"; 00364 cerr<<endl; 00365 00366 return(1); 00367 } 00368 00369 m_T_Timer.Start(); 00370 00371 int i_ColoringStatus = GraphColoring::AcyclicColoring(); 00372 00373 m_T_Timer.Stop(); 00374 00375 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00376 00377 return(i_ColoringStatus); 00378 } 00379 00380 //Public Function 1610 00381 int GraphColoringInterface::TriangularColoring(string s_OrderingVariant) 00382 { 00383 m_T_Timer.Start(); 00384 00385 int i_OrderingStatus = OrderVertices(s_OrderingVariant); 00386 00387 m_T_Timer.Stop(); 00388 00389 m_d_OrderingTime = m_T_Timer.GetWallTime(); 00390 00391 if(i_OrderingStatus != _TRUE) 00392 { 00393 cerr<<endl; 00394 cerr<<s_OrderingVariant<<" Ordering Failed"; 00395 cerr<<endl; 00396 00397 return(1); 00398 } 00399 00400 m_T_Timer.Start(); 00401 00402 int i_ColoringStatus = GraphColoring::TriangularColoring(); 00403 00404 m_T_Timer.Stop(); 00405 00406 m_d_ColoringTime = m_T_Timer.GetWallTime(); 00407 00408 return(i_ColoringStatus); 00409 } 00410 00411 00412 //void GraphColoringInterface::GenerateSeedHessian(unsigned int ** uip2_HessianSparsityPattern, int i_RowCount, double*** dp3_seed, int *ip1_SeedRowCount, int *ip1_SeedColumnCount, string s_OrderingVariant, string s_ColoringVariant) { 00413 void GraphColoringInterface::GenerateSeedHessian(double*** dp3_seed, int *ip1_SeedRowCount, int *ip1_SeedColumnCount, string s_OrderingVariant, string s_ColoringVariant) { 00414 //Clear (Re-initialize) the graph 00415 //Clear(); 00416 00417 //Read the sparsity pattern of the given Hessian matrix (compressed sparse rows format) 00418 //and create the corresponding graph 00419 //BuildGraphFromRowCompressedFormat(uip2_HessianSparsityPattern, i_RowCount); 00420 //PrintGraphStructure(); 00421 00422 //Color the bipartite graph with the specified ordering 00423 if (s_ColoringVariant=="DISTANCE_TWO" 00424 || s_ColoringVariant=="RESTRICTED_STAR" 00425 || s_ColoringVariant=="STAR" 00426 || s_ColoringVariant=="ACYCLIC_FOR_INDIRECT_RECOVERY") 00427 { 00428 Coloring(s_OrderingVariant, s_ColoringVariant); 00429 } 00430 else { 00431 cerr<<"Error: Unrecognized coloring method."<<endl; 00432 return; 00433 } 00434 00435 //Create the seed matrix from the coloring information 00436 (*dp3_seed) = GetSeedMatrix(ip1_SeedRowCount, ip1_SeedColumnCount); 00437 00438 /* 00439 PrintVertexColors(); 00440 PrintVertexColoringMetrics(); 00441 double **Seed = *dp3_seed; 00442 int rows = GetVertexCount(); 00443 int cols = GetVertexColorCount(); 00444 cout<<"Seed matrix: ("<<rows<<","<<cols<<")"<<endl; 00445 for(int i=0; i<rows; i++) { 00446 for(int j=0; j<cols; j++) { 00447 cout<<setw(6)<<Seed[i][j]; 00448 } 00449 cout<<endl; 00450 } 00451 //*/ 00452 } 00453 00454 void GraphColoringInterface::GenerateSeedHessian_unmanaged(double*** dp3_seed, int *ip1_SeedRowCount, int *ip1_SeedColumnCount, string s_OrderingVariant, string s_ColoringVariant) { 00455 00456 //Color the bipartite graph with the specified ordering 00457 if (s_ColoringVariant=="DISTANCE_TWO" 00458 || s_ColoringVariant=="RESTRICTED_STAR" 00459 || s_ColoringVariant=="STAR" 00460 || s_ColoringVariant=="ACYCLIC_FOR_INDIRECT_RECOVERY") 00461 { 00462 Coloring(s_OrderingVariant, s_ColoringVariant); 00463 } 00464 else { 00465 cerr<<"Error: Unrecognized coloring method."<<endl; 00466 return; 00467 } 00468 00469 //Create the seed matrix from the coloring information 00470 (*dp3_seed) = GetSeedMatrix_unmanaged(ip1_SeedRowCount, ip1_SeedColumnCount); 00471 } 00472 00473 void GraphColoringInterface::PrintVertexEdgeMap(vector<int> &vi_Vertices, vector<int> &vi_Edges , map< int, map< int, int> > &mimi2_VertexEdgeMap) { 00474 00475 cout<<endl; 00476 cout<<"DEBUG | Acyclic Coloring | Edge Vertex Map"<<endl; 00477 cout<<endl; 00478 00479 int i_VertexCount = vi_Vertices.size() - 1; 00480 00481 for(int i=0; i<i_VertexCount; i++) 00482 { 00483 for(int j=vi_Vertices[i]; j<vi_Vertices[STEP_UP(i)]; j++) 00484 { 00485 if(i < vi_Edges[j]) 00486 { 00487 cout<<"Edge "<<STEP_UP(mimi2_VertexEdgeMap[i][vi_Edges[j]])<<"\t"<<" : "<<STEP_UP(i)<<" - "<<STEP_UP(vi_Edges[j])<<endl; 00488 } 00489 } 00490 } 00491 00492 cout<<endl; 00493 } 00494 00495 void GraphColoringInterface::PrintInducedVertexDegrees(int SetID, int i_HighestInducedVertexDegree, vector< list<int> > &vli_GroupedInducedVertexDegrees) { 00496 00497 int k; 00498 00499 list<int>::iterator lit_ListIterator; 00500 00501 cout<<endl; 00502 cout<<"DEBUG 5103 | Hessian Evaluation | Induced Vertex Degrees | Set "<<STEP_UP(SetID)<<endl; 00503 cout<<endl; 00504 00505 for(int j=0; j<STEP_UP(i_HighestInducedVertexDegree); j++) 00506 { 00507 int i_SetSize = (signed) vli_GroupedInducedVertexDegrees[j].size(); 00508 00509 if(i_SetSize == _FALSE) 00510 { 00511 continue; 00512 } 00513 00514 k = _FALSE; 00515 00516 cout<<"Degree "<<j<<"\t"<<" : "; 00517 00518 for(lit_ListIterator=vli_GroupedInducedVertexDegrees[j].begin(); lit_ListIterator!=vli_GroupedInducedVertexDegrees[j].end(); lit_ListIterator++) 00519 { 00520 if(k == STEP_DOWN(i_SetSize)) 00521 { 00522 cout<<STEP_UP(*lit_ListIterator)<<" ("<<i_SetSize<<")"<<endl; 00523 } 00524 else 00525 { 00526 cout<<STEP_UP(*lit_ListIterator)<<", "; 00527 } 00528 00529 k++; 00530 } 00531 } 00532 00533 } 00534 00535 int GraphColoringInterface::Coloring(string s_OrderingVariant, string s_ColoringVariant) { 00536 if(s_ColoringVariant == "DISTANCE_ONE") { 00537 return DistanceOneColoring(s_OrderingVariant); 00538 } else if (s_ColoringVariant == "ACYCLIC") { 00539 return AcyclicColoring(s_OrderingVariant); 00540 } else if (s_ColoringVariant == "ACYCLIC_FOR_INDIRECT_RECOVERY") { 00541 return AcyclicColoring_ForIndirectRecovery(s_OrderingVariant); 00542 } else if (s_ColoringVariant == "STAR") { 00543 return StarColoring(s_OrderingVariant); 00544 } else if (s_ColoringVariant == "RESTRICTED_STAR") { 00545 return RestrictedStarColoring(s_OrderingVariant); 00546 } else if (s_ColoringVariant == "DISTANCE_TWO") { 00547 return DistanceTwoColoring(s_OrderingVariant); 00548 } else { 00549 cout<<" Unknown Coloring Method "<<s_ColoringVariant<<". Please use a legal Coloring Method."<<endl; 00550 return (_FALSE); 00551 } 00552 00553 return (_TRUE); 00554 } 00555 }
1.7.6.1 
