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 GraphInputOutput::ParseWidth(string FortranFormat)
00029 {
00030 int i;
00031
00032 int LetterCount;
00033
00034 char PresentLetter;
00035
00036 string FieldWidth;
00037
00038 boolean FOUND;
00039
00040 FieldWidth.clear();
00041
00042 FOUND = FALSE;
00043
00044 LetterCount = (signed) FortranFormat.size();
00045
00046 for(i=0; i<LetterCount; i++)
00047 {
00048 PresentLetter = FortranFormat[i];
00049
00050 if(FOUND == TRUE)
00051 {
00052 FieldWidth += PresentLetter;
00053 }
00054
00055 if(PresentLetter == 'I' || PresentLetter == 'Z' || PresentLetter == 'F' || PresentLetter == 'E' || PresentLetter == 'G' || PresentLetter == 'D' || PresentLetter == 'L' || PresentLetter == 'A')
00056 {
00057 FOUND = TRUE;
00058 }
00059 else
00060 if(PresentLetter == '.' || PresentLetter == ')')
00061 {
00062 FOUND = FALSE;
00063
00064 break;
00065 }
00066 }
00067
00068 return(atoi(FieldWidth.c_str()));
00069 }
00070
00071
00072
00073 void GraphInputOutput::CalculateVertexDegrees()
00074 {
00075 int i_VertexCount = STEP_DOWN((signed) m_vi_Vertices.size());
00076
00077 for(int i = 0; i < i_VertexCount; i++)
00078 {
00079 int i_VertexDegree = m_vi_Vertices[i + 1] - m_vi_Vertices[i];
00080
00081 if(m_i_MaximumVertexDegree < i_VertexDegree)
00082 {
00083 m_i_MaximumVertexDegree = i_VertexDegree;
00084 }
00085
00086 if(m_i_MinimumVertexDegree == _UNKNOWN)
00087 {
00088 m_i_MinimumVertexDegree = i_VertexDegree;
00089 }
00090 else
00091 if(m_i_MinimumVertexDegree > i_VertexDegree)
00092 {
00093 m_i_MinimumVertexDegree = i_VertexDegree;
00094 }
00095 }
00096
00097 m_d_AverageVertexDegree = (double)m_vi_Edges.size()/i_VertexCount;
00098
00099 return;
00100
00101 }
00102
00103
00104
00105 GraphInputOutput::GraphInputOutput()
00106 {
00107 Clear();
00108
00109 GraphCore::Clear();
00110 }
00111
00112
00113
00114 GraphInputOutput::~GraphInputOutput()
00115 {
00116 Clear();
00117 }
00118
00119
00120 void GraphInputOutput::Initialize()
00121 {
00122
00123 }
00124
00125
00126 void GraphInputOutput::Clear()
00127 {
00128 GraphCore::Clear();
00129
00130 return;
00131 }
00132
00133
00134 string GraphInputOutput::GetInputFile()
00135 {
00136 return(m_s_InputFile);
00137 }
00138
00139
00140
00141 int GraphInputOutput::ReadMatrixMarketAdjacencyGraph(string s_InputFile, bool b_getStructureOnly)
00142 {
00143
00144 Clear();
00145
00146 m_s_InputFile=s_InputFile;
00147
00148
00149 int col=0, row=0, rowIndex=0, colIndex=0;
00150 int entry_counter = 0, num_of_entries = 0;
00151 bool value_not_specified = false;
00152
00153 float value;
00154 bool b_getValue = !b_getStructureOnly, b_symmetric;
00155 istringstream in2;
00156 string line="";
00157 map<int,vector<int> > nodeList;
00158 map<int,vector<float> > valueList;
00159
00160
00161 MM_typecode matcode;
00162 FILE *f;
00163 if ((f = fopen(m_s_InputFile.c_str(), "r")) == NULL) {
00164 cout<<m_s_InputFile<<" not Found!"<<endl;
00165 exit(1);
00166 }
00167 else cout<<"Found file "<<m_s_InputFile<<endl;
00168
00169 if (mm_read_banner(f, &matcode) != 0)
00170 {
00171 printf("Could not process Matrix Market banner.\n");
00172 exit(1);
00173 }
00174
00175
00176 if( mm_is_pattern(matcode) ) {
00177 b_getValue = false;
00178 }
00179 if(mm_is_symmetric(matcode)) {
00180 b_symmetric = true;
00181 }
00182 else b_symmetric = false;
00183
00184 char * result = mm_typecode_to_str(matcode);
00185 printf("Graph of Market Market type: [%s]\n", result);
00186 free(result);
00187 if (b_getValue) printf("\t Graph structure and VALUES will be read\n");
00188 else printf("\t Read graph struture only. Values will NOT be read\n");
00189 if( !( mm_is_coordinate(matcode) && (mm_is_symmetric(matcode) || mm_is_general(matcode) ) && ( mm_is_real(matcode) || mm_is_pattern(matcode) || mm_is_integer(matcode) ) ) ) {
00190 printf("Sorry, this application does not support this type.");
00191 exit(-1);
00192 }
00193
00194 fclose(f);
00195
00196
00197
00198 ifstream in (m_s_InputFile.c_str());
00199 if(!in) {
00200 cout<<m_s_InputFile<<" not Found!"<<endl;
00201 exit(1);
00202 }
00203 else {
00204
00205 }
00206
00207 getline(in,line);
00208 while(line.size()>0&&line[0]=='%') {
00209 getline(in,line);
00210 }
00211 in2.str(line);
00212 in2>>row>>col>>num_of_entries;
00213
00214
00215 if(row!=col) {
00216 cout<<"* WARNING: GraphInputOutput::ReadMatrixMarketAdjacencyGraph()"<<endl;
00217 cout<<"*\t row!=col. This is not a square matrix. Can't process."<<endl;
00218 return _FALSE;
00219 }
00220
00221
00222 while(!in.eof() && entry_counter<num_of_entries)
00223 {
00224 getline(in,line);
00225 entry_counter++;
00226
00227 if(line!="")
00228 {
00229 in2.clear();
00230 in2.str(line);
00231
00232
00233
00234
00235 in2 >> rowIndex >> colIndex >> value;
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252 rowIndex--;
00253 colIndex--;
00254
00255 if(b_symmetric) {
00256 if(rowIndex>colIndex) {
00257
00258 nodeList[rowIndex].push_back(colIndex);
00259 nodeList[colIndex].push_back(rowIndex);
00260
00261 if(b_getValue) {
00262
00263 valueList[rowIndex].push_back(value);
00264 valueList[colIndex].push_back(value);
00265 }
00266
00267 }
00268 else if (rowIndex == colIndex) {
00269 continue;
00270 }
00271 else {
00272 cerr<<"* WARNING: GraphInputOutput::ReadMatrixMarketAdjacencyGraph()"<<endl;
00273 cerr<<"\t Found a nonzero in the upper triangular. A symmetric Matrix Market file format should only specify the nonzeros in the lower triangular."<<endl;
00274 exit( -1);
00275 }
00276 }
00277 else {
00278 if(rowIndex!=colIndex) {
00279
00280 nodeList[rowIndex].push_back(colIndex);
00281
00282 if(b_getValue) {
00283
00284 valueList[rowIndex].push_back(value);
00285 }
00286 }
00287 else {
00288 continue;
00289 }
00290 }
00291
00292 }
00293 else
00294 {
00295 cerr<<"* WARNING: GraphInputOutput::ReadMatrixMarketAdjacencyGraph()"<<endl;
00296 cerr<<"*\t Entry == \"\" at row "<<entry_counter<<". Empty line. Wrong input format. Can't process."<<endl;
00297 cerr<<"\t # entries so far: "<<entry_counter<<"/"<<num_of_entries<<endl;
00298 return _FALSE;
00299 }
00300 }
00301 if(entry_counter<num_of_entries) {
00302 cerr<<"* WARNING: GraphInputOutput::ReadMatrixMarketAdjacencyGraph()"<<endl;
00303 cerr<<"*\t entry_counter<num_of_entries. Wrong input format. Can't process."<<endl;
00304 cerr<<"\t # entries so far: "<<entry_counter<<"/"<<num_of_entries<<endl;
00305 return _FALSE;
00306 }
00307
00308
00309
00310 m_vi_Vertices.push_back(m_vi_Edges.size());
00311
00312 for(int i=0;i<row; i++) {
00313 m_vi_Edges.insert(m_vi_Edges.end(),nodeList[i].begin(),nodeList[i].end());
00314 m_vi_Vertices.push_back(m_vi_Edges.size());
00315 }
00316 if(b_getValue) {
00317 for(int i=0;i<row; i++) {
00318 m_vd_Values.insert(m_vd_Values.end(),valueList[i].begin(),valueList[i].end());
00319 }
00320 }
00321
00322
00323
00324
00325 CalculateVertexDegrees();
00326
00327 return(_TRUE);
00328 }
00329
00330
00331
00332 int GraphInputOutput::ReadHarwellBoeingAdjacencyGraph(string s_InputFile)
00333 {
00334 int i, j;
00335
00336 int i_VertexCount, i_VertexDegree;
00337
00338 int LineCount;
00339
00340 int AssemblyCount, ColumnCount, DataCount, RowCount;
00341
00342 int ColumnFormatWidth, RowFormatWidth, DataFormatWidth;
00343
00344 int ColumnStartLine, DataStartLine, RowStartLine;
00345
00346 int IndexCount;
00347
00348 int RightCount, RightIndexCount;
00349
00350 int RightHeader;
00351
00352 int TotalColumnLines, TotalDataLines, TotalEntryLines, TotalRowLines;
00353
00354 int TotalRightDataLines;
00355
00356 string InputLine;
00357
00358 string MatrixTitle, MatrixKey, MatrixType;
00359
00360 string ColumnFormat, RowFormat, DataFormat;
00361
00362 string RightFormat;
00363
00364 string RightType;
00365
00366 string __GAP(" ");
00367
00368 ifstream InputStream;
00369
00370 vector<int> ColumnIndices, RowIndices;
00371
00372 vector<double> DataValues;
00373
00374 vector<string> InputTokens;
00375
00376 vector< vector<int> > v2i_VertexAdjacency;
00377
00378 Clear();
00379
00380 ColumnIndices.clear();
00381 RowIndices.clear();
00382 DataValues.clear();
00383
00384 m_s_InputFile = s_InputFile;
00385
00386 InputStream.open(m_s_InputFile.c_str());
00387 if(!InputStream) {
00388 cout<<m_s_InputFile<<" not Found!"<<endl;
00389 return (_FALSE);
00390 }
00391 else cout<<"Found file "<<m_s_InputFile<<endl;
00392
00393 TotalColumnLines = TotalRowLines = TotalDataLines = _FALSE;
00394
00395 ColumnFormatWidth = RowFormatWidth = DataFormatWidth = _FALSE;
00396
00397 TotalRightDataLines = _FALSE;
00398
00399 RightHeader = _FALSE;
00400
00401 LineCount = _FALSE;
00402
00403 do
00404 {
00405 InputLine.clear();
00406
00407 getline(InputStream, InputLine);
00408
00409 if(!InputStream)
00410 {
00411 break;
00412 }
00413
00414 if(LineCount == 0)
00415 {
00416 MatrixTitle = InputLine.substr(0, 72);
00417
00418 MatrixKey = InputLine.substr(72, 8);
00419 }
00420
00421 if(LineCount == 1)
00422 {
00423 TotalEntryLines = atoi(InputLine.substr(0, 14).c_str());
00424 TotalColumnLines = atoi(InputLine.substr(14, 14).c_str());
00425 TotalRowLines = atoi(InputLine.substr(28, 14).c_str());
00426 TotalDataLines = atoi(InputLine.substr(42, 14).c_str());
00427 TotalRightDataLines = atoi(InputLine.substr(56, 14).c_str());
00428 }
00429
00430 if(LineCount == 2)
00431 {
00432 MatrixType = InputLine.substr(0, 3);
00433
00434 RowCount = atoi(InputLine.substr(14, 14).c_str());
00435 ColumnCount = atoi(InputLine.substr(28, 14).c_str());
00436 DataCount = atoi(InputLine.substr(42, 14).c_str());
00437 AssemblyCount = atoi(InputLine.substr(56, 14).c_str());
00438 }
00439
00440 if(LineCount == 3)
00441 {
00442 ColumnFormat = InputLine.substr(0, 16);
00443 RowFormat = InputLine.substr(16, 16);
00444 DataFormat = InputLine.substr(32, 20);
00445 RightFormat= InputLine.substr(52, 20);
00446
00447 ColumnFormatWidth = ParseWidth(ColumnFormat);
00448 RowFormatWidth = ParseWidth(RowFormat);
00449 DataFormatWidth = ParseWidth(DataFormat);
00450 }
00451
00452 if(LineCount == 4)
00453 {
00454 if(TotalRightDataLines != _FALSE)
00455 {
00456 RightType = InputLine.substr(0, 3);
00457 RightCount = atoi(InputLine.substr(14, 14).c_str());
00458 RightIndexCount = atoi(InputLine.substr(28, 14).c_str());
00459
00460 RightHeader = _TRUE;
00461 }
00462 }
00463
00464 ColumnStartLine = RightHeader + 4;
00465
00466 if(LineCount >= ColumnStartLine && LineCount < ColumnStartLine + TotalColumnLines)
00467 {
00468 IndexCount = _FALSE;
00469
00470 while(IndexCount <(signed) InputLine.size())
00471 {
00472 ColumnIndices.push_back(atoi(InputLine.substr(IndexCount, ColumnFormatWidth).c_str()));
00473
00474 IndexCount += ColumnFormatWidth;
00475 }
00476 }
00477
00478 RowStartLine = ColumnStartLine + TotalColumnLines;
00479
00480 if(LineCount >= RowStartLine && LineCount < RowStartLine + TotalRowLines)
00481 {
00482 IndexCount = _FALSE;
00483
00484 while(IndexCount <(signed) InputLine.size())
00485 {
00486 RowIndices.push_back(atoi(InputLine.substr(IndexCount, RowFormatWidth).c_str()));
00487
00488 IndexCount += RowFormatWidth;
00489 }
00490 }
00491
00492 DataStartLine = RowStartLine + TotalRowLines;
00493
00494 if(LineCount >= DataStartLine && LineCount < DataStartLine + TotalDataLines)
00495 {
00496 IndexCount = _FALSE;
00497
00498 while(IndexCount <(signed) InputLine.size())
00499 {
00500 DataValues.push_back(atof(InputLine.substr(IndexCount, DataFormatWidth).c_str()));
00501
00502 IndexCount += DataFormatWidth;
00503 }
00504 }
00505
00506 LineCount++;
00507
00508 }
00509 while(InputStream);
00510
00511 InputStream.close();
00512
00513 IndexCount = (signed) ColumnIndices.size();
00514
00515 v2i_VertexAdjacency.clear();
00516 v2i_VertexAdjacency.resize((unsigned) STEP_DOWN(IndexCount));
00517
00518 for(i=0; i<STEP_DOWN(IndexCount); i++)
00519 {
00520 for(j=STEP_DOWN(ColumnIndices[i]); j<STEP_DOWN(ColumnIndices[STEP_UP(i)]); j++)
00521 {
00522 if(i == STEP_DOWN(RowIndices[j]))
00523 {
00524 continue;
00525 }
00526
00527 v2i_VertexAdjacency[i].push_back(STEP_DOWN(RowIndices[j]));
00528 v2i_VertexAdjacency[STEP_DOWN(RowIndices[j])].push_back(i);
00529 }
00530 }
00531
00532 i_VertexCount = (signed) v2i_VertexAdjacency.size();
00533
00534 for(i=0; i<i_VertexCount; i++)
00535 {
00536 m_vi_Vertices.push_back((signed) m_vi_Edges.size());
00537
00538 i_VertexDegree = (signed) v2i_VertexAdjacency[i].size();
00539
00540 for(j=0; j<i_VertexDegree; j++)
00541 {
00542 m_vi_Edges.push_back(v2i_VertexAdjacency[i][j]);
00543 }
00544 }
00545
00546 m_vi_Vertices.push_back((signed) m_vi_Edges.size());
00547
00548 CalculateVertexDegrees();
00549
00550 #if DEBUG == 1258
00551
00552 cout<<endl;
00553
00554 cout<<"Matrix Title = "<<MatrixTitle<<endl;
00555 cout<<"Matrix Key = "<<MatrixKey<<endl;
00556
00557 cout<<endl;
00558
00559 cout<<"Total Entry Lines = "<<TotalEntryLines<<endl;
00560 cout<<"Total Column Lines = "<<TotalColumnLines<<endl;
00561 cout<<"Total Row Lines = "<<TotalRowLines<<endl;
00562 cout<<"Total Data Lines = "<<TotalDataLines<<endl;
00563 cout<<"Total Right Data Lines = "<<TotalRightDataLines<<endl;
00564
00565 cout<<endl;
00566
00567 cout<<"Matrix Type = "<<MatrixType<<endl;
00568 cout<<"Row Count = "<<RowCount<<endl;
00569 cout<<"Column Count = "<<ColumnCount<<endl;
00570 cout<<"Data Count = "<<DataCount<<endl;
00571 cout<<"Assembly Count = "<<AssemblyCount<<endl;
00572
00573 cout<<endl;
00574
00575 cout<<"Column Format = "<<ColumnFormat<<endl;
00576 cout<<"Row Format = "<<RowFormat<<endl;
00577 cout<<"Data Format = "<<DataFormat<<endl;
00578 cout<<"Right Format = "<<RightFormat<<endl;
00579
00580 cout<<endl;
00581
00582 cout<<"Column Format Width = "<<ColumnFormatWidth<<endl;
00583 cout<<"Row Format Width = "<<RowFormatWidth<<endl;
00584 cout<<"Data Format Width = "<<DataFormatWidth<<endl;
00585
00586 cout<<endl;
00587
00588 if(TotalRightDataLines != _FALSE)
00589 {
00590 cout<<"Right Type = "<<RightType<<endl;
00591 cout<<"Right Count = "<<RightCount<<endl;
00592 cout<<"Right Index Count = "<<RightIndexCount<<endl;
00593
00594 cout<<endl;
00595 }
00596
00597 IndexCount = (signed) ColumnIndices.size();
00598
00599 cout<<"Column Indices = ";
00600
00601 for(i=0; i<IndexCount; i++)
00602 {
00603 if(i == STEP_DOWN(IndexCount))
00604 {
00605 cout<<ColumnIndices[i]<<" ("<<IndexCount<<")"<<endl;
00606 }
00607 else
00608 {
00609 cout<<ColumnIndices[i]<<", ";
00610 }
00611 }
00612
00613 if(!IndexCount)
00614 {
00615 cout<<"Not Found"<<endl;
00616 }
00617
00618 cout<<endl;
00619
00620 IndexCount = (signed) RowIndices.size();
00621
00622 cout<<"Row Indices = ";
00623
00624 for(i=0; i<IndexCount; i++)
00625 {
00626 if(i == STEP_DOWN(IndexCount))
00627 {
00628 cout<<RowIndices[i]<<" ("<<IndexCount<<")"<<endl;
00629 }
00630 else
00631 {
00632 cout<<RowIndices[i]<<", ";
00633 }
00634 }
00635
00636 if(!IndexCount)
00637 {
00638 cout<<"Not Found"<<endl;
00639 }
00640
00641 cout<<endl;
00642
00643 IndexCount = (signed) DataValues.size();
00644
00645 cout<<"Data Values = ";
00646
00647 for(i=0; i<IndexCount; i++)
00648 {
00649 if(i == STEP_DOWN(IndexCount))
00650 {
00651 cout<<DataValues[i]<<" ("<<IndexCount<<")"<<endl;
00652 }
00653 else
00654 {
00655 cout<<DataValues[i]<<", ";
00656 }
00657 }
00658
00659 if(!IndexCount)
00660 {
00661 cout<<"Not Found"<<endl;
00662 }
00663
00664 cout<<endl;
00665
00666 #endif
00667
00668 #if DEBUG == 1258
00669
00670 int i_EdgeCount;
00671
00672 cout<<endl;
00673 cout<<"DEBUG 1258 | Acyclic Coloring | Vertex Adjacency | "<<InputFile<<endl;
00674 cout<<endl;
00675
00676 i_EdgeCount = _FALSE;
00677 i_VertexCount = RowCount;
00678
00679 for(i=0; i<i_VertexCount; i++)
00680 {
00681 cout<<"Vertex "<<STEP_UP(i)<<"\t"<<" : ";
00682
00683 i_VertexDegree = (signed) v2i_VertexAdjacency[i].size();
00684
00685 for(j=0; j<i_VertexDegree; j++)
00686 {
00687 if(j == STEP_DOWN(i_VertexDegree))
00688 {
00689 cout<<STEP_UP(v2i_VertexAdjacency[i][j])<<" ("<<i_VertexDegree<<")";
00690
00691 i_EdgeCount++;
00692 }
00693 else
00694 {
00695 cout<<STEP_UP(v2i_VertexAdjacency[i][j])<<", ";
00696
00697 i_EdgeCount++;
00698 }
00699 }
00700
00701 cout<<endl;
00702 }
00703
00704 cout<<endl;
00705 cout<<"[Vertices = "<<i_VertexCount<<"; Edges = "<<i_EdgeCount/2<<"]"<<endl;
00706 cout<<endl;
00707
00708 #endif
00709
00710 return(_TRUE);
00711 }
00712
00713 int GraphInputOutput::ReadMeTiSAdjacencyGraph(string s_InputFile)
00714 {
00715 istringstream in2;
00716 int i, j;
00717
00718 int i_LineCount, i_TokenCount;
00719
00720 int i_Vertex;
00721
00722 int i_VertexCount, i_VertexDegree;
00723
00724 int i_EdgeCount;
00725
00726 int i_VertexWeights, i_EdgeWeights;
00727
00728 string _GAP(" ");
00729
00730 string s_InputLine;
00731
00732 ifstream InputStream;
00733
00734 vector<string> vs_InputTokens;
00735
00736 vector<double> vi_EdgeWeights;
00737 vector<double> vi_VertexWeights;
00738
00739 vector< vector<int> > v2i_VertexAdjacency;
00740
00741 vector< vector<double> > v2i_VertexWeights;
00742
00743 Clear();
00744
00745 m_s_InputFile = s_InputFile;
00746
00747 InputStream.open(m_s_InputFile.c_str());
00748 if(!InputStream) {
00749 cout<<m_s_InputFile<<" not Found!"<<endl;
00750 return (_FALSE);
00751 }
00752 else cout<<"Found file "<<m_s_InputFile<<endl;
00753
00754 vi_EdgeWeights.clear();
00755
00756 v2i_VertexWeights.clear();
00757
00758 i_VertexWeights = i_EdgeWeights = _FALSE;
00759
00760 i_LineCount = _FALSE;
00761
00762 do
00763 {
00764 getline(InputStream, s_InputLine);
00765
00766 if(!InputStream)
00767 {
00768 break;
00769 }
00770
00771 if(s_InputLine[0] == '%')
00772 {
00773 continue;
00774 }
00775
00776 if(i_LineCount == _FALSE)
00777 {
00778 in2.clear();
00779 in2.str(s_InputLine);
00780 in2>>i_VertexCount>>i_EdgeCount;
00781
00782 i_VertexWeights = _FALSE;
00783 i_EdgeWeights = _FALSE;
00784
00785 if(!in2.eof())
00786 {
00787 int Weights;
00788 in2>>Weights;
00789 if(Weights == 1)
00790 {
00791 i_EdgeWeights = _TRUE;
00792 }
00793 else
00794 if(Weights == 10)
00795 {
00796 i_VertexWeights = _TRUE;
00797 }
00798 else
00799 if(Weights == 11)
00800 {
00801 i_EdgeWeights = _TRUE;
00802 i_VertexWeights = _TRUE;
00803 }
00804 }
00805
00806 if(!in2.eof())
00807 {
00808 in2>>i_VertexWeights ;
00809 }
00810
00811 v2i_VertexAdjacency.clear();
00812 v2i_VertexAdjacency.resize((unsigned) i_VertexCount);
00813
00814 i_LineCount++;
00815
00816 }
00817 else
00818 {
00819 in2.clear();
00820
00821 int input_end= s_InputLine.size() - 1;
00822 if(input_end>=0) {
00823 while(s_InputLine[input_end] == ' ' || s_InputLine[input_end] == '\t') input_end--;
00824 }
00825 if(input_end<0) s_InputLine = "";
00826 else s_InputLine = s_InputLine.substr(0, input_end+1);
00827
00828 in2.str(s_InputLine);
00829 string tokens;
00830
00831 vs_InputTokens.clear();
00832
00833 while( !in2.eof() )
00834 {
00835 in2>>tokens;
00836 vs_InputTokens.push_back(tokens);
00837 }
00838
00839 i_TokenCount = (signed) vs_InputTokens.size();
00840
00841 vi_VertexWeights.clear();
00842
00843 for(i=0; i<i_VertexWeights; i++)
00844 {
00845 vi_VertexWeights.push_back(atoi(vs_InputTokens[i].c_str()));
00846 }
00847
00848 if(i_VertexWeights != _FALSE)
00849 {
00850 v2i_VertexWeights.push_back(vi_VertexWeights);
00851 }
00852
00853 if(i_EdgeWeights == _FALSE)
00854 {
00855 for(i=i_VertexWeights; i<i_TokenCount; i++)
00856 {
00857 if(vs_InputTokens[i] != "") {
00858 i_Vertex = STEP_DOWN(atoi(vs_InputTokens[i].c_str()));
00859
00860
00861
00862
00863
00864
00865 if(i_Vertex != STEP_DOWN(i_LineCount))
00866 {
00867 v2i_VertexAdjacency[STEP_DOWN(i_LineCount)].push_back(i_Vertex);
00868 }
00869 }
00870 }
00871 }
00872 else
00873 {
00874 for(i=i_VertexWeights; i<i_TokenCount; i=i+2)
00875 {
00876 i_Vertex = STEP_DOWN(atoi(vs_InputTokens[i].c_str()));
00877
00878 if(i_Vertex != STEP_DOWN(i_LineCount))
00879 {
00880 v2i_VertexAdjacency[STEP_DOWN(i_LineCount)].push_back(i_Vertex);
00881
00882 vi_EdgeWeights.push_back(STEP_DOWN(atof(vs_InputTokens[STEP_UP(i)].c_str())));
00883 }
00884 }
00885 }
00886
00887 i_LineCount++;
00888 }
00889
00890 }
00891 while(InputStream);
00892
00893 InputStream.close();
00894
00895 i_VertexCount = (signed) v2i_VertexAdjacency.size();
00896
00897 for(i=0; i<i_VertexCount; i++)
00898 {
00899 m_vi_Vertices.push_back((signed) m_vi_Edges.size());
00900
00901 i_VertexDegree = (signed) v2i_VertexAdjacency[i].size();
00902
00903 for(j=0; j<i_VertexDegree; j++)
00904 {
00905 m_vi_Edges.push_back(v2i_VertexAdjacency[i][j]);
00906 }
00907 }
00908
00909 m_vi_Vertices.push_back((signed) m_vi_Edges.size());
00910
00911 CalculateVertexDegrees();
00912
00913 #if DEBUG == 1259
00914
00915 cout<<endl;
00916 cout<<"DEBUG 1259 | Graph Coloring | Vertex Adjacency | "<<m_s_InputFile<<endl;
00917 cout<<endl;
00918
00919 i_EdgeCount = _FALSE;
00920
00921 for(i=0; i<i_VertexCount; i++)
00922 {
00923 cout<<"Vertex "<<STEP_UP(i)<<"\t"<<" : ";
00924
00925 i_VertexDegree = (signed) v2i_VertexAdjacency[i].size();
00926
00927 for(j=0; j<i_VertexDegree; j++)
00928 {
00929 if(j == STEP_DOWN(i_VertexDegree))
00930 {
00931 cout<<STEP_UP(v2i_VertexAdjacency[i][j])<<" ("<<i_VertexDegree<<")";
00932
00933 i_EdgeCount++;
00934 }
00935 else
00936 {
00937 cout<<STEP_UP(v2i_VertexAdjacency[i][j])<<", ";
00938
00939 i_EdgeCount++;
00940 }
00941 }
00942
00943 cout<<endl;
00944 }
00945
00946 cout<<endl;
00947 cout<<"[Vertices = "<<i_VertexCount<<"; Edges = "<<i_EdgeCount/2<<"]"<<endl;
00948 cout<<endl;
00949
00950 #endif
00951
00952 return(_TRUE);
00953
00954 }
00955
00956
00957
00958 int GraphInputOutput::ReadMeTiSAdjacencyGraph2(string s_InputFile)
00959 {
00960 int i, j;
00961
00962 int i_LineCount, i_TokenCount;
00963
00964 int i_Vertex;
00965
00966 int i_VertexCount, i_VertexDegree;
00967
00968 int i_EdgeCount;
00969
00970 int i_VertexWeights, i_EdgeWeights;
00971
00972 string _GAP(" ");
00973
00974 string s_InputLine;
00975
00976 ifstream InputStream;
00977
00978 vector<string> vs_InputTokens;
00979
00980 vector<double> vi_EdgeWeights;
00981 vector<double> vi_VertexWeights;
00982
00983 vector< vector<int> > v2i_VertexAdjacency;
00984
00985 vector< vector<double> > v2i_VertexWeights;
00986
00987 Clear();
00988
00989 m_s_InputFile = s_InputFile;
00990
00991 InputStream.open(m_s_InputFile.c_str());
00992 if(!InputStream) {
00993 cout<<m_s_InputFile<<" not Found!"<<endl;
00994 return (_FALSE);
00995 }
00996 else cout<<"Found file "<<m_s_InputFile<<endl;
00997
00998 vi_EdgeWeights.clear();
00999
01000 v2i_VertexWeights.clear();
01001
01002 i_VertexWeights = i_EdgeWeights = _FALSE;
01003
01004 i_LineCount = _FALSE;
01005
01006 do
01007 {
01008 getline(InputStream, s_InputLine);
01009
01010 if(!InputStream)
01011 {
01012 break;
01013 }
01014
01015 if(s_InputLine[0] == '%')
01016 {
01017 continue;
01018 }
01019
01020 if(i_LineCount == _FALSE)
01021 {
01022 StringTokenizer GapTokenizer(s_InputLine, _GAP);
01023
01024 vs_InputTokens.clear();
01025
01026 while(GapTokenizer.HasMoreTokens())
01027 {
01028 vs_InputTokens.push_back(GapTokenizer.GetNextToken());
01029 }
01030
01031 i_VertexCount = atoi(vs_InputTokens[0].c_str());
01032 i_EdgeCount = atoi(vs_InputTokens[1].c_str());
01033
01034 i_VertexWeights = _FALSE;
01035 i_EdgeWeights = _FALSE;
01036
01037 if(vs_InputTokens.size() > 2)
01038 {
01039 if(atoi(vs_InputTokens[2].c_str()) == 1)
01040 {
01041 i_EdgeWeights = _TRUE;
01042 }
01043 else
01044 if(atoi(vs_InputTokens[2].c_str()) == 10)
01045 {
01046 i_VertexWeights = _TRUE;
01047 }
01048 else
01049 if(atoi(vs_InputTokens[2].c_str()) == 11)
01050 {
01051 i_EdgeWeights = _TRUE;
01052 i_VertexWeights = _TRUE;
01053 }
01054 }
01055
01056 if(vs_InputTokens.size() > 3)
01057 {
01058 i_VertexWeights = atoi(vs_InputTokens[3].c_str());
01059 }
01060
01061 v2i_VertexAdjacency.clear();
01062 v2i_VertexAdjacency.resize((unsigned) i_VertexCount);
01063
01064 i_LineCount++;
01065
01066 }
01067 else
01068 {
01069 StringTokenizer GapTokenizer(s_InputLine, _GAP);
01070
01071 vs_InputTokens.clear();
01072
01073 while(GapTokenizer.HasMoreTokens())
01074 {
01075 vs_InputTokens.push_back(GapTokenizer.GetNextToken());
01076 }
01077
01078 i_TokenCount = (signed) vs_InputTokens.size();
01079
01080 vi_VertexWeights.clear();
01081
01082 for(i=0; i<i_VertexWeights; i++)
01083 {
01084 vi_VertexWeights.push_back(atoi(vs_InputTokens[i].c_str()));
01085 }
01086
01087 if(i_VertexWeights != _FALSE)
01088 {
01089 v2i_VertexWeights.push_back(vi_VertexWeights);
01090 }
01091
01092 if(i_EdgeWeights == _FALSE)
01093 {
01094 for(i=i_VertexWeights; i<i_TokenCount; i++)
01095 {
01096 i_Vertex = STEP_DOWN(atoi(vs_InputTokens[i].c_str()));
01097
01098 if(i_Vertex != STEP_DOWN(i_LineCount))
01099 {
01100 v2i_VertexAdjacency[STEP_DOWN(i_LineCount)].push_back(i_Vertex);
01101 }
01102 }
01103 }
01104 else
01105 {
01106 for(i=i_VertexWeights; i<i_TokenCount; i=i+2)
01107 {
01108 i_Vertex = STEP_DOWN(atoi(vs_InputTokens[i].c_str()));
01109
01110 if(i_Vertex != STEP_DOWN(i_LineCount))
01111 {
01112 v2i_VertexAdjacency[STEP_DOWN(i_LineCount)].push_back(i_Vertex);
01113
01114 vi_EdgeWeights.push_back(STEP_DOWN(atof(vs_InputTokens[STEP_UP(i)].c_str())));
01115 }
01116 }
01117 }
01118
01119 i_LineCount++;
01120 }
01121
01122 }
01123 while(InputStream);
01124
01125 InputStream.close();
01126
01127 i_VertexCount = (signed) v2i_VertexAdjacency.size();
01128
01129 for(i=0; i<i_VertexCount; i++)
01130 {
01131 m_vi_Vertices.push_back((signed) m_vi_Edges.size());
01132
01133 i_VertexDegree = (signed) v2i_VertexAdjacency[i].size();
01134
01135 for(j=0; j<i_VertexDegree; j++)
01136 {
01137 m_vi_Edges.push_back(v2i_VertexAdjacency[i][j]);
01138 }
01139 }
01140
01141 m_vi_Vertices.push_back((signed) m_vi_Edges.size());
01142
01143 CalculateVertexDegrees();
01144
01145 #if DEBUG == 1259
01146
01147 cout<<endl;
01148 cout<<"DEBUG 1259 | Graph Coloring | Vertex Adjacency | "<<m_s_InputFile<<endl;
01149 cout<<endl;
01150
01151 i_EdgeCount = _FALSE;
01152
01153 for(i=0; i<i_VertexCount; i++)
01154 {
01155 cout<<"Vertex "<<STEP_UP(i)<<"\t"<<" : ";
01156
01157 i_VertexDegree = (signed) v2i_VertexAdjacency[i].size();
01158
01159 for(j=0; j<i_VertexDegree; j++)
01160 {
01161 if(j == STEP_DOWN(i_VertexDegree))
01162 {
01163 cout<<STEP_UP(v2i_VertexAdjacency[i][j])<<" ("<<i_VertexDegree<<")";
01164
01165 i_EdgeCount++;
01166 }
01167 else
01168 {
01169 cout<<STEP_UP(v2i_VertexAdjacency[i][j])<<", ";
01170
01171 i_EdgeCount++;
01172 }
01173 }
01174
01175 cout<<endl;
01176 }
01177
01178 cout<<endl;
01179 cout<<"[Vertices = "<<i_VertexCount<<"; Edges = "<<i_EdgeCount/2<<"]"<<endl;
01180 cout<<endl;
01181
01182 #endif
01183
01184 return(_TRUE);
01185
01186 }
01187
01188
01189
01190 int GraphInputOutput::PrintGraph()
01191 {
01192 int i;
01193
01194 int i_VertexCount, i_EdgeCount;
01195
01196 i_VertexCount = (signed) m_vi_Vertices.size();
01197
01198 cout<<endl;
01199 cout<<"Graph Coloring | Vertex List | "<<m_s_InputFile<<endl;
01200 cout<<endl;
01201
01202 for(i=0; i<i_VertexCount; i++)
01203 {
01204 if(i == STEP_DOWN(i_VertexCount))
01205 {
01206 cout<<STEP_UP(m_vi_Vertices[i])<<" ("<<i_VertexCount<<")"<<endl;
01207 }
01208 else
01209 {
01210 cout<<STEP_UP(m_vi_Vertices[i])<<", ";
01211 }
01212 }
01213
01214 i_EdgeCount = (signed) m_vi_Edges.size();
01215
01216 cout<<endl;
01217 cout<<"Graph Coloring | Edge List | "<<m_s_InputFile<<endl;
01218 cout<<endl;
01219
01220 for(i=0; i<i_EdgeCount; i++)
01221 {
01222 if(i == STEP_DOWN(i_EdgeCount))
01223 {
01224 cout<<STEP_UP(m_vi_Edges[i])<<" ("<<i_EdgeCount<<")"<<endl;
01225 }
01226 else
01227 {
01228 cout<<STEP_UP(m_vi_Edges[i])<<", ";
01229 }
01230 }
01231
01232 if(m_vd_Values.size() > _FALSE)
01233 {
01234
01235 cout<<endl;
01236 cout<<"Graph Coloring | Nonzero List | "<<m_s_InputFile<<endl;
01237 cout<<endl;
01238
01239 for(i=0; i<i_EdgeCount; i++)
01240 {
01241 if(i == STEP_DOWN(i_EdgeCount))
01242 {
01243 cout<<m_vd_Values[i]<<" ("<<i_EdgeCount<<")"<<endl;
01244 }
01245 else
01246 {
01247 cout<<m_vd_Values[i]<<", ";
01248 }
01249 }
01250
01251 cout<<endl;
01252 cout<<"[Vertices = "<<STEP_DOWN(i_VertexCount)<<"; Edges = "<<i_EdgeCount/2<<"; Nonzeros = "<<i_EdgeCount/2<<"]"<<endl;
01253 cout<<endl;
01254 }
01255 else
01256 {
01257 cout<<endl;
01258 cout<<"[Vertices = "<<STEP_DOWN(i_VertexCount)<<"; Edges = "<<i_EdgeCount/2<<"]"<<endl;
01259 cout<<endl;
01260
01261 }
01262
01263 return(_TRUE);
01264 }
01265
01266
01267
01268 int GraphInputOutput::PrintGraphStructure()
01269 {
01270 int i;
01271
01272 int i_VertexCount, i_EdgeCount;
01273
01274 i_VertexCount = (signed) m_vi_Vertices.size();
01275
01276 cout<<endl;
01277 cout<<"Graph Coloring | Vertex List | "<<m_s_InputFile<<endl;
01278 cout<<endl;
01279
01280 for(i=0; i<i_VertexCount; i++)
01281 {
01282 if(i == STEP_DOWN(i_VertexCount))
01283 {
01284 cout<<STEP_UP(m_vi_Vertices[i])<<" ("<<i_VertexCount<<")"<<endl;
01285 }
01286 else
01287 {
01288 cout<<STEP_UP(m_vi_Vertices[i])<<", ";
01289 }
01290 }
01291
01292 i_EdgeCount = (signed) m_vi_Edges.size();
01293
01294 cout<<endl;
01295 cout<<"Graph Coloring | Edge List | "<<m_s_InputFile<<endl;
01296 cout<<endl;
01297
01298 for(i=0; i<i_EdgeCount; i++)
01299 {
01300 if(i == STEP_DOWN(i_EdgeCount))
01301 {
01302 cout<<STEP_UP(m_vi_Edges[i])<<" ("<<i_EdgeCount<<")"<<endl;
01303 }
01304 else
01305 {
01306 cout<<STEP_UP(m_vi_Edges[i])<<", ";
01307 }
01308 }
01309
01310 cout<<endl;
01311 cout<<"[Vertices = "<<STEP_DOWN(i_VertexCount)<<"; Edges = "<<i_EdgeCount/2<<"]"<<endl;
01312 cout<<endl;
01313
01314 return(_TRUE);
01315 }
01316
01317
01318
01319 int GraphInputOutput::PrintMatrix()
01320 {
01321 int i, j;
01322
01323 int i_VertexCount;
01324
01325 cout<<endl;
01326 cout<<"Graph Coloring | Matrix Elements | "<<m_s_InputFile<<endl;
01327 cout<<endl;
01328
01329 i_VertexCount = (signed) m_vi_Vertices.size();
01330
01331 for(i=0; i<i_VertexCount-1; i++)
01332 {
01333 for(j=m_vi_Vertices[i]; j<m_vi_Vertices[STEP_UP(i)]; j++)
01334 {
01335 cout<<"Element["<<STEP_UP(i)<<"]["<<STEP_UP(m_vi_Edges[j])<<"] = "<<m_vd_Values[j]<<endl;
01336 }
01337 }
01338
01339 cout<<endl;
01340
01341 return(_TRUE);
01342 }
01343
01344
01345
01346 int GraphInputOutput::PrintMatrix(vector<int> & vi_Vertices, vector<int> & vi_Edges, vector<double> & vd_Values)
01347 {
01348 int i, j;
01349
01350 int i_VertexCount;
01351
01352 cout<<endl;
01353 cout<<"Graph Coloring | Matrix Elements | "<<m_s_InputFile<<endl;
01354 cout<<endl;
01355 i_VertexCount = (signed) vi_Vertices.size();
01356
01357 for(i=0; i<i_VertexCount-1; i++)
01358 {
01359 for(j=vi_Vertices[i]; j<vi_Vertices[STEP_UP(i)]; j++)
01360 {
01361 cout<<"Element["<<STEP_UP(i)<<"]["<<STEP_UP(vi_Edges[j])<<"] = "<<vd_Values[j]<<endl;
01362 }
01363 }
01364
01365 cout<<endl;
01366
01367 return(_TRUE);
01368 }
01369
01370
01371
01372 void GraphInputOutput::PrintVertexDegrees()
01373 {
01374 cout<<endl;
01375 cout<<"Graph | "<<m_s_InputFile<<" | Maximum Vertex Degree | "<<m_i_MaximumVertexDegree<<endl;
01376 cout<<"Graph | "<<m_s_InputFile<<" | Minimum Vertex Degree | "<<m_i_MinimumVertexDegree<<endl;
01377 cout<<"Graph | "<<m_s_InputFile<<" | Average Vertex Degree | "<<m_d_AverageVertexDegree<<endl;
01378 cout<<endl;
01379
01380 return;
01381 }
01382
01383 int GraphInputOutput::BuildGraphFromRowCompressedFormat(unsigned int ** uip2_HessianSparsityPattern, int i_RowCount) {
01384 int i, j;
01385
01386 int i_ElementCount, i_PositionCount;
01387
01388 int i_HighestDegree;
01389
01390 #if DEBUG == 1
01391
01392 cout<<endl;
01393 cout<<"DEBUG | Graph Coloring | Sparsity Pattern"<<endl;
01394 cout<<endl;
01395
01396 for(i=0; i<i_RowCount; i++)
01397 {
01398 cout<<i<<"\t"<<" : ";
01399
01400 i_PositionCount = uip2_HessianSparsityPattern[i][0];
01401
01402 for(j=0; j<i_PositionCount; j++)
01403 {
01404 if(j == STEP_DOWN(i_PositionCount))
01405 {
01406 cout<<uip2_HessianSparsityPattern[i][STEP_UP(j)]<<" ("<<i_PositionCount<<")";
01407 }
01408 else
01409 {
01410 cout<<uip2_HessianSparsityPattern[i][STEP_UP(j)]<<", ";
01411 }
01412
01413 }
01414
01415 cout<<endl;
01416 }
01417
01418 cout<<endl;
01419
01420 #endif
01421
01422 m_vi_Vertices.clear();
01423 m_vi_Vertices.push_back(_FALSE);
01424
01425 m_vi_Edges.clear();
01426
01427 i_HighestDegree = _UNKNOWN;
01428
01429 for(i=0; i<i_RowCount; i++)
01430 {
01431 i_ElementCount = _FALSE;
01432
01433 i_PositionCount = uip2_HessianSparsityPattern[i][0];
01434
01435 if(i_HighestDegree < i_PositionCount)
01436 {
01437 i_HighestDegree = i_PositionCount;
01438 }
01439
01440 for(j=0; j<i_PositionCount; j++)
01441 {
01442 if((signed) uip2_HessianSparsityPattern[i][STEP_UP(j)] != i)
01443 {
01444 m_vi_Edges.push_back((signed) uip2_HessianSparsityPattern[i][STEP_UP(j)]);
01445
01446 i_ElementCount++;
01447 }
01448
01449 }
01450
01451 m_vi_Vertices.push_back(m_vi_Vertices.back() + i_ElementCount);
01452 }
01453
01454 #if DEBUG == 1
01455
01456 int i_VertexCount, i_EdgeCount;
01457
01458 cout<<endl;
01459 cout<<"DEBUG | Graph Coloring | Graph Format"<<endl;
01460 cout<<endl;
01461
01462 cout<<"Vertices"<<"\t"<<" : ";
01463
01464 i_VertexCount = (signed) m_vi_Vertices.size();
01465
01466 for(i=0; i<i_VertexCount; i++)
01467 {
01468 if(i == STEP_DOWN(i_VertexCount))
01469 {
01470 cout<<m_vi_Vertices[i]<<" ("<<i_VertexCount<<")";
01471 }
01472 else
01473 {
01474 cout<<m_vi_Vertices[i]<<", ";
01475 }
01476 }
01477
01478 cout<<endl;
01479
01480 cout<<"Edges"<<"\t"<<" : ";
01481
01482 i_EdgeCount = (signed) m_vi_Edges.size();
01483
01484 for(i=0; i<i_EdgeCount; i++)
01485 {
01486 if(i == STEP_DOWN(i_EdgeCount))
01487 {
01488 cout<<m_vi_Edges[i]<<" ("<<i_EdgeCount<<")";
01489 }
01490 else
01491 {
01492 cout<<m_vi_Edges[i]<<", ";
01493 }
01494 }
01495
01496 cout<<endl;
01497
01498 #endif
01499
01500 CalculateVertexDegrees();
01501
01502 return(i_HighestDegree);
01503 }
01504
01505 int GraphInputOutput::ReadAdjacencyGraph(string s_InputFile, string s_fileFormat)
01506 {
01507 if (s_fileFormat == "AUTO_DETECTED" || s_fileFormat == "") {
01508 File file(s_InputFile);
01509 string fileExtension = file.GetFileExtension();
01510 if (isHarwellBoeingFormat(fileExtension)) {
01511 cout<<"ReadHarwellBoeingAdjacencyGraph"<<endl;
01512 return ReadHarwellBoeingAdjacencyGraph(s_InputFile);
01513 }
01514 else if (isMeTiSFormat(fileExtension)) {
01515 cout<<"ReadMeTiSAdjacencyGraph"<<endl;
01516 return ReadMeTiSAdjacencyGraph(s_InputFile);
01517 }
01518 else if (isMatrixMarketFormat(fileExtension)) {
01519 cout<<"ReadMatrixMarketAdjacencyGraph"<<endl;
01520 return ReadMatrixMarketAdjacencyGraph(s_InputFile);
01521 }
01522 else {
01523 cout<<"unfamiliar extension \""<<fileExtension<<"\", use ReadMatrixMarketAdjacencyGraph"<<endl;
01524 return ReadMatrixMarketAdjacencyGraph(s_InputFile);
01525 }
01526 }
01527 else if (s_fileFormat == "MM") {
01528 cout<<"ReadMatrixMarketAdjacencyGraph"<<endl;
01529 return ReadMatrixMarketAdjacencyGraph(s_InputFile);
01530 }
01531 else if (s_fileFormat == "HB") {
01532 cout<<"ReadHarwellBoeingAdjacencyGraph"<<endl;
01533 return ReadHarwellBoeingAdjacencyGraph(s_InputFile);
01534 }
01535 else if (s_fileFormat == "MeTiS") {
01536 cout<<"ReadMeTiSAdjacencyGraph"<<endl;
01537 return ReadMeTiSAdjacencyGraph(s_InputFile);
01538 }
01539 else {
01540 cerr<<"GraphInputOutput::ReadAdjacencyGraph s_fileFormat is not recognized"<<endl;
01541 exit(1);
01542 }
01543
01544 return(_TRUE);
01545 }
01546
01547 }