如何在不使用networkx包的情况下检查字典是否表示图形？

Question

以下是一些示例词典：

G = {0:[1,2], 1:[0], 2:[0]}
V = {0:[0,2], 1:[0], 2:[0]}
W = {0:[1,2], 1:[4], 2:[0]}
X = {0:[2], 1:[0], 2:[0]}
Y = [2,3,4]

为了检查它们是否表示一个图，我试图检查没有节点将自身作为邻居，列为邻居的唯一事物是有效的节点，如果a将b作为邻居，那么b也将a作为邻居，并且所有对象都具有适当的类型

def IsItAGraph(D):
    if type(D) is dict:
        for x in D.keys():
            if x not in D[x]:
                for y in D[x]:
                    if y in D.keys():
                        if y in D[x]:
                            if x in D[y]:
                                return True
                            else:
                                return False
                    else:
                       return False
            else:
                return False
    else:
        return False

N = [IsItAGraph(Y), IsItAGraph(G), IsItAGraph(V), IsItAGraph(W), IsItAGraph(X)]

当我把它作为输入发送时，作为输出，我得到字典的True和所有其他的X和False，除了G之外，我应该得到所有的False

我做错了什么

Answer 1

您可以编写一个函数来检查每个需求

def valid_graph(g):
    for key, value in g.items():
        # Is key correct type
        if not isinstance(key, (int, str)):
            return False

        # Are all values correct type
        if not isinstance(value, list):
            return False
        
        if not all(isinstance(i, int) for i in value):
            return False

        # Do all values refer to a key in the graph
        if not all(i in g.keys() for i in value):
            return False

        # Do any keys have themself as a neighbor
        if any(i == key for i in value):
            return False

        # Do these neighbors refer back to this node
        if not all(key in g[i] for i in value):
            return False

    # All checks succeeded
    return True

那么比如说

>>> valid_graph({0:[1,2], 1:[0], 2:[0]})
True
>>> valid_graph({0:[1,0], 1:[0], 2:[0]})  # 0 links to itself
False
>>> valid_graph({0:['str'], 1:[0], 2:[0]})  # invalid value type
False
>>> valid_graph({0:[2], 1:[0], 2:[0]})  # 1->0 but no 0->1
False

另外，我只是想澄清一下，我基本上遵循了你问题中的要求，但这些不一定是所有图形的要求。比如说

• 有向图可以有一个指向邻居的节点，但该邻居不必指向该节点
• 图可能有循环，包括指向自身的节点
• 节点可以简单地终止，而不指向任何其他节点