ColPack
ColPack::GraphOrdering Class Reference

class GraphOrdering in group1. More...

#include <GraphOrdering.h>

Inheritance diagram for ColPack::GraphOrdering:
Collaboration diagram for ColPack::GraphOrdering:

List of all members.

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

Definition at line 113 of file GraphOrdering.cpp.

References Clear().

Here is the call graph for this function:

Definition at line 120 of file GraphOrdering.cpp.

References Clear().

Here is the call graph for this function:


Member Function Documentation

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:

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::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

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:

void ColPack::GraphOrdering::GetOrderedVertices ( vector< int > &  output)

Reimplemented in ColPack::GraphColoringInterface.

Definition at line 1597 of file GraphOrdering.cpp.

References m_vi_OrderedVertices.

Definition at line 129 of file GraphOrdering.h.

Definition at line 1604 of file GraphOrdering.cpp.

References m_d_OrderingTime.

Referenced by toFileC(), and toFileC_forColoringBasedOrdering().

Here is the caller graph for this function:

Definition at line 151 of file GraphOrdering.cpp.

References _TRUE, CheckVertexOrdering(), m_vi_OrderedVertices, ColPack::GraphCore::m_vi_Vertices, and STEP_DOWN.

Here is the call graph for this function:

int ColPack::GraphOrdering::OrderVertices ( string  s_OrderingVariant)

Definition at line 28 of file GraphOrdering.cpp.

References _TRUE, and toUpper().

Here is the call graph for this function:

int ColPack::GraphOrdering::printVertexEdgeMap ( vector< vector< pair< int, int > > > &  vvpii_VertexEdgeMap) [private]

Definition at line 339 of file GraphOrdering.cpp.

References _TRUE.

Definition at line 672 of file GraphOrdering.cpp.

References SmallestLastOrdering_serial().

Referenced by ColPack::GraphColoring::TriangularColoring().

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 678 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.

Referenced by SmallestLastOrdering().

Here is the call graph for this function:

Here is the caller graph for this function:


Member Data Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines