ColPack
ColPack::BipartiteGraphBicoloring Class Reference

class BipartiteGraphBicoloring in group22. More...

#include <BipartiteGraphBicoloring.h>

Inheritance diagram for ColPack::BipartiteGraphBicoloring:
Collaboration diagram for ColPack::BipartiteGraphBicoloring:

List of all members.

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 ()

Detailed Description

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.


Constructor & Destructor Documentation


Member Function Documentation

Definition at line 5099 of file BipartiteGraphBicoloring.cpp.

References _FALSE, _TRUE, STEP_DOWN, and STEP_UP.

Referenced by main().

Here is the caller graph for this function:

int ColPack::BipartiteGraphBicoloring::CheckVertexColoring ( string  s_VertexColoringVariant) [private]

Definition at line 60 of file BipartiteGraphBicoloring.cpp.

References _FALSE, and _TRUE.

Reimplemented from ColPack::BipartiteGraphOrdering.

Reimplemented in ColPack::BipartiteGraphBicoloringInterface.

Definition at line 410 of file BipartiteGraphBicoloring.cpp.

References _UNKNOWN.

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:

  • the Graph has been Bicolored

Postcondition:

  • Size of the returned matrix is (*ip1_SeedRowCount) rows x (*ip1_SeedColumnCount) columns. (*ip1_SeedColumnCount) == num of rows of the original matrix == GetRowVertexCount() (*ip1_SeedRowCount) == num of colors used to color the left (row) vertices excluding color 0.

Notes:

  • Vertices with color 0 are ignored. That also means left (row) vertices with color 1 will be grouped together into the first row (row 0) of the seed matrix and so on.

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:

  • This Seed matrix is NOT managed by ColPack. Therefore, the user should free the Seed matrix manually when the matrix is no longer needed.

Definition at line 5488 of file BipartiteGraphBicoloring.cpp.

Definition at line 5211 of file BipartiteGraphBicoloring.cpp.

Referenced by toFileBiC().

Here is the caller graph for this function:

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().

Here is the caller graph for this function:

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:

  • the Graph has been Bicolored

Postcondition:

  • Size of the returned matrix is (*ip1_SeedRowCount) rows x (*ip1_SeedColumnCount) columns. (*ip1_SeedRowCount) == num of columns of the original matrix == GetColumnVertexCount() (*ip1_SeedColumnCount) == num of colors used to color the right (column) vertices excluding color 0.

Notes:

  • Vertices with color 0 are ignored. That also means right (column) vertices with color 1 will be grouped together into the first column (column 0) of the seed matrix and so on.

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:

  • This Seed matrix is NOT managed by ColPack. Therefore, the user should free the Seed matrix manually when the matrix is no longer needed.

Definition at line 5524 of file BipartiteGraphBicoloring.cpp.

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().

Here is the caller graph for this function:

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().

Here is the caller graph for this function:

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:

  • These Seed matrices are NOT managed by ColPack. Therefore, the user should free the Seed matrices manually when the matrices are no longer needed.

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:

  • These Seed matrices are NOT managed by ColPack. Therefore, the user should free the Seed matrices manually when the matrices are no longer needed.

Definition at line 5570 of file BipartiteGraphBicoloring.cpp.

Definition at line 5224 of file BipartiteGraphBicoloring.cpp.

Referenced by toFileBiC().

Here is the caller graph for this function:

Definition at line 5561 of file BipartiteGraphBicoloring.cpp.

Referenced by toFileBiC().

Here is the caller graph for this function:

Definition at line 5439 of file BipartiteGraphBicoloring.cpp.

References ColPack::StringTokenizer::GetLastToken(), and STEP_DOWN.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 5397 of file BipartiteGraphBicoloring.cpp.

References ColPack::StringTokenizer::GetLastToken(), and STEP_UP.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

Reimplemented from ColPack::BipartiteGraphOrdering.

Reimplemented in ColPack::BipartiteGraphBicoloringInterface.

Definition at line 461 of file BipartiteGraphBicoloring.cpp.

References _UNKNOWN.

Definition at line 368 of file BipartiteGraphBicoloring.cpp.

Definition at line 378 of file BipartiteGraphBicoloring.cpp.

References free_2DMatrix().

Here is the call graph for this function:


Member Data Documentation

Definition at line 158 of file BipartiteGraphBicoloring.h.

Definition at line 162 of file BipartiteGraphBicoloring.h.

Whether or not color 0 is used for left vertices.

i_LeftVertexDefaultColor ==

  • 0 if color 0 is not used
  • 1 if color 0 is used

Definition at line 123 of file BipartiteGraphBicoloring.h.

Whether or not color 0 is used for right vertices.

i_RightVertexDefaultColor ==

  • 0 if color 0 is not used
  • 1 if color 0 is used

Definition at line 130 of file BipartiteGraphBicoloring.h.

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.

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.

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.

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.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines