7.9.1. networkx.algorithms.coloring.greedy_color

networkx.algorithms.coloring.greedy_color(G, strategy='largest_first', interchange=False)[source]

Color a graph using various strategies of greedy graph coloring.

Attempts to color a graph using as few colors as possible, where no neighbours of a node can have same color as the node itself. The given strategy determines the order in which nodes are colored.

The strategies are described in [R565].

Parameters:

G : NetworkX graph

strategy : string or function(G, colors)

A function (or a string representing a function) that provides the coloring strategy, by returning nodes in the ordering they should be colored. G is the graph, and colors is a dictionary of the currently assigned colors, keyed by nodes. The function must return an iterable over all the nodes in G.

If the strategy function is an iterator generator (that is, a function with yield statements), keep in mind that the colors dictionary will be updated after each yield, since this function chooses colors greedily.

If strategy is a string, it must be one of the following, each of which represents one of the built-in strategy functions.

  • 'largest_first'
  • 'random_sequential'
  • 'smallest_last'
  • 'independent_set'
  • 'connected_sequential_bfs'
  • 'connected_sequential_dfs'
  • 'connected_sequential' (alias for the previous strategy)
  • 'strategy_saturation_largest_first'
  • 'DSATUR' (alias for the previous strategy)

interchange: bool

Will use the color interchange algorithm described by [R566] if set to True.

Note that strategy_saturation_largest_first and strategy_independent_set do not work with interchange. Furthermore, if you use interchange with your own strategy function, you cannot rely on the values in the colors argument.
Returns:

A dictionary with keys representing nodes and values representing

corresponding coloring.
Raises:

NetworkXPointlessConcept

If strategy is strategy_saturation_largest_first or strategy_independent_set and interchange is True.

References

[R565](1, 2) Adrian Kosowski, and Krzysztof Manuszewski, Classical Coloring of Graphs, Graph Colorings, 2-19, 2004. ISBN 0-8218-3458-4.
[R566](1, 2) Maciej M. Sysło, Marsingh Deo, Janusz S. Kowalik, Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983. ISBN 0-486-45353-7.

Examples

>>> G = nx.cycle_graph(4)
>>> d = nx.coloring.greedy_color(G, strategy='largest_first')
>>> d in [{0: 0, 1: 1, 2: 0, 3: 1}, {0: 1, 1: 0, 2: 1, 3: 0}]
True