So, as part of my programming studies, I am making a disjoint set data structure. However, one method requires fetching two nodes, and if they aren't the same nodes, joining the nodes. This is supposed to be done by setting one node's parent attribute to be the other node. However, after stepping through the method with a debugger, the parent value never changes. For reference, some of the code:
class Node:
# a bare bones node class representing an entry in the disjoint set
# track the ids as a static variable
id = 0
def __init__(self):
self.id = Node.id
Node.id += 1
self.parent = None
self.rank = 0
and the problem code itself, a method in the disjoint set class:
def union(self, u, v):
# the union operation is used to join two components into one
# this implementation uses the component's ranks to optimize the union operation
# in this varient, the component with the lesser rank is attached to the root with the greater rank
# the find method searches for a particular node, and returns a Node object
# (an instance of the above class)
u_root = self.find(u)
v_root = self.find(v)
# if u and v's root are the same, they are in the same component
# therefore, end the operation because they are already merged
if u_root.id == v_root.id:
return
# to simplify coding, we force the u root to always be the root of lower rank
if u_root.rank > v_root.rank:
u_root, v_root = v_root, u_root
# merge u root into v root
u_root.parent = v_root
# the offending bit of code that isn't working as intended
# if the two roots share the same rank, you can't just add one onto the other
if v_root.rank == u_root.rank:
v_root.rank += 1
I suspect I am making assumptions about how variable assignments work in Python, especially when concerning Python objects. I thought variables and attributes that are assigned a Python object treated it like a reference, and any variable referencing the same object could edit it. However, I am definitely at an impasse and need some direction.