Python 设置不检测重复节点

Question

我创建了一个 Graph 类以及一个我已经测试过的 Node 类。它正在进行基本测试。我现在尝试使用自定义输入文件进行测试，但遇到了一些 Node 被重复的错误。在Graph类中，有一个名为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 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

在 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 以及它如何返回更多信息。

这是该方法的一个变体：

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

如果您执行以下操作：

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

...它将输出：

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

Answer 2

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

您应该将以下方法添加到节点类中：

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

Answer 3

有一些问题，一些与缺乏类型检查有关，一些与类的设计有关。

首先，您有一个 Node 类，您隐含的实例可能应该具有唯一的 self.value，并且该 self.value code> 期望始终是一个字符串（尽管这些期望不包含在代码中）。

导致 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

我不清楚节点的“邻居”属性是否对其身份重要，因为术语 node 和 graph 不携带有关类实际是什么的信息或代表，所以也许 neighbors 也应该包含在 __eq__ 中。

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

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

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