turicreate.graph_coloring.create

turicreate.graph_coloring.create(graph, verbose=True)

Compute the graph coloring. Assign a color to each vertex such that no adjacent vertices have the same color. Return a model object with total number of colors used as well as the color ID for each vertex in the graph. This algorithm is greedy and is not guaranteed to find the minimum graph coloring. It is also not deterministic, so successive runs may return different answers.

Parameters:

graph : SGraph

The graph on which to compute the coloring.

verbose : bool, optional

If True, print progress updates.

Returns:

out : GraphColoringModel

See also

GraphColoringModel

References

• Wikipedia - graph coloring

Examples

If given an SGraph g, we can create a GraphColoringModel as follows:

>>> g = turicreate.load_sgraph('http://snap.stanford.edu/data/email-Enron.txt.gz', format='snap')
>>> gc = turicreate.graph_coloring.create(g)

We can obtain the color id corresponding to each vertex in the graph g as follows:

>>> color_id = gc['color_id']  # SFrame

We can obtain the total number of colors required to color the graph g as follows:

>>> num_colors = gc['num_colors']