The Graph Color SOP assigns an integer value to each point or primitive. The coloring is built so that points or primitives that are directly connected will not have the same color.
Graph coloring is a hard problem, so this does not attempt an exact solution.
Graph colorings can be very useful for OpenCL algorithms as they can split the polygons and points into non-overlapping groups that can be operated on in parallel.
The integer attribute to create, if missing, and initialize to the color value.
How to determine if two points or two primitives are connected. This also implicitly determines if the attribute is a point or primitive attribute.
Two primitives are connected if they have any point in common. A primitive attribute is created.
Two points are connected if they both belong to the same primitive. A point attribute is created.
Two primitives are connected if they have a shared edge. This applies only for closed polygons. A primitive attribute is created.
Note that the "map coloring" problem corresponds to this mode.
Sort Output by Color
Sort the geometry so contiguous blocks have the same graph color.
Create Workset Attributes
Create a pair of detail attributes suitable for the OpenCL SOP to run over the groups in multiple passes using the workset mode.
Worksets Begin Attr.
This array attribute stores the index of the start of each unique color in the graph.
Worksets Length Attr.
This array attrib7ute stores the number of each unique color in the graph.
The greedy graph coloring algorithm usually terminates will before this number of iterations, so this acts mostly as an upper bound in case something goes wrong.