Partitioning problems that arise in the efficient computation of
sparse Jacobian or Hessian matrices using Automatic Differentiation or
Finite Differencing can be modeled using specialized vertex coloring
problems on appropriate graph representations.  

Listing of important functions:

COLPACK.GraphInputOutput Class:

int ReadMatrixMarketAdjacencyGraph(string)
int ReadMatrixMarketAdjacencyGraphStructure(string)
int ReadHarwellBoeingAdjacencyGraph(string)
int ReadMeTiSAdjacencyGraph(string)
int PrintGraph()
int PrintGraphStructure()
int PrintMatrix()
int PrintMatrix(vector<int> \&, vector<int> \&, vector<double> \&)
void PrintVertexDegrees()

COLPACK.GraphOrdering Class:

NaturalOrdering()
LargestFirstOrdering()
DynamicLargestFirstOrdering()
DistanceTwoLargestFirstOrdering()
SmallestLastOrdering()
DistanceTwoSmallestLastOrdering()
IncidenceDegreeOrdering()
DistanceTwoIncidenceDegreeOrdering()

COLPACK.GraphColoring Class:

DistanceOneColoring()
DistanceTwoColoring()
NaiveStarColoring()
RestrictedStarColoring()
StarColoring()
AcyclicColoring()
TriangularColoring()
ModifiedTriangularColoring()
CheckStarColoring()
CheckAcyclicColoring()
CheckTriangularColoring()


COLPACK.BipartiteGraphBicoloring Class:

ExplicitCoveringStarBicoloring()
ExplicitCoveringModifiedStarBicoloring()
ImplicitCoveringConservativeStarBicoloring()
ImplicitCoveringGreedyStarBicoloring()
ImplicitCoveringRestrictedGreedyStarBicoloring()
ImplicitCoveringStarBicoloring()
CheckStarBicoloring()
ImplicitCoveringAcyclicBicoloring()
CheckAcyclicBicoloring()

COLPACK.GraphColoringInterface Class:
DistanceOneColoring(string)
DistanceTwoColoring(string)
NaiveStarColoring(string)
RestrictedStarColoring(string)
StarColoring(string)
AcyclicColoring(string)
ModifiedTriangularColoring(string)
CompareVertexColorsWithNaturalOrdering()
CompareVertexColorsWithLargestFirstOrdering()
CompareVertexColorsWithDynamicLargestFirstOrdering()
CompareVertexColorsWithDistanceTwoLargestFirstOrdering()
CompareVertexColorsWithSmallestLastOrdering()
CompareVertexColorsWithDistanceTwoSmallestLastOrdering()
CompareVertexColorsWithIncidenceDegreeOrdering()
CompareVertexColorsWithDistanceTwoIncidenceDegreeOrdering()
CompareVertexOrdersWithDistanceOneColoring()
CompareVertexOrdersWithDistanceTwoColoring()
CompareVertexOrdersWithNaiveStarColoring()
CompareVertexOrdersWithRestrictedStarColoring()
CompareVertexOrdersWithStarColoring()
CompareVertexOrdersWithAcyclicColoring()
CompareVertexOrdersWithModifiedTriangularColoring()

COLPACK.BipartiteGraphInputOutput Class:
ReadMatrixMarketBipartiteGraph(string)
ReadHarwellBoeingBipartiteGraph(string)
ReadMeTiSBipartiteGraph(string)

COLPACK.BipartiteGraphPartialOrdering Class:
RowNaturalOrdering()
ColumnNaturalOrdering()
RowLargestFirstOrdering()
ColumnLargestFirstOrdering()
RowSmallestLastOrdering()
ColumnSmallestLastOrdering()
RowIncidenceDegreeOrdering()
ColumnIncidenceDegreeOrdering()

COLPACK.BipartiteGraphPartialColoring Class:
PartialDistanceTwoRowColoring()
PartialDistanceTwoRowColoring()

COLPACK.BipartiteGraphOrdering Class:
NaturalOrdering()
LargestFirstOrdering()
DynamicLargestFirstOrdering()
SmallestLastOrdering()
IncidenceDegreeOrdering()
SelectiveLargestFirstOrdering()
SelectiveSmallestLastOrdering()
SelectiveIncidenceOrdering()

COLPACK.BipartiteGraphCovering Class:
CoverVertex()

COLPACK.BipartiteGraphBicoloring Class:
ExplicitCoveringStarBicoloring()
ExplicitCoveringModifiedStarBicoloring()
ImplicitCoveringStarBicoloring()
ImplicitCoveringConservativeStarBicoloring()
ImplicitCoveringGreedyStarBicoloring()
ImplicitCoveringRestrictedStarBicoloring()
ImplicitCoveringAcyclicBicoloring()
CheckStarBicoloring()
CheckAcyclicBicoloring()

COLPACK.Timer Class:
void Start()
void Stop()
double GetWallTime()
double GetProcessorTime()
double GetUserTime()
double GetSystemTime()

COLPACK.DisjointSets Class:
int Find(int)
int FindAndCompress(int)
int Union(int, int)
int UnionBySize(int, int)
int UnionByRank(int, int)
int Count()

COLPACK.StringTokenizer Class:
string GetFirstToken()
string GetNextToken()
string GetLastToken()
int CountTokens()
int HasMoreTokens()


COLPACK.HessianMatrix Class:
int ComputeHessianMatrixFromHarwellBoeingGraph(string)
int ComputeHessianMatrixFromMatrixMarketGraph(string)
int ComputeHessianMatrixFromMeTiSGraph(string)