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