Zoltan User's Guide  |  Next  |  Previous

Coloring Algorithms

The following coloring algorithms are currently included in the Zoltan library:

Parallel Coloring
They are accessed through calls to Zoltan_Color.


Coloring Parameters

While the overall behavior of Zoltan is controlled by general Zoltan parameters, the behavior of each coloring method is controlled by parameters specific to coloring which are also set by calls to Zoltan_Set_Param. These parameters are described below.
 
Parameters:
  COLORING_PROBLEM The specific coloring problem to be solved. Supported values include "DISTANCE-1" (the standard vertex coloring problem), "DISTANCE-2" (useful for Jacobian coloring) and "PARTIAL-DISTANCE-2". When called with "PARTIAL-DISTANCE-2", only the objects listed in global_ids (paramter of Zoltan_Color function) are colored. "BIPARTITE" is an alternative name for "PARTIAL-DISTANCE-2".
  SUPERSTEP_SIZE Number of local objects to be colored on each processor before exchanging color information. SUPERSTEP_SIZE should be greater than 0.
  COMM_PATTERN Valid values are "S" (synchronous) and "A" (asynchronous). If synchronous communication is selected, processors are forced to wait for the color information from all other processors to be received before proceeding with coloring of the next SUPERSTEP_SIZE number of local objects. If asynchronous communication is selected, there is no such restriction.
  VERTEX_VISIT_ORDER Valid values are "I" (internal first), "B" (boundary first) and "U" (unordered), "N" (natural), "L" (largest degree first), "S" (smallest degree last). If "I" is selected, each processor colors its internal objects before boundary objects. If "B" is selected, each processor colors its boundary objects first. If "U" is selected, there is no such distinction between internal and boundary objects. "N" is equivalent to "U". If "L" is selected, the objects are sorted according to their number of neighbors so that the object with larger number of neighbors are colored first. If "S" is selected, the order is dynamically constructed; the object with smallest number of neighbors will be colored last and is temporarily removed from the graph. This process repeats itself until all objects are ordered.
  RECOLORING_NUM_OF_ITERATIONS Number of distance-1 recoloring iterations to be performed after first coloring phase. A value of zero disables recoloring.
  RECOLORING_TYPE Valid values are "SYNCHRONOUS" and "ASYNCHRONOUS". If "SYNCHRONOUS" is selected, each processor waits for its neighboors to finish processing one color before processing the next one. If "ASYNCHRONOUS" is selected, each processor itself recolors all of its vertices in specified order, independent from other processors. It is then necessary to detect and resolve conflicts.
  RECOLORING_PERMUTATION Valid values are "FORWARD", "REVERSE", "NONDECREASING" and "NONINCREASING". The "FORWARD" permutation orders the colors in increasing order of their color identifiers. The "REVERSE" permutation is the opposite one. The "NONDECREASING" orders the colors in non-decreasing order of the number of time the colors are used in the whole graph. In other words, the less used colors are colored first. "NONINCREASING" is the opposite of "NONDECREASING".
  Options for graph build See more informations about graph build options on this page
Default Values:
COLORING_PROBLEM = DISTANCE-1
SUPERSTEP_SIZE = 100
COMM_PATTERN = S
VERTEX_VISIT_ORDER = I
RECOLORING_NUM_OF _ITERATIONS = 0
RECOLORING_TYPE = SYNCHRONOUS
RECOLORING_PERMUTATION = NONDECREASING


[Table of Contents  | Next:  Parallel Coloring  |  Previous:  Nested Dissection by ParMETIS  |  Privacy and Security]