ColPack::BipartiteGraphVertexCover Class Reference

class BipartiteGraphVertexCover in group22. More...

#include <BipartiteGraphVertexCover.h>

Inheritance diagram for ColPack::BipartiteGraphVertexCover:

Collaboration diagram for ColPack::BipartiteGraphVertexCover:

List of all members.

Public Member Functions
	BipartiteGraphVertexCover ()
	~BipartiteGraphVertexCover ()
virtual void	Clear ()
virtual void	Reset ()
int	CoverVertex ()
int	CoverVertex (vector< int > &)
int	CoverMinimalVertex ()
void	GetIncludedLeftVertices (vector< int > &output)
void	GetIncludedRightVertices (vector< int > &output)
void	GetCoveredLeftVertices (vector< int > &output)
void	GetCoveredRightVertices (vector< int > &output)
void	PrintBicoloringVertexCover ()
Protected Attributes
double	m_d_CoveringTime
vector< int >	m_vi_IncludedLeftVertices
vector< int >	m_vi_IncludedRightVertices
vector< int >	m_vi_CoveredLeftVertices
vector< int >	m_vi_CoveredRightVertices

---

Detailed Description

class BipartiteGraphVertexCover in group22.

The bipartite graph bicoloring algorithms included in ColPack are variations of greedy, star and acyclic bicolorings combined with explicit and implicit vertex coverings and guided by pre-computed vertex orderings. The row and column vertices are initalized with two default colors, which are generally the color 0 for row vertices and for column vertices the color equal to one more than the sum of the numbers of row and column vertices. The vertices whose colors are subsequently changed by the algorithms constitute a vertex cover for the bipartite graph. The goal is to get the smallest vertex cover that can be colored to conform to the bicoloring constraints. The computation of vertex cover has given rise to two types of algorithms, in one of which a specialized vertex cover is computed explicitly for consumption by bicoloring algorithms and in the other implicitly within the bicoloring algorithms. The bipartite graph covering class provides methods for explicitly computing these specialized vertex covers.

Definition at line 42 of file BipartiteGraphVertexCover.h.

---

Constructor & Destructor Documentation

ColPack::BipartiteGraphVertexCover::BipartiteGraphVertexCover

(

)

Definition at line 28 of file BipartiteGraphVertexCover.cpp.

ColPack::BipartiteGraphVertexCover::~BipartiteGraphVertexCover

(

)

Definition at line 35 of file BipartiteGraphVertexCover.cpp.

---

Member Function Documentation

void ColPack::BipartiteGraphVertexCover::Clear

(

)

[virtual]

Reimplemented from ColPack::BipartiteGraphInputOutput.

Reimplemented in ColPack::BipartiteGraphBicoloring, ColPack::BipartiteGraphBicoloringInterface, and ColPack::BipartiteGraphOrdering.

Definition at line 42 of file BipartiteGraphVertexCover.cpp.

References _UNKNOWN.

int ColPack::BipartiteGraphVertexCover::CoverMinimalVertex

(

)

Definition at line 1570 of file BipartiteGraphVertexCover.cpp.

References _FALSE, _TRUE, _UNKNOWN, STEP_DOWN, and STEP_UP.

int ColPack::BipartiteGraphVertexCover::CoverVertex

(

)

Definition at line 74 of file BipartiteGraphVertexCover.cpp.

References _FALSE, _TRUE, _UNKNOWN, STEP_DOWN, and STEP_UP.

int ColPack::BipartiteGraphVertexCover::CoverVertex

(

vector< int > &

vi_EdgeCodes

)

Definition at line 821 of file BipartiteGraphVertexCover.cpp.

References _FALSE, _TRUE, _UNKNOWN, STEP_DOWN, and STEP_UP.

void ColPack::BipartiteGraphVertexCover::GetCoveredLeftVertices

(

vector< int > &

output

)

Definition at line 2042 of file BipartiteGraphVertexCover.cpp.

void ColPack::BipartiteGraphVertexCover::GetCoveredRightVertices

(

vector< int > &

output

)

Definition at line 2049 of file BipartiteGraphVertexCover.cpp.

void ColPack::BipartiteGraphVertexCover::GetIncludedLeftVertices

(

vector< int > &

output

)

Definition at line 2029 of file BipartiteGraphVertexCover.cpp.

void ColPack::BipartiteGraphVertexCover::GetIncludedRightVertices

(

vector< int > &

output

)

Definition at line 2035 of file BipartiteGraphVertexCover.cpp.

void ColPack::BipartiteGraphVertexCover::PrintBicoloringVertexCover

(

)

Definition at line 1928 of file BipartiteGraphVertexCover.cpp.

References _FALSE, STEP_DOWN, and STEP_UP.

void ColPack::BipartiteGraphVertexCover::Reset

(

)

[virtual]

Reimplemented in ColPack::BipartiteGraphBicoloring, ColPack::BipartiteGraphBicoloringInterface, and ColPack::BipartiteGraphOrdering.

Definition at line 59 of file BipartiteGraphVertexCover.cpp.

References _UNKNOWN.

---

Member Data Documentation

double ColPack::BipartiteGraphVertexCover::m_d_CoveringTime [protected]

Definition at line 47 of file BipartiteGraphVertexCover.h.

vector<int> ColPack::BipartiteGraphVertexCover::m_vi_CoveredLeftVertices [protected]

Definition at line 52 of file BipartiteGraphVertexCover.h.

vector<int> ColPack::BipartiteGraphVertexCover::m_vi_CoveredRightVertices [protected]

Definition at line 53 of file BipartiteGraphVertexCover.h.

vector<int> ColPack::BipartiteGraphVertexCover::m_vi_IncludedLeftVertices [protected]

Definition at line 49 of file BipartiteGraphVertexCover.h.

vector<int> ColPack::BipartiteGraphVertexCover::m_vi_IncludedRightVertices [protected]

Definition at line 50 of file BipartiteGraphVertexCover.h.