The following coloring algorithms are currently included in the Zoltan library:
Parallel ColoringThey are accessed through calls to Zoltan_Color.
| 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 | |