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_firstindependent_set 不要使用交换。此外,如果使用具有自己策略功能的交换,则不能依赖 colors 参数。

返回
具有表示节点的键和表示的值的字典
相应的颜色。
加薪
NetworkXPointlessConcept

如果 strategysaturation_largest_firstindependent_setinterchangeTrue

工具书类

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