Home > Software design >  check if a object exists within a set() python
check if a object exists within a set() python

Time:08-20

I have a problem with python when I do this:

# initialise vistited set
visited = set()
# Add Node to visited set
self.visited.add(Node(2, 1)) 
# set a current node 
currentNode = Node(2, 1)
# Check if the currentNode is in visited
if currentNode in self.visited:
    print("Node is in visited") 

Now this above does not work, I don't know why its not checking if an object Node is in a set?

The Node definition:

class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y

Any help or tips will be appreciated!

CodePudding user response:

This line:

self.visited.add(Node(2, 1)) 

Creates a new Node() object and adds it to visited.

This line:

currentNode = Node(2, 1)

Creates a new Node object and assigns it to currentNode. Although currentNode and the most recently added element of self.visited are identicial objects (assuming they are constructed deterministically from the parameters of the constructor), they are not the same object.

So, the node currentNode points at is not in self.visited.

Compare:

# initialise vistited set
visited = set()
# set a current node 
currentNode = Node(2, 1)
# Add Node to visited set
visited.add(currentNode) 
# Check if the currentNode is in visited
if currentNode in visited:
    print("Node is in visited") 

Here only one Node object is created, which is added to the set.

(self was left off, since the example doesn't actually sit inside a method, but it would be the same if it did - although your code seems to be missing self. on the first reference to visited)

This may be confusing if you compare it to this:

x = 1
y = 1
numbers = {y}

if x in numbers:
    print('yes')

However, the reason this prints yes is that numbers aren't separate objects. There's only one 1, one 2, etc. in Python and similarly, two string variables that both have the value 'test' effectively refer to 'the same string'.

This works because you can't modify part of a string or an integer. But with other (or at least mutable) object types, that's not true.

For example, for tuples (another immutable type):

x = (1,)
y = (1,)
tuples = {y}

if x in tuples:
    print('yes')

Again, this prints yes.

But for lists, a mutable type:

x = [1]
y = [1]
lists = {y}

if x in lists:
    print('yes')

This won't even run, because a list is not a hashable type.

Your Node is an example of a hashable, but mutable type. From the documentation: "Objects which are instances of user-defined classes are hashable by default. They all compare unequal (except with themselves), and their hash value is derived from their id()."

Note: people suggested in the comments that adding an equality method (i.e. __eq__) would help, but it won't unless you also add a __hash__ function, as user @Mark also points out - not doing so makes the object no longer hashable and adding it to a set won't work.

So, this is an example of how you can make it work:

class Node:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))


visited = set()
visited.add(Node(2, 1))

x = Node(2, 1)
if x in visited:
    print('it is in there')
  • Related