ColPack
|
class BipartiteGraphBicoloring in group22. More...
#include <BipartiteGraphBicoloring.h>
Public Member Functions | |
void | GetLeftVertexColors (vector< int > &output) |
Get the color IDs for the left vertices (rows). Color IDs start from 1, color ID 0 should be ignored. | |
void | GetRightVertexColors (vector< int > &output) |
Get the color IDs for the right vertices (columns). Color IDs start from (# of rows + 1), color ID (# of rows + # of columns + 1) should be ignored. | |
void | GetRightVertexColors_Transformed (vector< int > &output) |
Get the color IDs for the right vertices (columns) in the format similar to GetLeftVertexColor(). Color IDs start from 1, color ID 0 should be ignored. | |
double ** | GetLeftSeedMatrix (int *ip1_SeedRowCount, int *ip1_SeedColumnCount) |
Generate and return the Left Seed matrix. This Seed matrix is managed and freed by ColPack. | |
double ** | GetLeftSeedMatrix_unmanaged (int *ip1_SeedRowCount, int *ip1_SeedColumnCount) |
Same as GetLeftSeedMatrix(), except that this Seed matrix is NOT managed by ColPack. | |
double ** | GetRightSeedMatrix (int *ip1_SeedRowCount, int *ip1_SeedColumnCount) |
Return the Right Seed matrix. This Seed matrix is managed and freed by ColPack. | |
double ** | GetRightSeedMatrix_unmanaged (int *ip1_SeedRowCount, int *ip1_SeedColumnCount) |
Same as GetRightSeedMatrix(), except that this Seed matrix is NOT managed by ColPack. | |
void | GetSeedMatrix (double ***dp3_LeftSeed, int *ip1_LeftSeedRowCount, int *ip1_LeftSeedColumnCount, double ***dp3_RightSeed, int *ip1_RightSeedRowCount, int *ip1_RightSeedColumnCount) |
Return both the Left and Right Seed matrix. These Seed matrices are managed and freed by ColPack. | |
void | GetSeedMatrix_unmanaged (double ***dp3_LeftSeed, int *ip1_LeftSeedRowCount, int *ip1_LeftSeedColumnCount, double ***dp3_RightSeed, int *ip1_RightSeedRowCount, int *ip1_RightSeedColumnCount) |
Same as GetSeedMatrix(), except that These Seed matrices are NOT managed by ColPack. | |
BipartiteGraphBicoloring () | |
~BipartiteGraphBicoloring () | |
virtual void | Clear () |
virtual void | Reset () |
int | ImplicitCoveringStarBicoloring () |
int | ExplicitCoveringStarBicoloring () |
int | ExplicitCoveringModifiedStarBicoloring () |
int | ImplicitCoveringGreedyStarBicoloring () |
int | MinimalCoveringRowMajorStarBicoloring () |
int | MinimalCoveringColumnMajorStarBicoloring () |
int | ImplicitCoveringConservativeStarBicoloring () |
int | MinimalCoveringStarBicoloring () |
int | ImplicitCoveringRestrictedStarBicoloring () |
int | CheckStarBicoloring () |
int | GetLeftVertexColorCount () |
int | GetRightVertexColorCount () |
int | GetVertexColorCount () |
int | GetViolationCount () |
int | GetRightVertexDefaultColor () |
string | GetVertexBicoloringVariant () |
string | GetVertexColoringVariant () |
void | PrintVertexBicolors () |
void | PrintVertexBicoloringMetrics () |
void | PrintVertexBicolorClasses () |
double | GetVertexColoringTime () |
Protected Member Functions | |
void | Seed_init () |
void | Seed_reset () |
Protected Attributes | |
int | i_LeftVertexDefaultColor |
Whether or not color 0 is used for left vertices. | |
int | i_RightVertexDefaultColor |
Whether or not color 0 is used for right vertices. | |
int | m_i_LeftVertexColorCount |
The number of colors used to color Left Vertices. | |
int | m_i_RightVertexColorCount |
The number of colors used to color Right Vertices. | |
int | m_i_VertexColorCount |
vector< int > | m_vi_LeftVertexColors |
The color IDs used to color the left vertices (rows). | |
vector< int > | m_vi_RightVertexColors |
The color IDs used to color the right vertices (columns). | |
bool | lseed_available |
int | i_lseed_rowCount |
double ** | dp2_lSeed |
bool | rseed_available |
int | i_rseed_rowCount |
double ** | dp2_rSeed |
int | m_i_ViolationCount |
int | m_i_LargestLeftVertexColorClass |
int | m_i_LargestRightVertexColorClass |
int | m_i_LargestLeftVertexColorClassSize |
int | m_i_LargestRightVertexColorClassSize |
int | m_i_SmallestLeftVertexColorClass |
int | m_i_SmallestRightVertexColorClass |
int | m_i_SmallestLeftVertexColorClassSize |
int | m_i_SmallestRightVertexColorClassSize |
int | m_i_LargestVertexColorClass |
int | m_i_SmallestVertexColorClass |
int | m_i_LargestVertexColorClassSize |
int | m_i_SmallestVertexColorClassSize |
double | m_d_AverageLeftVertexColorClassSize |
double | m_d_AverageRightVertexColorClassSize |
double | m_d_AverageVertexColorClassSize |
double | m_d_ColoringTime |
double | m_d_CheckingTime |
string | m_s_VertexColoringVariant |
vector< int > | m_vi_LeftVertexColorFrequency |
vector< int > | m_vi_RightVertexColorFrequency |
Private Member Functions | |
void | PresetCoveredVertexColors () |
int | CheckVertexColoring (string s_VertexColoringVariant) |
int | CalculateVertexColorClasses () |
int | FixMinimalCoverStarBicoloring () |
class BipartiteGraphBicoloring in group22.
Bipartite graph bicoloring is an assignment of colors to subsets of column and row vertices of the bipartite graph of a Jacobian matrix. The present version of ColPack provides methods for star bicoloring only. The distance-one coloring constraint is satisfied by all bicoloring algorithms by selecting colors for row and column vertices from two disjoint sets of colors. Sizes of the sets are equal to the number of row and column vertices respectively, which are the maximum number of colors that can be required by the row or column vertices.
In star bicoloring, vertex cover can be computed either explicitly or implicitly. An explicit vertex cover is computed and used to determine which vertices are to be colored. An implicit vertex cover is computed by including vertices as they get colored, into the cover and is used to determine the end of coloring as a vertex cover is reached. In both cases pre-computed vertex ordering determines the order in which vertices are colored. In implicit vertex cover, a vertex is not selected as a candidate vertex to be colored if no edge is incident on the vertex which has not been covered by any other colored vertex.
Definition at line 46 of file BipartiteGraphBicoloring.h.
Definition at line 352 of file BipartiteGraphBicoloring.cpp.
Definition at line 361 of file BipartiteGraphBicoloring.cpp.
int ColPack::BipartiteGraphBicoloring::CalculateVertexColorClasses | ( | ) | [private] |
int ColPack::BipartiteGraphBicoloring::CheckVertexColoring | ( | string | s_VertexColoringVariant | ) | [private] |
Definition at line 60 of file BipartiteGraphBicoloring.cpp.
void ColPack::BipartiteGraphBicoloring::Clear | ( | ) | [virtual] |
Reimplemented from ColPack::BipartiteGraphOrdering.
Reimplemented in ColPack::BipartiteGraphBicoloringInterface.
Definition at line 410 of file BipartiteGraphBicoloring.cpp.
References _UNKNOWN.
int ColPack::BipartiteGraphBicoloring::FixMinimalCoverStarBicoloring | ( | ) | [private] |
double ** ColPack::BipartiteGraphBicoloring::GetLeftSeedMatrix | ( | int * | ip1_SeedRowCount, |
int * | ip1_SeedColumnCount | ||
) |
Generate and return the Left Seed matrix. This Seed matrix is managed and freed by ColPack.
Precondition:
Postcondition:
Notes:
Reimplemented in ColPack::BipartiteGraphBicoloringInterface.
Definition at line 5461 of file BipartiteGraphBicoloring.cpp.
double ** ColPack::BipartiteGraphBicoloring::GetLeftSeedMatrix_unmanaged | ( | int * | ip1_SeedRowCount, |
int * | ip1_SeedColumnCount | ||
) |
Same as GetLeftSeedMatrix(), except that this Seed matrix is NOT managed by ColPack.
Notes:
Definition at line 5488 of file BipartiteGraphBicoloring.cpp.
Definition at line 5211 of file BipartiteGraphBicoloring.cpp.
Referenced by toFileBiC().
void ColPack::BipartiteGraphBicoloring::GetLeftVertexColors | ( | vector< int > & | output | ) |
Get the color IDs for the left vertices (rows). Color IDs start from 1, color ID 0 should be ignored.
Definition at line 5306 of file BipartiteGraphBicoloring.cpp.
Referenced by ColPack::JacobianRecovery2D::DirectRecover_CoordinateFormat_usermem(), ColPack::JacobianRecovery2D::DirectRecover_RowCompressedFormat_usermem(), ColPack::JacobianRecovery2D::DirectRecover_SparseSolversFormat_usermem(), and main().
double ** ColPack::BipartiteGraphBicoloring::GetRightSeedMatrix | ( | int * | ip1_SeedRowCount, |
int * | ip1_SeedColumnCount | ||
) |
Return the Right Seed matrix. This Seed matrix is managed and freed by ColPack.
Precondition:
Postcondition:
Notes:
Reimplemented in ColPack::BipartiteGraphBicoloringInterface.
Definition at line 5475 of file BipartiteGraphBicoloring.cpp.
double ** ColPack::BipartiteGraphBicoloring::GetRightSeedMatrix_unmanaged | ( | int * | ip1_SeedRowCount, |
int * | ip1_SeedColumnCount | ||
) |
Same as GetRightSeedMatrix(), except that this Seed matrix is NOT managed by ColPack.
Notes:
Definition at line 5524 of file BipartiteGraphBicoloring.cpp.
Definition at line 5217 of file BipartiteGraphBicoloring.cpp.
Referenced by ColPack::JacobianRecovery2D::DirectRecover_CoordinateFormat_usermem(), ColPack::JacobianRecovery2D::DirectRecover_RowCompressedFormat_usermem(), ColPack::JacobianRecovery2D::DirectRecover_SparseSolversFormat_usermem(), and toFileBiC().
void ColPack::BipartiteGraphBicoloring::GetRightVertexColors | ( | vector< int > & | output | ) |
Get the color IDs for the right vertices (columns). Color IDs start from (# of rows + 1), color ID (# of rows + # of columns + 1) should be ignored.
Definition at line 5313 of file BipartiteGraphBicoloring.cpp.
Referenced by main().
void ColPack::BipartiteGraphBicoloring::GetRightVertexColors_Transformed | ( | vector< int > & | output | ) |
Get the color IDs for the right vertices (columns) in the format similar to GetLeftVertexColor(). Color IDs start from 1, color ID 0 should be ignored.
Definition at line 5318 of file BipartiteGraphBicoloring.cpp.
Referenced by ColPack::JacobianRecovery2D::DirectRecover_CoordinateFormat_usermem(), ColPack::JacobianRecovery2D::DirectRecover_RowCompressedFormat_usermem(), and ColPack::JacobianRecovery2D::DirectRecover_SparseSolversFormat_usermem().
Definition at line 5236 of file BipartiteGraphBicoloring.cpp.
Referenced by ColPack::JacobianRecovery2D::DirectRecover_CoordinateFormat_usermem(), ColPack::JacobianRecovery2D::DirectRecover_RowCompressedFormat_usermem(), and ColPack::JacobianRecovery2D::DirectRecover_SparseSolversFormat_usermem().
void ColPack::BipartiteGraphBicoloring::GetSeedMatrix | ( | double *** | dp3_LeftSeed, |
int * | ip1_LeftSeedRowCount, | ||
int * | ip1_LeftSeedColumnCount, | ||
double *** | dp3_RightSeed, | ||
int * | ip1_RightSeedRowCount, | ||
int * | ip1_RightSeedColumnCount | ||
) |
Return both the Left and Right Seed matrix. These Seed matrices are managed and freed by ColPack.
Notes:
Definition at line 5565 of file BipartiteGraphBicoloring.cpp.
void ColPack::BipartiteGraphBicoloring::GetSeedMatrix_unmanaged | ( | double *** | dp3_LeftSeed, |
int * | ip1_LeftSeedRowCount, | ||
int * | ip1_LeftSeedColumnCount, | ||
double *** | dp3_RightSeed, | ||
int * | ip1_RightSeedRowCount, | ||
int * | ip1_RightSeedColumnCount | ||
) |
Same as GetSeedMatrix(), except that These Seed matrices are NOT managed by ColPack.
Notes:
Definition at line 5570 of file BipartiteGraphBicoloring.cpp.
Definition at line 5247 of file BipartiteGraphBicoloring.cpp.
Definition at line 5224 of file BipartiteGraphBicoloring.cpp.
Referenced by toFileBiC().
Definition at line 5561 of file BipartiteGraphBicoloring.cpp.
Referenced by toFileBiC().
Definition at line 5241 of file BipartiteGraphBicoloring.cpp.
Definition at line 5231 of file BipartiteGraphBicoloring.cpp.
void ColPack::BipartiteGraphBicoloring::PresetCoveredVertexColors | ( | ) | [private] |
Definition at line 28 of file BipartiteGraphBicoloring.cpp.
Definition at line 5332 of file BipartiteGraphBicoloring.cpp.
Definition at line 5439 of file BipartiteGraphBicoloring.cpp.
References ColPack::StringTokenizer::GetLastToken(), and STEP_DOWN.
Referenced by main().
Definition at line 5397 of file BipartiteGraphBicoloring.cpp.
References ColPack::StringTokenizer::GetLastToken(), and STEP_UP.
Referenced by main().
void ColPack::BipartiteGraphBicoloring::Reset | ( | ) | [virtual] |
Reimplemented from ColPack::BipartiteGraphOrdering.
Reimplemented in ColPack::BipartiteGraphBicoloringInterface.
Definition at line 461 of file BipartiteGraphBicoloring.cpp.
References _UNKNOWN.
void ColPack::BipartiteGraphBicoloring::Seed_init | ( | ) | [protected] |
Definition at line 368 of file BipartiteGraphBicoloring.cpp.
void ColPack::BipartiteGraphBicoloring::Seed_reset | ( | ) | [protected] |
Definition at line 378 of file BipartiteGraphBicoloring.cpp.
References free_2DMatrix().
double** ColPack::BipartiteGraphBicoloring::dp2_lSeed [protected] |
Definition at line 158 of file BipartiteGraphBicoloring.h.
double** ColPack::BipartiteGraphBicoloring::dp2_rSeed [protected] |
Definition at line 162 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::i_LeftVertexDefaultColor [protected] |
Whether or not color 0 is used for left vertices.
i_LeftVertexDefaultColor ==
Definition at line 123 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::i_lseed_rowCount [protected] |
Definition at line 157 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::i_RightVertexDefaultColor [protected] |
Whether or not color 0 is used for right vertices.
i_RightVertexDefaultColor ==
Definition at line 130 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::i_rseed_rowCount [protected] |
Definition at line 161 of file BipartiteGraphBicoloring.h.
bool ColPack::BipartiteGraphBicoloring::lseed_available [protected] |
Definition at line 156 of file BipartiteGraphBicoloring.h.
double ColPack::BipartiteGraphBicoloring::m_d_AverageLeftVertexColorClassSize [protected] |
Definition at line 205 of file BipartiteGraphBicoloring.h.
double ColPack::BipartiteGraphBicoloring::m_d_AverageRightVertexColorClassSize [protected] |
Definition at line 206 of file BipartiteGraphBicoloring.h.
double ColPack::BipartiteGraphBicoloring::m_d_AverageVertexColorClassSize [protected] |
Definition at line 207 of file BipartiteGraphBicoloring.h.
double ColPack::BipartiteGraphBicoloring::m_d_CheckingTime [protected] |
Definition at line 210 of file BipartiteGraphBicoloring.h.
double ColPack::BipartiteGraphBicoloring::m_d_ColoringTime [protected] |
Definition at line 209 of file BipartiteGraphBicoloring.h.
Definition at line 187 of file BipartiteGraphBicoloring.h.
Definition at line 190 of file BipartiteGraphBicoloring.h.
Definition at line 188 of file BipartiteGraphBicoloring.h.
Definition at line 191 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::m_i_LargestVertexColorClass [protected] |
Definition at line 199 of file BipartiteGraphBicoloring.h.
Definition at line 202 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::m_i_LeftVertexColorCount [protected] |
The number of colors used to color Left Vertices.
Note: Color 0 is also counted if used. If color 0 is used, i_LeftVertexDefaultColor will be set to 1.
Definition at line 136 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::m_i_RightVertexColorCount [protected] |
The number of colors used to color Right Vertices.
Note: Color 0 (or actually (i_LeftVertexCount + i_RightVertexCount + 1)) is also counted if used. If color 0 is used, i_RightVertexDefaultColor will be set to 1.
Definition at line 142 of file BipartiteGraphBicoloring.h.
Definition at line 193 of file BipartiteGraphBicoloring.h.
Definition at line 196 of file BipartiteGraphBicoloring.h.
Definition at line 194 of file BipartiteGraphBicoloring.h.
Definition at line 197 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::m_i_SmallestVertexColorClass [protected] |
Definition at line 200 of file BipartiteGraphBicoloring.h.
Definition at line 203 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::m_i_VertexColorCount [protected] |
Definition at line 144 of file BipartiteGraphBicoloring.h.
int ColPack::BipartiteGraphBicoloring::m_i_ViolationCount [protected] |
Definition at line 183 of file BipartiteGraphBicoloring.h.
string ColPack::BipartiteGraphBicoloring::m_s_VertexColoringVariant [protected] |
Definition at line 212 of file BipartiteGraphBicoloring.h.
vector<int> ColPack::BipartiteGraphBicoloring::m_vi_LeftVertexColorFrequency [protected] |
Definition at line 214 of file BipartiteGraphBicoloring.h.
vector<int> ColPack::BipartiteGraphBicoloring::m_vi_LeftVertexColors [protected] |
The color IDs used to color the left vertices (rows).
Note: Color IDs start from 1, color ID 0 should be ignored
Definition at line 149 of file BipartiteGraphBicoloring.h.
vector<int> ColPack::BipartiteGraphBicoloring::m_vi_RightVertexColorFrequency [protected] |
Definition at line 215 of file BipartiteGraphBicoloring.h.
vector<int> ColPack::BipartiteGraphBicoloring::m_vi_RightVertexColors [protected] |
The color IDs used to color the right vertices (columns).
Note: Color IDs start from (# of rows + 1), color ID (# of rows + # of columns + 1), which is color 0, should be ignored
Definition at line 154 of file BipartiteGraphBicoloring.h.
bool ColPack::BipartiteGraphBicoloring::rseed_available [protected] |
Definition at line 160 of file BipartiteGraphBicoloring.h.