#include <GraphOrdering.h>

Inheritance diagram for ColPack::GraphOrdering:

Collaboration diagram for ColPack::GraphOrdering:

Public Member Functions
int	GetMaxBackDegree ()
	Calculate and return the Maximum Back degree.
int	OrderVertices (string s_OrderingVariant)
int	CheckVertexOrdering ()
	Test and make sure that the ordering is valid. Return 0 if the ordering is invalid, 1 if the ordering is valid.
	GraphOrdering ()
	~GraphOrdering ()
virtual void	Clear ()
void	ClearOrderingONLY ()
int	NaturalOrdering ()
int	RandomOrdering ()
int	ColoringBasedOrdering (vector< int > &vi_VertexColors)
int	LargestFirstOrdering ()
int	DistanceTwoLargestFirstOrdering ()
int	DynamicLargestFirstOrdering ()
int	DistanceTwoDynamicLargestFirstOrdering ()
int	SmallestLastOrdering ()
int	SmallestLastOrdering_serial ()
int	DistanceTwoSmallestLastOrdering ()
int	IncidenceDegreeOrdering ()
int	DistanceTwoIncidenceDegreeOrdering ()
string	GetVertexOrderingVariant ()
void	GetOrderedVertices (vector< int > &output)
vector< int > *	GetOrderedVerticesPtr ()
void	PrintVertexOrdering ()
double	GetVertexOrderingTime ()
Protected Attributes
double	m_d_OrderingTime
string	m_s_VertexOrderingVariant
vector< int >	m_vi_OrderedVertices
Private Member Functions
int	GetBackDegree (int index)
	Get Back Degree of vertex m_vi_OrderedVertices[index].
int	CheckVertexOrdering (string s_VertexOrderingVariant)
int	printVertexEdgeMap (vector< vector< pair< int, int > > > &vvpii_VertexEdgeMap)

Detailed Description

class GraphOrdering in group1.

This class stores the ordered vertices as a vector of vertex identifiers to be used by coloring methods.

Definition at line 33 of file GraphOrdering.h.

Constructor & Destructor Documentation

ColPack::GraphOrdering::GraphOrdering ( )

Definition at line 113 of file GraphOrdering.cpp.

References Clear().

Here is the call graph for this function:

ColPack::GraphOrdering::~GraphOrdering ( )

Definition at line 120 of file GraphOrdering.cpp.

References Clear().

Here is the call graph for this function:

Member Function Documentation

int ColPack::GraphOrdering::CheckVertexOrdering ( )

Test and make sure that the ordering is valid. Return 0 if the ordering is invalid, 1 if the ordering is valid.

This routine will test for:

Duplicated vertices. If there is no duplicated vertex, this ordering is probably ok.
Invalid vertex #. The vertex # should be between 0 and ordering.size()

Actually make a call to "bool isValidOrdering(vector<int> & ordering, int offset = 0);"

Definition at line 92 of file GraphOrdering.cpp.

References isValidOrdering().

Referenced by DistanceTwoDynamicLargestFirstOrdering(), DistanceTwoIncidenceDegreeOrdering(), DistanceTwoLargestFirstOrdering(), DistanceTwoSmallestLastOrdering(), DynamicLargestFirstOrdering(), IncidenceDegreeOrdering(), LargestFirstOrdering(), NaturalOrdering(), RandomOrdering(), and SmallestLastOrdering_serial().

Here is the call graph for this function:

Here is the caller graph for this function:

int ColPack::GraphOrdering::CheckVertexOrdering ( string s_VertexOrderingVariant ) [private]

Definition at line 97 of file GraphOrdering.cpp.

References _FALSE, and _TRUE.

void ColPack::GraphOrdering::Clear ( ) [virtual]

Reimplemented from ColPack::GraphInputOutput.

Reimplemented in ColPack::GraphColoring, and ColPack::GraphColoringInterface.

Definition at line 127 of file GraphOrdering.cpp.

References _UNKNOWN, m_d_OrderingTime, m_s_VertexOrderingVariant, and m_vi_OrderedVertices.

Referenced by GraphOrdering(), and ~GraphOrdering().

Here is the caller graph for this function:

void ColPack::GraphOrdering::ClearOrderingONLY ( )

Definition at line 139 of file GraphOrdering.cpp.

References _UNKNOWN, m_d_OrderingTime, m_s_VertexOrderingVariant, and m_vi_OrderedVertices.

int ColPack::GraphOrdering::ColoringBasedOrdering ( vector< int > & vi_VertexColors )

Definition at line 227 of file GraphOrdering.cpp.

References _FALSE, _TRUE, m_s_VertexOrderingVariant, m_vi_OrderedVertices, ColPack::GraphCore::m_vi_Vertices, Pause(), STEP_DOWN, and STEP_UP.

Referenced by toFileC_forColoringBasedOrdering().

Here is the call graph for this function:

Here is the caller graph for this function:

int ColPack::GraphOrdering::DistanceTwoDynamicLargestFirstOrdering ( )

Definition at line 820 of file GraphOrdering.cpp.

References _FALSE, _TRUE, _UNKNOWN, CheckVertexOrdering(), ColPack::GraphCore::m_vi_Edges, m_vi_OrderedVertices, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

Here is the call graph for this function:

int ColPack::GraphOrdering::DistanceTwoIncidenceDegreeOrdering ( )

Definition at line 1378 of file GraphOrdering.cpp.

References _FALSE, _TRUE, _UNKNOWN, CheckVertexOrdering(), ColPack::GraphCore::m_vi_Edges, m_vi_OrderedVertices, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

Here is the call graph for this function:

int ColPack::GraphOrdering::DistanceTwoLargestFirstOrdering ( )

Definition at line 590 of file GraphOrdering.cpp.

References _FALSE, _TRUE, _UNKNOWN, CheckVertexOrdering(), ColPack::GraphCore::m_vi_Edges, m_vi_OrderedVertices, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

Here is the call graph for this function:

int ColPack::GraphOrdering::DistanceTwoSmallestLastOrdering ( )

Definition at line 1015 of file GraphOrdering.cpp.

References _FALSE, _TRUE, _UNKNOWN, CheckVertexOrdering(), ColPack::GraphCore::m_vi_Edges, m_vi_OrderedVertices, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

Here is the call graph for this function:

int ColPack::GraphOrdering::DynamicLargestFirstOrdering ( )

Definition at line 373 of file GraphOrdering.cpp.

References _FALSE, _TRUE, _UNKNOWN, CheckVertexOrdering(), ColPack::GraphCore::m_vi_Edges, m_vi_OrderedVertices, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

Here is the call graph for this function:

int ColPack::GraphOrdering::GetBackDegree ( int index ) [private]

Get Back Degree of vertex m_vi_OrderedVertices[index].

Precondition: OrderVertices() has been called, i.e. m_vi_OrderedVertices has been populated

Note: This function is written quickly so it is not optimal

int ColPack::GraphOrdering::GetMaxBackDegree ( )

Calculate and return the Maximum Back degree.

Precondition: OrderVertices() has been called, i.e. m_vi_OrderedVertices has been populated Note: Back degree of a vertex is the degree of that vertex in the subgraph consisting of vertices that had been ordered (i.e., the vertices that are ordered before the current vertex). Depend on the ordering style, each vertex in vector m_vi_OrderedVertices may have different Back degree. The Maximum Back degree of all vertices in the graph will be returned. This is the UPPER BOUND for the number of colors needed to D1-color the graph.

Definition at line 1609 of file GraphOrdering.cpp.

References ColPack::GraphCore::m_vi_Edges, m_vi_OrderedVertices, and ColPack::GraphCore::m_vi_Vertices.

Referenced by toFileC(), and toFileC_forColoringBasedOrdering().

Here is the caller graph for this function: