时间戳

首页 > 解决方案 > 如何在不使用networkx包的情况下检查字典是否代表图形？

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

问题描述

以下是一些示例字典：

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字典G和所有其他字典的输出X，除了.FalseFalseG

我做错了什么？

标签： pythondictionarygraph-theory

解决方案

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

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

另外要明确一点，我基本上遵循了您问题中的要求，但这些不一定是所有图表的要求。例如

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

推荐阅读