创建集团图以确定独立集合 [英] Creating clique graph to determine independent set

问题描述

尝试将s-clique转换为s-independent集.下面是代码和最底层的"independent_set_decision(H，s)"函数是我正在努力解决的问题.我了解我需要创建图的补图，然后检查该图是否为集团.但是，我编写的函数未按预期创建图形.任何人都对该代码有什么问题有任何建议吗?

Trying to transform an s-clique into a s-independent set. Below is code and the function at the very bottom 'independent_set_decision(H,s)' is what I am struggling with. I understand that I need to create a complement of the graph and then check if that graph is a clique. However, the function I wrote isn't creating the graph as intended. Anyone have any advice please on what's wrong with that code?

# 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)

推荐答案

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

您的图形表示形式不代表具有非1值的缺失链接.它表示根本不包括相关的dict条目，从而丢失了链接.遍历所有节点而不是仅遍历那些具有链接的节点，并检查node2是否为H[node1]中的键:

Your graph representation doesn't represent missing links with a non-1 value. It represents that a link is missing by not including the relevant dict entries at all. Iterate over all nodes instead of just the ones that have links, and check whether node2 is a key in H[node1]:

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

这篇关于创建集团图以确定独立集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！