Python 设置不检测重复节点

Question

我创建了 Graph class 以及我测试过的 Node class。它正在处理基本测试。我现在正在尝试使用自定义输入文件进行测试，但我运行遇到了一些 Node 被复制的错误。在 Graph class 中，有一个名为 Nodes 的集合，其中添加了正在创建的 Node。但是，在我的解析器文件中，我有一个检查器，用于检查之前是否添加了具有该值的节点，但它无法正常工作。
即使在下面添加哈希函数后，我仍然得到 set([Alpha, Beta, Hotel, Alpha]).
我做错了什么？

测试文件：

directed unweighted
Alpha=Hotel
Alpha=Beta
Beta=Charlie
Charlie=Juliett
Charlie=Juliett
Delta=Foxtrot
Delta=Golf
Echo=Charlie
Echo=Delta
Foxtrot=Golf
Golf=Juliett
Golf=Alpha
Hotel=Echo
Hotel=India
India=Beta
India=Golf
Juliett=Golf

图和节点Class：



class Graph:
    def __init__(self):
        self.Nodes = set()

    def addVertex(self, vertex):
        self.Nodes.add(vertex)
    
    def getVertices(self):
        return self.Nodes


    @staticmethod
    def addEdgeDirect(fromEdge, toEdge, cost=1):
        fromEdge.neighbors[toEdge] = cost


class Node():
    def __init__(self, val = None):
        self.value = val
        self.neighbors = {}

    def getEdges(self):
        return self.neighbors.keys()
    
    def __repr__(self):
        return str(self.value)

测试文件解析器：

from graph import Graph, Node

graph = Graph()

file1 = open('Graphs/du.gl', 'r')
Lines = file1.readlines()

direction = Lines[0].split(" ")[0].strip()
weight = Lines[0].split(" ")[1].strip() 

count = 0
if(direction == "directed"):
    if(weight == "unweighted"):
        for line in Lines:
            count += 1
            if(count == 1):
                continue
            node1 = Node(line.split("=")[0].strip())
            node2 = Node(line.split("=")[1].strip())
            if node1 not in graph.Nodes:
                print("not found, to be added")
                graph.addVertex(Node(node1))

            if node2 not in graph.Nodes:
                graph.addVertex(Node(node2))    

            print(graph.getVertices())
            graph.addEdgeDirect(node1,node2)
            # print("Line{}: {}".format(count, line.strip()))

Answer 1

您期望该集合应包含具有唯一名称的节点，但您没有指定唯一性应取决于这些节点的属性 value。

您应该将以下方法添加到您的节点 class:


def __hash__(self):
    return hash(self.value)

Answer 2

在 set 中，对象始终通过其对象 ID（引用）进行区分。所以定义 __hash__ 也无济于事。

我建议：

使用字典而不是集合
仅当您已经知道需要一个新实例时才创建 Node 个实例——因此在检查 Nodes 词典还没有它之后
因此：将字符串值传递给 addVertex 而不是 Node 实例。

经过一些其他的小改动，您的代码可能是：

class Graph:
    def __init__(self):
        self.nodes = {}

    def addVertex(self, key):
        if key not in self.nodes:
            self.nodes[key] = Node(key)
        return self.nodes[key]
    
    def getVertices(self):
        return self.nodes.values()

    @staticmethod
    def addEdgeDirect(fromEdge, toEdge, cost=1):
        fromEdge.neighbors[toEdge] = cost


class Node():
    def __init__(self, val=None):
        self.value = val
        self.neighbors = {}

    def getEdges(self):
        return self.neighbors.keys()
    
    def __repr__(self):
        return str(self.value)
    

graph = Graph()
file1 = open('du.gl', 'r')
firstline, *lines = file1.readlines()
direction, weight = firstline.split()
if direction == "directed":
    if weight == "unweighted":
        for line in lines:
            graph.addEdgeDirect(*(graph.addVertex(key.strip()) 
                                  for key in line.split("=")))
            print(graph.getVertices())

附录

在评论中，您询问 getEdges 以及如何 return 更多信息。

这是该方法的一个变体：

def getEdges(self):
    return { self: self.neighbors }

如果你这样做：

print(graph.nodes['Alpha'].getEdges())

...它将输出：

{Alpha: {Hotel: 1, Beta: 1}}

Answer 3

存在一些问题，一些与缺少类型检查有关，一些与您的 class.

的设计有关

首先，你有一个 Node class，你暗示的实例可能应该有一个唯一的 self.value，并且 self.value 是预期的始终是一个字符串（尽管这些期望不包含在代码中）。

导致 set() 行为的一个问题是缺少 __hash__() 方法，在另一条评论中已解决。因为当且仅当它们的 value 参数是相同的字符串时，您可能希望两个节点相等，所以添加

def __hash__(self):
    return hash(self.value)

需要。但是，要让 set() 像您希望的那样工作，您还需要添加一个 __eq__() 函数。

def __eq__(self, other):
    return isinstance(other, Node) and self.value == other.value

我不清楚节点的 'neighbors' 属性是否对其身份有影响，因为术语 node 和 graph 不包含有关 classes 实际上是或代表，所以也许 neighbors 也应该包含在 __eq__ 中。

添加这些方法后，您的循环体仍然不正确。问题行是 graph.addVertex(Node(node1))，特别是 Node(node1)。据说这是为了创建 node1 的副本，但它实际上初始化了一个新节点，其中 newnode.value 现在是 Node 的一个实例，而不是字符串。使用类型提示 and/or 显式类型检查有助于发现这些问题，例如，向初始化主体添加对 isinstance(value, str) 的检查。

从循环体中替换这两个条件，正确的版本是：

if node1 not in graph.Nodes:
    graph.addVertex(node1)
if node2 not in graph.Nodes:
    graph.addVertex(node2)

Python 设置不检测重复节点

Python Set not Detecting Duplicate Node

python

algorithm

graph

set

nodes

附录