ColPack
ColPack::GraphColoringInterface Class Reference

class GraphColoringInterface in group1. More...

#include <GraphColoringInterface.h>

Inheritance diagram for ColPack::GraphColoringInterface:
Collaboration diagram for ColPack::GraphColoringInterface:

List of all members.

Public Member Functions

 GraphColoringInterface (int i_type,...)
 Read graph structure and color the adjacency graph.
int Coloring (string s_OrderingVariant="NATURAL", string s_ColoringVariant="DISTANCE_ONE")
 Color the adjacency graph based on the requested s_ColoringVariant and s_OrderingVariant.
void GenerateSeedHessian (double ***dp3_seed, int *ip1_SeedRowCount, int *ip1_SeedColumnCount, string s_OrderingVariant="NATURAL", string s_ColoringVariant="STAR")
 Generate and return the seed matrix (OpenMP enabled for STAR coloring)
void GenerateSeedHessian_unmanaged (double ***dp3_seed, int *ip1_SeedRowCount, int *ip1_SeedColumnCount, string s_OrderingVariant="NATURAL", string s_ColoringVariant="STAR")
 Same as GenerateSeedHessian(), except that this Seed matrix is NOT managed by ColPack (OpenMP enabled for STAR coloring)
double ** GetSeedMatrix (int *ip1_SeedRowCount, int *ip1_SeedColumnCount)
 Return the Seed matrix based on existing coloring. This Seed matrix is managed and freed by ColPack.
void GetOrderedVertices (vector< int > &output)
int CalculateVertexColorClasses ()
 ~GraphColoringInterface ()
virtual void Clear ()
int DistanceOneColoring (string s_OrderingVariant)
int DistanceTwoColoring (string s_OrderingVariant)
int NaiveStarColoring (string s_OrderingVariant)
int RestrictedStarColoring (string s_OrderingVariant)
int StarColoring (string s_OrderingVariant)
int AcyclicColoring (string s_OrderingVariant)
int AcyclicColoring_ForIndirectRecovery (string s_OrderingVariant)
int TriangularColoring (string s_OrderingVariant)

Static Public Member Functions

static void PrintInducedVertexDegrees (int SetID, int i_HighestInducedVertexDegree, vector< list< int > > &vli_GroupedInducedVertexDegrees)
static void PrintVertexEdgeMap (vector< int > &vi_Vertices, vector< int > &vi_Edges, map< int, map< int, int > > &mimi2_VertexEdgeMap)

Private Attributes

Timer m_T_Timer

Detailed Description

class GraphColoringInterface in group1.

Definition at line 31 of file GraphColoringInterface.h.


Constructor & Destructor Documentation

Read graph structure and color the adjacency graph.

This function will:

  • 0. Create initial GraphColoringInterface object
  • 1. Create the adjacency graph based on the graph structure specified by the input source
  • 2. Order the vertices based on the requested Ordering Method (s_OrderingVariant)
  • 3. Color the graph based on the requested Coloring Method (s_ColoringVariant)
  • Ordering Time and Coloring Time will be recorded.

Structure of this variadic function's parameters: GraphColoringInterface(int i_type, [2 or more parameters for input source depending on the value of i_type], [char* s_OrderingVariant], [char* s_ColoringVariant]). Here are some examples:

  • Just create the GraphColoringInterface object: GraphColoringInterface(SRC_WAIT);
  • Just get the input from file without ordering and coloring: GraphColoringInterface(SRC_FILE, s_InputFile.c_str() ,"AUTO_DETECTED");
  • Get input from ADOLC and color the graph: GraphColoringInterface(SRC_MEM_ADOLC,uip2_SparsityPattern, i_rowCount);

About input parameters:

  • int i_type: specified the input source. i_type can be either:
    • -1 (SRC_WAIT): only step 0 will be done.
    • 0 (SRC_FILE): The graph structure will be read from file. The next 2 parameters are:
      • char* fileName: name of the input file for a symmetric matrix. If the full path is not given, the file is assumed to be in the current directory
      • char* fileType can be either:
    • 1 (SRC_MEM_ADOLC): The graph structure will be read from Row Compressed Structure (used by ADOLC). The next 2 parameters are:
      • unsigned int **uip2_SparsityPattern: The pattern of Hessian matrix stored in Row Compressed Format
      • int i_rowCount: number of rows in the Hessian matrix. Number of rows in uip2_SparsityPattern.
    • 2 (SRC_MEM_ADIC): TO BE IMPLEMENTED so that ColPack can interface with ADIC

!! add interface function that takes input from ADIC

Definition at line 28 of file GraphColoringInterface.cpp.

References SRC_FILE, SRC_MEM_ADIC, SRC_MEM_ADOLC, SRC_WAIT, and WriteMatrixMarket_ADOLCInput().

Here is the call graph for this function:


Member Function Documentation

int ColPack::GraphColoringInterface::AcyclicColoring ( string  s_OrderingVariant)

Definition at line 350 of file GraphColoringInterface.cpp.

References _TRUE.

Definition at line 319 of file GraphColoringInterface.cpp.

References _TRUE.

Reimplemented from ColPack::GraphColoring.

Definition at line 156 of file GraphColoringInterface.cpp.

int ColPack::GraphColoringInterface::Coloring ( string  s_OrderingVariant = "NATURAL",
string  s_ColoringVariant = "DISTANCE_ONE" 
)

Color the adjacency graph based on the requested s_ColoringVariant and s_OrderingVariant.

This function will

  • 1. Order the vertices based on the requested Ordering Method (s_OrderingVariant)
  • 2. Color the graph based on the requested Coloring Method (s_ColoringVariant)
  • Ordering Time and Coloring Time will be recorded.

About input parameters:

  • s_OrderingVariant can be either
    • "NATURAL" (default)
    • "LARGEST_FIRST"
    • "DYNAMIC_LARGEST_FIRST"
    • "DISTANCE_TWO_LARGEST_FIRST" (used primarily for DistanceTwoColoring and various StarColoring)
    • "SMALLEST_LAST"
    • "DISTANCE_TWO_SMALLEST_LAST" (used primarily for DistanceTwoColoring and various StarColoring)
    • "INCIDENCE_DEGREE"
    • "DISTANCE_TWO_INCIDENCE_DEGREE" (used primarily for DistanceTwoColoring and various StarColoring)
    • "RANDOM"
  • s_ColoringVariant can be either
    • "DISTANCE_ONE" (default)
    • "ACYCLIC"
    • "ACYCLIC_FOR_INDIRECT_RECOVERY"
    • "STAR"
    • "RESTRICTED_STAR"
    • "DISTANCE_TWO"

Postcondition:

  • The Graph is colored, i.e., m_vi_VertexColors will be populated.

Definition at line 535 of file GraphColoringInterface.cpp.

References _FALSE, and _TRUE.

Referenced by main(), toFileC(), and toFileC_forColoringBasedOrdering().

Here is the caller graph for this function:

int ColPack::GraphColoringInterface::DistanceOneColoring ( string  s_OrderingVariant)

Definition at line 164 of file GraphColoringInterface.cpp.

References _TRUE.

int ColPack::GraphColoringInterface::DistanceTwoColoring ( string  s_OrderingVariant)

Definition at line 195 of file GraphColoringInterface.cpp.

References _TRUE.

void ColPack::GraphColoringInterface::GenerateSeedHessian ( double ***  dp3_seed,
int *  ip1_SeedRowCount,
int *  ip1_SeedColumnCount,
string  s_OrderingVariant = "NATURAL",
string  s_ColoringVariant = "STAR" 
)

Generate and return the seed matrix (OpenMP enabled for STAR coloring)

This function will

  • 1. Color the graph based on the specified ordering and coloring
  • 2. Create and return the seed matrix (*dp3_seed) from the coloring information

About input parameters:

  • s_ColoringVariant can be either
    • "STAR" (default)
    • "RESTRICTED_STAR"
    • "ACYCLIC_FOR_INDIRECT_RECOVERY"
  • s_OrderingVariant can be either
    • "NATURAL" (default)
    • "LARGEST_FIRST"
    • "DYNAMIC_LARGEST_FIRST"
    • "DISTANCE_TWO_LARGEST_FIRST"
    • "SMALLEST_LAST"
    • "DISTANCE_TWO_SMALLEST_LAST"
    • "INCIDENCE_DEGREE"
    • "DISTANCE_TWO_INCIDENCE_DEGREE"
    • "RANDOM"

Postcondition:

  • *dp3_seed: [(*ip1_SeedRowCount) == num of cols of the original matrix == i_RowCount (because Hessian is a square matrix)] [(*ip1_SeedColumnCount) == ColorCount]

Definition at line 413 of file GraphColoringInterface.cpp.

void ColPack::GraphColoringInterface::GenerateSeedHessian_unmanaged ( double ***  dp3_seed,
int *  ip1_SeedRowCount,
int *  ip1_SeedColumnCount,
string  s_OrderingVariant = "NATURAL",
string  s_ColoringVariant = "STAR" 
)

Same as GenerateSeedHessian(), except that this Seed matrix is NOT managed by ColPack (OpenMP enabled for STAR coloring)

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 454 of file GraphColoringInterface.cpp.

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

Reimplemented from ColPack::GraphOrdering.

Definition at line 139 of file GraphColoringInterface.cpp.

double ** ColPack::GraphColoringInterface::GetSeedMatrix ( int *  ip1_SeedRowCount,
int *  ip1_SeedColumnCount 
)

Return the Seed matrix based on existing coloring. This Seed matrix is managed and freed by ColPack.

Precondition:

  • the Graph has been colored

Postcondition:

  • Size of the returned matrix is (*ip1_SeedRowCount) rows x (*ip1_SeedColumnCount) columns. (*ip1_SeedRowCount) == num of columns of the original matrix == GetVertexCount() (*ip1_SeedColumnCount) == num of colors used to color vertices == GetVertexColorCount().

Notes:

  • This Seed matrix is managed and automatically freed by ColPack when the Graph object is deleted. Therefore, the user should NOT attempt to free the Seed matrix again.

Reimplemented from ColPack::GraphColoring.

Definition at line 143 of file GraphColoringInterface.cpp.

Referenced by main().

Here is the caller graph for this function:

int ColPack::GraphColoringInterface::NaiveStarColoring ( string  s_OrderingVariant)

Definition at line 226 of file GraphColoringInterface.cpp.

References _TRUE.

void ColPack::GraphColoringInterface::PrintInducedVertexDegrees ( int  SetID,
int  i_HighestInducedVertexDegree,
vector< list< int > > &  vli_GroupedInducedVertexDegrees 
) [static]

Definition at line 495 of file GraphColoringInterface.cpp.

References _FALSE, STEP_DOWN, and STEP_UP.

void ColPack::GraphColoringInterface::PrintVertexEdgeMap ( vector< int > &  vi_Vertices,
vector< int > &  vi_Edges,
map< int, map< int, int > > &  mimi2_VertexEdgeMap 
) [static]

Definition at line 473 of file GraphColoringInterface.cpp.

References STEP_UP.

Definition at line 257 of file GraphColoringInterface.cpp.

References _TRUE.

int ColPack::GraphColoringInterface::StarColoring ( string  s_OrderingVariant)

Definition at line 288 of file GraphColoringInterface.cpp.

References _TRUE.

int ColPack::GraphColoringInterface::TriangularColoring ( string  s_OrderingVariant)

Definition at line 381 of file GraphColoringInterface.cpp.

References _TRUE.


Member Data Documentation

Definition at line 178 of file GraphColoringInterface.h.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines