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 using namespace std;
00022
00023 #ifndef BIPARTITEGRAPHBICOLORING_H
00024 #define BIPARTITEGRAPHBICOLORING_H
00025
00026 namespace ColPack
00027 {
00046 class BipartiteGraphBicoloring : public BipartiteGraphOrdering
00047 {
00048 public:
00049
00050
00052 void GetLeftVertexColors(vector<int> &output);
00053
00054
00056 void GetRightVertexColors(vector<int> &output);
00057
00059 void GetRightVertexColors_Transformed(vector<int> &output);
00060
00062
00075 double** GetLeftSeedMatrix(int* ip1_SeedRowCount, int* ip1_SeedColumnCount);
00076
00078
00081 double** GetLeftSeedMatrix_unmanaged(int* ip1_SeedRowCount, int* ip1_SeedColumnCount);
00082
00084
00097 double** GetRightSeedMatrix(int* ip1_SeedRowCount, int* ip1_SeedColumnCount);
00098
00100
00103 double** GetRightSeedMatrix_unmanaged(int* ip1_SeedRowCount, int* ip1_SeedColumnCount);
00104
00106
00109 void GetSeedMatrix(double*** dp3_LeftSeed, int* ip1_LeftSeedRowCount, int* ip1_LeftSeedColumnCount, double*** dp3_RightSeed, int* ip1_RightSeedRowCount, int* ip1_RightSeedColumnCount);
00110
00112
00115 void GetSeedMatrix_unmanaged(double*** dp3_LeftSeed, int* ip1_LeftSeedRowCount, int* ip1_LeftSeedColumnCount, double*** dp3_RightSeed, int* ip1_RightSeedRowCount, int* ip1_RightSeedColumnCount);
00116
00117 protected:
00119
00123 int i_LeftVertexDefaultColor;
00124
00126
00130 int i_RightVertexDefaultColor;
00131
00133
00136 int m_i_LeftVertexColorCount;
00137
00139
00142 int m_i_RightVertexColorCount;
00143
00144 int m_i_VertexColorCount;
00145
00147
00149 vector<int> m_vi_LeftVertexColors;
00150
00152
00154 vector<int> m_vi_RightVertexColors;
00155
00156 bool lseed_available;
00157 int i_lseed_rowCount;
00158 double** dp2_lSeed;
00159
00160 bool rseed_available;
00161 int i_rseed_rowCount;
00162 double** dp2_rSeed;
00163
00164 void Seed_init();
00165 void Seed_reset();
00166
00167 private:
00168
00169
00170 void PresetCoveredVertexColors();
00171
00172
00173 int CheckVertexColoring(string s_VertexColoringVariant);
00174
00175
00176 int CalculateVertexColorClasses();
00177
00178
00179 int FixMinimalCoverStarBicoloring();
00180
00181 protected:
00182
00183 int m_i_ViolationCount;
00184
00185
00186
00187 int m_i_LargestLeftVertexColorClass;
00188 int m_i_LargestRightVertexColorClass;
00189
00190 int m_i_LargestLeftVertexColorClassSize;
00191 int m_i_LargestRightVertexColorClassSize;
00192
00193 int m_i_SmallestLeftVertexColorClass;
00194 int m_i_SmallestRightVertexColorClass;
00195
00196 int m_i_SmallestLeftVertexColorClassSize;
00197 int m_i_SmallestRightVertexColorClassSize;
00198
00199 int m_i_LargestVertexColorClass;
00200 int m_i_SmallestVertexColorClass;
00201
00202 int m_i_LargestVertexColorClassSize;
00203 int m_i_SmallestVertexColorClassSize;
00204
00205 double m_d_AverageLeftVertexColorClassSize;
00206 double m_d_AverageRightVertexColorClassSize;
00207 double m_d_AverageVertexColorClassSize;
00208
00209 double m_d_ColoringTime;
00210 double m_d_CheckingTime;
00211
00212 string m_s_VertexColoringVariant;
00213
00214 vector<int> m_vi_LeftVertexColorFrequency;
00215 vector<int> m_vi_RightVertexColorFrequency;
00216
00217 public:
00218
00219
00220 BipartiteGraphBicoloring();
00221
00222
00223 ~BipartiteGraphBicoloring();
00224
00225
00226 virtual void Clear();
00227
00228
00229 virtual void Reset();
00230
00231
00232 int ImplicitCoveringStarBicoloring();
00233
00234
00235 int ExplicitCoveringStarBicoloring();
00236
00237
00238 int ExplicitCoveringModifiedStarBicoloring();
00239
00240
00241 int ImplicitCoveringGreedyStarBicoloring();
00242
00243
00244 int MinimalCoveringRowMajorStarBicoloring();
00245
00246
00247 int MinimalCoveringColumnMajorStarBicoloring();
00248
00249
00250 int ImplicitCoveringConservativeStarBicoloring();
00251
00252
00253 int MinimalCoveringStarBicoloring();
00254
00255
00256 int ImplicitCoveringRestrictedStarBicoloring();
00257
00258
00259 int CheckStarBicoloring();
00260
00261
00262
00263 int GetLeftVertexColorCount();
00264
00265
00266 int GetRightVertexColorCount();
00267
00268
00269 int GetVertexColorCount();
00270
00271
00272 int GetViolationCount();
00273
00274 int GetRightVertexDefaultColor();
00275
00276
00277 string GetVertexBicoloringVariant();
00278
00279
00280 void PrintVertexBicolors();
00281
00282
00283 void PrintVertexBicoloringMetrics();
00284
00285
00286 void PrintVertexBicolorClasses();
00287
00288 double GetVertexColoringTime();
00289 };
00290 }
00291 #endif