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 void BipartiteGraphInputOutput::CalculateVertexDegrees()
00029 {
00030 int i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size());
00031
00032 int i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size());
00033
00034 int i_TotalLeftVertexDegree = _FALSE;
00035
00036 int i_TotalRightVertexDegree = _FALSE;
00037
00038 i_TotalLeftVertexDegree = i_TotalRightVertexDegree = m_vi_Edges.size()/2;
00039
00040 for(int i = 0; i < i_LeftVertexCount; i++)
00041 {
00042 int i_VertexDegree = m_vi_LeftVertices[i + 1] - m_vi_LeftVertices[i];
00043
00044 if(m_i_MaximumLeftVertexDegree < i_VertexDegree)
00045 {
00046 m_i_MaximumLeftVertexDegree = i_VertexDegree;
00047 }
00048
00049 if(m_i_MinimumLeftVertexDegree == _UNKNOWN)
00050 {
00051 m_i_MinimumLeftVertexDegree = i_VertexDegree;
00052 }
00053 else if(m_i_MinimumLeftVertexDegree > i_VertexDegree)
00054 {
00055 m_i_MinimumLeftVertexDegree = i_VertexDegree;
00056 }
00057 }
00058
00059 for(int i = 0; i < i_RightVertexCount; i++)
00060 {
00061 int i_VertexDegree = m_vi_RightVertices[i + 1] - m_vi_RightVertices[i];
00062
00063 if(m_i_MaximumRightVertexDegree < i_VertexDegree)
00064 {
00065 m_i_MaximumRightVertexDegree = i_VertexDegree;
00066 }
00067
00068 if(m_i_MinimumRightVertexDegree == _UNKNOWN)
00069 {
00070 m_i_MinimumRightVertexDegree = i_VertexDegree;
00071 }
00072 else if(m_i_MinimumRightVertexDegree > i_VertexDegree)
00073 {
00074 m_i_MinimumRightVertexDegree = i_VertexDegree;
00075 }
00076 }
00077
00078 m_i_MaximumVertexDegree = m_i_MaximumLeftVertexDegree>m_i_MaximumRightVertexDegree?m_i_MaximumLeftVertexDegree:m_i_MaximumRightVertexDegree;
00079 m_i_MinimumVertexDegree = m_i_MinimumLeftVertexDegree<m_i_MinimumRightVertexDegree?m_i_MinimumLeftVertexDegree:m_i_MinimumRightVertexDegree;
00080
00081 m_d_AverageLeftVertexDegree = (double)i_TotalLeftVertexDegree/i_LeftVertexCount;
00082 m_d_AverageRightVertexDegree = (double)i_TotalRightVertexDegree/i_RightVertexCount;
00083 m_d_AverageVertexDegree = (double)(i_TotalLeftVertexDegree + i_TotalRightVertexDegree)/(i_LeftVertexCount + i_RightVertexCount);
00084
00085 return;
00086
00087 }
00088
00089
00090 BipartiteGraphInputOutput::BipartiteGraphInputOutput()
00091 {
00092 Clear();
00093 }
00094
00095
00096 BipartiteGraphInputOutput::~BipartiteGraphInputOutput()
00097 {
00098 Clear();
00099 }
00100
00101
00102 void BipartiteGraphInputOutput::Initialize()
00103 {
00104
00105 }
00106
00107
00108 void BipartiteGraphInputOutput::Clear()
00109 {
00110 BipartiteGraphCore::Clear();
00111
00112 return;
00113 }
00114
00115
00116 int BipartiteGraphInputOutput::ReadMatrixMarketBipartiteGraph(string s_InputFile)
00117 {
00118 bool b_symmetric;
00119
00120 istringstream in2;
00121 int entry_counter = 0, num_of_entries = 0, nz_counter=0;
00122 bool value_not_specified = false;
00123 int i_LineCount = _TRUE;
00124
00125 int i, j;
00126
00127
00128 int i_RowCount, i_ColumnCount;
00129
00130 int i_LeftVertex, i_RightVertex, i_Value;
00131
00132 int i_LeftVertexCount, i_RightVertexCount;
00133
00134 int i_VertexDegree;
00135
00136 int i_EdgeCount;
00137
00138 string _GAP(" ");
00139
00140 string s_InputLine;
00141
00142 ifstream InputStream;
00143
00144 vector<string> vs_InputTokens;
00145
00146 vector< vector<int> > v2i_LeftVertexAdjacency, v2i_RightVertexAdjacency;
00147
00148 Clear();
00149
00150 i_EdgeCount = _FALSE;
00151
00152 i_LeftVertexCount = i_RightVertexCount = _FALSE;
00153
00154 m_s_InputFile = s_InputFile;
00155
00156
00157
00158 MM_typecode matcode;
00159 FILE *f;
00160 if ((f = fopen(m_s_InputFile.c_str(), "r")) == NULL) {
00161 cout<<m_s_InputFile<<" not Found!"<<endl;
00162 exit(1);
00163 }
00164 else cout<<"Found file "<<m_s_InputFile<<endl;
00165
00166 if (mm_read_banner(f, &matcode) != 0)
00167 {
00168 printf("Could not process Matrix Market banner.\n");
00169 exit(1);
00170 }
00171
00172 if(mm_is_symmetric(matcode)) {
00173 b_symmetric = true;
00174 }
00175 else b_symmetric = false;
00176
00177
00178 char * result = mm_typecode_to_str(matcode);
00179 printf("Graph of Market Market type: [%s]\n", result);
00180 free(result);
00181 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) ) ) ) {
00182 printf("Sorry, this application does not support this type.");
00183 exit(1);
00184 }
00185
00186 fclose(f);
00187
00188
00189
00190 InputStream.open(m_s_InputFile.c_str());
00191
00192 if(!InputStream)
00193 {
00194 cout<<"File "<<m_s_InputFile<<" Not Found"<<endl;
00195 return _FALSE;
00196 }
00197 else
00198 {
00199
00200 }
00201
00202 do
00203 {
00204 getline(InputStream, s_InputLine);
00205
00206 if(!InputStream)
00207 {
00208 break;
00209 }
00210
00211 if(s_InputLine=="")
00212 {
00213 break;
00214 }
00215
00216 if(s_InputLine[0]=='%')
00217 {
00218 continue;
00219 }
00220
00221 if(i_LineCount == _TRUE)
00222 {
00223 in2.clear();
00224 in2.str(s_InputLine);
00225 in2>>i_RowCount>>i_ColumnCount>>num_of_entries;
00226 i_EdgeCount = num_of_entries;
00227
00228 i_LeftVertexCount = i_RowCount;
00229 i_RightVertexCount = i_ColumnCount;
00230
00231
00232 v2i_LeftVertexAdjacency.clear();
00233 v2i_LeftVertexAdjacency.resize((unsigned) i_LeftVertexCount);
00234
00235 v2i_RightVertexAdjacency.clear();
00236 v2i_RightVertexAdjacency.resize((unsigned) i_RightVertexCount);
00237
00238 }
00239
00240 if((i_LineCount > _TRUE) && (i_LineCount <= STEP_UP(i_EdgeCount)))
00241 {
00242
00243 in2.clear();
00244 in2.str(s_InputLine);
00245 i_Value =-999999999;
00246 value_not_specified=false;
00247 in2>>i_LeftVertex>>i_RightVertex>>i_Value;
00248 entry_counter++;
00249 if(i_Value == -999999999 && in2.eof()) {
00250
00251 value_not_specified = true;
00252 }
00253 else if (i_Value == 0) {
00254 continue;
00255 }
00256
00257
00258
00259 v2i_LeftVertexAdjacency[STEP_DOWN(i_LeftVertex)].push_back(STEP_DOWN(i_RightVertex));
00260 v2i_RightVertexAdjacency[STEP_DOWN(i_RightVertex)].push_back(STEP_DOWN(i_LeftVertex));
00261 nz_counter++;
00262
00263 if(b_symmetric && (i_RightVertex != i_LeftVertex)) {
00264
00265 v2i_LeftVertexAdjacency[STEP_DOWN(i_RightVertex)].push_back(STEP_DOWN(i_LeftVertex));
00266 v2i_RightVertexAdjacency[STEP_DOWN(i_LeftVertex)].push_back(STEP_DOWN(i_RightVertex));
00267 nz_counter++;
00268 }
00269 }
00270
00271 i_LineCount++;
00272
00273 }
00274 while(InputStream);
00275
00276 InputStream.close();
00277
00278 if(entry_counter < num_of_entries) {
00279 cerr<<"* WARNING: BipartiteGraphInputOutput::ReadMatrixMarketBipartiteGraph()"<<endl;
00280 cerr<<"*\t entry_counter<num_of_entries. Wrong input format. Can't process."<<endl;
00281 cerr<<"\t # entries so far: "<<entry_counter<<"/"<<num_of_entries<<endl;
00282 exit(-1);
00283 }
00284
00285 for(i=0; i<i_LeftVertexCount; i++)
00286 {
00287 m_vi_LeftVertices.push_back((signed) m_vi_Edges.size());
00288
00289 i_VertexDegree = (signed) v2i_LeftVertexAdjacency[i].size();
00290
00291 for(j=0; j<i_VertexDegree; j++)
00292 {
00293 m_vi_Edges.push_back(v2i_LeftVertexAdjacency[i][j]);
00294 }
00295 }
00296
00297 m_vi_LeftVertices.push_back((signed) m_vi_Edges.size());
00298
00299 for(i=0; i<i_RightVertexCount; i++)
00300 {
00301 m_vi_RightVertices.push_back((signed) m_vi_Edges.size());
00302
00303 i_VertexDegree = (signed) v2i_RightVertexAdjacency[i].size();
00304
00305 for(j=0; j<i_VertexDegree; j++)
00306 {
00307 m_vi_Edges.push_back(v2i_RightVertexAdjacency[i][j]);
00308 }
00309 }
00310
00311 m_vi_RightVertices.push_back((signed) m_vi_Edges.size());
00312
00313 CalculateVertexDegrees();
00314
00315
00316 #if DEBUG == 2255 || DEBUG == 3255
00317
00318 int k;
00319
00320 cout<<endl;
00321 cout<<"DEBUG 2255;3255 | Graph Coloring | Left Vertex Adjacency | "<<m_s_InputFile<<endl;
00322 cout<<endl;
00323
00324 for(i=0; i<i_LeftVertexCount; i++)
00325 {
00326 cout<<STEP_UP(i)<<"\t"<<" : ";
00327
00328 i_VertexDegree = mvi_LeftVertices[STEP_UP(i)] - mvi_LeftVertices[i];
00329
00330 k = _FALSE;
00331
00332 for(j=mvi_LeftVertices[i]; j<mvi_LeftVertices[STEP_UP(i)]; j++)
00333 {
00334 if(k == STEP_DOWN(i_VertexDegree))
00335 {
00336 cout<<STEP_UP(m_vi_Edges[j])<<" ("<<i_VertexDegree<<") ";
00337 }
00338 else
00339 {
00340 cout<<STEP_UP(m_vi_Edges[j])<<", ";
00341 }
00342
00343 k++;
00344 }
00345
00346 cout<<endl;
00347 }
00348
00349 cout<<endl;
00350 cout<<"DEBUG 2255;3255 | Graph Coloring | Right Vertex Adjacency | "<<m_s_InputFile<<endl;
00351 cout<<endl;
00352
00353 for(i=0; i<i_RightVertexCount; i++)
00354 {
00355 cout<<STEP_UP(i)<<"\t"<<" : ";
00356
00357 i_VertexDegree = mvi_RightVertices[STEP_UP(i)] - mvi_RightVertices[i];
00358
00359 k = _FALSE;
00360
00361 for(j=mvi_RightVertices[i]; j<mvi_RightVertices[STEP_UP(i)]; j++)
00362 {
00363 if(k == STEP_DOWN(i_VertexDegree))
00364 {
00365 cout<<STEP_UP(m_vi_Edges[j])<<" ("<<i_VertexDegree<<") ";
00366 }
00367 else
00368 {
00369 cout<<STEP_UP(m_vi_Edges[j])<<", ";
00370 }
00371
00372 k++;
00373 }
00374
00375 cout<<endl;
00376 }
00377
00378 cout<<endl;
00379 cout<<"[Left Vertices = "<<i_LeftVertexCount<<"; Right Vertices = "<<i_RightVertexCount<<"; Edges = "<<i_EdgeCount/2<<"]"<<endl;
00380 cout<<endl;
00381
00382 #endif
00383
00384 return(_TRUE);
00385 }
00386
00387
00388 int BipartiteGraphInputOutput::ReadMeTiSBipartiteGraph(string s_InputFile)
00389 {
00390 Clear();
00391
00392 m_s_InputFile=s_InputFile;
00393 ifstream InputStream (m_s_InputFile.c_str());
00394
00395 if(!InputStream)
00396 {
00397 cout<<"File "<<m_s_InputFile<<" Not Found"<<endl;
00398 return _FALSE;
00399 }
00400 else
00401 {
00402 cout<<"Found File "<<m_s_InputFile<<endl;
00403 }
00404
00405
00406 int rowCounter=0, row=0, edges=0, num=0, numCount=0;
00407 istringstream in2;
00408 string line="";
00409 map<int,vector<int> > colList;
00410
00411 getline(InputStream,line);
00412 rowCounter++;
00413 in2.str(line);
00414 in2>>row>>edges;
00415 m_vi_LeftVertices.push_back(m_vi_Edges.size());
00416
00417 while(!InputStream.eof())
00418 {
00419 getline(InputStream,line);
00420 if(line!="")
00421 {
00422
00423 in2.clear();
00424 in2.str(line);
00425 while(in2>>num)
00426 {
00427 num--;
00428 m_vi_Edges.push_back(num);
00429 colList[num].push_back(rowCounter-1);
00430 numCount++;
00431
00432
00433 }
00434 }
00435 rowCounter++;
00436 m_vi_LeftVertices.push_back(m_vi_Edges.size());
00437 }
00438 rowCounter--;
00439 m_vi_LeftVertices.pop_back();
00440 if(rowCounter!=row+1 || edges*2!=numCount)
00441 {
00442 cout<<"Read fail: rowCounter!=row+1 || edges*2!=numCount"<<endl;
00443 cout<<"Read fail: "<<rowCounter<<"!="<<row+1<<" || "<<edges*2<<"!="<<numCount<<endl;
00444 return _FALSE;
00445 }
00446
00447
00448 m_vi_RightVertices.push_back(m_vi_Edges.size());
00449 for(int i=0;i<row; i++) {
00450 m_vi_Edges.insert(m_vi_Edges.end(),colList[i].begin(),colList[i].end());
00451 m_vi_RightVertices.push_back(m_vi_Edges.size());
00452 }
00453
00454
00455
00456
00457
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467 CalculateVertexDegrees();
00468
00469 return(_TRUE);
00470 }
00471
00472
00473 int BipartiteGraphInputOutput::ReadHarwellBoeingBipartiteGraph(string s_InputFile)
00474 {
00475 char sz_Line [256];
00476 int i_Dummy, i_RHSCRD, i_Input;
00477 int i_Rows, i_Columns, i_NZ;
00478 int i, j, n;
00479 int i_RowCount;
00480 ifstream InputStream;
00481 vector<int> vi_Vertex;
00482 vector<int> vi_Degree, vi_RowPointer;
00483
00484 Clear();
00485
00486 m_s_InputFile = s_InputFile;
00487
00488 InputStream.open ( m_s_InputFile.c_str () );
00489
00490
00491 if(!InputStream)
00492 {
00493 cout<<"File "<<m_s_InputFile<<" Not Found"<<endl;
00494 return _FALSE;
00495 }
00496 else
00497 {
00498 cout<<"Found File "<<m_s_InputFile<<endl;
00499 }
00500
00501
00502
00503
00504 InputStream.getline ( sz_Line, 255 );
00505
00506
00507 InputStream >> i_Dummy >> i_Dummy >> i_Dummy >> i_Dummy >> i_RHSCRD;
00508 InputStream.getline ( sz_Line, 255 );
00509
00510
00511
00512
00513
00514 string format;
00515 InputStream >> format >> i_Rows >> i_Columns >> i_NZ;
00516 InputStream.getline ( sz_Line, 255 );
00517
00518
00519 InputStream.getline ( sz_Line, 255 );
00520
00521
00522 if ( i_RHSCRD > 0 )
00523 {
00524
00525 InputStream.getline ( sz_Line, 255 );
00526 }
00527
00528
00529
00530 n = i_Rows + i_Columns;
00531
00532
00533 m_vi_LeftVertices.resize ( i_Rows+1, 0 );
00534 m_vi_RightVertices.resize ( i_Columns+1, 0 );
00535 m_vi_Edges.resize ( 2 * i_NZ, 0 );
00536 vi_Degree.resize ( n, 0 );
00537 vi_RowPointer.resize ( i_Rows, 0 );
00538 vi_Vertex.resize ( n + 1, 0 );
00539
00540
00541 InputStream >> i_Dummy;
00542 for ( i=1; i<=i_Columns; i++ )
00543 {
00544 InputStream >> i_Input;
00545 vi_Vertex [i] = i_Input - 1;
00546 vi_Degree [i-1] = vi_Vertex [i] - vi_Vertex [i-1];
00547 }
00548 for ( i=0; i<i_NZ; i++ )
00549 {
00550 InputStream >> i_Input;
00551 m_vi_Edges [i] = i_Columns + i_Input - 1;
00552 ++vi_RowPointer [i_Input - 1];
00553 ++vi_Degree [i_Columns + i_Input - 1];
00554 }
00555
00556 InputStream.close ();
00557
00558 i_RowCount = i_NZ;
00559 for ( i=1; i<=i_Rows; i++ )
00560 {
00561 i_RowCount += vi_RowPointer [i-1];
00562 vi_Vertex [i + i_Columns] = i_RowCount;
00563 }
00564 for ( i=0; i<i_Columns; i++ )
00565 {
00566 for ( j=vi_Vertex [i]; j<vi_Vertex [i+1]; j++ )
00567 {
00568 if ( vi_RowPointer [m_vi_Edges [j] - i_Columns] > 0 )
00569 {
00570 --vi_RowPointer [m_vi_Edges [j] - i_Columns];
00571 m_vi_Edges [vi_Vertex [m_vi_Edges [j]] + vi_RowPointer [m_vi_Edges [j] - i_Columns]] = i;
00572 }
00573 }
00574 }
00575
00576
00577 for ( i=0; i<i_Columns; i++ )
00578 {
00579 m_vi_RightVertices [i] = vi_Vertex [i];
00580 }
00581
00582 m_vi_RightVertices [i_Columns] = i_NZ;
00583
00584 for ( i=0; i<i_Rows; i++ )
00585 {
00586 m_vi_LeftVertices [i] = vi_Vertex [i+i_Columns];
00587 }
00588
00589 m_vi_LeftVertices [i_Rows] = 2*i_NZ;
00590
00591 for ( i=0; i<i_NZ; i++ )
00592 {
00593 m_vi_Edges [i] = m_vi_Edges [i] - i_Columns;
00594 }
00595
00596 CalculateVertexDegrees();
00597
00598 return(_TRUE);
00599 }
00600
00601
00602
00603
00604 int BipartiteGraphInputOutput::ReadGenericMatrixBipartiteGraph(string s_InputFile)
00605 {
00606 Clear();
00607
00608 m_s_InputFile=s_InputFile;
00609
00610
00611 int rowCounter=0, colCounter=0, row=0, col=0, tempNum=0;
00612 istringstream in2;
00613 string line="";
00614
00615 map< int,vector<int> > colList;
00616
00617 ifstream InputStream (m_s_InputFile.c_str());
00618 if(!InputStream)
00619 {
00620 cout<<"Not Found File "<<m_s_InputFile<<endl;
00621 }
00622 else
00623 {
00624 cout<<"Found File "<<m_s_InputFile<<endl;
00625 }
00626
00627
00628 string sRow="", sCol="";
00629 int tempCounter=s_InputFile.size()-1;
00630 bool getRow=0, firstTime=1;
00631
00632 for(; tempCounter>-1;tempCounter--)
00633 {
00634 if(s_InputFile[tempCounter]=='\\') {tempCounter=0; continue;}
00635 if(getRow)
00636 {
00637 if(s_InputFile[tempCounter]<'0'||s_InputFile[tempCounter]>'9')
00638 {
00639 if(firstTime) continue;
00640 else break;
00641 }
00642 else firstTime=0;
00643 sRow=s_InputFile[tempCounter]+sRow;
00644 }
00645 else
00646 {
00647
00648 if(s_InputFile[tempCounter]<'0'||s_InputFile[tempCounter]>'9')
00649 {
00650 if(firstTime) continue;
00651 else {firstTime=1;getRow=1; continue;}
00652 }
00653 else firstTime=0;
00654 sCol=s_InputFile[tempCounter]+sCol;
00655 }
00656 }
00657 if (tempCounter==-1)
00658 {
00659 cout<<"Input file\""<<s_InputFile<<"\" has a wrong name format"<<endl;
00660 return _FALSE;
00661 }
00662 in2.clear();in2.str(sRow);in2>>row;
00663 in2.clear();in2.str(sCol);in2>>col;
00664 cout<<"Matrix: "<<row<<" x "<<col<<endl;
00665
00666
00667 m_vi_LeftVertices.push_back(m_vi_Edges.size());
00668 for(;rowCounter<row;rowCounter++)
00669 {
00670 colCounter=0;
00671 getline(InputStream,line);
00672 if(line=="") break;
00673 in2.clear(); in2.str(line);
00674 while(in2>>tempNum)
00675 {
00676 if(tempNum)
00677 {
00678 m_vi_Edges.push_back(colCounter);
00679 colList[colCounter].push_back(rowCounter);
00680 }
00681 colCounter++;
00682 }
00683 m_vi_LeftVertices.push_back(m_vi_Edges.size());
00684 if (colCounter!=col)
00685 {
00686 cerr<<"WARNING: BipartiteGraphInputOutput::ReadGenericMatrixBipartiteGraph()"<<endl;
00687 cerr<<"Input file\""<<s_InputFile<<"\" has a wrong format. The number of entries in 1 column < # of columns"<<endl;
00688 return _FALSE;
00689 }
00690 }
00691 if (rowCounter!=row)
00692 {
00693 cerr<<"WARNING: BipartiteGraphInputOutput::ReadGenericMatrixBipartiteGraph()"<<endl;
00694 cout<<"Input file\""<<s_InputFile<<"\" has a wrong format. The number of rows is less than what it suppose to be"<<endl;
00695 return _FALSE;
00696 }
00697
00698 m_vi_RightVertices.push_back(m_vi_Edges.size());
00699 for(int i=0;i<col; i++) {
00700 m_vi_Edges.insert(m_vi_Edges.end(),colList[i].begin(),colList[i].end());
00701 m_vi_RightVertices.push_back(m_vi_Edges.size());
00702 }
00703
00704 CalculateVertexDegrees();
00705
00706 return (_TRUE);
00707 }
00708
00709
00710 int BipartiteGraphInputOutput::ReadGenericSquareMatrixBipartiteGraph(string s_InputFile)
00711 {
00712 Clear();
00713
00714 m_s_InputFile=s_InputFile;
00715
00716 int rowCounter=0, colCounter=0, counter=0, row=0, col=0;
00717 istringstream in2;
00718 string line="", templ="";
00719
00720 map< int,vector<int> > colList;
00721
00722 ifstream InputStream (m_s_InputFile.c_str());
00723 if(!InputStream)
00724 {
00725 cout<<"Not Found File "<<m_s_InputFile<<endl;
00726 }
00727 else
00728 {
00729 cout<<"Found File "<<m_s_InputFile<<endl;
00730 }
00731
00732
00733 string sRow="", sCol="";
00734 int tempCounter=s_InputFile.size()-1;
00735 bool getRow=0, firstTime=1;
00736
00737 for(; tempCounter>-1;tempCounter--)
00738 {
00739 if(s_InputFile[tempCounter]=='\\') {tempCounter=0; continue;}
00740 if(getRow)
00741 {
00742 if(s_InputFile[tempCounter]<'0'||s_InputFile[tempCounter]>'9')
00743 {
00744 if(firstTime) continue;
00745 else break;
00746 }
00747 else firstTime=0;
00748 sRow=s_InputFile[tempCounter]+sRow;
00749 }
00750 else
00751 {
00752
00753 if(s_InputFile[tempCounter]<'0'||s_InputFile[tempCounter]>'9')
00754 {
00755 if(firstTime) continue;
00756 else {firstTime=1;getRow=1; continue;}
00757 }
00758 else firstTime=0;
00759 sCol=s_InputFile[tempCounter]+sCol;
00760 }
00761 }
00762 if (tempCounter==-1)
00763 {
00764 cout<<"Input file\""<<s_InputFile<<"\" has a wrong name format"<<endl;
00765 return _FALSE;
00766 }
00767 in2.clear();in2.str(sRow);in2>>row;
00768 in2.clear();in2.str(sCol);in2>>col;
00769 if(row>col) row=col; else col=row;
00770 cout<<"Matrix: "<<row<<" x "<<col<<endl;
00771
00772
00773 while(!InputStream.eof())
00774 {
00775 getline(InputStream,templ);
00776 line+=templ;
00777 }
00778
00779
00780 m_vi_LeftVertices.push_back(m_vi_Edges.size());
00781 counter=0;
00782 for(;rowCounter<row;rowCounter++)
00783 {
00784 for(colCounter=0;colCounter<row;colCounter++)
00785 {
00786 if(line[counter]=='1')
00787 {
00788 m_vi_Edges.push_back(colCounter);
00789 colList[colCounter].push_back(rowCounter);
00790 }
00791 counter++;
00792 }
00793 m_vi_LeftVertices.push_back(m_vi_Edges.size());
00794 }
00795
00796
00797 m_vi_RightVertices.push_back(m_vi_Edges.size());
00798 for(int i=0;i<col; i++) {
00799 m_vi_Edges.insert(m_vi_Edges.end(),colList[i].begin(),colList[i].end());
00800 m_vi_RightVertices.push_back(m_vi_Edges.size());
00801 }
00802
00803 CalculateVertexDegrees();
00804
00805 return (_TRUE);
00806 }
00807
00808
00809 void BipartiteGraphInputOutput::PrintBipartiteGraph()
00810 {
00811 int i, j, k;
00812
00813 int i_LeftVertexCount, i_RightVertexCount;
00814
00815 int i_EdgeCount;
00816
00817 int i_VertexDegree;
00818
00819 i_LeftVertexCount = STEP_DOWN((signed) m_vi_LeftVertices.size());
00820 i_RightVertexCount = STEP_DOWN((signed) m_vi_RightVertices.size());
00821
00822 i_EdgeCount = (signed) m_vi_Edges.size();
00823
00824 cout<<endl;
00825 cout<<"Bipartite Graph | Left Vertex Adjacency | "<<m_s_InputFile<<endl;
00826 cout<<endl;
00827
00828 for(i=0; i<i_LeftVertexCount; i++)
00829 {
00830 cout<<STEP_UP(i)<<"\t"<<" : ";
00831
00832 i_VertexDegree = m_vi_LeftVertices[STEP_UP(i)] - m_vi_LeftVertices[i];
00833
00834 k = _FALSE;
00835
00836 for(j=m_vi_LeftVertices[i]; j<m_vi_LeftVertices[STEP_UP(i)]; j++)
00837 {
00838 if(k == STEP_DOWN(i_VertexDegree))
00839 {
00840 cout<<STEP_UP(m_vi_Edges[j])<<" ("<<i_VertexDegree<<") ";
00841 }
00842 else
00843 {
00844 cout<<STEP_UP(m_vi_Edges[j])<<", ";
00845 }
00846
00847 k++;
00848 }
00849
00850 cout<<endl;
00851 }
00852
00853 cout<<endl;
00854 cout<<"Bipartite Graph | Right Vertex Adjacency | "<<m_s_InputFile<<endl;
00855 cout<<endl;
00856
00857 for(i=0; i<i_RightVertexCount; i++)
00858 {
00859 cout<<STEP_UP(i)<<"\t"<<" : ";
00860
00861 i_VertexDegree = m_vi_RightVertices[STEP_UP(i)] - m_vi_RightVertices[i];
00862
00863 k = _FALSE;
00864
00865 for(j=m_vi_RightVertices[i]; j<m_vi_RightVertices[STEP_UP(i)]; j++)
00866 {
00867 if(k == STEP_DOWN(i_VertexDegree))
00868 {
00869 cout<<STEP_UP(m_vi_Edges[j])<<" ("<<i_VertexDegree<<") ";
00870 }
00871 else
00872 {
00873 cout<<STEP_UP(m_vi_Edges[j])<<", ";
00874 }
00875
00876 k++;
00877 }
00878
00879 cout<<endl;
00880 }
00881
00882 cout<<endl;
00883 cout<<"[Left Vertices = "<<i_LeftVertexCount<<"; Right Vertices = "<<i_RightVertexCount<<"; Edges = "<<i_EdgeCount/2<<"]"<<endl;
00884 cout<<endl;
00885
00886 return;
00887 }
00888
00889
00890 void BipartiteGraphInputOutput::PrintVertexDegrees()
00891 {
00892 cout<<endl;
00893 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Maximum Row Vertex Degree | "<<m_i_MaximumLeftVertexDegree<<endl;
00894 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Maximum Column Vertex Degree | "<<m_i_MaximumRightVertexDegree<<endl;
00895 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Maximum Vertex Degree | "<<m_i_MaximumVertexDegree<<endl;
00896 cout<<endl;
00897 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Minimum Row Vertex Degree | "<<m_i_MinimumLeftVertexDegree<<endl;
00898 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Minimum Column Vertex Degree | "<<m_i_MinimumRightVertexDegree<<endl;
00899 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Minimum Vertex Degree | "<<m_i_MinimumVertexDegree<<endl;
00900 cout<<endl;
00901 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Average Row Vertex Degree | "<<m_d_AverageLeftVertexDegree<<endl;
00902 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Average Column Vertex Degree | "<<m_d_AverageRightVertexDegree<<endl;
00903 cout<<"Bipartite Graph | "<<m_s_InputFile<<" | Average Vertex Degree | "<<m_d_AverageVertexDegree<<endl;
00904 cout<<endl;
00905
00906 return;
00907 }
00908
00909 int BipartiteGraphInputOutput::BuildBPGraphFromRowCompressedFormat(unsigned int ** uip2_JacobianSparsityPattern, int i_RowCount, int i_ColumnCount) {
00910 return RowCompressedFormat2BipartiteGraph(uip2_JacobianSparsityPattern, i_RowCount, i_ColumnCount);
00911 }
00912
00913 int BipartiteGraphInputOutput::RowCompressedFormat2BipartiteGraph(unsigned int ** uip2_JacobianSparsityPattern, int i_RowCount, int i_ColumnCount) {
00914
00915
00916 int i;
00917 unsigned int j;
00918 map< int,vector<int> > colList;
00919
00920 m_vi_LeftVertices.clear();
00921 m_vi_RightVertices.clear();
00922 m_vi_Edges.clear();
00923 m_vi_LeftVertices.push_back(m_vi_Edges.size());
00924
00925 for(i=0; i < i_RowCount; i++) {
00926 for(j=1; j <= uip2_JacobianSparsityPattern[i][0]; j++) {
00927 m_vi_Edges.push_back(uip2_JacobianSparsityPattern[i][j]);
00928 colList[ uip2_JacobianSparsityPattern[i][j] ].push_back(i);
00929 }
00930 m_vi_LeftVertices.push_back(m_vi_Edges.size());
00931 }
00932
00933
00934 map< int,vector<int> >::iterator curr;
00935 m_vi_RightVertices.push_back(m_vi_Edges.size());
00936 for(int i=0; i < i_ColumnCount; i++) {
00937 curr = colList.find(i);
00938 if(curr !=colList.end()) {
00939 m_vi_Edges.insert(m_vi_Edges.end(),curr->second.begin(),curr->second.end());
00940 }
00941 m_vi_RightVertices.push_back(m_vi_Edges.size());
00942 }
00943
00944 CalculateVertexDegrees();
00945
00946
00947
00948
00949 return _TRUE;
00950 }
00951
00952 int BipartiteGraphInputOutput::BipartiteGraph2RowCompressedFormat(unsigned int *** uip3_JacobianSparsityPattern, unsigned int * uip1_RowCount, unsigned int * uip1_ColumnCount) {
00953
00954 unsigned int i = 0;
00955 unsigned int j = 0;
00956 unsigned int numOfNonZeros = 0;
00957 int offset = 0;
00958
00959 unsigned int i_RowCount = GetRowVertexCount();
00960 (*uip1_RowCount) = i_RowCount;
00961 (*uip1_ColumnCount) = GetColumnVertexCount();
00962
00963
00964 (*uip3_JacobianSparsityPattern) = new unsigned int*[GetRowVertexCount()];
00965 for(i=0; i < i_RowCount; i++) {
00966 numOfNonZeros = m_vi_LeftVertices[i + 1] - m_vi_LeftVertices[i];
00967 (*uip3_JacobianSparsityPattern)[i] = new unsigned int[numOfNonZeros + 1];
00968 (*uip3_JacobianSparsityPattern)[i][0] = numOfNonZeros;
00969
00970
00971 offset = m_vi_LeftVertices[i] - 1;
00972 for(j=1; j <= numOfNonZeros; j++) {
00973 (*uip3_JacobianSparsityPattern)[i][j] = m_vi_Edges[offset + j];
00974 }
00975 }
00976
00977 return _TRUE;
00978 }
00979
00980 int BipartiteGraphInputOutput::ReadBipartiteGraph(string s_InputFile, string s_fileFormat) {
00981 if (s_fileFormat == "AUTO_DETECTED" || s_fileFormat == "") {
00982 File file(s_InputFile);
00983 string fileExtension = file.GetFileExtension();
00984 if (isHarwellBoeingFormat(fileExtension)) {
00985 cout<<"ReadHarwellBoeingBipartiteGraph"<<endl;
00986 ReadHarwellBoeingBipartiteGraph(s_InputFile);
00987 }
00988 else if (isMeTiSFormat(fileExtension)) {
00989 cout<<"ReadMeTiSBipartiteGraph"<<endl;
00990 ReadMeTiSBipartiteGraph(s_InputFile);
00991 }
00992 else if (fileExtension == "gen") {
00993 cout<<"ReadGenericMatrixBipartiteGraph"<<endl;
00994 ReadGenericMatrixBipartiteGraph(s_InputFile);
00995 }
00996 else if (fileExtension == "gens") {
00997 cout<<"ReadGenericSquareMatrixBipartiteGraph"<<endl;
00998 ReadGenericSquareMatrixBipartiteGraph(s_InputFile);
00999 }
01000 else if (isMatrixMarketFormat(fileExtension)) {
01001 cout<<"ReadMatrixMarketBipartiteGraph"<<endl;
01002 ReadMatrixMarketBipartiteGraph(s_InputFile);
01003 }
01004 else {
01005 cout<<"unfamiliar extension, use ReadMatrixMarketBipartiteGraph"<<endl;
01006 ReadMatrixMarketBipartiteGraph(s_InputFile);
01007 }
01008 }
01009 else if (s_fileFormat == "MM") {
01010 cout<<"ReadMatrixMarketBipartiteGraph"<<endl;
01011 ReadMatrixMarketBipartiteGraph(s_InputFile);
01012 }
01013 else if (s_fileFormat == "HB") {
01014 cout<<"ReadHarwellBoeingBipartiteGraph"<<endl;
01015 ReadHarwellBoeingBipartiteGraph(s_InputFile);
01016 }
01017 else if (s_fileFormat == "MeTiS") {
01018 cout<<"ReadMeTiSBipartiteGraph"<<endl;
01019 ReadMeTiSBipartiteGraph(s_InputFile);
01020 }
01021 else if (s_fileFormat == "GEN") {
01022 cout<<"ReadGenericMatrixBipartiteGraph"<<endl;
01023 ReadGenericMatrixBipartiteGraph(s_InputFile);
01024 }
01025 else if (s_fileFormat == "GENS") {
01026 cout<<"ReadGenericSquareMatrixBipartiteGraph"<<endl;
01027 ReadGenericSquareMatrixBipartiteGraph(s_InputFile);
01028 }
01029 else {
01030 cerr<<"BipartiteGraphInputOutput::ReadBipartiteGraph s_fileFormat is not recognized"<<endl;
01031 exit(1);
01032 }
01033
01034 return(_TRUE);
01035 }
01036 }