創建集團圖確定獨立集

Question

試圖將一個s集團轉變爲一個獨立集。下面是代碼，最底層的'independent_set_decision（H，s）'的功能就是我正在努力的。我知道我需要創建一個圖的補充，然後檢查該圖是否是一個團。但是，我寫的函數並不是按照預期創建圖。任何人有任何建議，請問該代碼有什麼問題？

# Returns a list of all the subsets of a list of size k 
def k_subsets(lst, k): 
    if len(lst) < k: 
     return [] 
    if len(lst) == k: 
     return [lst] 
    if k == 1: 
     return [[i] for i in lst] 
    return k_subsets(lst[1:],k) + map(lambda x: x + [lst[0]], k_subsets(lst[1:], k-1)) 

# Checks if the given list of nodes forms a clique in the given graph. 
def is_clique(G, nodes): 
    for pair in k_subsets(nodes, 2): 
     if pair[1] not in G[pair[0]]: 
      return False 
    return True 

# Determines if there is clique of size k or greater in the given graph. 
def k_clique_decision(G, k): 
    nodes = G.keys() 
    for i in range(k, len(nodes) + 1): 
     for subset in k_subsets(nodes, i): 
      if is_clique(G, subset): 
       return True 
    return False 

def make_link(G, node1, node2): 
    if node1 not in G: 
     G[node1] = {} 
    (G[node1])[node2] = 1 
    if node2 not in G: 
     G[node2] = {} 
    (G[node2])[node1] = 1 
    return G 

def break_link(G, node1, node2): 
    if node1 not in G: 
     print "error: breaking link in a non-existent node" 
     return 
    if node2 not in G: 
     print "error: breaking link in a non-existent node" 
     return 
    if node2 not in G[node1]: 
     print "error: breaking non-existent link" 
     return 
    if node1 not in G[node2]: 
     print "error: breaking non-existent link" 
     return 
    del G[node1][node2] 
    del G[node2][node1] 
    return G 

# This function should use the k_clique_decision function 
# to solve the independent set decision problem 
def independent_set_decision(H, s): 
    nodes = H.keys() 
    I = {} 
    for node1 in nodes: 
     for node2 in H[node1]: 
      if (H[node1])[node2] != 1: 
       make_link(I,node1,node2) 

    return k_clique_decision(I, s) 

Answer 1

  if (H[node1])[node2] != 1: 

你的圖形表示並不代表與非1值的缺失環節。它表示由於沒有包含相關詞典條目而缺少鏈接。遍歷所有節點，而不是僅僅是有聯繫的那些，並檢查是否node2在H[node1]關鍵：

for node1 in H: 
    for node2 in H: 
     if node2 not in H[node1]: 
      make_link(I, node1, node2)