00001 // An example for using GraphColoringInterface to color Graph 00002 /* 00003 How to compile this driver manually: 00004 Please make sure that "baseDir" point to the directory (folder) containing the input matrix file, and 00005 s_InputFile should point to the input file that you want to use 00006 To compile the code, replace the Main.cpp file in Main directory with this file 00007 and run "make" in ColPack installation directory. Make will generate "ColPack.exe" executable 00008 Run "ColPack.exe" 00009 00010 Note: If you got "symbol lookup error ... undefined symbol " 00011 Please make sure that your LD_LIBRARY_PATH contains libColPack.so 00012 00013 Any time you have trouble understanding what a routine does, how to use a routine, or what are the accepted values for a parameter, 00014 please reference the COLPACK's online documentation (temporarily located at 00015 http://www.cscapes.org/dox/ColPack/html/ ). 00016 00017 For more information, please visit our webpage http://www.cscapes.org/coloringpage/ 00018 //*/ 00019 00020 #include "ColPackHeaders.h" 00021 #include "stat.h" 00022 00023 using namespace ColPack; 00024 using namespace std; 00025 00026 #ifndef TOP_DIR 00027 #define TOP_DIR "." 00028 #endif 00029 00030 // baseDir should point to the directory (folder) containing the input file 00031 string baseDir=TOP_DIR; 00032 00033 int f (string s_InputFile); 00034 00035 //* A SHORT VERSION 00036 int main(int argc, char ** argv) { 00037 return 0; 00038 /************************************************/ 00039 /* 00040 string s_InputFile; //path of the input file. PICK A SYMMETRIC MATRIX!!! 00041 00042 s_InputFile = "/home/nguyend/Desktop/Duck/Research/Prog/graph/bozdagd/application/pkustk10.psa.graph"; 00043 //Generate and color the graph 00044 BipartiteGraphBicoloringInterface * g1 = new BipartiteGraphBicoloringInterface(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00045 00046 s_InputFile = "/home/nguyend/Desktop/Duck/Research/Prog/graph/bozdagd/application/pkustk11.psa.graph"; 00047 //Generate and color the graph 00048 BipartiteGraphPartialColoringInterface * g2 = new BipartiteGraphPartialColoringInterface(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00049 00050 if(*g1 == *g2) cout<<"g1 == g2"<<endl; 00051 else cout<<"g1 != g2"<<endl; 00052 //*/ 00053 00054 /************************************************/ 00055 //toFile("/home/nguyend/Desktop/Working_U/research_Assefaw/"); 00056 00057 00058 /************************************************/ 00059 /* 00060 vector <string> listOfGraphs = getListOfGraphs("/home/nguyend/Desktop/Working_U/research_Assefaw/listOfGraphs.txt"); 00061 for(unsigned int i=0;i < listOfGraphs.size(); i++){ 00062 cout<<"Graph: "<<listOfGraphs[i]<<endl<<endl; 00063 00064 f(listOfGraphs[i]); 00065 } 00066 //*/ 00067 00068 } 00069 /* 00070 { 00071 // s_InputFile = baseDir + <name of the input file> 00072 string s_InputFile; //path of the input file. PICK A SYMMETRIC MATRIX!!! 00073 s_InputFile = baseDir; 00074 s_InputFile += DIR_SEPARATOR; s_InputFile += "Graphs"; s_InputFile += DIR_SEPARATOR; s_InputFile += "mtx-spear-head.mtx"; 00075 s_InputFile = "/home/nguyend/Desktop/Duck/Research/Prog/graph/bozdagd/application/ldoor.rsa.graph"; 00076 00077 //Generate and color the graph 00078 GraphColoringInterface * g = new GraphColoringInterface(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00079 00080 g->PrintVertexDegrees(); 00081 00082 //Color the bipartite graph with the specified ordering 00083 g->Coloring("LARGEST_FIRST", "DISTANCE_TWO"); 00084 00085 /*Done with coloring. Below are possible things that you may 00086 want to do after coloring: 00087 //*/ 00088 00089 /* 1. Check DISTANCE_TWO coloring result 00090 cout<<"Check DISTANCE_TWO coloring result"<<endl; 00091 g->CheckDistanceTwoColoring(); 00092 Pause(); 00093 //*-/ 00094 00095 //* 2. Print coloring results 00096 g->PrintVertexColoringMetrics(); 00097 Pause(); 00098 //*-/ 00099 00100 //* 3. Get the list of colorID of vertices 00101 vector<int> vi_VertexColors; 00102 g->GetVertexColors(vi_VertexColors); 00103 00104 //Display vector of VertexColors 00105 printf("vector of VertexColors (size %d) \n", vi_VertexColors.size()); 00106 displayVector(&vi_VertexColors[0], vi_VertexColors.size(), 1); 00107 Pause(); 00108 //*/ 00109 00110 /* 4. Get seed matrix 00111 int i_SeedRowCount = 0; 00112 int i_SeedColumnCount = 0; 00113 double** Seed = g->GetSeedMatrix(&i_SeedRowCount, &i_SeedColumnCount); 00114 00115 //Display Seed 00116 printf("Seed matrix %d x %d \n", i_SeedRowCount, i_SeedColumnCount); 00117 displayMatrix(Seed, i_SeedRowCount, i_SeedColumnCount, 1); 00118 Pause(); 00119 //*-/ 00120 00121 delete g; 00122 return 0; 00123 } 00124 //*/ 00125 00126 00127 int f (string s_InputFile) { 00128 /************************************************/ 00129 /* 00130 GraphColoringInterface gci(SRC_WAIT), gci2(SRC_WAIT); 00131 gci.ReadMeTiSAdjacencyGraph(s_InputFile); 00132 gci2.ReadMeTiSAdjacencyGraph2(s_InputFile); 00133 00134 if(gci == gci2) cout<<endl<<endl<<"**** gci == gci2"<<endl<<endl; 00135 else { 00136 //gci.PrintGraph(); 00137 //gci2.PrintGraph(); 00138 cout<<"gci.GetVertexCount() = "<<gci.GetVertexCount()<<"; gci.GetEdgeCount() = "<<gci.GetEdgeCount()<<endl; 00139 cout<<"gci2.GetVertexCount() = "<<gci2.GetVertexCount()<<"; gci2.GetEdgeCount() = "<<gci2.GetEdgeCount()<<endl; 00140 vector<int> gci_vertices, gci_edges, gci2_vertices, gci2_edges; 00141 00142 gci.GetVertices(gci_vertices); 00143 gci2.GetVertices(gci2_vertices); 00144 diffVectors(gci_vertices, gci2_vertices); 00145 00146 gci.GetEdges(gci_edges); 00147 gci2.GetEdges(gci2_edges); 00148 diffVectors(gci_edges, gci2_edges, 1, 1); 00149 00150 gci.PrintVertexD1Neighbor(124608,-5); 00151 gci2.PrintVertexD1Neighbor(124608,-5); 00152 cout<<endl<<endl<<"**** gci != gci2"<<endl<<endl; 00153 exit(1); 00154 } 00155 //*/ 00156 00157 /************************************************/ 00158 //* 00159 cout<<endl<<endl<<"****GraphColoringInterface"<<endl; 00160 GraphColoringInterface gci(SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00161 00162 //cout<<endl<<endl<<"****BipartiteGraphPartialColoringInterface"<<endl; 00163 //BipartiteGraphPartialColoringInterface bgpci (SRC_FILE, s_InputFile.c_str(), "AUTO_DETECTED"); 00164 00165 cout<<endl<<endl<<"****ConvertMatrixMarketFormatToRowCompressedFormat"<<endl; 00166 unsigned int *** uip3_SparsityPattern = new unsigned int **; //uip3_ means triple pointers of type unsigned int 00167 double*** dp3_Value = new double**; //dp3_ means double pointers of type double. Other prefixes follow the same notation 00168 int rowCount, columnCount; 00169 ConvertMatrixMarketFormatToRowCompressedFormat(s_InputFile, uip3_SparsityPattern, dp3_Value,rowCount, columnCount); 00170 //displayCompressedRowMatrix(*uip3_SparsityPattern,rowCount); 00171 //BipartiteGraphBicoloringInterface bgbci (SRC_MEM_ADOLC, *uip3_SparsityPattern, rowCount, columnCount); 00172 GraphColoringInterface gci2 (SRC_MEM_ADOLC, *uip3_SparsityPattern, rowCount, columnCount); 00173 00174 00175 if(gci.areEqual(gci2)) cout<<endl<<endl<<"**** g1 == g2"<<endl<<endl; 00176 else { 00177 gci.PrintGraph(); 00178 gci2.PrintGraph(); 00179 displayCompressedRowMatrix(*uip3_SparsityPattern,rowCount); 00180 cout<<endl<<endl<<"**** g1 != g2"<<endl<<endl; 00181 Pause(); 00182 } 00183 //*/ 00184 00185 //Pause(); 00186 00187 } 00188 00189 /* A LONGER VERSION showing steps actually executed by the constructor. 00190 int main(int argc, char ** argv) 00191 { 00192 // s_InputFile = baseDir + <name of the input file> 00193 string s_InputFile; //path of the input file. PICK A SYMMETRIC MATRIX!!! 00194 s_InputFile = baseDir + "bcsstk01_symmetric\\bcsstk01_symmetric.mtx"; 00195 GraphColoringInterface * g = new GraphColoringInterface(); 00196 00197 //Read a matrix from an input file and generate a corresponding graph. 00198 //The input format will be determined based on the file extension and a correct reading routine will be used to read the file. 00199 //Note: the input matrix MUST be SYMMETRIC in order for a graph to be generated correctly 00200 // If you are new to COLPACK, pick either a .graph file (MeTiS format) or a symmetric .mtx (Matrix Market format) 00201 if ( g->ReadAdjacencyGraph(s_InputFile) == _FALSE) { 00202 cout<<"ReadAdjacencyGraph() Failed!!!"<<endl; 00203 return _FALSE; 00204 } 00205 cout<<"Done with ReadAdjacencyGraph()"<<endl; 00206 //Pause(); 00207 00208 //(Distance-2)Color the graph using "LARGEST_FIRST" Ordering. Other coloring and ordering can also be used. 00209 g->Coloring("DISTANCE_TWO", "LARGEST_FIRST"); 00210 cout<<"Done with Coloring()"<<endl; 00211 //Pause(); 00212 00213 //Print coloring results 00214 g->PrintVertexColoringMetrics(); 00215 cout<<"Done with PrintVertexColoringMetrics()"<<endl; 00216 delete g; 00217 //Pause(); 00218 00219 return _TRUE; 00220 } 00221 //*/
1.7.1