greedy_color#
- greedy_color(G, strategy='largest_first', interchange=False)[源代码]#
使用贪婪图着色的各种策略为图着色。
试图用尽可能少的颜色给图形上色,在这种情况下,节点的相邻节点不能与节点本身具有相同的颜色。给定的策略确定节点的颜色顺序。
The strategies are described in [1], and smallest-last is based on [2].
- 参数
- G网络X图表
- strategy字符串或函数(G,颜色)
提供着色策略的函数(或表示函数的字符串),方法是按照节点应该着色的顺序返回节点。
G
是图表,并且colors
是当前指定颜色的字典,按节点设置关键字。中的所有节点返回一个迭代数G
。如果策略函数是迭代器生成器(即
yield
声明),记住colors
字典将在每个之后更新yield
,因为此函数贪婪地选择颜色。如果
strategy
是一个字符串,它必须是下面的其中一个字符串,每个字符串表示一个内置的策略函数。'largest_first'
'random_sequential'
'smallest_last'
'independent_set'
'connected_sequential_bfs'
'connected_sequential_dfs'
'connected_sequential'
(以前策略的别名)'saturation_largest_first'
'DSATUR'
(以前策略的别名)
- interchange: bool
将使用由描述的颜色交换算法 [3] 如果设置为
True
。注意
saturation_largest_first
和independent_set
不要使用交换。此外,如果使用具有自己策略功能的交换,则不能依赖colors
参数。
- 返回
- 具有表示节点的键和表示的值的字典
- 相应的颜色。
- 加薪
- NetworkXPointlessConcept
如果
strategy
是saturation_largest_first
或independent_set
和interchange
是True
。
工具书类
- 1
Adrian Kosowski和Krzysztof Manuszewski,《图形的经典着色》,图形着色,2004年2月19日。国际标准书号0-8218-3458-4。
- 2
David W.Matula和Leland L.Beck,“最小的最后排序和聚类以及图着色算法。” J.ACM 30,3(1983年7月),417–427。<https://doi.org/10.1145/2402.322385>
- 3
Maciej M.Sys_o,Marsingh Deo,Janusz S.Kowalik,《带Pascal程序的离散优化算法》,415-424,1983年。国际标准书号0-486-45353-7。
实例
>>> 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