顶点着色由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

你应该发布你得到的错误，你的期望和实际发生的事情。

最低限度，这样的：

color_of_neighbor = colors_of_nodes(neighbor) 

将引发TypeError: 'dict' object is not callable错误。

Answer 2

多种问题在这段代码：

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不可散列therther不能是字典键。
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() 

请注意，这是一个着色图的贪婪技术，不一定给你的图的最佳色彩。