I am attempting to implement an algorithm (in Python) which involves a growing forest. The number of nodes are fixed, and at each step an edge is added. Throughout the course of the algorithm I need to keep track of the roots of the trees. This is a fairly common problem, e.g. Kruskal's Algorithm. Naively one might compute the root on the fly, but my forest is too large to make this feasable. A second attempt might be to keep a dictionary keyed by the nodes and whose values are the roots of the tree containing the node. This seems more promising, but I need to avoid updating the dictionary value of every node in two trees to be merged (the trees eventually get very deep and this is too computationally expensive). I was hopeful when I found the topic:
The notion was to keep a pointer to the root of each tree and simply update the roots when trees were merged. However, I quickly ran into the following (undesirable) behavior:
class ref:
def __init__(self,obj): self.obj = obj
def get(self): return self.obj
def set(self,obj): self.obj=obj
a = ref(1)
b = ref(2)
c = ref(3)
a = b
b = c
print(a,b,c) # => 2, 3, 3
Of course the desired output would be 3,3,3. I I check the addresses at each step I find that a and b are indeed pointing to the same thing (after a=b), but that a is not updated when I set b=c.
a = ref(1)
b = ref(2)
c = ref(3)
print(id(a),id(b),id(c)) # => 140512500114712 140512500114768 140512500114824
a = b
print(id(a),id(b),id(c)) # => 140512500114768 140512500114768 140512500114824
b = c
print(id(a),id(b),id(c)) # => 140512500114768 140512500114824 140512500114824
My primary concern is to be able to track to roots of trees when they are merged without a costly update, I would take any reasonable solution on this front whether or not it relates to the ref class. My secondary concern is to understand why Python is behaving this way with the ref class and how to modify the class to get the desired behavior. Any help or insight with regards to these problems is greatly appreciated.
