頂點着色由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() 

請注意，這是一個着色圖的貪婪技術，不一定給你的圖的最佳色彩。