Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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:
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
00113 int FindCycle(int, int, int, int, vector<int> &, vector<int> &, vector<int> &);
00114
00115
00116 int UpdateSet(int, int, int, map< int, map<int, int> > &, vector<int> &, vector<int> &, vector<int> &);
00117
00118
00119 int SearchDepthFirst(int, int, int, vector<int> &);
00120
00121
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
00157
00158 GraphColoring();
00159
00160
00161 ~GraphColoring();
00162
00163
00164 virtual void Clear();
00165
00166
00167 int DistanceOneColoring();
00168
00169
00170 int DistanceTwoColoring();
00171
00172
00173 int NaiveStarColoring();
00174
00175
00176 int RestrictedStarColoring();
00177
00178
00179 int StarColoring();
00180
00181
00182 int StarColoring(vector<int> &, vector<int> &, map< int, map<int, int> > &);
00183
00184
00185 int CheckStarColoring();
00186
00187
00191 int AcyclicColoring();
00192
00193
00197 int AcyclicColoring(vector<int> &, map< int, vector<int> > &);
00198
00202 int AcyclicColoring_ForIndirectRecovery();
00203
00204
00205 int CheckAcyclicColoring();
00206
00207
00208 int TriangularColoring();
00209
00210
00211 int ModifiedTriangularColoring();
00212
00213
00214 int CheckTriangularColoring();
00215
00216
00217 string GetVertexColoringVariant();
00218
00219
00220 int GetVertexColorCount();
00221
00222
00223 void GetVertexColors(vector<int> &output);
00224
00225
00226 int GetHubCount();
00227
00228
00229 int GetSetCount();
00230
00231
00232 double GetVertexColoringTime();
00233
00234
00235 double GetVertexColoringCheckingTime();
00236
00237
00238 int PrintVertexColors();
00239
00240
00241 int FileVertexColors();
00242
00243
00244 int PrintVertexColoringMetrics();
00245
00246
00247 int FileVertexColoringMetrics();
00248
00249
00250 void PrintVertexColorClasses();
00251 };
00252 }
00253 #endif
00254