ColPack
ColPack::GraphColoring Class Reference

class GraphColoring in group1. More...

#include <GraphColoring.h>

Inheritance diagram for ColPack::GraphColoring:
Collaboration diagram for ColPack::GraphColoring:

List of all members.

Classes

struct  Colors2Edge_Value
struct  lt_pii

Public Member Functions

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.
double ** GetSeedMatrix_unmanaged (int *ip1_SeedRowCount, int *ip1_SeedColumnCount)
 Same as GetSeedMatrix(), except that this Seed matrix is NOT managed by ColPack.
int CheckQuickDistanceTwoColoring (int Verbose=0)
 Quick check to see if DistanceTwoColoring() ran correctly.
int CheckDistanceTwoColoring (int Verbose=0)
 Check to see if DistanceTwoColoring() ran correctly.
int CalculateVertexColorClasses ()
void SetStringVertexColoringVariant (string s)
void SetVertexColorCount (int i_VertexColorCount)
 GraphColoring ()
 ~GraphColoring ()
virtual void Clear ()
void ClearColoringONLY ()
int DistanceOneColoring ()
int DistanceTwoColoring ()
int NaiveStarColoring ()
int RestrictedStarColoring ()
 Star Coloring with an additional restriction.
int StarColoring_serial ()
int StarColoring_serial2 ()
int StarColoring ()
int BuildStarCollection (vector< int > &vi_VerticesToBeRecolored)
 Build the collection of 2-color star from the coloring result.
int PrintStarCollection (vector< int > &vi_EdgeStarMap, vector< int > &vi_StarHubMap, map< int, map< int, int > > &mimi2_VertexEdgeMap)
int DetectConflictInColorCombination (int i_MaxNumThreads, int i_thread_num, pair< int, int > pii_ColorCombination, map< pair< int, int >, Colors2Edge_Value, lt_pii > *Colors2Edge_Private, map< int, vector< pair< int, int > > > *Vertex2ColorCombination_Private, map< int, int > *PotentialHub_Private, vector< pair< int, int > > *ConflictedEdges_Private, vector< int > *ConflictCount_Private)
 Build the collection of 2-color star from the coloring result.
int BuildStarFromColorCombination (int i_MaxNumThreads, int i_thread_num, pair< int, int > pii_ColorCombination, map< pair< int, int >, Colors2Edge_Value, lt_pii > *Colors2Edge_Private, map< int, vector< pair< int, int > > > *Vertex2ColorCombination_Private, map< int, int > *PotentialHub_Private)
 This function assume that there is no conflicts in the color assignment.
int BuildVertex2ColorCombination (int i_MaxNumThreads, map< int, vector< pair< int, int > > > *Vertex2ColorCombination_Private, vector< map< int, int > > *Vertex2ColorCombination)
 Build Vertex2ColorCombination from Vertex2ColorCombination_Private.
int CheckStarColoring_OMP (int i_Mode, pair< int, int > *pii_ConflictColorCombination)
int BuildStarFromColorCombination_forChecking (int i_Mode, int i_MaxNumThreads, int i_thread_num, pair< int, int > pii_ColorCombination, map< pair< int, int >, Colors2Edge_Value, lt_pii > *Colors2Edge_Private, map< int, int > *PotentialHub_Private)
int BuildForbiddenColors (int i_MaxNumThreads, int i_thread_num, int i_CurrentVertex, map< int, bool > *mip_ForbiddenColors, map< int, int > *D1Colors, vector< map< int, int > > *Vertex2ColorCombination)
int PrintVertex2ColorCombination (vector< map< int, int > > *Vertex2ColorCombination)
int PrintVertex2ColorCombination_raw (vector< map< int, int > > *Vertex2ColorCombination)
int PrintVertexAndColorAdded (int i_MaxNumThreads, vector< pair< int, int > > *vi_VertexAndColorAdded, int i_LastNEntries=999999999)
int PrintForbiddenColors (map< int, bool > *mip_ForbiddenColors, int i_thread_num)
int PickVerticesToBeRecolored (int i_MaxNumThreads, vector< pair< int, int > > *ConflictedEdges_Private, vector< int > &ConflictCount)
int PrintAllColorCombination (map< pair< int, int >, Colors2Edge_Value, lt_pii > *Colors2Edge_Private, int i_MaxNumThreads, int i_MaxNumOfCombination=1000000, int i_MaxElementsOfCombination=100000)
int PrintColorCombination (map< pair< int, int >, Colors2Edge_Value, lt_pii > *Colors2Edge_Private, int i_MaxNumThreads, pair< int, int > pii_ColorCombination, int i_MaxElementsOfCombination=100000)
int PrintPotentialHub (map< int, int > *PotentialHub_Private, int i_thread_num, pair< int, int > pii_ColorCombination)
int PrintConflictEdges (vector< pair< int, int > > *ConflictedEdges_Private, int i_MaxNumThreads)
int PrintConflictCount (vector< int > &ConflictCount)
int PrintVertex2ColorCombination (int i_MaxNumThreads, map< int, vector< pair< int, int > > > *Vertex2ColorCombination_Private)
int PrintD1Colors (map< int, int > *D1Colors, int i_thread_num)
int PrintVertexColorCombination (map< int, int > *VertexColorCombination)
int BuildSubGraph (map< int, map< int, bool > > *graph, int i_CenterVertex, int distance=1, map< int, bool > *mib_FilterByColors=NULL)
 Note: FDP and CIRCO are the 2 good filters to display this subgraph.
int BuildConnectedSubGraph (map< int, map< int, bool > > *graph, int i_CenterVertex, int distance=1, map< int, bool > *mib_FilterByColors=NULL)
int BuildColorsSubGraph (map< int, map< int, bool > > *graph, map< int, bool > *mib_Colors)
int PrintSubGraph (map< int, map< int, bool > > *graph)
int PrintVertexD1NeighborAndColor (int VertexIndex, int excludedVertex=-1)
int FindDistance (int v1, int v2)
int StarColoring (vector< int > &, vector< int > &, map< int, map< int, int > > &)
int CheckStarColoring ()
int GetStarColoringConflicts (vector< vector< int > > &ListOfConflicts)
int AcyclicColoring ()
int AcyclicColoring (vector< int > &, map< int, vector< int > > &)
int AcyclicColoring_ForIndirectRecovery ()
int CheckAcyclicColoring ()
int TriangularColoring ()
int ModifiedTriangularColoring ()
int CheckTriangularColoring ()
string GetVertexColoringVariant ()
void SetVertexColoringVariant (string s_VertexColoringVariant)
int GetVertexColorCount ()
void GetVertexColors (vector< int > &output)
vector< int > * GetVertexColorsPtr ()
int GetHubCount ()
int GetSetCount ()
double GetVertexColoringTime ()
double GetVertexColoringCheckingTime ()
int PrintVertexColors ()
int FileVertexColors ()
int PrintVertexColoringMetrics ()
int FileVertexColoringMetrics ()
void PrintVertexColorClasses ()

Public Attributes

ofstream fout
int i_ProcessedEdgeCount

Protected Member Functions

void Seed_init ()
void Seed_reset ()

Protected Attributes

int m_i_VertexColorCount
int m_i_LargestColorClass
int m_i_SmallestColorClass
int m_i_LargestColorClassSize
int m_i_SmallestColorClassSize
double m_d_AverageColorClassSize
double m_d_ColoringTime
double m_d_CheckingTime
string m_s_VertexColoringVariant
vector< int > m_vi_VertexColors
vector< int > m_vi_VertexColorFrequency
bool seed_available
int i_seed_rowCount
double ** dp2_Seed

Private Member Functions

int FindCycle (int, int, int, int, vector< int > &, vector< int > &, vector< int > &)
int UpdateSet (int, int, int, map< int, map< int, int > > &, vector< int > &, vector< int > &, vector< int > &)
int SearchDepthFirst (int, int, int, vector< int > &)
int CheckVertexColoring (string s_GraphColoringVariant)

Private Attributes

int m_i_ColoringUnits

Detailed Description

class GraphColoring in group1.

Graph coloring is an assignment of consecutive integral numbers (each representing a color) to vertices, edges or faces or a combination of two or more of these objects of a graph such that it satisfes one or more constraints. The present version of ColPack provides methods for vertex coloring only. The minimum number of vertex colors required to color a graph is known as the chromatic number of the graph. The problem of finding the chromatic number for even a planar graph is NP-hard. ColPack features some of the most efficient approximation algorithms available to date for some of the vertex coloring problems.

Definition at line 38 of file GraphColoring.h.


Constructor & Destructor Documentation

Definition at line 239 of file GraphColoring.cpp.

References Clear(), and Seed_init().

Here is the call graph for this function:

Definition at line 248 of file GraphColoring.cpp.

References Clear(), and Seed_reset().

Here is the call graph for this function:


Member Function Documentation

int ColPack::GraphColoring::BuildColorsSubGraph ( map< int, map< int, bool > > *  graph,
map< int, bool > *  mib_Colors 
)

Sample code: map< int, map<int,bool> > *graph = new map< int, map<int,bool> >; map<int, bool> *mib_Colors = new map<int, bool>; (*mib_Colors)[m_vi_VertexColors[i_CurrentVertex]]=true; (*mib_Colors)[color2]=true; (*mib_Colors)[color3]=true;

BuildSubGraph(graph, mib_Colors);

vector<int> vi_VertexColors; GetVertexColors(vi_VertexColors); displayGraph(graph, &vi_VertexColors, true, FDP); delete graph;

Definition at line 1667 of file GraphColoring.cpp.

References _FALSE, _TRUE, ColPack::GraphCore::m_vi_Edges, m_vi_VertexColors, and ColPack::GraphCore::m_vi_Vertices.

Referenced by BuildStarFromColorCombination_forChecking().

Here is the caller graph for this function:

int ColPack::GraphColoring::BuildConnectedSubGraph ( map< int, map< int, bool > > *  graph,
int  i_CenterVertex,
int  distance = 1,
map< int, bool > *  mib_FilterByColors = NULL 
)

Sample code: (see function int BuildSubGraph() )

Definition at line 1777 of file GraphColoring.cpp.

References _TRUE, ColPack::GraphCore::m_vi_Edges, m_vi_VertexColors, and ColPack::GraphCore::m_vi_Vertices.

int ColPack::GraphColoring::BuildForbiddenColors ( int  i_MaxNumThreads,
int  i_thread_num,
int  i_CurrentVertex,
map< int, bool > *  mip_ForbiddenColors,
map< int, int > *  D1Colors,
vector< map< int, int > > *  Vertex2ColorCombination 
)

Definition at line 1866 of file GraphColoring.cpp.

References _UNKNOWN, ColPack::GraphCore::m_vi_Edges, m_vi_VertexColors, ColPack::GraphCore::m_vi_Vertices, and PrintD1Colors().

Here is the call graph for this function:

int ColPack::GraphColoring::BuildStarCollection ( vector< int > &  vi_VerticesToBeRecolored)

Build the collection of 2-color star from the coloring result.

NOTE: At this point, this routine will not work correctly if there are conflicts

Definition at line 2302 of file GraphColoring.cpp.

References _FALSE, _TRUE, _UNKNOWN, ColPack::GraphCore::m_vi_Edges, m_vi_VertexColors, ColPack::GraphCore::m_vi_Vertices, PrintStarCollection(), PrintVertexColors(), and STEP_UP.

Here is the call graph for this function:

int ColPack::GraphColoring::BuildStarFromColorCombination ( int  i_MaxNumThreads,
int  i_thread_num,
pair< int, int >  pii_ColorCombination,
map< pair< int, int >, Colors2Edge_Value, lt_pii > *  Colors2Edge_Private,
map< int, vector< pair< int, int > > > *  Vertex2ColorCombination_Private,
map< int, int > *  PotentialHub_Private 
)

This function assume that there is no conflicts in the color assignment.

Definition at line 1016 of file GraphColoring.cpp.

References m_vi_VertexColors, ColPack::GraphCore::m_vi_Vertices, Pause(), PrintColorCombination(), PrintPotentialHub(), ColPack::CoutLock::set(), and ColPack::CoutLock::unset().

Here is the call graph for this function:

int ColPack::GraphColoring::BuildStarFromColorCombination_forChecking ( int  i_Mode,
int  i_MaxNumThreads,
int  i_thread_num,
pair< int, int >  pii_ColorCombination,
map< pair< int, int >, Colors2Edge_Value, lt_pii > *  Colors2Edge_Private,
map< int, int > *  PotentialHub_Private 
)

Definition at line 703 of file GraphColoring.cpp.

References BuildColorsSubGraph(), displayGraph(), FDP, GetVertexColors(), m_vi_VertexColors, Pause(), PrintColorCombination(), PrintPotentialHub(), ColPack::CoutLock::set(), and ColPack::CoutLock::unset().

Referenced by CheckStarColoring_OMP().

Here is the call graph for this function:

Here is the caller graph for this function:

int ColPack::GraphColoring::BuildSubGraph ( map< int, map< int, bool > > *  graph,
int  i_CenterVertex,
int  distance = 1,
map< int, bool > *  mib_FilterByColors = NULL 
)

Note: FDP and CIRCO are the 2 good filters to display this subgraph.

Sample code: map< int, map<int,bool> > *graph = new map< int, map<int,bool> >; map<int, bool> *mib_FilterByColors = new map<int, bool>; (*mib_FilterByColors)[m_vi_VertexColors[i_CurrentVertex]]=true; (*mib_FilterByColors)[color2]=true; (*mib_FilterByColors)[color3]=true;

BuildSubGraph(graph, i_CurrentVertex, 2, mib_FilterByColors);

vector<int> vi_VertexColors; GetVertexColors(vi_VertexColors); displayGraph(graph, &vi_VertexColors, true, FDP); delete graph;

Definition at line 1702 of file GraphColoring.cpp.

References _TRUE, ColPack::GraphCore::m_vi_Edges, m_vi_VertexColors, and ColPack::GraphCore::m_vi_Vertices.

int ColPack::GraphColoring::BuildVertex2ColorCombination ( int  i_MaxNumThreads,
map< int, vector< pair< int, int > > > *  Vertex2ColorCombination_Private,
vector< map< int, int > > *  Vertex2ColorCombination 
)

Build Vertex2ColorCombination from Vertex2ColorCombination_Private.

This process is done in parallel After Vertex2ColorCombination is built, Vertex2ColorCombination_Private will be deallocated

Definition at line 1526 of file GraphColoring.cpp.

References _TRUE, and ColPack::GraphCore::m_vi_Vertices.

Reimplemented in ColPack::GraphColoringInterface.

Definition at line 188 of file GraphColoring.cpp.

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

Referenced by PrintVertexColorClasses().

Here is the caller graph for this function:

Definition at line 5009 of file GraphColoring.cpp.

References _FALSE, _TRUE, ColPack::GraphCore::m_vi_Vertices, SearchDepthFirst(), and STEP_DOWN.

Referenced by CheckTriangularColoring().

Here is the call graph for this function:

Here is the caller graph for this function:

Check to see if DistanceTwoColoring() ran correctly.

100% accurate but slow. For a quick check, use CheckQuickDistanceTwoColoring().

Return value:

Precondition: DistanceTwoColoring() has been run.

Parameter: int Verbose

  • If Verbose == 0, this function will silently return after the first error is detected.
  • If Verbose == 1, this function will print out the error message and return after the first error is detected.
  • If Verbose == 2, this function will print out all the errors and then return.

Definition at line 6000 of file GraphColoring.cpp.

References ColPack::GraphCore::m_vi_Edges, m_vi_VertexColors, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

Quick check to see if DistanceTwoColoring() ran correctly.

Return value:

IMPORTANT: This is the quick check so if CheckQuickDistanceTwoColoring() return 1, then DistanceTwoColoring() definitely ran INcorrectly. However, when CheckQuickDistanceTwoColoring() return 0, it doesn't mean that DistanceTwoColoring() ran correctly (it may, it may not). To be 100% sure, use CheckDistanceTwoColoring()

Precondition: DistanceTwoColoring() has been run.

Parameter: int Verbose

  • If Verbose == 0, this function only check and see if m_i_MaximumVertexDegree <= m_i_VertexColorCount + 1.
  • If Verbose == 1, this function will print out the vertex with m_i_MaximumVertexDegree where the error can be detected.
  • If Verbose == 2, this function will print out all the errors (violations) and then return.

Algorithm:

Definition at line 5961 of file GraphColoring.cpp.

References ColPack::GraphCore::m_i_MaximumVertexDegree, m_i_VertexColorCount, ColPack::GraphCore::m_vi_Edges, m_vi_VertexColors, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

int ColPack::GraphColoring::CheckStarColoring_OMP ( int  i_Mode,
pair< int, int > *  pii_ConflictColorCombination 
)

Definition at line 5280 of file GraphColoring.cpp.

References CheckAcyclicColoring().

Here is the call graph for this function:

int ColPack::GraphColoring::DetectConflictInColorCombination ( int  i_MaxNumThreads,
int  i_thread_num,
pair< int, int >  pii_ColorCombination,
map< pair< int, int >, Colors2Edge_Value, lt_pii > *  Colors2Edge_Private,
map< int, vector< pair< int, int > > > *  Vertex2ColorCombination_Private,
map< int, int > *  PotentialHub_Private,
vector< pair< int, int > > *  ConflictedEdges_Private,
vector< int > *  ConflictCount_Private 
)

Build the collection of 2-color star from the coloring result.

This function also helps us identify a list of vertices need to be recolored if conlict is detected If vi_VerticesToBeRecolored.size() == 0, then the coloring is a valid star coloring. The algorithm is done in parallel

This function will go through 2-color combination, attemp to build stars and identify conflict edges. Conflict edges will be pushed into (thread private) ConflictedEdges. ConflictCount of each vertex will be increased accordingly

Definition at line 1138 of file GraphColoring.cpp.

References _TRUE, fout, and ColPack::GraphCore::m_vi_Vertices.

int ColPack::GraphColoring::FindCycle ( int  i_Vertex,
int  i_AdjacentVertex,
int  i_DistanceOneVertex,
int  i_SetID,
vector< int > &  vi_CandidateColors,
vector< int > &  vi_FirstVisitedOne,
vector< int > &  vi_FirstVisitedTwo 
) [private]

Definition at line 28 of file GraphColoring.cpp.

References _TRUE, _UNKNOWN, and STEP_UP.

Referenced by AcyclicColoring(), and AcyclicColoring_ForIndirectRecovery().

Here is the caller graph for this function:

Definition at line 5313 of file GraphColoring.cpp.

References _UNKNOWN, CheckVertexColoring(), and m_i_ColoringUnits.

Here is the call graph for this function:

double ** ColPack::GraphColoring::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 in ColPack::GraphColoringInterface.

Definition at line 5909 of file GraphColoring.cpp.

References dp2_Seed, GetSeedMatrix_unmanaged(), i_seed_rowCount, seed_available, and Seed_reset().

Here is the call graph for this function:

double ** ColPack::GraphColoring::GetSeedMatrix_unmanaged ( int *  ip1_SeedRowCount,
int *  ip1_SeedColumnCount 
)

Same as GetSeedMatrix(), 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 5920 of file GraphColoring.cpp.

References m_i_VertexColorCount, and m_vi_VertexColors.

Referenced by GetSeedMatrix().

Here is the caller graph for this function:

Definition at line 5327 of file GraphColoring.cpp.

References _UNKNOWN, CheckVertexColoring(), and m_i_ColoringUnits.

Here is the call graph for this function:

int ColPack::GraphColoring::GetStarColoringConflicts ( vector< vector< int > > &  ListOfConflicts)

Definition at line 3196 of file GraphColoring.cpp.

References _FALSE, ColPack::GraphCore::m_vi_Edges, m_vi_VertexColors, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

Referenced by buildDotWithColor().

Here is the caller graph for this function:

Definition at line 5340 of file GraphColoring.cpp.

References m_d_ColoringTime.

Referenced by toFileC(), and toFileC_forColoringBasedOrdering().

Here is the caller graph for this function:

vector<int>* ColPack::GraphColoring::GetVertexColorsPtr ( ) [inline]

Definition at line 361 of file GraphColoring.h.

int ColPack::GraphColoring::PickVerticesToBeRecolored ( int  i_MaxNumThreads,
vector< pair< int, int > > *  ConflictedEdges_Private,
vector< int > &  ConflictCount 
)

Definition at line 1428 of file GraphColoring.cpp.

References _TRUE, _UNKNOWN, fout, and m_vi_VertexColors.

int ColPack::GraphColoring::PrintAllColorCombination ( map< pair< int, int >, Colors2Edge_Value, lt_pii > *  Colors2Edge_Private,
int  i_MaxNumThreads,
int  i_MaxNumOfCombination = 1000000,
int  i_MaxElementsOfCombination = 100000 
)

Definition at line 1330 of file GraphColoring.cpp.

References _TRUE.

int ColPack::GraphColoring::PrintColorCombination ( map< pair< int, int >, Colors2Edge_Value, lt_pii > *  Colors2Edge_Private,
int  i_MaxNumThreads,
pair< int, int >  pii_ColorCombination,
int  i_MaxElementsOfCombination = 100000 
)

Definition at line 1302 of file GraphColoring.cpp.

Referenced by BuildStarFromColorCombination(), BuildStarFromColorCombination_forChecking(), and CheckStarColoring_OMP().

Here is the caller graph for this function:

int ColPack::GraphColoring::PrintConflictCount ( vector< int > &  ConflictCount)

Definition at line 1418 of file GraphColoring.cpp.

References _TRUE.

int ColPack::GraphColoring::PrintConflictEdges ( vector< pair< int, int > > *  ConflictedEdges_Private,
int  i_MaxNumThreads 
)

Definition at line 1406 of file GraphColoring.cpp.

References _TRUE.

int ColPack::GraphColoring::PrintD1Colors ( map< int, int > *  D1Colors,
int  i_thread_num 
)

Definition at line 1562 of file GraphColoring.cpp.

Referenced by BuildForbiddenColors(), and StarColoring_serial2().

Here is the caller graph for this function:

int ColPack::GraphColoring::PrintForbiddenColors ( map< int, bool > *  mip_ForbiddenColors,
int  i_thread_num 
)

Definition at line 1571 of file GraphColoring.cpp.

Referenced by StarColoring_serial2().

Here is the caller graph for this function:

int ColPack::GraphColoring::PrintPotentialHub ( map< int, int > *  PotentialHub_Private,
int  i_thread_num,
pair< int, int >  pii_ColorCombination 
)

Definition at line 680 of file GraphColoring.cpp.

References m_vi_VertexColors.

Referenced by BuildStarFromColorCombination(), and BuildStarFromColorCombination_forChecking().

Here is the caller graph for this function:

int ColPack::GraphColoring::PrintStarCollection ( vector< int > &  vi_EdgeStarMap,
vector< int > &  vi_StarHubMap,
map< int, map< int, int > > &  mimi2_VertexEdgeMap 
)

Definition at line 2458 of file GraphColoring.cpp.

References _TRUE, ColPack::GraphCore::m_vi_Edges, ColPack::GraphCore::m_vi_Vertices, and STEP_UP.

Referenced by BuildStarCollection().

Here is the caller graph for this function:

int ColPack::GraphColoring::PrintSubGraph ( map< int, map< int, bool > > *  graph)

Definition at line 1580 of file GraphColoring.cpp.

int ColPack::GraphColoring::PrintVertex2ColorCombination ( vector< map< int, int > > *  Vertex2ColorCombination)

Definition at line 2261 of file GraphColoring.cpp.

References m_vi_VertexColors.

int ColPack::GraphColoring::PrintVertex2ColorCombination ( int  i_MaxNumThreads,
map< int, vector< pair< int, int > > > *  Vertex2ColorCombination_Private 
)
int ColPack::GraphColoring::PrintVertex2ColorCombination_raw ( vector< map< int, int > > *  Vertex2ColorCombination)

Definition at line 2280 of file GraphColoring.cpp.

References m_vi_VertexColors.

int ColPack::GraphColoring::PrintVertexAndColorAdded ( int  i_MaxNumThreads,
vector< pair< int, int > > *  vi_VertexAndColorAdded,
int  i_LastNEntries = 999999999 
)

Definition at line 1846 of file GraphColoring.cpp.

int ColPack::GraphColoring::PrintVertexColorCombination ( map< int, int > *  VertexColorCombination)

Definition at line 659 of file GraphColoring.cpp.

References m_vi_VertexColors.

Star Coloring with an additional restriction.

The additional restriction: When we try to decide the color of a vertex:

  • If D1 neighbor has color id > D2 neighbor's color id, then that D2 neighbor's color is forbidden (the current vertex cannot use that color)
  • Else, we can just reuse the color of that D2 neighbor

Definition at line 570 of file GraphColoring.cpp.

References _TRUE, _UNKNOWN, CheckVertexColoring(), m_i_VertexColorCount, ColPack::GraphCore::m_vi_Edges, ColPack::GraphOrdering::m_vi_OrderedVertices, m_vi_VertexColors, ColPack::GraphCore::m_vi_Vertices, STEP_DOWN, and STEP_UP.

Here is the call graph for this function:

int ColPack::GraphColoring::SearchDepthFirst ( int  i_RootVertex,
int  i_ParentVertex,
int  i_Vertex,
vector< int > &  vi_TouchedVertices 
) [private]

Definition at line 96 of file GraphColoring.cpp.

References _FALSE, _TRUE, STEP_DOWN, and STEP_UP.

Referenced by CheckAcyclicColoring().

Here is the caller graph for this function:

void ColPack::GraphColoring::Seed_init ( ) [protected]

Definition at line 5943 of file GraphColoring.cpp.

References dp2_Seed, i_seed_rowCount, and seed_available.

Referenced by GraphColoring().

Here is the caller graph for this function:

void ColPack::GraphColoring::Seed_reset ( ) [protected]

Definition at line 5950 of file GraphColoring.cpp.

References dp2_Seed, free_2DMatrix(), i_seed_rowCount, and seed_available.

Referenced by GetSeedMatrix(), and ~GraphColoring().

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 6040 of file GraphColoring.cpp.

References m_s_VertexColoringVariant.

Referenced by toFileC_forColoringBasedOrdering().

Here is the caller graph for this function:

void ColPack::GraphColoring::SetVertexColorCount ( int  i_VertexColorCount)

Definition at line 6045 of file GraphColoring.cpp.

References m_i_VertexColorCount.

void ColPack::GraphColoring::SetVertexColoringVariant ( string  s_VertexColoringVariant)

Definition at line 5292 of file GraphColoring.cpp.

References m_s_VertexColoringVariant.

Definition at line 2292 of file GraphColoring.cpp.

References StarColoring_serial2().

Here is the call graph for this function:

int ColPack::GraphColoring::StarColoring ( vector< int > &  vi_StarHubMap,
vector< int > &  vi_EdgeStarMap,
map< int, map< int, int > > &  mimi2_VertexEdgeMap 
)
int ColPack::GraphColoring::UpdateSet ( int  i_Vertex,
int  i_AdjacentVertex,
int  i_DistanceOneVertex,
map< int, map< int, int > > &  mimi2_VertexEdgeMap,
vector< int > &  vi_FirstSeenOne,
vector< int > &  vi_FirstSeenTwo,
vector< int > &  vi_FirstSeenThree 
) [private]

Definition at line 61 of file GraphColoring.cpp.

References _UNKNOWN.

Referenced by AcyclicColoring(), and AcyclicColoring_ForIndirectRecovery().

Here is the caller graph for this function:


Member Data Documentation

double** ColPack::GraphColoring::dp2_Seed [protected]

Definition at line 148 of file GraphColoring.h.

Referenced by GetSeedMatrix(), Seed_init(), and Seed_reset().

Definition at line 147 of file GraphColoring.h.

Referenced by GetSeedMatrix(), Seed_init(), and Seed_reset().

Definition at line 144 of file GraphColoring.h.

Referenced by Clear(), ClearColoringONLY(), and PrintVertexColorClasses().

Definition at line 146 of file GraphColoring.h.

Referenced by GetSeedMatrix(), Seed_init(), and Seed_reset().

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines