python - python 的顶点着色 - 色数 X(G)

Question

我正在尝试用 python 编写一段小代码来为图顶点着色，并计算使用的颜色数量，以便没有两个连接的顶点具有相同的颜色。 这是我的代码，我不知道它有什么问题，有什么帮助吗？ 这不是作业!

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()

colors = ['Red', 'Blue', 'Green', 'Yellow',  'Black','Pink','Orange','White','Gray','Purpul','Brown','Navy']

G.nodes = [1,2,3,4,5]
G.edges= [{1,5},{1,3},{1,2},{1,4},{4,5}]
colors_of_nodes={}

def coloring(node, color):
   for neighbor in G.edges:
       color_of_neighbor = colors_of_nodes(neighbor)
       if color_of_neighbor == color:
          return False

   return True

def get_color_for_node(node):
    for color in colors:
       if coloring(node, color):
          return color

def main():
    for node in G.nodes:
        colors_of_nodes[node] = get_color_for_node(node)

    print colors_of_nodes


main()

Answer 1

此代码中存在多个问题:

1. 小拼写错误 Purpul -> Purple
2. 语法错误:colors_of_nodes是一个字典，因此它不能作为函数调用。所以colors_of_nodes(neighbor)将失败。您可以通过两种方式索引字典 colors_of_nodes[node]或colors_of_nodes.get(node, default_value_if_node_is_not_a_key) 。你想做第二个。
3. 逻辑错误:邻居被设置为边缘值而不是节点。您想要循环遍历邻居节点或特定节点。幸运的是，networkx 有一个简单的函数:G.neighbors(node) 。此外，边缘是 set不可散列，因此不能是字典键。
4. 语义错误:您没有使用正确的语义来创建和访问 networkx 图。看the website for networkx 。 G.add_nodes_from([1,2,3,4,5]) , G.add_edges_from([(1,2),(1,3),(1,4),(1,5),(4,5)]) , G.nodes()

下面是您编辑后的工作格式代码。

作者 = '布伦特'

import networkx as nx
import matplotlib.pyplot as plt
G=nx.Graph()

colors = ['Red', 'Blue', 'Green', 'Yellow',  'Black', 'Pink', 'Orange', 'White', 'Gray', 'Purple', 'Brown', 'Navy']

G.add_nodes_from([1,2,3,4,5])
G.add_edges_from([(1,5),(1,3),(1,2),(1,4),(4,5)])
colors_of_nodes={}


def coloring(node, color):
   for neighbor in G.neighbors(node):
       color_of_neighbor = colors_of_nodes.get(neighbor, None)
       if color_of_neighbor == color:
          return False

   return True

def get_color_for_node(node):
    for color in colors:
       if coloring(node, color):
          return color

def main():
    for node in G.nodes():
        colors_of_nodes[node] = get_color_for_node(node)

    print colors_of_nodes


main()

请注意，这是一种为图形着色的贪婪技术，并不一定能为您提供最佳的图形着色。