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 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
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
00163 BipartiteGraphPartialColoring::BipartiteGraphPartialColoring()
00164 {
00165 Clear();
00166
00167 Seed_init();
00168 }
00169
00170
00171
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
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
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
00285 int BipartiteGraphPartialColoring::PartialDistanceTwoRowColoring()
00286 {
00287 if(CheckVertexColoring("ROW_PARTIAL_DISTANCE_TWO"))
00288 {
00289 return(_TRUE);
00290 }
00291
00292 int i, w, x, c;
00293 int i_LeftVertexCount, i_CurrentVertex;
00294 vector<int> vi_forbiddenColors;
00295
00296 i_LeftVertexCount = (int)m_vi_LeftVertices.size () - 1;
00297
00298 m_vi_LeftVertexColors.resize ( i_LeftVertexCount, _UNKNOWN );
00299
00300 vi_forbiddenColors.resize ( i_LeftVertexCount, _UNKNOWN );
00301
00302 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = m_i_VertexColorCount;
00303
00304 for ( i=0; i<i_LeftVertexCount; ++i )
00305 {
00306 i_CurrentVertex = m_vi_OrderedVertices[i];
00307
00308 for ( w=m_vi_LeftVertices [i_CurrentVertex]; w<m_vi_LeftVertices [i_CurrentVertex+1]; ++w )
00309 {
00310 for ( x=m_vi_RightVertices [m_vi_Edges [w]]; x<m_vi_RightVertices [m_vi_Edges [w]+1]; ++x )
00311 {
00312 if ( m_vi_LeftVertexColors [m_vi_Edges [x]] != _UNKNOWN )
00313 {
00314 vi_forbiddenColors [m_vi_LeftVertexColors [m_vi_Edges [x]]] = i_CurrentVertex;
00315 }
00316 }
00317 }
00318
00319
00320 for ( c=0; c<i_LeftVertexCount; ++c )
00321 {
00322 if ( vi_forbiddenColors [c] != i_CurrentVertex )
00323 {
00324 m_vi_LeftVertexColors [i_CurrentVertex] = c;
00325
00326 if(m_i_LeftVertexColorCount < c)
00327 {
00328 m_i_LeftVertexColorCount = c;
00329 }
00330
00331 break;
00332 }
00333 }
00334
00335 }
00336
00337 m_i_VertexColorCount = m_i_LeftVertexColorCount;
00338
00339 return ( _TRUE );
00340 }
00341
00342
00343 int BipartiteGraphPartialColoring::PartialDistanceTwoColumnColoring()
00344 {
00345 if(CheckVertexColoring("COLUMN_PARTIAL_DISTANCE_TWO"))
00346 {
00347 return(_TRUE);
00348 }
00349
00350 int i, w, x, c;
00351 int i_LeftVertexCount, i_RightVertexCount, i_CurrentVertex;
00352 vector<int> vi_forbiddenColors;
00353
00354 i_LeftVertexCount = (int) m_vi_LeftVertices.size() - 1;
00355 i_RightVertexCount = (int)m_vi_RightVertices.size () - 1;
00356
00357
00358 m_vi_RightVertexColors.resize ( i_RightVertexCount, _UNKNOWN );
00359
00360
00361 vi_forbiddenColors.resize ( i_RightVertexCount, _UNKNOWN );
00362
00363 m_i_LeftVertexColorCount = m_i_RightVertexColorCount = m_i_VertexColorCount;
00364
00365
00366 for ( i=0; i<i_RightVertexCount; ++i )
00367 {
00368 i_CurrentVertex = m_vi_OrderedVertices[i] - i_LeftVertexCount;
00369
00370 for ( w=m_vi_RightVertices [i_CurrentVertex]; w<m_vi_RightVertices [i_CurrentVertex+1]; ++w )
00371 {
00372 for ( x=m_vi_LeftVertices [m_vi_Edges [w]]; x<m_vi_LeftVertices [m_vi_Edges [w]+1]; ++x )
00373 {
00374 if ( m_vi_RightVertexColors [m_vi_Edges [x]] != _UNKNOWN )
00375 {
00376 vi_forbiddenColors [m_vi_RightVertexColors [m_vi_Edges [x]]] = i_CurrentVertex;
00377 }
00378 }
00379 }
00380
00381
00382 for ( c=0; c<i_RightVertexCount; ++c )
00383 {
00384 if ( vi_forbiddenColors [c] != i_CurrentVertex )
00385 {
00386 m_vi_RightVertexColors [i_CurrentVertex] = c;
00387
00388 if(m_i_RightVertexColorCount < c)
00389 {
00390 m_i_RightVertexColorCount = c;
00391 }
00392
00393 break;
00394 }
00395 }
00396
00397 }
00398
00399 m_i_VertexColorCount = m_i_RightVertexColorCount;
00400
00401 return ( _TRUE );
00402 }
00403
00404
00405
00406
00407 int BipartiteGraphPartialColoring::CheckPartialDistanceTwoRowColoring()
00408 {
00409 for(int i=0;i<(signed) m_vi_LeftVertices.size()-1;i++)
00410
00411 {
00412 for(int j=m_vi_LeftVertices[i];j<m_vi_LeftVertices[i+1];j++)
00413 {
00414 for(int k=m_vi_RightVertices[m_vi_Edges[j]]; k<m_vi_RightVertices[m_vi_Edges[j]+1];k++)
00415
00416 {
00417 if(m_vi_Edges[k]==i) continue;
00418 if(m_vi_LeftVertexColors[m_vi_Edges[k]]==m_vi_LeftVertexColors[i])
00419 {
00420 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;
00421
00422 return _FALSE;
00423 }
00424 }
00425 }
00426 }
00427
00428 return _TRUE;
00429 }
00430
00431
00432
00433 int BipartiteGraphPartialColoring::CheckPartialDistanceTwoColumnColoring()
00434 {
00435 for(int i=0;i<(signed) m_vi_RightVertices.size()-1;i++)
00436
00437 {
00438 for(int j=m_vi_RightVertices[i];j<m_vi_RightVertices[i+1];j++)
00439 {
00440 for(int k=m_vi_LeftVertices[m_vi_Edges[j]]; k<m_vi_LeftVertices[m_vi_Edges[j]+1];k++)
00441
00442 {
00443 if(m_vi_Edges[k]==i) continue;
00444 if(m_vi_RightVertexColors[m_vi_Edges[k]]==m_vi_RightVertexColors[i])
00445 {
00446 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;
00447 return _FALSE;
00448 }
00449 }
00450 }
00451 }
00452
00453 return (_TRUE);
00454 }
00455
00456
00457 int BipartiteGraphPartialColoring::GetLeftVertexColorCount()
00458 {
00459 return(STEP_UP(m_i_LeftVertexColorCount));
00460 }
00461
00462
00463 int BipartiteGraphPartialColoring::GetRightVertexColorCount()
00464 {
00465 return(STEP_UP(m_i_RightVertexColorCount));
00466 }
00467
00468
00469
00470 int BipartiteGraphPartialColoring::GetVertexColorCount()
00471 {
00472 return(STEP_UP(m_i_VertexColorCount));
00473 }
00474
00475
00476
00477 string BipartiteGraphPartialColoring::GetVertexColoringVariant()
00478 {
00479 if(m_s_VertexColoringVariant.compare("ROW_PARTIAL_DISTANCE_TWO") == 0)
00480 {
00481 return("Row Partial Distance Two");
00482 }
00483 else
00484 if(m_s_VertexColoringVariant.compare("COLUMN_PARTIAL_DISTANCE_TWO") == 0)
00485 {
00486 return("Column Partial Distance Two");
00487 }
00488 else
00489 {
00490 return("Unknown");
00491 }
00492 }
00493
00494
00495 void BipartiteGraphPartialColoring::GetLeftVertexColors(vector<int> &output)
00496 {
00497 output = (m_vi_LeftVertexColors);
00498 }
00499
00500
00501 void BipartiteGraphPartialColoring::GetRightVertexColors(vector<int> &output)
00502 {
00503 output = (m_vi_RightVertexColors);
00504 }
00505
00506
00507
00508
00509 void BipartiteGraphPartialColoring::PrintRowPartialColors()
00510 {
00511 int i;
00512
00513 int i_LeftVertexCount;
00514
00515 string _SLASH("/");
00516
00517 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
00518
00519 m_s_InputFile = SlashTokenizer.GetLastToken();
00520
00521 i_LeftVertexCount = (signed) m_vi_LeftVertexColors.size();
00522
00523 cout<<endl;
00524 cout<<"Bipartite Graph | Row Partial Coloring | Row Vertices | Vertex Colors "<<m_s_InputFile<<endl;
00525 cout<<endl;
00526
00527 for(i=0; i<i_LeftVertexCount; i++)
00528 {
00529 cout<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(m_vi_LeftVertexColors[i])<<endl;
00530 }
00531
00532 cout<<endl;
00533 cout<<"[Total Row Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
00534 cout<<endl;
00535
00536 return;
00537 }
00538
00539
00540 void BipartiteGraphPartialColoring::PrintColumnPartialColors()
00541 {
00542 int i;
00543
00544 int i_RightVertexCount;
00545
00546 string _SLASH("/");
00547
00548 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
00549
00550 m_s_InputFile = SlashTokenizer.GetLastToken();
00551
00552 i_RightVertexCount = (signed) m_vi_RightVertexColors.size();
00553
00554 cout<<endl;
00555 cout<<"Bipartite Graph | Column Partial Coloring | Column Vertices | Vertex Colors | "<<m_s_InputFile<<endl;
00556 cout<<endl;
00557
00558 for(i=0; i<i_RightVertexCount; i++)
00559 {
00560 cout<<STEP_UP(i)<<"\t"<<" : "<<STEP_UP(m_vi_RightVertexColors[i])<<endl;
00561 }
00562
00563 cout<<endl;
00564 cout<<"[Total Column Colors = "<<STEP_UP(m_i_VertexColorCount)<<"]"<<endl;
00565 cout<<endl;
00566
00567 return;
00568 }
00569
00570
00571
00572
00573 void BipartiteGraphPartialColoring::PrintRowPartialColoringMetrics()
00574 {
00575 string _SLASH("/");
00576
00577 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
00578
00579 string s_InputFile = SlashTokenizer.GetLastToken();
00580
00581 cout<<endl;
00582 cout<<GetVertexColoringVariant()<<" Bicoloring | "<<GetVertexOrderingVariant()<<" Ordering | "<<s_InputFile<<endl;
00583 cout<<endl;
00584
00585 cout<<endl;
00586 cout<<"[Total Row Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Violation Count = "<<m_i_ViolationCount<<"]"<<endl;
00587 cout<<"[Row Vertex Count = "<<STEP_DOWN(m_vi_LeftVertices.size())<<"; Column Vertex Count = "<<STEP_DOWN(m_vi_RightVertices.size())<<endl;
00588 cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"; Checking Time = "<<m_d_CheckingTime<<"]"<<endl;
00589 cout<<endl;
00590 }
00591
00592
00593
00594 void BipartiteGraphPartialColoring::PrintColumnPartialColoringMetrics()
00595 {
00596 string _SLASH("/");
00597
00598 StringTokenizer SlashTokenizer(m_s_InputFile, _SLASH);
00599
00600 string s_InputFile = SlashTokenizer.GetLastToken();
00601
00602 cout<<endl;
00603 cout<<GetVertexColoringVariant()<<" Bicoloring | "<<GetVertexOrderingVariant()<<" Ordering | "<<s_InputFile<<endl;
00604 cout<<endl;
00605
00606 cout<<endl;
00607 cout<<"[Total Column Colors = "<<STEP_UP(m_i_VertexColorCount)<<"; Violation Count = "<<m_i_ViolationCount<<"]"<<endl;
00608 cout<<"[Row Vertex Count = "<<STEP_DOWN(m_vi_LeftVertices.size())<<"; Column Vertex Count = "<<STEP_DOWN(m_vi_RightVertices.size())<<endl;
00609 cout<<"[Ordering Time = "<<m_d_OrderingTime<<"; Coloring Time = "<<m_d_ColoringTime<<"; Checking Time = "<<m_d_CheckingTime<<"]"<<endl;
00610 cout<<endl;
00611 }
00612
00613
00614 void BipartiteGraphPartialColoring::PrintVertexPartialColorClasses()
00615 {
00616 if(CalculateVertexColorClasses() != _TRUE)
00617 {
00618 cout<<endl;
00619 cout<<"Vertex Partial Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<" | Vertex Partial Colors Not Set"<<endl;
00620 cout<<endl;
00621
00622 return;
00623 }
00624
00625 if(m_i_LeftVertexColorCount != _UNKNOWN)
00626 {
00627
00628 cout<<endl;
00629 cout<<"Row Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl;
00630 cout<<endl;
00631
00632 int i_TotalLeftVertexColors = STEP_UP(m_i_LeftVertexColorCount);
00633
00634 for(int i = 0; i < i_TotalLeftVertexColors; i++)
00635 {
00636 if(m_vi_LeftVertexColorFrequency[i] <= 0)
00637 {
00638 continue;
00639 }
00640
00641 cout<<"Color "<<STEP_UP(i)<<" : "<<m_vi_LeftVertexColorFrequency[i]<<endl;
00642 }
00643
00644 cout<<endl;
00645 cout<<"[Largest Row Color Class : "<<STEP_UP(m_i_LargestLeftVertexColorClass)<<"; Largest Row Color Class Size : "<<m_i_LargestLeftVertexColorClassSize<<"]"<<endl;
00646 cout<<"[Smallest Row Color Class : "<<STEP_UP(m_i_SmallestLeftVertexColorClass)<<"; Smallest Row Color Class Size : "<<m_i_SmallestLeftVertexColorClassSize<<"]"<<endl;
00647 cout<<"[Average Row Color Class Size : "<<m_d_AverageLeftVertexColorClassSize<<"]"<<endl;
00648 cout<<endl;
00649 }
00650
00651 if(m_i_RightVertexColorCount != _UNKNOWN)
00652 {
00653 cout<<endl;
00654 cout<<"Column Color Classes | "<<m_s_VertexColoringVariant<<" Coloring | "<<m_s_VertexOrderingVariant<<" Ordering | "<<m_s_InputFile<<endl;
00655 cout<<endl;
00656
00657 int i_TotalRightVertexColors = STEP_UP(m_i_RightVertexColorCount);
00658
00659 for(int i = 0; i < i_TotalRightVertexColors; i++)
00660 {
00661 if(m_vi_RightVertexColorFrequency[i] <= 0)
00662 {
00663 continue;
00664 }
00665
00666 cout<<"Color "<<STEP_UP(i)<<" : "<<m_vi_RightVertexColorFrequency[i]<<endl;
00667 }
00668
00669 cout<<endl;
00670 cout<<"[Largest Column Color Class : "<<STEP_UP(m_i_LargestRightVertexColorClass)<<"; Largest Column Color Class Size : "<<m_i_LargestRightVertexColorClassSize<<"]"<<endl;
00671 cout<<"[Smallest Column Color Class : "<<STEP_UP(m_i_SmallestRightVertexColorClass)<<"; Smallest Column Color Class Size : "<<m_i_SmallestRightVertexColorClassSize<<"]"<<endl;
00672 cout<<"[Average Column Color Class Size : "<<m_d_AverageRightVertexColorClassSize<<"]"<<endl;
00673 cout<<endl;
00674 }
00675
00676 return;
00677 }
00678
00679
00680 double** BipartiteGraphPartialColoring::GetLeftSeedMatrix(int* i_SeedRowCount, int* i_SeedColumnCount) {
00681
00682 if(seed_available) Seed_reset();
00683
00684 int i_size = m_vi_LeftVertexColors.size();
00685 int i_num_of_colors = m_i_LeftVertexColorCount + 1;
00686 (*i_SeedRowCount) = i_num_of_colors;
00687 (*i_SeedColumnCount) = i_size;
00688 if(i_num_of_colors == 0 || i_size == 0) return NULL;
00689 double** Seed = new double*[i_num_of_colors];
00690
00691
00692 for (int i=0; i<i_num_of_colors; i++) {
00693 Seed[i] = new double[i_size];
00694 for(int j=0; j<i_size; j++) Seed[i][j]=0.;
00695 }
00696
00697
00698 for (int i=0; i < i_size; i++) {
00699 Seed[m_vi_LeftVertexColors[i]][i] = 1.;
00700 }
00701
00702 seed_available = true;
00703 i_seed_rowCount = *i_SeedRowCount;
00704 dp2_Seed = Seed;
00705
00706 return Seed;
00707 }
00708
00709 double** BipartiteGraphPartialColoring::GetRightSeedMatrix(int* i_SeedRowCount, int* i_SeedColumnCount) {
00710
00711 if(seed_available) Seed_reset();
00712
00713 int i_size = m_vi_RightVertexColors.size();
00714 int i_num_of_colors = m_i_RightVertexColorCount + 1;
00715 (*i_SeedRowCount) = i_size;
00716 (*i_SeedColumnCount) = i_num_of_colors;
00717 if(i_num_of_colors == 0 || i_size == 0) return NULL;
00718 double** Seed = new double*[i_size];
00719
00720
00721 for (int i=0; i<i_size; i++) {
00722 Seed[i] = new double[i_num_of_colors];
00723 for(int j=0; j<i_num_of_colors; j++) Seed[i][j]=0.;
00724 }
00725
00726
00727 for (int i=0; i < i_size; i++) {
00728 Seed[i][m_vi_RightVertexColors[i]] = 1.;
00729 }
00730
00731 seed_available = true;
00732 i_seed_rowCount = *i_SeedRowCount;
00733 dp2_Seed = Seed;
00734
00735 return Seed;
00736 }
00737
00738 double** BipartiteGraphPartialColoring::GetLeftSeedMatrix_unmanaged(int* i_SeedRowCount, int* i_SeedColumnCount) {
00739
00740 int i_size = m_vi_LeftVertexColors.size();
00741 int i_num_of_colors = m_i_LeftVertexColorCount + 1;
00742 (*i_SeedRowCount) = i_num_of_colors;
00743 (*i_SeedColumnCount) = i_size;
00744 if(i_num_of_colors == 0 || i_size == 0) return NULL;
00745 double** Seed = new double*[i_num_of_colors];
00746
00747
00748 for (int i=0; i<i_num_of_colors; i++) {
00749 Seed[i] = new double[i_size];
00750 for(int j=0; j<i_size; j++) Seed[i][j]=0.;
00751 }
00752
00753
00754 for (int i=0; i < i_size; i++) {
00755 Seed[m_vi_LeftVertexColors[i]][i] = 1.;
00756 }
00757
00758 return Seed;
00759 }
00760
00761 double** BipartiteGraphPartialColoring::GetRightSeedMatrix_unmanaged(int* i_SeedRowCount, int* i_SeedColumnCount) {
00762
00763 int i_size = m_vi_RightVertexColors.size();
00764 int i_num_of_colors = m_i_RightVertexColorCount + 1;
00765 (*i_SeedRowCount) = i_size;
00766 (*i_SeedColumnCount) = i_num_of_colors;
00767 if(i_num_of_colors == 0 || i_size == 0) return NULL;
00768 double** Seed = new double*[i_size];
00769
00770
00771 for (int i=0; i<i_size; i++) {
00772 Seed[i] = new double[i_num_of_colors];
00773 for(int j=0; j<i_num_of_colors; j++) Seed[i][j]=0.;
00774 }
00775
00776
00777 for (int i=0; i < i_size; i++) {
00778 Seed[i][m_vi_RightVertexColors[i]] = 1.;
00779 }
00780
00781 return Seed;
00782 }
00783
00784 void BipartiteGraphPartialColoring::PrintPartialColoringMetrics() {
00785 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
00786 PrintColumnPartialColoringMetrics();
00787 }
00788 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
00789 PrintRowPartialColoringMetrics();
00790 }
00791 else {
00792 cerr<<" Unknown Partial Distance Two Coloring Method "<<m_s_VertexColoringVariant
00793 <<". Please use a legal Method before calling PrintPartialColors()."<<endl;
00794 }
00795 }
00796
00797 double** BipartiteGraphPartialColoring::GetSeedMatrix(int* i_SeedRowCount, int* i_SeedColumnCount) {
00798
00799 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
00800 return GetRightSeedMatrix(i_SeedRowCount, i_SeedColumnCount);
00801 }
00802 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
00803 return GetLeftSeedMatrix(i_SeedRowCount, i_SeedColumnCount);
00804 }
00805 else {
00806 cerr<<" Unknown Partial Distance Two Coloring Method "<<m_s_VertexColoringVariant
00807 <<". Please use a legal Method before calling PrintPartialColors()."<<endl;
00808 }
00809 return NULL;
00810 }
00811
00812 double** BipartiteGraphPartialColoring::GetSeedMatrix_unmanaged(int* i_SeedRowCount, int* i_SeedColumnCount) {
00813
00814 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
00815 return GetRightSeedMatrix_unmanaged(i_SeedRowCount, i_SeedColumnCount);
00816 }
00817 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
00818 return GetLeftSeedMatrix_unmanaged(i_SeedRowCount, i_SeedColumnCount);
00819 }
00820 else {
00821 cerr<<" Unknown Partial Distance Two Coloring Method "<<m_s_VertexColoringVariant
00822 <<". Please use a legal Method before calling PrintPartialColors()."<<endl;
00823 }
00824 return NULL;
00825 }
00826
00827 void BipartiteGraphPartialColoring::GetVertexPartialColors(vector<int> &output)
00828 {
00829 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
00830 GetRightVertexColors(output);
00831 }
00832 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
00833 GetLeftVertexColors(output);
00834 }
00835 else {
00836 cerr<<" Unknown Partial Distance Two Coloring Method: "<<m_s_VertexColoringVariant
00837 <<". Please use a legal Method before calling GetVertexColors()."<<endl;
00838 }
00839 }
00840
00841 void BipartiteGraphPartialColoring::PrintPartialColors() {
00842 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
00843 PrintColumnPartialColors();
00844 }
00845 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
00846 PrintRowPartialColors();
00847 }
00848 else {
00849 cerr<<" Unknown Partial Distance Two Coloring Method "<<m_s_VertexColoringVariant
00850 <<". Please use a legal Method before calling PrintPartialColors()."<<endl;
00851 }
00852 }
00853
00854 int BipartiteGraphPartialColoring::CheckPartialDistanceTwoColoring() {
00855 if ( m_s_VertexColoringVariant == "COLUMN_PARTIAL_DISTANCE_TWO") {
00856 return CheckPartialDistanceTwoColumnColoring();
00857 }
00858 else if (m_s_VertexColoringVariant == "ROW_PARTIAL_DISTANCE_TWO") {
00859 return CheckPartialDistanceTwoRowColoring();
00860 }
00861 else {
00862 cerr<<" Unknown Partial Distance Two Coloring Method: "<<m_s_VertexColoringVariant
00863 <<". Please use a legal Method before calling CheckPartialDistanceTwoColoring()."<<endl;
00864 return _FALSE;
00865 }
00866 }
00867
00868
00869 double BipartiteGraphPartialColoring::GetVertexColoringTime() {
00870 return m_d_ColoringTime;
00871 }
00872 }
00873