greedy_color(G, strategy='largest_first', interchange=False)
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 , and smallest-last is based on .
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)
'saturation_largest_first'
'DSATUR'
(alias for the previous strategy)
Will use the color interchange algorithm described by if set to True
.
Note that saturation_largest_first
and 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.
If strategy
is saturation_largest_first
or independent_set
and interchange
is True
.
Color a graph using various strategies of greedy graph coloring.
>>> G = nx.cycle_graph(4)See :
... 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
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.coloring.greedy_coloring.greedy_color
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them