00001 00002 00003 #include "ColPackHeaders.h" 00004 #include "stat.h" 00005 00006 using namespace ColPack; 00007 using namespace std; 00008 00009 #ifndef TOP_DIR 00010 #define TOP_DIR "." 00011 #endif 00012 00013 // baseDir should point to the directory (folder) containing the input file 00014 string baseDir=TOP_DIR; 00015 00016 int f (string s_InputFile); 00017 00018 //* A SHORT VERSION 00019 int main(int argc, char ** argv) { 00020 00021 // s_InputFile = baseDir + <name of the input file> 00022 string s_InputFile; //path of the input file 00023 s_InputFile = "/home/nguyend/Desktop/Working_U/research_Assefaw/ColPack/Graphs/bcsstk01.mtx"; 00024 00025 // Step 1: Determine sparsity structure of the Jacobian. 00026 // This step is done by an AD tool. For the purpose of illustration here, we read the structure from a file, 00027 // and store the structure in a Compressed Row Format. 00028 unsigned int *** uip3_SparsityPattern = new unsigned int **; 00029 double*** dp3_Value = new double**; 00030 int rowCount, columnCount; 00031 ConvertMatrixMarketFormatToRowCompressedFormat(s_InputFile, uip3_SparsityPattern, dp3_Value,rowCount, columnCount); 00032 00033 cout<<"just for debugging purpose, display the 2 matrices: the matrix with SparsityPattern only and the matrix with Value"<<endl; 00034 cout<<fixed<<showpoint<<setprecision(2); //formatting output 00035 cout<<"(*uip3_SparsityPattern)"<<endl; 00036 displayCompressedRowMatrix((*uip3_SparsityPattern),rowCount); 00037 cout<<"(*dp3_Value)"<<endl; 00038 displayCompressedRowMatrix((*dp3_Value),rowCount); 00039 cout<<"Finish ConvertMatrixMarketFormatToRowCompressedFormat()"<<endl; 00040 Pause(); 00041 00042 //Step 2: Obtain the seed matrix via coloring. 00043 double*** dp3_Seed = new double**; 00044 int *ip1_SeedRowCount = new int; 00045 int *ip1_SeedColumnCount = new int; 00046 int *ip1_ColorCount = new int; //The number of distinct colors used to color the graph 00047 00048 //Step 2.1: Read the sparsity pattern of the given Jacobian matrix (compressed sparse rows format) 00049 //and create the corresponding bipartite graph 00050 BipartiteGraphPartialColoringInterface *g = new BipartiteGraphPartialColoringInterface(SRC_MEM_ADOLC, *uip3_SparsityPattern, rowCount, columnCount); 00051 00052 //Step 2.2: Do Partial-Distance-Two-Coloring the bipartite graph with the specified ordering 00053 g->PartialDistanceTwoColoring("SMALLEST_LAST", "ROW_PARTIAL_DISTANCE_TWO"); 00054 00055 //Step 2.3 (Option 1): From the coloring information, create and return the seed matrix 00056 (*dp3_Seed) = g->GetSeedMatrix_unmanaged(ip1_SeedRowCount, ip1_SeedColumnCount); 00057 /* Notes: 00058 Step 2.3 (Option 2): From the coloring information, you can also get the vector of colorIDs of left or right vertices (depend on the s_ColoringVariant that you choose) 00059 vector<int> vi_VertexPartialColors; 00060 g->GetVertexPartialColors(vi_VertexPartialColors); 00061 */ 00062 cout<<"Finish GenerateSeed()"<<endl; 00063 *ip1_ColorCount = *ip1_SeedRowCount; 00064 00065 //Display results of step 2 00066 printf(" dp3_Seed %d x %d", *ip1_SeedRowCount, *ip1_SeedColumnCount); 00067 displayMatrix(*dp3_Seed, *ip1_SeedRowCount, *ip1_SeedColumnCount); 00068 Pause(); 00069 00070 // Step 3: Obtain the seed-Jacobian matrix product. 00071 // This step will also be done by an AD tool. For the purpose of illustration here, the seed matrix S 00072 // is multiplied with the orginial matrix V (for Values). The resulting matrix is stored in dp3_CompressedMatrix. 00073 double*** dp3_CompressedMatrix = new double**; 00074 cout<<"Start MatrixMultiplication()"<<endl; 00075 MatrixMultiplication_SxV(*uip3_SparsityPattern, *dp3_Value, rowCount, columnCount, *dp3_Seed, *ip1_ColorCount, dp3_CompressedMatrix); 00076 cout<<"Finish MatrixMultiplication()"<<endl; 00077 00078 displayMatrix(*dp3_CompressedMatrix,*ip1_ColorCount,columnCount); 00079 Pause(); 00080 00081 //Step 4: Recover the numerical values of the original matrix from the compressed representation. 00082 // The new values are store in "dp3_NewValue" 00083 double*** dp3_NewValue = new double**; 00084 JacobianRecovery1D* jr1d = new JacobianRecovery1D; 00085 jr1d->RecoverD2Row_RowCompressedFormat(g, *dp3_CompressedMatrix, *uip3_SparsityPattern, dp3_NewValue); 00086 cout<<"Finish Recover()"<<endl; 00087 00088 displayCompressedRowMatrix(*dp3_NewValue,rowCount); 00089 Pause(); 00090 00091 //Check for consistency, make sure the values in the 2 matrices are the same. 00092 if (CompressedRowMatricesREqual(*dp3_Value, *dp3_NewValue, rowCount,0)) cout<< "*dp3_Value == dp3_NewValue"<<endl; 00093 else cout<< "*dp3_Value != dp3_NewValue"<<endl; 00094 00095 Pause(); 00096 00097 //Deallocate memory using functions in Utilities/MatrixDeallocation.h 00098 00099 free_2DMatrix( (*dp3_Seed), (*ip1_SeedRowCount) ); 00100 00101 free_2DMatrix(uip3_SparsityPattern, rowCount); 00102 uip3_SparsityPattern=NULL; 00103 00104 free_2DMatrix(dp3_Value, rowCount); 00105 dp3_Value=NULL; 00106 00107 delete dp3_Seed; 00108 dp3_Seed = NULL; 00109 00110 delete ip1_SeedRowCount; 00111 ip1_SeedRowCount=NULL; 00112 00113 delete ip1_SeedColumnCount; 00114 ip1_SeedColumnCount = NULL; 00115 00116 free_2DMatrix(dp3_CompressedMatrix, *ip1_ColorCount); 00117 dp3_CompressedMatrix = NULL; 00118 00119 delete ip1_ColorCount; 00120 ip1_ColorCount = NULL; 00121 00122 delete jr1d; 00123 jr1d = NULL; 00124 00125 delete dp3_NewValue; 00126 dp3_NewValue = NULL; 00127 00128 delete g; 00129 g=NULL; 00130 00131 return 0; 00132 00133 00134 /************************************************/ 00135 /* 00136 map<string, bool> stat_flags; 00137 stat_flags["NumberOfColors"] = 1; 00138 stat_flags["Time"] = 1; 00139 stat_flags["MaxBackDegree"] = 1; 00140 stat_flags["Graph_Stat"] = 1; 00141 stat_flags["output_append"] = 0; 00142 stat_flags["refresh_list"] = 0; 00143 00144 vector<string> Orderings, Colorings; 00145 Orderings.push_back("NATURAL"); 00146 Orderings.push_back("LARGEST_FIRST"); 00147 Orderings.push_back("SMALLEST_LAST"); 00148 Orderings.push_back("INCIDENCE_DEGREE"); 00149 //Orderings.push_back("DYNAMIC_LARGEST_FIRST"); 00150 Orderings.push_back("RANDOM"); 00151 //Orderings.push_back("DISTANCE_TWO_LARGEST_FIRST"); 00152 //Orderings.push_back("DISTANCE_TWO_SMALLEST_LAST"); 00153 //Orderings.push_back("DISTANCE_TWO_INCIDENCE_DEGREE"); 00154 00155 //Colorings.push_back("DISTANCE_ONE"); 00156 //Colorings.push_back("ACYCLIC"); 00157 Colorings.push_back("STAR"); 00158 //Colorings.push_back("RESTRICTED_STAR"); 00159 //Colorings.push_back("DISTANCE_TWO"); 00160 00161 //toFileC("/home/nguyend/Desktop/Working_U/research_Assefaw/", "-toFileC-bozdagd-synthetic", Orderings, Colorings, stat_flags); 00162 00163 Colorings.clear(); 00164 Colorings.push_back("IMPLICIT_COVERING__STAR_BICOLORING"); 00165 Colorings.push_back("EXPLICIT_COVERING__STAR_BICOLORING"); 00166 Colorings.push_back("EXPLICIT_COVERING__MODIFIED_STAR_BICOLORING"); 00167 Colorings.push_back("IMPLICIT_COVERING__GREEDY_STAR_BICOLORING"); 00168 00169 toFileBiC("/home/nguyend/Desktop/Working_U/research_Assefaw/","-toFileBiC", Orderings, Colorings, stat_flags); 00170 00171 00172 Colorings.clear(); 00173 Colorings.push_back("COLUMN_PARTIAL_DISTANCE_TWO"); 00174 Colorings.push_back("ROW_PARTIAL_DISTANCE_TWO"); 00175 00176 toFileBiPC("/home/nguyend/Desktop/Working_U/research_Assefaw/","-toFileBiPC", Orderings, Colorings, stat_flags); 00177 00178 //toFileC_forColoringBasedOrdering("/home/nguyend/Desktop/Working_U/research_Assefaw/","-toFileC_forColoringBasedOrdering"); 00179 //toFileStatisticForGraph("/home/nguyend/Desktop/Working_U/research_Assefaw/","-toFileStatisticForGraph"); //i.e. Symmetric Matrix, Hessian 00180 //toFileStatisticForBipartiteGraph("/home/nguyend/Desktop/Working_U/research_Assefaw/","-toFileStatisticForBipartiteGraph"); //i.e. Matrix, Jacobian 00181 00182 //*/ 00183 00184 /************************************************/ 00185 /* 00186 string s_InputFile; //path of the input file. PICK A SYMMETRIC MATRIX!!! 00187 00188 s_InputFile = "/home/nguyend/Desktop/Duck/Research/Prog/graph/bozdagd/application/pkustk10.psa.graph"; 00189 //Generate and color the graph 00190 BipartiteGraphBicoloringInterface * g1 = new BipartiteGraphBicoloringInterface(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00191 00192 s_InputFile = "/home/nguyend/Desktop/Duck/Research/Prog/graph/bozdagd/application/pkustk11.psa.graph"; 00193 //Generate and color the graph 00194 BipartiteGraphPartialColoringInterface * g2 = new BipartiteGraphPartialColoringInterface(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00195 00196 if(*g1 == *g2) cout<<"g1 == g2"<<endl; 00197 else cout<<"g1 != g2"<<endl; 00198 //*/ 00199 00200 /************************************************/ 00201 //toFile("/home/nguyend/Desktop/Working_U/research_Assefaw/"); 00202 00203 00204 /************************************************/ 00205 /* 00206 vector <string> listOfGraphs = getListOfGraphs("/home/nguyend/Desktop/Working_U/research_Assefaw/listOfGraphs.txt"); 00207 for(unsigned int i=0;i < listOfGraphs.size(); i++){ 00208 cout<<"Graph: "<<listOfGraphs[i]<<endl<<endl; 00209 00210 f(listOfGraphs[i]); 00211 } 00212 //*/ 00213 00214 } 00215 /* 00216 { 00217 // s_InputFile = baseDir + <name of the input file> 00218 string s_InputFile; //path of the input file. PICK A SYMMETRIC MATRIX!!! 00219 s_InputFile = baseDir; 00220 s_InputFile += DIR_SEPARATOR; s_InputFile += "Graphs"; s_InputFile += DIR_SEPARATOR; s_InputFile += "mtx-spear-head.mtx"; 00221 s_InputFile = "/home/nguyend/Desktop/Duck/Research/Prog/graph/bozdagd/application/ldoor.rsa.graph"; 00222 00223 //Generate and color the graph 00224 GraphColoringInterface * g = new GraphColoringInterface(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00225 00226 g->PrintVertexDegrees(); 00227 00228 //Color the bipartite graph with the specified ordering 00229 g->Coloring("LARGEST_FIRST", "DISTANCE_TWO"); 00230 00231 /*Done with coloring. Below are possible things that you may 00232 want to do after coloring: 00233 //*/ 00234 00235 /* 1. Check DISTANCE_TWO coloring result 00236 cout<<"Check DISTANCE_TWO coloring result"<<endl; 00237 g->CheckDistanceTwoColoring(); 00238 Pause(); 00239 //*-/ 00240 00241 //* 2. Print coloring results 00242 g->PrintVertexColoringMetrics(); 00243 Pause(); 00244 //*-/ 00245 00246 //* 3. Get the list of colorID of vertices 00247 vector<int> vi_VertexColors; 00248 g->GetVertexColors(vi_VertexColors); 00249 00250 //Display vector of VertexColors 00251 printf("vector of VertexColors (size %d) \n", vi_VertexColors.size()); 00252 displayVector(&vi_VertexColors[0], vi_VertexColors.size(), 1); 00253 Pause(); 00254 //*/ 00255 00256 /* 4. Get seed matrix 00257 int i_SeedRowCount = 0; 00258 int i_SeedColumnCount = 0; 00259 double** Seed = g->GetSeedMatrix(&i_SeedRowCount, &i_SeedColumnCount); 00260 00261 //Display Seed 00262 printf("Seed matrix %d x %d \n", i_SeedRowCount, i_SeedColumnCount); 00263 displayMatrix(Seed, i_SeedRowCount, i_SeedColumnCount, 1); 00264 Pause(); 00265 //*-/ 00266 00267 delete g; 00268 return 0; 00269 } 00270 //*/ 00271 00272 00273 int f (string s_InputFile) { 00274 /************************************************/ 00275 /* 00276 GraphColoringInterface gci(SRC_WAIT), gci2(SRC_WAIT); 00277 gci.ReadMeTiSAdjacencyGraph(s_InputFile); 00278 gci2.ReadMeTiSAdjacencyGraph2(s_InputFile); 00279 00280 if(gci == gci2) cout<<endl<<endl<<"**** gci == gci2"<<endl<<endl; 00281 else { 00282 //gci.PrintGraph(); 00283 //gci2.PrintGraph(); 00284 cout<<"gci.GetVertexCount() = "<<gci.GetVertexCount()<<"; gci.GetEdgeCount() = "<<gci.GetEdgeCount()<<endl; 00285 cout<<"gci2.GetVertexCount() = "<<gci2.GetVertexCount()<<"; gci2.GetEdgeCount() = "<<gci2.GetEdgeCount()<<endl; 00286 vector<int> gci_vertices, gci_edges, gci2_vertices, gci2_edges; 00287 00288 gci.GetVertices(gci_vertices); 00289 gci2.GetVertices(gci2_vertices); 00290 diffVectors(gci_vertices, gci2_vertices); 00291 00292 gci.GetEdges(gci_edges); 00293 gci2.GetEdges(gci2_edges); 00294 diffVectors(gci_edges, gci2_edges, 1, 1); 00295 00296 gci.PrintVertexD1Neighbor(124608,-5); 00297 gci2.PrintVertexD1Neighbor(124608,-5); 00298 cout<<endl<<endl<<"**** gci != gci2"<<endl<<endl; 00299 exit(1); 00300 } 00301 //*/ 00302 00303 /************************************************/ 00304 /* 00305 cout<<endl<<endl<<"****GraphColoringInterface"<<endl; 00306 GraphColoringInterface gci(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00307 00308 //cout<<endl<<endl<<"****BipartiteGraphPartialColoringInterface"<<endl; 00309 //BipartiteGraphPartialColoringInterface bgpci (SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00310 00311 cout<<endl<<endl<<"****ConvertMatrixMarketFormatToRowCompressedFormat"<<endl; 00312 unsigned int *** uip3_SparsityPattern = new unsigned int **; //uip3_ means triple pointers of type unsigned int 00313 double*** dp3_Value = new double**; //dp3_ means double pointers of type double. Other prefixes follow the same notation 00314 int rowCount, columnCount; 00315 ConvertMatrixMarketFormatToRowCompressedFormat(s_InputFile, uip3_SparsityPattern, dp3_Value,rowCount, columnCount); 00316 //displayCompressedRowMatrix(*uip3_SparsityPattern,rowCount); 00317 //BipartiteGraphBicoloringInterface bgbci (SRC_MEM_ADOLC, *uip3_SparsityPattern, rowCount, columnCount); 00318 GraphColoringInterface gci2 (SRC_MEM_ADOLC, *uip3_SparsityPattern, rowCount, columnCount); 00319 00320 00321 if(gci.areEqual(gci2)) cout<<endl<<endl<<"**** g1 == g2"<<endl<<endl; 00322 else { 00323 gci.PrintGraph(); 00324 gci2.PrintGraph(); 00325 displayCompressedRowMatrix(*uip3_SparsityPattern,rowCount); 00326 cout<<endl<<endl<<"**** g1 != g2"<<endl<<endl; 00327 Pause(); 00328 } 00329 //*/ 00330 00331 /************************************************/ 00332 /* 00333 cout<<endl<<endl<<"****GraphColoringInterface"<<endl; 00334 GraphColoringInterface gci(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00335 gci.PrintGraph();5 00336 Pause(); 00337 00338 cout<<endl<<endl<<"****BipartiteGraphBicoloringInterface"<<endl; 00339 BipartiteGraphBicoloringInterface bgbci (SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00340 bgbci.PrintBipartiteGraph(); 00341 00342 //*/ 00343 //* 00344 cout<<endl<<endl<<"****GraphColoringInterface"<<endl; 00345 GraphColoringInterface gci(SRC_FILE, "/home/nguyend/Desktop/Working_U/research_Assefaw/ColPack/Graphs/bcsstk01.mtx", "AUTO_DETECTED"); 00346 gci.PrintGraph(); 00347 //Pause(); 00348 00349 cout<<endl<<endl<<"****GraphColoringInterface2"<<endl; 00350 GraphColoringInterface gci2(SRC_FILE, "/home/nguyend/Desktop/Working_U/research_Assefaw/ColPack/Graphs/bcsstk01.rsa", "AUTO_DETECTED"); 00351 gci2.PrintGraph(); 00352 //Pause(); 00353 00354 if(gci == gci2) cout<<endl<<endl<<"**** gci == gci2"<<endl<<endl; 00355 else { 00356 //gci.PrintGraph(); 00357 //gci2.PrintGraph(); 00358 cout<<"gci.GetVertexCount() = "<<gci.GetVertexCount()<<"; gci.GetEdgeCount() = "<<gci.GetEdgeCount()<<endl; 00359 cout<<"gci2.GetVertexCount() = "<<gci2.GetVertexCount()<<"; gci2.GetEdgeCount() = "<<gci2.GetEdgeCount()<<endl; 00360 vector<int> gci_vertices, gci_edges, gci2_vertices, gci2_edges; 00361 00362 gci.GetVertices(gci_vertices); 00363 gci2.GetVertices(gci2_vertices); 00364 diffVectors(gci_vertices, gci2_vertices); 00365 00366 gci.GetEdges(gci_edges); 00367 gci2.GetEdges(gci2_edges); 00368 diffVectors(gci_edges, gci2_edges, 1, 1); 00369 00370 gci.PrintVertexD1Neighbor(124608,-5); 00371 gci2.PrintVertexD1Neighbor(124608,-5); 00372 cout<<endl<<endl<<"**** gci != gci2"<<endl<<endl; 00373 exit(1); 00374 } 00375 //*/ 00376 00377 Pause(); 00378 00379 } 00380 00381 /* A LONGER VERSION showing steps actually executed by the constructor. 00382 int main(int argc, char ** argv) 00383 { 00384 // s_InputFile = baseDir + <name of the input file> 00385 string s_InputFile; //path of the input file. PICK A SYMMETRIC MATRIX!!! 00386 s_InputFile = baseDir + "bcsstk01_symmetric\\bcsstk01_symmetric.mtx"; 00387 GraphColoringInterface * g = new GraphColoringInterface(); 00388 00389 //Read a matrix from an input file and generate a corresponding graph. 00390 //The input format will be determined based on the file extension and a correct reading routine will be used to read the file. 00391 //Note: the input matrix MUST be SYMMETRIC in order for a graph to be generated correctly 00392 // If you are new to COLPACK, pick either a .graph file (MeTiS format) or a symmetric .mtx (Matrix Market format) 00393 if ( g->ReadAdjacencyGraph(s_InputFile) == _FALSE) { 00394 cout<<"ReadAdjacencyGraph() Failed!!!"<<endl; 00395 return _FALSE; 00396 } 00397 cout<<"Done with ReadAdjacencyGraph()"<<endl; 00398 //Pause(); 00399 00400 //(Distance-2)Color the graph using "LARGEST_FIRST" Ordering. Other coloring and ordering can also be used. 00401 g->Coloring("DISTANCE_TWO", "LARGEST_FIRST"); 00402 cout<<"Done with Coloring()"<<endl; 00403 //Pause(); 00404 00405 //Print coloring results 00406 g->PrintVertexColoringMetrics(); 00407 cout<<"Done with PrintVertexColoringMetrics()"<<endl; 00408 delete g; 00409 //Pause(); 00410 00411 return _TRUE; 00412 } 00413 //*/
1.7.1