networkx.algorithms.coloring.greedy_color

greedy_color(G, strategy='largest_first', interchange=False)[源代码]

使用贪婪图着色的各种策略为图着色。

试图用尽可能少的颜色给图形上色,在这种情况下,节点的相邻节点不能与节点本身具有相同的颜色。给定的策略确定节点的颜色顺序。

这些策略在 [1], 最小的最后一个是基于 [2].

参数:
  • GNETWorkX图

  • 策略字符串或函数(G,颜色) )--提供着色策略的函数(或表示函数的字符串),通过按顺序返回节点来着色。 G 是图表,和 colors 是当前分配的颜色的字典,由节点键控。函数必须在中的所有节点上返回ITerable G .

    如果策略函数是迭代器生成器(即 yield 声明),记住 colors 字典将在每个之后更新 yield ,因为此函数贪婪地选择颜色。

    如果 strategy 是一个字符串,它必须是下面的其中一个字符串,每个字符串表示一个内置的策略函数。

    • 'largest_first'
    • 'random_sequential'
    • 'smallest_last'
    • 'independent_set'
    • 'connected_sequential_bfs'
    • 'connected_sequential_dfs'
    • 'connected_sequential' (以前策略的别名)
    • 'strategy_saturation_largest_first'
    • 'DSATUR' (以前策略的别名)
  • 立交bool )--将使用下面描述的颜色交换算法 [3] 如果设置为 True .

    注意 strategy_saturation_largest_firststrategy_independent_set 不要使用交换。此外,如果使用具有自己策略功能的交换,则不能依赖 colors 争论。

返回:

  • 一种字典,其中键表示节点,值表示
  • 相应的颜色。

实际案例

>>> 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
加薪:NetworkXPointlessConcept ——如果 strategystrategy_saturation_largest_firststrategy_independent_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。