|
ColPack
|
|
ColPack
|
00001 /************************************************************************************ 00002 Copyright (C) 2005-2008 Assefaw H. Gebremedhin, Arijit Tarafdar, Duc Nguyen, 00003 Alex Pothen 00004 00005 This file is part of ColPack. 00006 00007 ColPack is free software: you can redistribute it and/or modify 00008 it under the terms of the GNU Lesser General Public License as published 00009 by the Free Software Foundation, either version 3 of the License, or 00010 (at your option) any later version. 00011 00012 ColPack is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 GNU Lesser General Public License for more details. 00016 00017 You should have received a copy of the GNU Lesser General Public License 00018 along with ColPack. If not, see <http://www.gnu.org/licenses/>. 00019 ************************************************************************************/ 00020 00021 #ifndef GRAPHCOLORING_H 00022 #define GRAPHCOLORING_H 00023 00024 using namespace std; 00025 00026 namespace ColPack 00027 { 00038 class GraphColoring : public GraphOrdering 00039 { 00040 public: //DOCUMENTED 00041 00043 00054 double** GetSeedMatrix(int* ip1_SeedRowCount, int* ip1_SeedColumnCount); 00055 00057 00060 double** GetSeedMatrix_unmanaged(int* ip1_SeedRowCount, int* ip1_SeedColumnCount); 00061 00063 00088 int CheckQuickDistanceTwoColoring(int Verbose = 0); 00089 00091 00104 int CheckDistanceTwoColoring(int Verbose = 0); 00105 00106 int CalculateVertexColorClasses(); 00107 00108 private: 00109 00110 int m_i_ColoringUnits; 00111 00112 //Private Function 1401 00113 int FindCycle(int, int, int, int, vector<int> &, vector<int> &, vector<int> &); 00114 00115 //Private Function 1402 00116 int UpdateSet(int, int, int, map< int, map<int, int> > &, vector<int> &, vector<int> &, vector<int> &); 00117 00118 //Private Function 1403 00119 int SearchDepthFirst(int, int, int, vector<int> &); 00120 00121 //Private Function 1404 00122 int CheckVertexColoring(string s_GraphColoringVariant); 00123 00124 00125 protected: 00126 00127 int m_i_VertexColorCount; 00128 00129 int m_i_LargestColorClass; 00130 int m_i_SmallestColorClass; 00131 00132 int m_i_LargestColorClassSize; 00133 int m_i_SmallestColorClassSize; 00134 00135 double m_d_AverageColorClassSize; 00136 00137 double m_d_ColoringTime; 00138 double m_d_CheckingTime; 00139 00140 string m_s_VertexColoringVariant; 00141 00142 vector<int> m_vi_VertexColors; 00143 00144 vector<int> m_vi_VertexColorFrequency; 00145 00146 bool seed_available; 00147 int i_seed_rowCount; 00148 double** dp2_Seed; 00149 00150 void Seed_init(); 00151 void Seed_reset(); 00152 00153 public: 00154 00155 void SetStringVertexColoringVariant(string s); 00156 void SetVertexColorCount(int i_VertexColorCount); 00157 00158 //Public Constructor 1451 00159 GraphColoring(); 00160 00161 //Public Destructor 1452 00162 ~GraphColoring(); 00163 00164 //Virtual Function 1453 00165 virtual void Clear(); 00166 void ClearColoringONLY(); 00167 00168 //Public Function 1454 00169 int DistanceOneColoring(); 00170 00171 //Public Function 1455 00172 int DistanceTwoColoring(); 00173 00174 //Public Function 1456 00175 int NaiveStarColoring(); 00176 00177 //Public Function 1457 00179 00184 int RestrictedStarColoring(); 00185 00186 //Public Function 1458 00187 /* 00188 * Related paper: A. Gebremedhin, A. Tarafdar, F. Manne and A. Pothen, New Acyclic and Star Coloring Algorithms with Applications to Hessian Computation, SIAM Journal on Scientific Computing, Vol 29, No 3, pp 1042--1072, 2007. 00189 * http://www.cs.purdue.edu/homes/agebreme/publications/SISC29-2-2009.pdf 00190 * ?This is the algorithm 4.1 in the above paper 00191 */ 00192 int StarColoring_serial(); 00193 int StarColoring_serial2(); // Essentially based on StarColoring_OMP() v1 00194 00195 // TO BE IMPLEMENTED 00196 int StarColoring(); 00197 00199 00202 int BuildStarCollection(vector<int> & vi_VerticesToBeRecolored); 00203 int PrintStarCollection(vector<int>& vi_EdgeStarMap, vector<int>& vi_StarHubMap, map< int, map<int, int> >& mimi2_VertexEdgeMap); 00204 00205 struct lt_pii 00206 { 00207 bool operator()(const pair<int, int> pii_ColorCombination1, const pair<int, int> pii_ColorCombination2) const 00208 { 00209 if(pii_ColorCombination1.first < pii_ColorCombination2.first) { 00210 return true; 00211 } 00212 else if (pii_ColorCombination1.first > pii_ColorCombination2.first) { 00213 return false; 00214 } 00215 // pii_ColorCombination1.first == pii_ColorCombination2.first 00216 return (pii_ColorCombination1.second < pii_ColorCombination2.second); 00217 } 00218 }; 00219 00220 struct Colors2Edge_Value { 00221 Colors2Edge_Value() { 00222 visited=false; 00223 } 00224 vector< pair<int, int> > value; 00225 bool visited; 00226 }; 00228 00233 int DetectConflictInColorCombination(int i_MaxNumThreads, int i_thread_num, pair<int, int> pii_ColorCombination, map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private, 00234 map< int, vector< pair<int, int> > > *Vertex2ColorCombination_Private, map< int, int> * PotentialHub_Private, vector< pair<int, int> >* ConflictedEdges_Private, vector<int>* ConflictCount_Private); 00236 int BuildStarFromColorCombination(int i_MaxNumThreads, int i_thread_num, pair<int, int> pii_ColorCombination, map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private, 00237 map< int, vector< pair<int, int> > > *Vertex2ColorCombination_Private, map< int, int> * PotentialHub_Private); 00238 00239 ofstream fout; // !!! 00240 int i_ProcessedEdgeCount; // !!! 00242 00246 int BuildVertex2ColorCombination(int i_MaxNumThreads, map< int, vector< pair<int, int> > > *Vertex2ColorCombination_Private, vector< map <int, int > > *Vertex2ColorCombination); 00247 /* 00248 * if(i_Mode==1) : stop at the first failure 00249 * else if(i_Mode==0): pause but then continue 00250 * 00251 * Return values: 00252 * - >= 0: Fail. the vertex that causes conflict as this routine progress. Note: this may not be the latest-added vertex that cause coloring conflict in the graph 00253 * - -2: Fail. 2 potential hub are connected 00254 * - -1: Pass. 00255 * 00256 * If pii_ConflictColorCombination is provided (i.e. pii_ConflictColorCombination!=NULL) and this Check fail, pii_ConflictColorCombination will contain the 2 problematic colors 00257 */ 00258 int CheckStarColoring_OMP(int i_Mode, pair<int,int> *pii_ConflictColorCombination); 00259 int BuildStarFromColorCombination_forChecking(int i_Mode, int i_MaxNumThreads, int i_thread_num, pair<int, int> pii_ColorCombination, map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private, 00260 map< int, int> * PotentialHub_Private); 00261 int BuildForbiddenColors(int i_MaxNumThreads, int i_thread_num, int i_CurrentVertex, map<int, bool>* mip_ForbiddenColors, map<int, int>* D1Colors, vector< map <int, int > > *Vertex2ColorCombination); 00262 int PrintVertex2ColorCombination (vector< map <int, int > > *Vertex2ColorCombination); 00263 int PrintVertex2ColorCombination_raw (vector< map <int, int > > *Vertex2ColorCombination); 00264 int PrintVertexAndColorAdded(int i_MaxNumThreads, vector< pair<int, int> > *vi_VertexAndColorAdded, int i_LastNEntries = 999999999); 00265 int PrintForbiddenColors(map<int, bool>* mip_ForbiddenColors,int i_thread_num); 00266 int PickVerticesToBeRecolored(int i_MaxNumThreads, vector< pair<int, int> > *ConflictedEdges_Private, vector<int> &ConflictCount); 00267 int PrintAllColorCombination(map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private, int i_MaxNumThreads, int i_MaxNumOfCombination=1000000, int i_MaxElementsOfCombination=100000); 00268 int PrintColorCombination(map< pair<int, int>, Colors2Edge_Value , lt_pii>* Colors2Edge_Private, int i_MaxNumThreads, pair<int, int> pii_ColorCombination, int i_MaxElementsOfCombination=100000); 00269 int PrintPotentialHub(map< int, int> *PotentialHub_Private, int i_thread_num, pair<int, int> pii_ColorCombination); 00270 int PrintConflictEdges(vector< pair<int, int> > *ConflictedEdges_Private, int i_MaxNumThreads); 00271 int PrintConflictCount(vector<int> &ConflictCount); 00272 int PrintVertex2ColorCombination(int i_MaxNumThreads, map< int, vector< pair<int, int> > > *Vertex2ColorCombination_Private); 00273 int PrintD1Colors(map<int, int>* D1Colors, int i_thread_num); 00274 int PrintVertexColorCombination(map <int, int >* VertexColorCombination); 00275 00277 00291 int BuildSubGraph(map< int, map<int,bool> > *graph, int i_CenterVertex, int distance=1, map<int, bool> *mib_FilterByColors=NULL); 00292 00295 int BuildConnectedSubGraph(map< int, map<int,bool> > *graph, int i_CenterVertex, int distance=1, map<int, bool> *mib_FilterByColors=NULL); 00296 00311 int BuildColorsSubGraph(map< int, map<int,bool> > *graph, map<int,bool> *mib_Colors); 00312 int PrintSubGraph(map< int, map<int,bool> > *graph); 00313 int PrintVertexD1NeighborAndColor(int VertexIndex, int excludedVertex=-1); 00314 int FindDistance(int v1, int v2); 00315 00316 //Public Function 1459 00317 int StarColoring(vector<int> &, vector<int> &, map< int, map<int, int> > &); 00318 00319 //Public Function 1460 00320 int CheckStarColoring(); 00321 int GetStarColoringConflicts(vector<vector<int> > &ListOfConflicts); 00322 00323 //Public Function 1461 00327 int AcyclicColoring(); 00328 00329 //Public Function 1462 00333 int AcyclicColoring(vector<int> &, map< int, vector<int> > &); 00334 00338 int AcyclicColoring_ForIndirectRecovery(); 00339 00340 //Public Function 1463 00341 int CheckAcyclicColoring(); 00342 00343 //Public Function 1464 00344 int TriangularColoring(); 00345 00346 //Public Function 1465 00347 int ModifiedTriangularColoring(); 00348 00349 //Public Function 1466 00350 int CheckTriangularColoring(); 00351 00352 //Public Function 1467 00353 string GetVertexColoringVariant(); 00354 void SetVertexColoringVariant(string s_VertexColoringVariant); 00355 00356 //Public Function 1468 00357 int GetVertexColorCount(); 00358 00359 //Public Function 1469 00360 void GetVertexColors(vector<int> &output); 00361 vector <int>* GetVertexColorsPtr(){ return &m_vi_VertexColors; } 00362 00363 //Public Function 1470 00364 int GetHubCount(); 00365 00366 //Public Function 1471 00367 int GetSetCount(); 00368 00369 //Public Function 1472 00370 double GetVertexColoringTime(); 00371 00372 //Public Function 1473 00373 double GetVertexColoringCheckingTime(); 00374 00375 //Public Function 1474 00376 int PrintVertexColors(); 00377 00378 //Public Function 1475 00379 int FileVertexColors(); 00380 00381 //Public Function 1476 00382 int PrintVertexColoringMetrics(); 00383 00384 //Public Function 1477 00385 int FileVertexColoringMetrics(); 00386 00387 //Public Function 1478 00388 void PrintVertexColorClasses(); 00389 }; 00390 } 00391 #endif 00392
1.7.6.1 
