greedy_color¶
- 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 [1], and smallest-last is based on [2].
- Parameters
- GNetworkX graph
- strategystring 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, andcolors
is a dictionary of the currently assigned colors, keyed by nodes. The function must return an iterable over all the nodes inG
.If the strategy function is an iterator generator (that is, a function with
yield
statements), keep in mind that thecolors
dictionary will be updated after eachyield
, 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)'saturation_largest_first'
'DSATUR'
(alias for the previous strategy)
- interchange: bool
Will use the color interchange algorithm described by [3] if set to
True
.Note that
saturation_largest_first
andindependent_set
do not work with interchange. Furthermore, if you use interchange with your own strategy function, you cannot rely on the values in thecolors
argument.
- Returns
- A dictionary with keys representing nodes and values representing
- corresponding coloring.
- Raises
- NetworkXPointlessConcept
If
strategy
issaturation_largest_first
orindependent_set
andinterchange
isTrue
.
References
- 1
Adrian Kosowski, and Krzysztof Manuszewski, Classical Coloring of Graphs, Graph Colorings, 2-19, 2004. ISBN 0-8218-3458-4.
- 2
David W. Matula, and Leland L. Beck, “Smallest-last ordering and clustering and graph coloring algorithms.” J. ACM 30, 3 (July 1983), 417–427. <https://doi.org/10.1145/2402.322385>
- 3
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